Ion, these concrete examples you brought up are very compelling. I think you should include them with the documentation. It is helpful to me, at least, to have an example analysis in front of me, so I can review my own situation by it. -- Tack On Mar 16, 2007, at 4:54 PM, Ion Gaztañaga wrote:
Gennadiy Rozental wrote:
"Ion Gaztañaga" <igaztanaga@gmail.com> wrote in message news:45FAD381.1090600@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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost