Re: [Boost-users] [pool] pool allocator: customizing and memory usage

From: Lang Stefan (SLang_at_[hidden])
Date: 2008-02-19 12:24:15

> There is a bug in pool that causes it to severely leak memory if
> sizeof(T) is not aligned on bounds of at least sizeof(void*). This
> could be the reason.
> 
> -- 
> Cory Nelson

Thanks Cory for your response. The leaks I observed were on lists with
sizes of 16 and 24 bytes respectively. I doubt there is any alignment
problem with these. The tests I am currently running use nodes of 12
bytes (list type is std::list<int> : two pointers plus one int per node)
and I am experiencing similar problems: after constructing a list of
1000 nodes (12000 bytes needed) the amount of allocated storage is 48480
bytes!

In response to my own questions, since I think I found the answers to
some - this is what I found so far:

Q: Why does pool<>::release_memory() not work for lists using
fast_pool_allocator?
A: Two reasons: First of all, release_memory() requires the free list
(list of free chunks) to be ordered. This in turn requires the allocater
being used to call the methods ordered_malloc() and ordered_free()
respectively - fast_pool_allocator does not. Secondly, release_memory()
can only be accessed via the singleton_pool underlying the
implementation of fast_pool_allocator - which is hidden from the public
interface. This means it should not be used! (Or that is my impression)
It is probably possible to work around this problem by writing another
allocator, or just by specializing the implementations of
fast_pool_allocator<>::allocate() and
fast_pool_allocator<>::deallocate() for the allocator types being used.
However, this is likely to severely impact performance, and I'm not
entirely sure this is a safe route to go.

Q: Why does pool<>::purge_memory() cause run_time errors occasionally
(when used on lists using fast_pool_allocator)?
A: Some (or all?) implementations of std:list<> allocate one llist node
to represent the list head. This node will be destructed once the list
is explicitely destructed, or once a list constructed on the stack runs
out of scope. This list head is stored within the same singleton_pool as
it's nodes are. This means, even after removing all elements from a
list, one node is still stored in the pool: the list's head. If
pool<>::purge_memory() is called on this pool before the list itself is
destructed, the destruction of the list will provoke a memory access
error.
As an aside, purge_memory() is available only over the pool interface
and since the singleton_pool underlying fast_pool_allocator is hidden
from the public interface, this function is not supposed to be used for
fast_pool_allocator.

In short: singleton_pool is probably not meant to support purge_memory,
especially when you are using it for different types that might share
the same pool instance. Releasing memory might make more sense, but is
expensive because it requires ordered_malloc and ordered_free. Since
singleton_pool might be shared by different types there's no way to
guarantee the ordered allocation and deallocation routines will always
be used, so release_memory() is probably not a good idea either! The
only way to make releasing memory from singleton_pool feasible, is to
provide a garbage collection function that does not require the free
list to be ordered. A trivial solution would be O(n^2) - definitely not
a good idea - but with a little more sophistication this could be
achieved at O(n). (it will be considerably slower than ordered_release
though)

Looks like I'm out of luck here, unless I start writing my own
pool_allocator...

Cheers,
Stefan