Boost logo

Boost :

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-15 05:12:49


David Abrahams:
>Vesa Karvonen:
> > BTW, the same "acceleration" technique can be used with templates to
> > overcome template recursion depth limitations. Probably most people
> > know about it already, though I haven't explicitly checked. > (Plain
>unrolling is not as effective: Theta(k*n) < Theta(pow(k,n)).)
>
>Well, if I understand your suggestion correctly, it's one thing I
>thought of. Basically you're doing "tree unrolling" instead of
>"linear unrolling", right? In the TMP case you don't have the
>advantage of auto-detecting the depth limit, though ;-)

You are right, top-down "tree unrolling" isn't probably practical. However,
I think that it should be possible to do the "tree unrolling" in a bottom-up
style rather than top-down fashion. In other words, the "iteration tree"
would look something like this:

  0 -> 1 -> 4 -> ...
       / \ / \
      2 3 5 8
             / \ / \
            6 7 9 10

Above, each node represents a single iteration and the numbering represents
the order in which the iterations would be done. (The numbering might also
look different - take it as a hint rather than the only/correct/best
choice.) The idea is that from one "top-level" iteration to another, the
template would try iterating bigger and bigger [sub-]trees. I really
seriously Do Not have the time to [try to] implement such a
while_<pred,op,state> template, but out of interest I probably will, unless
someone else demonstrates it earlier.

> > IMO, it is not a very good argument to say that more powerful tools
> > are unnecessary
>I am not making that argument.

Sorry, I guess my interpretation of your argument was too quick.

>Ever thought about writing Yacc with just the preprocessor (<wink>, I
>think)?

I have been thinking about making a lexical analyzer generator (using a
syntax for regular expressions and using the preprocessor or run-time
(initialization) code to generate the transition tables (once)), which is a
lot easier to implement than a parser generator. I'd rather start with a
simpler task, as getting something nearly as complicated done with the
preprocessor is enough of a challenge.

-Vesa Karvonen

_________________________________________________________________
The new MSN 8: smart spam protection and 2 months FREE*
http://join.msn.com/?page=features/junkmail


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk