[boost] MPL list optomization for GCC

From: Hamish Mackenzie (hamish_at_[hidden])
Date: 2002-04-19 19:52:11

I have done some more tests, this time for count_if.  The
generic/portable optimisation (TEST3) does improve things hugely, but
the list_node based version (TEST2) is faster still.

My feeling is that in order for MPL to work well with gcc it needs to
provide both optimisations as well as a facility for users of mpl::list
to optimise their own algorithms in the same way.

In order to do this the list_node will have to be accessible.  This
could be done in a number of ways
1) Change list<>::type so that it is a list_node<> and and stop list<>
itself being a sequence.
2) Add raw_list< Sequence >::type.
3) Add raw_list< Sequence >::type and change list<>::type to list_node.
4) Ideas???

Hamish

Compile time results for count_if in seconds

TEST_N	N	TEST1 	TEST2 	TEST3 
1	10	13.98 	1.88 	1.87 
2	20 	30.85 	1.89 	1.92 
3	30	52.08	1.89	1.93 
4	40	81.45	1.89	1.98 
5	50	114.94	1.89	2.06 
6	60	157.16	1.91	2.12 
7	70	203.66	1.89	2.16 
8	80	258.60	1.92	2.26 
9	90	?	1.93	2.40 
10	100	?	1.94	2.53 
20	200	?	2.21	4.62 
30	300	?	2.71	9.07 
40	400	?	3.60	16.80
50	500	?	5.05	29.71
60	600	?	7.55	51.08
70	700	?	10.74	74.81

TEST_N = N/10
N = size of list
TEST1 = Result using existing MPL
TEST2 = Top level recursion
TEST3 = unrolling_size/do_count_if

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)

If you are wondering why these figures are better than the corresponding
ones for size then you are not alone.  It seems that the compiler
prefers the input data I used here which is a repeating sequence of two
different classes (for size I tested a sequence containing only one item
type).  I am going to look into this some more.