KatolaZ <katolaz@???> writes:
> On Mon, Feb 01, 2016 at 05:36:38PM +0100, Didier Kryn wrote:
>
> [cut]
>
>>

>>     Note that if you manage your memory pool as an array then
>> allocation and deallocation are extremely fast and can be done
>> without consuming a single byte for book-keeping. I think this
>> almost trivial allocator actually fits with many cases. It can even
>> make sense to loose part of the memory if objects haven't all the
>> same size, provided this size is bounded.

>>
>
> If you know in advance the typical sizes of chunks to be allocated,
> then reserving different sections of your array to chunks of different
> sizes can be quite efficient, and helps limiting external
> fragmenttion. This was more or less the strategy actually implemented
> in the original slab allocator of the Linux kernel, and might work
> decently.

The original slab allocator was implemented by Jeff Bonwick for the
SunOS kernel (5, not 4) and it decidedly didn't work in this way. It
used type-segregated, linked free lists and was based on some kind of
underlying 'page allocator'. This can be used to limit internal
fragmentation (memory lost due to bookkeeping overhead) and it's a good,
generally scheme for dealin with many types of objects of discrete sizes
but it's totally powerless agains external fragmention, ie, memory
consumed by inactive objects of a certain kind which can't be reused
because the inactive objects are interspersed with active ones.