[Boost-users] [review] intrusive container comments

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-03-21 11:48:46

Hi Ion,

Here are some comments I have from reading the online documentation.
I haven't followed the review discussion (because I don't have the 
time), so I apologize if my comments have already been discussed.

I was originally review manager for Olaf, and was almost ready to
allow a review when he said he did not have time to finnish the library.

 From what I recall, the docs have been improved somewhat, so kudos for 
that work.

1. "Constant time size: The intrusive container holds a size member that 
it's updated with every insertion/erasure. This implies that the size() 
function has constant time complexity. On the other hand, increases the 
size of the container, and some operations, like splice() taking a range 
of iterators, have linear time complexity in linked lists."

Howward Hinnant proposed a new splice() function that allows one to pass 
the size into splice() to keep splice() O(1). Would this not be an idea
here?

2. My general view of the design: fairly complicated, though the extra 
speed can be worth the effort. I find the amount of typedef'ing fairly
large and can't help feeling it could be simplified.

3. Is 'Foo' really needed twice:

   typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> 
FooValueTraits;

???

4. The cloning example 
(http://ice.prohosting.com/newfunk/boost/libs/intrusive/doc/html/intrusive/clone_from.html)
I don't quite get; I thought the whole point of intrusive container was 
to avoid memory allotions. Also, how does this affect exception-safety?

In general I feel this is an important library with many uses for 
performance savy applications. I feel the quality in general is high.

I had one major discussion with Olaf which relates to the general 
easy-of-use and also to space-tradeoffs:
----------------------------------------

When it is a design-time decision to allow the object to be inserted
into 1 container, one object always carry the node-structure overhead
(that is also when I don't insert the object into an intrusive container).

Furthermore, If some objects must be in more than one container, all
objects of that type pay the space penalty even though only a few
objects are in several containers.

Third, the compile-time dependency is fairly complicated,
and would be cool to get rid of.

Therefore I think there are compelling reasons for exploring
a different design: an extrusive design where the node-structure
is not part of the object.

This immediately eliminates three problems:

-1- there is no compile-time dependency
-2- there is by default no any space overhead
-3- there is by default no problem or contstraint when an object is 
added to more containers at runtime

The approach has one serious drawback:

-1- it might require extra memory

This happens when all live objects are added to an intrusive container.

An example: consider an ilist of size N. The node structure requires two 
T* objects and so the space required is

   N * 2 * sizeof(T*)

An extrusive approach would look a bit like this:

template< class T >
class extrusive_list
{
   struct Node
   {
      T* prev;
      T* next;
      T* me;
   };
   std::vector<Node> nodes;
};

Thus the space required would be

   N * 3 * sizeof(T*)

if all N objects are put into the container. If less than 2/3's of the 
live objects are put into the container, the extrusive version takes up 
less space.

As you add support for several containers, the extrusive version is even 
more likely to save space IMO.

Now, I haven't actually implemented extrusive containers as out-lined 
above, but the simplity of use and the potential space savings tells me 
that it would be well worth persue.

Let me know what you all think.

best regards

Thortsen