Thread: New List

New List

From
Gaetano Mendola
Date:
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


















Re: New List

From
Neil Conway
Date:
Gaetano Mendola <mendola@bigfoot.com> writes:
>     10E6 INSERT => real   0m5.161s
>                         user   0m4.010s
>                         sys    0m1.150s

What operation is this benchmarking? Only linked-list appends, or
something else?

-Neil


Re: New List

From
Gaetano Mendola
Date:
Neil Conway wrote:
> Gaetano Mendola <mendola@bigfoot.com> writes:
>
>>    10E6 INSERT => real   0m5.161s
>>                        user   0m4.010s
>>                        sys    0m1.150s
>
>
> What operation is this benchmarking? Only linked-list appends, or
> something else?

Only the head append.

Regards
Gaetano Mendola