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

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-16 17:54:00

Gennadiy Rozental wrote:
> "Ion Gaztañaga" <igaztanaga_at_[hidden]> wrote in message 
> news:45FAD381.1090600_at_gmail.com...
>> Gennadiy Rozental wrote:
>>> IOW this library promotes unsafe programming right?
>> Don't be that hard ;-) Let's say that intrusive containers are
>> interesting for the following purposes:
>>
>> -> Embedded systems.
> 
> It's too generic. So are you saying std::list is not usefull for Embedded 
> systems?

I've used std::list in embedded systems. I'm only saying that intrusive
containers are more embedded friendly because they are more space
efficient than non-intrusive containers. An class whose sizeof is 12 
bytes to be inserted in two lists at the same time would be implemented 
using two std::list<Object*> + dynamic allocation, which means (in a 
typical 32 system):

12 bytes + bookeeping memory from the heap for each object
12 bytes per std::list node (two pointers to form the list plus thes 
sizeof(Object*) + plus bookeeping memory from the heap

This means that you have 36 bytes per object + 3*bookeeping memory from 
the heap.

With an intrusive list your object needs 12 bytes + 16 bytes from the 
hooks: 28 bytes + bookeeping from the heap.

If bookepping is 8 bytes (a typical figure) you have 60 bytes vs. 36 
bytes in size. If you have a million objects, there is big difference.

An intrusive container will always be more space efficient than the 
non-intrusive approach, specially for small objects. I know that you can 
use memory pools to minimize the size overhead, but you will never beat 
the intrusive approach.

>> -> High performance algorithms.
> 
> How intrusive containers enhance performance?

Intrusive containers save memory allocations. That's a big advantage. 
For example:

    std::vector<MyObject> objects(NUM_OBJECTS);

    std::list<MyObject*> list;

    for(int i = 0; i < NUM_OBJECTS; ++i){
       list.push_back(objects[i]);
    }

needs NUM_OBJECTS + 1 calls to the heap.

The same example with intrusive containers:

    std::vector<MyIntrusiveObject> objects(NUM_OBJECTS);

    boost::intrusive::ilist<MyIntrusiveObject> list
       (objects.begin(), objects.end());

just need 1 call to the heap. That's a big difference.

Apart from that, iterating std::list<Object*> needs two memory accesses 
to reach the object. ilist<Object> just needs one. You can insert an 
object in several containers at the same time, without any dynamic 
memory allocation.

>> -> Low-level memory algorithms, node pools, and similar stuff.
>> -> To build more complex containers, avoiding memory allocations.
> 
> What an alternative existing solutions and how your library compare with 
> them?

Insertions in some intrusive containers (like lists) have no-throw 
guarantee. So inserting in an intrusive list can't never fail and that's 
an important feature when writing low-level algorithms. 
std::list<Object*> can throw because the allocation can throw.

>> I agree that Intrusive is not a high-level library comparing it to other
>> Boost libraries, but I really think that it will be very useful to build
>> other Boost libraries. I would say that Intrusive wants to convert some
>> currently unsafe/low-level practices a bit more safer without losing
>> performance.
> 
> How safer? How much it adds to handwritten 10 liner intrusive container?

Write an intrusive red-black tree. I'm pretty sure you will need
more than 10 lines.

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.

Best,

Ion