Boost :

atack2_at_[hidden]

--
Tack
On Mar 16, 2007, at 4:54 PM, Ion Gaztañaga wrote:
> 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
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost