Intrusive C++ containers

Recently, whilst continuing to improve the performance of various aspects of The Server Framework, I reached a point where I found I needed to replace some STL containers with intrusive containers which didn’t need to perform memory allocations during data insertion and removal. I had been toying with the idea of implementing custom containers for some time but have only recently had a pressing need for them.

The STL provides some marvellously usable code which has changed the way people view container classes in C++. The result is that you hardly ever need to write your own containers as the STL provides containers with known performance characteristics which, thanks to templates, work with any data. The downside of this is that you hardly ever need to write your own containers and so you get out of the habit of doing so…

What’s so special?

STL containers allow you to store any data in them without changing your data in any way. They achieve this by creating the extra data required to store your data in the container and storing your data inside. This makes them very flexible but generally requires memory allocation during insertion and removal of data.

Intrusive containers, on the other hand, require that you change the data that you want to store so that it conforms to the requirements of the container in which you want to store it. Thus the container’s requirements intrude on the data’s design… This intrusion could be as simple as adding a single pointer to allow data items to be chained together to form a singly linked list, or more complex, such as adding a tree node to your data so that it can be stored in a balanced search tree when being placed into a map or set.

When to use them?

In general it’s best to stick to the known performance and reliability of STL containers unless you have specific requirements that they don’t meet. One such requirement is reduced thread contention. If you need to allocate and release memory on insertions and deletions then you are inserting potential thread contention into a multi-threaded system. In this situation is may be better to have a custom intrusive container which doesn’t need to do the memory allocation.

I have been working on reducing thread contention in The Server Framework and in some places the use of intrusive containers would greatly reduce the potential contention in a heavily loaded system.

Pre-existing implementations?

As I mentioned back in 2010, Boost includes an intrusive containers library. Unfortunately this doesn’t actually help me at all as it doesn’t provide a std::map replacement.

I have been unable to find any reusable intrusive containers that fit my requirements, and so, in the end, reluctantly wrote my own generic intrusive red-black tree which now forms the basis of the associative containers that I required.

Implementing a red-black tree

I implemented the red-black tree based on the description in CLR (Cormen, Leiserson, Rivest and Stein’s Introduction to Algorithms (3rd ed)) with some help from an article by Julienne Walker and some code from the Literate Programming Wiki. I found Julienne’s article interesting and thought provoking but in the end the implementation didn’t work for me as it caused too much ‘shaking’ of the tree during attempts to insert which resulted in us finding a node already present with the same key, or attempts to delete a node which didn’t exist. Also the lack of parent pointers in this implementation made it harder to iterate the tree and harder to remove a node or navigate from it if given only the node. I did, however, like the case reduction that was achieved by using an array of two pointers for the left and right tree nodes rather than explicit left and right pointers. The Literate Programming code was more useful but needed some changes to deal with my requirement for the tree to be intrusive and not require memory allocations during insertion and removal.

The code I ended up with is a template that looks something like this:

template <
   class T,                                                 // The type to store
   class K,                                                 // The type of the key
   class TtoK,                                              // Functions to access a key from a T
   class Pr = std::less<K>,                                 // Predicate
   class TtoN = TIntrusiveRedBlackTreeNodeIsBaseClass<T> >  // Functions to access the node from a T
class TIntrusiveRedBlackTree

There are function objects that you can specify which allow you to change how the tree locates the node that forms part of your data and how the tree works out what the key for your data is. I talk about these a little more here and here.

My tree implementation could, no doubt, be improved upon. I expect we could store the ‘red/black’ flag within one of the link pointers to reduce the size of the node fractionally, there’s scope for performance tuning and the generic nature could be improved somewhat (I’m thinking about how I specify and use the function objects that I use to obtain the node information and key from the data to be stored) and the tree could be extended to allow the containers to support more of the STL’s functionality. Right now though, things work quite nicely.

Containers based on a tree

A map, or associative array, can be implemented in terms of a tree where we have a key which is used to locate the data within the tree. The key and data are stored with the node in the tree. A set is just a special kind of map where the key is the ‘identity’ of the data and is implicit. A set’s key may be the address of the data (if storing arbitrary data structures) or the value of the data if storing strings or numbers or whatever.

One of my use cases requires a multi-map. I decided to implement this in terms of a tree where each node can consist of a list of data items with that key. The node type for this container is bigger than a tree node as it needs pointers for a doubly linked list in addition to the normal tree pointers. I briefly considered creating a new kind of node for the red-black tree and re-using the tree node pointers to form my doubly linked list but that seemed like too much work as the tree algorithm would need to be changed to incorporate a third node type and the tree’s search performance characteristics would change for the worse.

The multi-map allows for atomic removal of all items with a specific key, you’re given a collection of nodes that you can iterate, as well as allowing you to treat all duplicate values as equal (and remove any one by key) or remove a specific data value by passing the data item itself.

Source code

The code can be downloaded from the end of this article which uses the intrusive containers. The code will build with Visual Studio 2008, 2010, 2012 and 2013. Win32Tools is the solution that you want and Win32ToolsTest is the project that you should set as active. The code will build with either the standard STL that comes with Visual Studio or with a version of STL Port. The code uses precompiled headers the right way so that you can build with precompiled headers for speed or build without them to ensure minimal code coupling. For more details see here. This code is in the Public Domain.