Re: Fusion-ifying proto parse trees

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.

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)!

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


> > Regarding your question about taking the minimum result, I lifted this 
> > code from John Maddock's regex performance shoot-out. This is how he 
> > collects his timing. Yes, this is a black art -- I don't really 
> > understand it.
>
> I recall Dave A mention some benchmarking strategies that take off
> the unwanted effects. I'm still looking for the links. You can see
> in the VC8.0 tests that fusion list is winning. My guess is that
> this is a problem with VC7.1's optimizer that gives fusion lists
> a great disadvantage. My guess is that if that effect is known
> and isolated, fusion lists can be optimized for VC7.1 to mitigate
> this effect. I believe that what we are seeing is an effect; not
> really due to the raw-algorithmic advantage of segmentation. IOTW,
> I think you were just lucky to have found a good formulation for 7.1
> and for 7.1 alone.


Oh, I never suggested segmentation was an algorithmic improvement! 
Obviously, the computational complexity for visiting every element in a 
sequence is O(N) no matter how you slice it. The ultimate goal is to 
make Spirit-2 evaluate fast, while giving Boost a general ET library and 
allowing Spirit-2, Karma, xpressive and other parsing strategies to play 
well together. I agree we're not there yet, but I think these results 
are encouraging.


--
Eric Niebler
Boost Consulting
www.boost-consulting.com


-------------------------------------------------------
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