From: Hamish Mackenzie (hamish_at_[hidden])
Date: 2002-04-18 10:10:06
On Wed, 2002-04-17 at 09:34, Aleksey Gurtovoy wrote:
> The 'aux::unrolling_size' template then would return -1 by default, and
> would be specialized for specific sequence types (e.g. list##i) for which we
> can determine the size at O(1).
Am I correct in thinking aux::unrolling_size needs to work on list_node
as well as list##i?
On GCC the fastest implementation of size I have found so far is the one
I posted earlier so I will use this for unrolling_size.
To get an idea of the overhead of the the approach you have suggested I
implemented size in the same way (in fact as size is based on distance I
have implemented do_distance)
Here are the results (times in seconds)
TEST_N N TEST1 TEST2 TEST3
1 10 13.89 1.83 1.85
2 20 30.70 1.85 1.88
3 30 51.98 1.86 1.90
6 60 158.63 1.88 2.26
10 100 ? 2.06 3.43
20 200 ? 3.43 13.39
30 300 ? 6.80 39.23
40 400 ? 13.23 88.76
TEST_N = N/10
N = size of list
TEST1 = Result using existing MPL
TEST2 = Top level recursion
TEST3 = unrolling_size/do_distance
Reading specs from /usr/local/lib/gcc-lib/i686-pc-linux-gnu/3.1/specs
Configured with: ../gcc-20020415/configure
Thread model: single
gcc version 3.1 20020415 (prerelease)
Obviously we would not use do_distance for size if unroll_size was not
-1 so these results should be take with a pinch of salt.
I'll have a crack at count_if next.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk