Re: [Boost-users] boost:interprocess sizeof(list<Type>::Node)

Subject: Re: [Boost-users] boost:interprocess sizeof(list<Type>::Node)
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2009-03-06 11:25:46

waterbed wrote:
> Hello,
> 
> My problem is really basic :
> I have N objects of type Type to store in a boost::interprocess::list<Type>.
> The question is easy : How many bytes should I provide to the
> managed_mapped_file, in order it fits correctly?
> 
> 
> So, I supposed I had to store (let's assume bi = boost::interprocess):
>   + The list allocator : sizeof( bi::allocator<Type,
> bi::managed_shared_memory::segment_manager> )
>   + The struct of the list itself : sizeof( bi::list<Type,
> bi::allocator<Type, ...> > )
>   + The N nodes of the list containing each one of my objects : sizeof(
> bi::list<Type, ...>::Node)
> 
> First issue : bi::list<Type, ...>::Node is private. Fine, I changed it as
> public.
> Second issue : sizeof(bi::list<Type, ...>::Node) was not enough, actually I
> can't add N objets, I was just able to allocate (N - x) objets
> Third issue : so I tried to fix the value of x, but x is not constant, it
> changes according to N...
> 
> Thus I think, I made a mistake but where? or I forgot something but what?

When you allocate memory, it allocates more space than the space of the 
node:

-> Alignment: memory allocators allocate raw memory so they usually 
allocate data aligned to a value that allows to build any data type 
(usually 8 bytes).

-> Metadata: memory allocators needs some metadata to be able to 
deallocate an allocated block and merge free blocks. This usually is 4-8 
bytes per-allocation (example of metadata: the size of the memory block 
in bytes).

-> The memory allocator usually has a minimum memory allocation size to 
be able to allocate a block because free blocks are stored in a data 
structure and the algorithm can't create free blocks smaller than a 
size. Depending on the algorithm to store free nodes, it can be 8-16 
bytes. Interprocess uses red-black trees to store free nodes by size (12 
bytes).

-> Fragmentation, depending on the allocation pattern, you might have 
free memory holes but not enough to allocate a node.

And don't forget managed_shared_memory also needs some metadata to build 
name-value indexes.

When allocating contiguous nodes (imagine you allocate the whole list 
with no other allocation between node insertion) default interprocess 
memory allocator should have an overhead of 4 bytes per allocation in 32 
bit systems and an alignment of 8 bytes (in windows, in linux-gcc max 
aligment seems to be 4 bytes). The same as usual allocators like 
dlmalloc. A think it's pretty efficient ;-) Of course you should add 
space for the name-object map, and other goodies provided by managed 
segments.

That might produce a waste 8 bytes per node. If you want to reduce the 
waste, use a pool allocator but take in care that they allocate arrays 
of nodes and then the allocator returns pointers to them, so 
anticipating the amount of memory the pool you will need (when will it 
allocate the array) is even harder.

Try to add the size of two-three pointers per node and I think that 
should be pretty accurate.

Best,

Ion