mapfor 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::mapbut 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<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...