How do STL linked structures handle allocation?

Question

The C++ Standard Template Library provides a number of container types which have very obvious implementations as linked structures, such as list and map.

A very basic optimization with highly-linked structures is to use a custom sub-allocator with a private memory pool providing fixed-size allocation. Given the STL's emphasis on performance, I would expect this or similar optimizations to be performed. At the same time, all these containers have an optional Allocator template parameter, and it would seem largely redundant to be able to provide a custom allocator to something that already uses a custom allocator.

So, if I'm looking for maximum-performance linked structures with the STL, do I need to specify a custom allocator, or can I count on the STL to do that work for me?

Answer 1

Naturally it can vary from one standard lib implementation to the next, but last time I checked in libs like MSVC, GNU C++, and EASTL, linked structures allocate node and element data in a single allocation.

However, each node is still allocated one-at-a-time against std::allocator which is a fairly general-purpose variable-length allocator (though it can at least assume that all elements being allocated are of a particular data type, but many times I've found it just defaulting to malloc calls in VTune and CodeXL sessions). Sometimes there's even thread-safe memory allocation going on which is a bit wasteful when the data structure itself isn't designed for concurrent modifications or simultaneous reads/writes while using thread-safe, general-purpose memory allocation to allocate one node at a time.

The design makes sense though if you want to allow the client to pass in their own custom allocators as template parameters. In that case you don't want the data structure to pool memory since that would be fighting against what the allocator might want to do. There's a decision to be made with linked structures in particular whether you allocate one node at a time and pass the responsibility of more efficient allocation techniques like free lists to the allocator to make each individual node allocation efficient, or avoid depending on the allocator to make that efficient and effectively do the pooling in the data structure by allocating many nodes at once in a contiguous fashion and pooling them. The standard lib leans towards the former route which can unfortunately makes things like std::list and std::map, when used against default std::allocator, very inefficient.

Personally for linked structures, I use my own handrolled solutions which rely on 32-bit indexes into arrays (ex: std::vector) which effectively serve as the pooled memory and work like an "indexed free list", like so:

... where we might actually store the linked list nodes inside std::vector. The links just become a way to allow us to remove things in constant-time and reclaim these empty spaces in constant-time. The real example is a little more complex than the pseudocode above since that code only works for PODs (real one uses aligned_storage, placement new, and manual dtor invocation like the standard containers), but it's not that much more complex. Similar case here:

... a doubly-linked "index" list using std::vector (or something like std::deque if you don't want pointer invalidation), for example, to store the list nodes. In that case the links allow us to just skip around when traversing the vector's contiguous memory. The whole point of that is to allow constant-time removal and insertion anywhere to the list while preserving insertion order on traversal (something which would be lost with just std::vector if we used swap-to-back-and-pop-back technique for constant-time removal from the middle).

Aside from making everything more contiguous and cache-friendly to traverse as well as faster to allocate and free, it also halves the sizes of the links on 64-bit architectures when we can use 32-bit indices instead into a random-access sequence storing the nodes.

Linked lists have actually accumulated a really bad rep in C++ and I believe it's largely for this reason. The people benchmarking are using std::list against the default allocator and incurring bottlenecks in the form of cache misses galore on traversal and costly, possibly thread-safe memory allocations with the insertion of each individual node and freeing with the removal of each individual node. Similar case with the huge preference these days towards unordered_map and unordered_set over map and set. Hash tables might have always had some edge but that edge is so skewed when map and set just use a general-purpose allocator one node at a time and incur cache misses galore on tree traversal.

So, if I'm looking for maximum-performance linked structures with the STL, do I need to specify a custom allocator, or can I count on the STL to do that work for me?

The advice to measure/profile is always wise, but if your needs are genuinely critical (like you're looping over the data repeatedly every single frame and it stores hundreds of thousands of elements or more while repeatedly also inserting and removing elements to/from the middle each frame), then I'd at least reach for a free list before using the likes of std::list or std::map. And linked lists are such trivial data structures that I'd actually recommend rolling your own if you're really hitting hotspots with the linked structures in the standard library instead of having to deal with the combo of both allocator and data structure to achieve an efficient solution (it can be easier to just have a data structure which is very efficient for your exact needs in its default form if it's trivial enough to implement).

I used to fiddle around with allocators a lot, reaching around data structures and trying to make them more efficient by experimenting with allocators (with moderate success, enough to encourage me but not amazing results), but I've found my life becoming so much easier to just make linked structures which pool their memory upfront (which gave me the most amazing results). And funnily enough, just creating these data structures which are more efficient about their allocation strategies upfront took less time than all the time I spent fiddling with allocators (trying out third party ones as well as implementing my own). Here's a quick example I whipped up which uses linked lists for the collision detection with 4 million particles (this is old so it was running on an i3).

It uses singly-linked lists using my own deque-like container to store the nodes like so:

Similar thing here with a spatial index for collision between 500k variable-sized agents (just took 2 hours to implement the whole thing and I didn't even bother to multithread it):

I point this out mainly for those who say linked lists are so inefficient since, as long as you store the nodes in an efficient and relatively contiguous way, they can really be a useful tool to add to your arsenal. I think the C++ community at large dismissed them a bit too hastily as I'd be completely lost without linked lists. Used correctly, they can reduce heap allocations rather than multiply them and improve spatial locality rather than degrade it (ex: consider that grid diagram above if it used a separate instance of std::vector or SmallVector with a fixed SBO for every single cell instead of just storing one 32-bit integer). And it doesn't take long to write, say, a linked list which allocates nodes very efficiently -- I'd be surprised if anyone takes more than a half hour to write both the data structure and unit test. Similar case with, say, an efficient red-black tree which might take a couple of hours but it's not that big of a deal.

These days I just end up storing the linked nodes directly inside things like std::vector, my own chunkier equivalent of std::deque, tbb::concurrent_vector if I need to build a concurrent linked structure, etc. Life becomes a lot easier when efficient allocation is absorbed into the data structure's responsibility rather than having to think about efficient allocation and the data structure as two entirely separate concepts and having to whip up and pass all these different types of allocators around all over the place. The design I favor these days is something like:

// Creates a tree storing elements of type T with 'BlockSize' contiguous
// nodes allocated at a time and pooled.
Tree<T, BlockSize> tree;

... or I just omit that BlockSize parameter and let the nodes be stored in std::vector with amortized reallocations while storing all nodes contiguously. I don't even bother with an allocator template parameter anymore. Once you absorb efficient node allocation responsibilities into the tree structure, there's no longer much benefit to a class template for your allocator since it just becomes like a malloc and free interface and dynamic dispatch becomes trivially cheap at that point when you're only involving it once for, say, every 128 nodes allocated/freed at once contiguously if you still need a custom allocator for some reason.

So, if I'm looking for maximum-performance linked structures with the STL, do I need to specify a custom allocator, or can I count on the STL to do that work for me?

So coming back to this question, if you genuinely have a very performance-critical need (either anticipated upfront like large amounts of data you have to process every frame or in hindsight through measurements), you might even consider just rolling some data structures of your own which store nodes in things like std::vector. As counter-productive as that sounds, it can take a lot less time than fiddling around and experimenting with memory allocators all day long, not to mention an "indexed linked list" which allocates nodes into std::vector using 32-bit indices for the links will halve the cost of the links and also probably take less time to implement than an std::allocator-conforming free list, e.g. And hopefully if people do this more often, linked lists can start to become a bit more popular again, since I think they've become too easily dismissed as inefficient when, used in a way that allocates nodes efficiently, they might actually be an excellent data structure for certain problems.

Answer 2

While the standard does not explicitly forbid such optimizations, it would be a poor design choice by the implementer.

First of all, one could imagine a use case where pooling allocation would not be a desirable choice. It's not too hard to refer a custom allocator in the template parameters to introduce the pooling behavior you want, but disabling that behavior if it was a part of the container would be pretty much impossible.

Also from the OOP point of view, you'd have a template that obviously has more than one responsibility, some consider it a bad sign.

The overall answer seems to be "Yes, you do need a custom allocator" (Boost::pool_alloc?).

Finally, you can write a simple test to check what does your specific implementation do.

Answer 3

It depends a lot on your workload.

If you don't iterate through your datastructures a lot, don't even bother optimizing anything. Your time is better spent elsewhere.

If you do iterate, but your payload is large and you do a lot of work per item, it's unlikely that the default implementation is going to be the bottleneck. The iteration inefficiencies are going to be swallowed by the per item work.

If you store small elements (ints, pointers), you do trivial operations and you iterate through the structure a lot, then you'll get better performance out of something like std::vector or boost::flat_map since they allow better pre-fetch operations.

Allocators are mostly useful when you find yourself allocating and deallocating a lot of small bits of memory. This causes memory fragmentation and can have performance implications.

As with all performance advice you need to benchmark your workload on your target machine.

P.S. Make sure the optimizations are turned on (i.e. -O3).