STL allocators, hmm...

As I mentioned a while ago, I have some code which needs to perform better than it currently does and one of the areas that could be improved upon is the amount of contention for the heap that's occurring. The fact that I'm using an STL map for my collection means that the class has a 'big C' contention value of C(n threads using the heap) rather than C(n threads using the object). Of course, the fact that allocations need to be done at all is an unfortunate feature of std::map but rather than immediately replace the container with an invasive collection I decided to look into replacing the STL allocator that's being used with one that uses a private heap so that I could reduce the contention value of the allocations to C(n threads using the object). Doing this has required that I take a look at STL allocators and my initial thought is "hmm..."

STL containers can be configured to use custom allocators but by default they use a default allocator which, generally, uses the heap to allocate and free memory in a thread safe way. An allocator is a template parameter to the container and, as pointed out in several references, you don't generally need to mess with them. Still, my requirements are to improve performance and part of that job is to reduce potential contention so the allocators need to be looked at. My reference books didn't adequately cover allocators, though Generic Programming and the STL did explain it all in a rather terse manner with lots of "you don't need to know this" provisos.

A quick Google led me to Pete Isensee's pages where he talks about STL allocators for games programming. He has a nice set of slides and some code and this has helped me get started.

I can't help thinking that allocators weren't really thought through especially well; the whole 'rebind' from allocator<int> to allocator<node> is, IMHO, just pointless 'aren't we clever with templates' crap ;) especially given the fact that at the end of the day all these things are doing is allocating memory of a given size...

Anyway, being able to plug my own allocator into the containers is one small step on the path to improving the performance of the objects in question.


" the end of the day all these things are doing is allocating memory of a given size..."

Except that's not all that's happening, though the EASTL's take on allocators is better than I can explain here. I'll resort to a simplistic alignment example: allocating three bytes without restriction (something like a char[3]) and with (something like a struct { short; char }, if we imagine sizeof(short) is 2 with 2-byte alignment).

Rebinding allocators is annoying; it would be nice to use unspecialized templates without the restrictions of template template-parameters, but the language just doesn't allow that. Rebinding makes a reasonable compromise, including implementation support, circa 1998 (even though the technique is even older).

Hmmm, the EASTL doc says this about normal STL allocators; "Allocators don't understand alignment requirements. Objects allocated by a std allocator are assumed to be of default alignment (usually equal to sizeof double) or it is assumed that the implementor of the allocator knows what the alignment is."

Which makes me think that "all these things are doing is allocating memory of a given size..." seems fairly accurate...

The EASTL doc pretty much sums up what's wrong with allocators, but I do take on board your point about the design having to work with 1998 compilers.

Of course that makes it sound like I don't understand the reason that the allocator is typed, I do, but I don't buy the fact that the current design with the rebinding and the fact that the allocator that you supply isn't the one that's used, etc, etc, is the best way to do things...

Leave a comment