------- Additional Comments From pcarlini at suse dot de 2005-01-14 11:50
-------
> I was a little in a hurry, so I'll add a comment on the test programm now.
> The "reference time" of std::list ctor taking range must be linear. Thus it
> makes sence to have a look at the quotient of the second and third collumn
> in the output. And that's where you can see the logarithmic behaviour.
> It is visible even for std::allocator but the pool allocator makes it shine.
Thanks for the clarification. I will definitely adapt your test program for
our performance testsuite.
> ... With the access to the rightmost node in constant time the insertions
> at the end could actualy be in "amortized" constant time ("amortized" wrt.
> consecutive insertions at the end). This is just a feeling and needs to be
> proved.
Indeed, it works: on my home machine (P4-2400) currently the quotient above
grows from about 2.8 to 3.5 during the test. The trivial patch that I'm
finishing testing leads to a constant value (~2.4), as expected. This is
with the standard allocator, more suited for our testsuite.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422
