Re: [Boost-users] [review] intrusive container comments

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-21 13:36:22

Hi Thorsten,

Thorsten Ottosen wrote:
> Hi Ion,
> 
 > [snip]
 >
> 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.

I would like to thank Olaf for his great work. It's a shame we had no 
time to finish the library but I think the need of a good intrusive 
library (I badly needed one for Interprocess containers and memory 
algorithms) has pushed this to the review.

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

Joaquin is the main responsible of the general improvement. I was scared 
every time I received comments from him ;-)

> 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?

It's already there. "On list's size" 
(http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html) was 
the main motivation ;-)

> 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.

Ok.

> 3. Is 'Foo' really needed twice:
> 
>   typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> 
> FooValueTraits;
> 
> ???

The first Foo is a tag. Previously, each base hook needed a number to 
distinguish different base hooks from each other. Recently this was 
changed with a tag, and the example just uses Foo as a tag. I could have 
used any other type. Or as Daniel James suggests, a default tag, if only 
have one hook. Something like:

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

> 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?

Yes the whole point is to avoid memory allocations, but also offer an 
easy way to build non-intrusive containers. For example, copying a 
red-black tree is not efficient if you don't do an structural copy 
(which also has better exception guarantees, because the potentially 
throwing comparison functor is not used). Some copies are recursive and 
need to create values as the cloning algorithm does the work.

Obviously, the cloning function is allowed to throw but the function 
will only throw if the cloner throws whereas the usual clear()+insert() 
can throw with the predicate. This cloner can be used, for example, to 
implement an assignment that recycles the memory where the old values 
where placed. I agree that for list and slist the cloning algorithm is 
not complicated, but I wanted to establish a common cloning function for 
all the algorithms, so the can have access to the most efficient cloning 
algorithm (structural copy) without knowing the internals of the 
intrusive container.

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

Thanks.

> 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.

Right.

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

Compile-time dependency is basically because of performance reasons. The 
hook can be placed everywhere in the type (any base or member at any 
offset) and having this information at compile time makes code faster, 
instead of querying this at runtime.

> 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.

Interesting. "Extrusive" sounds cool ;-)

> 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*)

Ok.

> 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*)

When an a node is erased from the container, I suppose you are you going 
to erase it from the vector (otherwise, you would need to track the free 
and used Nodes), so depending when the Node was placed (in the beginning 
or end of the vector), the overhead of an erasure can be high.

Wait! Another option would be to convert a Node in a union so that free 
Nodes can form a linked list when they are not used, and add to to 
extrusive_list a pointer to the first free Node. If there are no free 
Nodes to reuse, the vector can be safely expanded and the last nodes can 
form again a linked list of free nodes. But you lose exception safety in 
insertions, a unique property of intrusive containers, because the 
needed memory is already allocated.

> Let me know what you all think.

Still not sure about the advantages (and I'm afraid they are not trivial 
to implement efficiently), but I'm interested in the idea. Are you 
volunteering to write the alter-ego of Intrusive, Extrusive? Even this 
Extrusive library would benefit from its evil twin Intrusive ;-)

> best regards
> 
> Thortsen

Regards,

Ion