Re: Fusion-ifying proto parse trees

Joel de Guzman wrote:
> Ok, let's put your hypothesis to test. Can we try your
> Zero-copy expression template construction idea with the
> current tests that you have? (i.e. seq<> holding its left
> and right children by reference).


The results are in. The following ET schemes were tested:

1) The Spirit2 approach: eager flattening in the ET
2) Non-segmented proto: Zero-copy ET construction, non-segmented ET 
traversal.
3) Segmented proto: Zero-copy ET construction, segmented ET traversal.

Time taken to construct the ET and traverse it was measured. The winner 
by a wide margin is (3) segmented proto. For larger ET trees, segmented 
proto is over 8x faster than the Spirit2 approach. (Note that even 
non-segmented proto is marginally faster than the Spirit2 approach.)

I have also reformulated the segmentation interface according to the 
simpler scheme Joel and I discussed. It's *much* easier to work with.

For kicks, I also ran the test with proto modified to hold copies of its 
child nodes instead of references, on the chance that the cost of the 
indirections might outweigh the cost of the copies. It doesn't. Holding 
children by value is 2x slower than holding them by reference. (The 
indirections do have a cost, however, so if you plan to traverse the 
proto tree multiple times, it might make sense to deep-copy it first. 
Proto should provide a deep-copy utility.)

Attached is the test and the timing results. Be sure to sync to 
$boost_root/boost/xpressive, as I had to make changes to proto to 
support zero-copy ET construction.


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

segmented_fusion.tar.gz
Description: GNU Zip compressed data

// MSVC 7.1
Short test ...
80
80
80
Fusion list time         : 1.11908e-008
Non-segmented proto time : 3.88175e-009
Segmented proto time     : 5.07385e-009
Long test ...
480
480
480
Fusion list time         : 3.17001e-006
Non-segmented proto time : 1.14632e-006
Segmented proto time     : 2.96116e-007

// MSVC 8
Short test ...
80
80
80
Fusion list time         : 3.65451e-009
Non-segmented proto time : 3.65451e-009
Segmented proto time     : 3.62098e-009
Long test ...
480
480
480
Fusion list time         : 2.86484e-006
Non-segmented proto time : 1.02997e-006
Segmented proto time     : 3.39031e-007

// GCC 3.4.4
Short test ...
80
80
80
Fusion list time         : 3.77178e-07
Non-segmented proto time : 3.48568e-07
Segmented proto time     : 3.62873e-07
Long test ...
480
480
480
Fusion list time         : 1.02386e-05
Non-segmented proto time : 2.71225e-06
Segmented proto time     : 2.59781e-06