Hi all,
in the thread "equal() perf tweak" I and
Neil we were discussing about the new
implementation of a list.
We add a little discussion on how implement it
these are my results:
1) "Neil" list and length linear time
10E6 INSERT => real 0m5.161s
user 0m4.010s
sys 0m1.150s
2) "Neil" list and length constant time
10E6 INSERT => real 0m5.232s
user 0m4.200s
sys 0m1.030s
3) "stl::list" fashion and length linear time
10E6 INSERT => real 0m5.352s
user 0m4.260s
sys 0m1.090s
4) "stl::list" fashion and length constant time
10E6 INSERT => real 0m5.480s
user 0m4.340s
sys 0m1.110s
this show, at list on my HW
Pentium III (Coppermine)
870.587 MHz
256 KB cache
that implement the length in constant time
is almost the same ( less than 2% of the total time)
This show also that the classical implementation win
vs the stl::list fashion.
We shall consider also that in case of stl::list all
methods are inlined, I tried also "inlining" the function
replacing the function call with the body function:
5) "Neil" list
real 0m4.909s
user 0m3.790s
sys 0m1.110s
6) "stl::list"
real 0m5.146s
user 0m3.980s
sys 0m1.090s
So at the end I think that the best solution is
the Neil classical proposal and mantain the length
function constant time.
Regards
Gaetano Mendola