Re: [boost] pool allocation

Subject: Re: [boost] pool allocation
From: Stefan Strasser (strasser_at_[hidden])
Date: 2009-09-24 20:28:31

Am Thursday 24 September 2009 23:30:18 schrieb OvermindDL1:
> On Tue, Sep 22, 2009 at 7:17 PM, Emil Dotchevski
>
> <emildotchevski_at_[hidden]> wrote:
> > Have you considered/evaluated dlmalloc?
>
> Or tcmalloc?  (Google's memory pool/alloctor, amazing time efficiency)

external library suggestions are appreciated but besides the point, since this 
code is part of a boost library proposal.
don't you think Boost.Pool is missing something here? something that's not 
very hard to write, since there is Boost.Intrusive, so you can implement 
allocation algorithms quite easily.
even pools that support allocation of arbitrary sized objects using an 
intrusive set and an allocation algorithm like the ones deployed by 
Boost.Interprocess here:
http://www.boost.org/doc/libs/1_35_0/doc/html/interprocess/allocators_containers.html#interprocess.allocators_containers.memory_algorithms.rbtree_best_fit

I've used something similar for a disk space allocator:

typedef set_base_hook<tag<by_size_tag> > by_size_hook;
typedef set_base_hook<tag<by_offset_tag> > by_offset_hook;
struct free_block : by_size_hook,by_offset_hook
...
intrusive::multiset<free_block,base_hook<by_size_hook>...
intrusive::set<free_block,base_hook<by_offset_hook>...

allocation and deallocation of arbitrary sized blocks in O(log N), with block 
merging and block splitting. in a few hundred lines of code.