Re: [boost] [allocators] Article and library about allocator improvements

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-06-23 12:14:54

David Abrahams wrote:
> Ion Gaztañaga wrote:
> 
>> I plan to publish the article somewhere (supposing someone is crazy
>> enough to publish it ;-) ) but first I wanted to share this with
>> boosters to try to improve the article/library and know if developers
>> are interested in allocator issues. Comments are welcome!
> 
> Hi Ion,
> 
> Are you aware of the "scoped allocator" support that has recently been
> accepted into the WP?

Yes, thanks. I participated in some discussions with Pablo Halpern and 
John Lakos to make Scoped allocators with non-scoped ones (basically 
shared memory). Scoped allocators are basically mainly related to 
allocator propagation and polymorphic allocators (plus the machinery to 
implement this). My proposal has 3 different parts:

1) Realloc (expand in-place) and shrink to fit for std::vector. This 
means reusing the old buffer (and avoiding moving or copying data) if 
the allocator supports this.

2) Burst allocation: Some node containers (list, map...) just implement 
range insertion with a loop:

for(/*every input element*/){
    this->insert(pos, *inpit);
}

the idea here is to make a single to the allocator to allocate N nodes 
with a single call. The allocator can just allocate a single big chunk 
(thus, avoiding N lookups) and divide the big chunk in individually 
deallocatable nodes.

3) Adaptive pools:

Some allocators, (like Boost.Pool) use simple segregated storage to 
minimize node overhead. Sadly, they don't implicitly return memory to 
the general-purpose allocator because the operation is costly 
(Boost.Pool offers a purge() or release_memory() function to explicitly 
trim allocated nodes). Adaptive pools are similar to simple segregated 
storage allocators but they use alignment to automatically deallocate 
memory while maintaining zero per-node payload. These allocators don't 
need any allocator extension but they work extremely well with 
burst-allocation because we can simplify bookkeeping operations that 
have some impact when using single node allocation scheme.

In other words, Scoped Allocators and my proposal are completely 
complementary.

Regards,

Ion