Re: [boost] Ion Gaztañaga's Intrusive Library

From: Timmo Stange (ts_at_[hidden])
Date: 2007-03-16 19:01:29

Ion Gaztañaga wrote:

> I agree that I should add numbers to the library documentation. But I 
> think that the advantages of intrusive containers are well-known. For 
> example, operating system kernels use intrusive containers internally 
> (linux is an example) because they are more efficient than their 
> non-intrusive counterparts. Just like intrusive_ptr is more efficient 
> than shared_ptr, because avoids an extra allocation to allocate the 
> reference count and the reference count is stored inside the object 
> avoiding extra memory accesses and cache misses.

While I would generally agree with the performance and size advantages
of intrusive containers you mentioned, efficient cache usage will not
always be a strength but sometimes a weakness of that approach. Just
like with intrusive reference counting, you have the disadvantage of
cache pollution and potential false sharing across threads with
the maintenance data being part of the object. That depends heavily
on the use case, but in your example of one set of objects being stored
in two lists, the result may be almost three times the necessary
memory bandwidth/cache load for iterating over just one list looking for
a certain object by address (intrusive approach worst case).

It seems to be difficult to describe the advantages of intrusive
containers in a few words without raising objections, which is
probably because non-intrusive containers (together with para-
meterizable allocators) already are sufficiently fast in most
cases. I'd still like to see your library to become part of
boost.

Regards

Timmo Stange