Boost logo

Boost :

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

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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at