Boost::Intrusive for HPC

Question

How good is boost::intrusive library for high performance computing? I want to use a container for a non-copyable non-assignable class. I was planning to use normal STL with shared_ptr. I found out that boost::intrusive can also be used for the same purpose. So my question is, are they really that efficient?

if given an option between a STL container with shared_ptr types and a boost::intrusive which one would you prefer?

Answer 1

Generally, intrusive collections are the most efficient in terms of memory usage. If your goal is to squeeze every last cpu cycle that is the only way to go.

Consider a list of boost shared pointers. When creating a new object what happens is:

• the object allocated from the heap and initialized
• constructor of boost shared pointer from a raw pointer allocates another object on the heap to store the object'a reference counter (that is why boost intrusive pointer is better since the reference counter is stored in the object avoiding this allocation)
• list::insert allocates a list node and copies the shared pointer

In the above, there are three memory allocations involved to create and insert a new object into a collection.

Now consider using an intrusive list. For the same task what happens is:

• a new object gets allocated and initialized
• list::insert just assigns to the object's list node pointers, since the node is embedded in the object and has been already allocated

Here, only one memory allocation happens. Since the cpu addresses less memory when using intrusive collections, cpu caches get utilized better, resulting in fewer cache misses along with reduced memory footprint (known as locality of reference principle).

The drawback of intrusive collections is that it has to be known in advance in what type and how many collections an object can be an element of at one time. In my personal experience this extra upfront thinking leads to cleaner and simpler designs.