[boost] Re: Intrusive containers: second iteration

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2005-05-01 05:52:11

Hi,

frank_at_[hidden] wrote:
> Yep, now I understood. The whole thing is about laying out objects in 
> memory in an efficient way. Sorry for always talking in critic, but I would
> love to suggest to think about memory allocators.
> Pool allocators can be utilised greatly to achieve memory layout for
> ideal cache heating. I missed that point in the efficiency discussion
> of intrusive containers versus non-intrusive containers.
Well, I'm not sure if this discussion belongs to the doc.
Anyway, let's think about the four points in 'Overviw: Properties of 
intrusive containers' wrt pool allocators.
The first point: Depending on your RTL pool allocators may improve the 
performance of the memory management. But it's a step in quantity, not 
in quality. That is, there is still some memory management, while for 
intrusive containers computing a node from a value and vice versa (to a 
certain degree this operations are the counterparts of memory 
management) is boiled down by the compiler to maybe three machine 
instructions (in some cases it vanishes completely).
The second point: indeed it's possible to write a pool allocator in a 
way, that at least the algorithm, that would need an intrusive container 
otherwise, don't throw. Just preallocate enough elements beforehand (for 
intrusive containers you do that implicitly).
The third point: I have no clue how to accomplish this task using 
non-intrusive containers without a lot of additionally effort. And in 
fact, this feature is very useful.
The fourth point: Regarding this discussion this is a non-issue IMHO. I 
just wnat to point out, that clearing a std::list<T*> is as linear as 
implicitly removing all elements stored in an ilist.

Best regards
Olaf Krzikalla