Re: [boost] Re: Re: loki::type_list == boost::mpl::list_node

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

g++ -v
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.

Hamish