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