I am a bit worried about the performance of the current containers.
While the implementations and algorithms are no doubt of the highest
quality in todays STL libraries, the current memory allocation scheme
seems to slow down the node-based containers dramatically.

To back up this claim, here are the results of a simple test:
(Visual Studio 2005 SP1, with checked iterators turned off, release
mode).

On Apr 3, 9:22 pm, Kaba hotmail.com>
wrote:

Do you use optimization? I dealt with the problem of STL container
iterators being remarkably slow, however with GCC level-1 optimization
they turn out to be faster than pointers themselves (also using -O1.)
They aren't specialized for specific purposes and are meant to be
written and left alone for years at a time, so it's no surprise they
are slower than a container you've written. Can you post some numbers
with compiler optimization? I do all of my work with GCC, so I don't
know if VS knows its own STL as well as GCC knows its own.
Kevin P. Barry

On Apr 4, 3:22 am, Kaba hotmail.com>
wrote:

IME, there is something wrong with STL and VS2005. With the same
benchmark, VS2005 is about 50%% slower than VS2003...:

http://www.ultimatepp.org/www$uppweb2$vsstd$en-us.html
http://garrys-brain.blogspot.com/2007/01/more-on-stlport-and-microsoft-stl.html

(Of course, there are issues with STL's suboptimal definition and
implementation as well, anyway VS2005 is not the best environment for
such tests...)

Mirek

Kaba hotmail.com> wrote:

I am not sure what either 'the current containers' nor 'the current
memory allocation scheme' is supposed to mean in a general C++ setting.

Absolute performance is related to the quality of the implementation,
but as long as the asymptotic guarantees are fulfilled, the
implementation is 'fine' as far as the language is concerned. Your
numbers indicate nothing unusual in this direction.

Of course, the constant factor might be huge (and this, btw, indicates
how inadequate the big-O notation for any finite application is, but
that's another issue...), and yes, your particular combination for which
you produced numbers seem to have an unusual big factor.

So quite probably there's nothing _formally_ wrong with either your
compiler nor its library. Being _practically_ wrong might be another
issue ;-}

Andre'

Kaba napsal:

- you can supply your own memory allocators for STL containers too (as
optional template parameter)
- for vector you can preallocate memory for all items if you know, how
many items you will insert (specify 0 size in constructor and then use
method reserve)
- for any container or data structure you can always find use-case,
for which is such container not efficient and for which exists better
implementation - that's life, nothing may be 100%% universaly best

On Apr 3, 9:22 pm, Kaba hotmail.com>
wrote:
...

...

...

Did you do any comparisons between single and multi-threaded builds?
Do you do any locking in your own allocator?

Out-of-the-box, the allocators that come with Visual Studio 2003 and 2005
are not optimal as alternative offerings
But I believe Dinkumware sell an add-on package which does have drop-in
allocators that are faster.

Well splice() gets used by some list::merge()'s and list::sorts()'s
And it is used by some programmers.
linked lists are the only container, currently where splicing can be O(1)

But others do. Why the concern? They should not affect you.

This is a combined answer to Kevin, Mirek, Andre and Ondra.

I am not using GCC, I must see if I can the timing results from my
friend. Anyway, this slow performance should not come as a surprise and
on rough scale is not dependent on the implementation. Here's why:

By current containers and current memory allocation, I refer to the
problems with current allocators. As one can read from example from
Scott Meyer's "Efficient STL", sections 10 and 11, the use of STL
allocators is very, very limited. Let me quote the relevant part:

"That's all well and good, but the more you think about it. the more
you'll realize just how draconian a restriction it is that STL
implementations may assume that allocators of the same type are
equivalent. It means that portable allocator objects ? allocators
that will function correctly under different STL implementations ? may
not have state. Let's be explicit about this: it means that portable
allocators may not have any nonstatic data members, at least not any
that affect their behavior. None. Nada."

So where does the requirement for equivalence come from? I am aware of
just one answer: std::list splice().

On Apr 4, 3:22 am, Kaba hotmail.com>
wrote:

There is a proposal to fix just that.

There is an interesting thing here: the destructions take about as long
as the constructions. In my timings, std::set took about 80x time to
destruct than to construct.

Ok, we probably agree that the performance gain I am experiencing with
this insertion/destruction test comes directly from the allocator
change. Thus, we could actually just compare the performances of
std::allocator between gcc, visual studio and ours. In the following,
std is for std::allocator, Pastel is for our pool allocator. Note again
that visual studio takes much more time to destruct than to construct.
Anyone knows if this is because of some compiler options?