Re: Fusion-ifying proto parse trees

Eric Niebler wrote:
> Joel de Guzman wrote:
> > Eric Niebler wrote:
> > > Also, these tests leave out one detail ... the cost of building the 
> > > expression template. Is building an unflattened proto parse tree more 
> > > or less expensive than flattening into a list/vector eagerly? We 
> > > should really be taking that into account. The cost of building the 
> > > ET would probably dominate.
> >
> > I think it would be the same, but I am guessing. I am basing that
> > guess from the code size generated from proto and the pre-proto
> > code, which more or less amounts to the same footprint.
>
>
> I'm not so sure. To flatten A>>B>>C>>D, the following lists must be 
> constructed:
>
> cons<A>
> cons<A,cons<B>>
> cons<A,cons<B>,cons<C>>>
> cons<A,cons<B>,cons<C>,cons<D>>>
>
> You're pushing stuff to the *end* of a singly-linked list, which is 
> slow, and you end up instantiating lots of mostly unneeded intermediate 
> cons<> types. I count 10 separate instantiations of cons<> here. In 
> other words, this: "return fusion::as_list(join_type(a.elements, 
> b.elements));" from compose.hpp gets more and more expensive as the list 
> grows.
>
> When building a proto ET tree, no instantiations are wasted. It gets 
> built by composing sub-trees, like:
>
> lit<A>
> seq<lit<A>,lit<B>>
> seq<seq<lit<A>,lit<B>>,lit<C>>
> seq<seq<seq<lit<A>,lit<B>>,lit<C>>,lit<D>>
>
> I count only 3 separate instantiations of seq<> and 4 instantiations of 
> lit<> here -- for a total of 7. Three less than eagerly cons-ifying.

Right!

> Oh, wait! I just had a thought. When building a cons<> list as you do, 
> you have to copy the elements from the old list to the new because the 
> list types differ. (In the example above, A is copied 4 times, B 3 
> times, C twice and D once -- that's 10 copies.) Today, proto makes no 
> fewer copies, but it doesn't have to be that way. seq<> can hold its 
> left and right children by reference! The temporaries won't go out of 
> scope before the expression gets evaluated. And if you're assigning an 
> ET to a rule<>, you can deep-copy (and flatten!) the tree only then. Hmm 
> ... that means going from 10 copies to 0 (assuming that even lit<A> can 
> hold A by reference)!

That's exactly like the result of fusion::push_back, a reverse cons
list.

> What do you think? Zero-copy expression template construction and 
> segmented iteration over the tree -- I think there's potential there.

Or, simply use the raw view returned from push_back without doing
a fusion::as_list call. That also amounts to zero-copy expression
template construction.

Pardon my stubbornness. It's just that I always strive to arrive
at the simplest solution. For Spirit-2, I'd like to adhere to the
mantra that "less is more". Then here we are again adding complexity
to tackle what I view as a simple need. I understand that you also wish
to make proto "as simple as possible", but what we are doing seems
more like moving the complexity somewhere else, and in the process,
ultimately adding more complexity to address the need.

Ok... I'd really want to take a step back and meditate on this.
I'd like to re-think the "flatness" requirement in hopes of
eliminating it. If that is indeed possible, then we have a
win-win situation.

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