Re: Fusion-ifying proto parse trees

David Abrahams wrote:
> "Eric Niebler" <eric@xxxxxxxxxxxxxxxxxxxx> writes:
>
> > Not to worry, we're not stuck in a groove. :-) I asked you why you
> > needed flat sequences because, when I get hung up on a design problem,
> > I often find it useful to go back to the beginning, start from first
> > principles, and make sure that I haven't overlooked something. That's
> > all. I'm not trying to tell you what you do or don't need, I'm just
> > trying to understand the problem.
>
>
> Well, I don't mind sounding obnoxious, so -- admittedly without having
> followed this discussion closely -- I'll tell you that you don't need
> flattening :).
>
> I see no reason that Spirit's performance (runtime or compile-time)
> should depend on generating a "flat structure" in its expression
> trees.  After all, you're just talking about the type structure.  The
> result of evaluating the expression tree is fundamentally a struct
> containing references to the objects in play.  It doesn't really
> matter where the angle brackets are.
>
> Just to be provocative, I'll even go further and claim that flattening
> is evil :).  For the maximum performance in most linear fusion
> algorithms, you actually want to impose a tree structure on flat data.
> That is, divide the sequence in two (for example), do your algorithm
> on the first half, and then continue on the second half, recursively.
> Among other things, this approach makes the most of the compiler's
> inherent inlining depth limitations.

Good points! I am not sure though how to put your theories into
practice. In the real world ET trees are almost flat, heavily
lopsided trees. Take (a >> b >> c >> d), for example. That ET
gives you a tree like this:

    seq(seq(seq(a, b), c), d)

which is almost like a reverse cons list.

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642