[boost] Re: Challenge: pool allocator

From: scleary_at_[hidden]
Date: 2000-02-29 17:08:01

Dave -

I accept the challenge.  My first attempt is in the Boost vault under
pool_allocator.

The pool_alloc.h is the header file and also (currently) the
implementation file.  test_pool_alloc.cpp is a quick & dirty
test/example program.

The end result is usage of the form:

class Foo { ... };
boost::pool<Foo> foo_pool;
Foo * foo1 = foo_pool.construct(); // if Foo has default constructor
Foo * foo2 = foo_pool.construct(*foo1); // if Foo has const copy
constructor
Foo * foo3 = foo_pool.construct(x);
  // where x is a function object representing a constructor of Foo,
  //  taking one parameter, the address at which to construct an object
  //  of type Foo.  (When writing these function objects, just use
  //  placement new -- see the test/example file).

> This is harder than it looks - remember that if an exception is thrown
> during construction the the memory for the instance should be
returned to
> the pool *and more importantly* the instance should not be
double-destroyed
> when the pool is destroyed.

No problem.  This behaviour is tested for in the test file.

> Some of the hard issues are:
> 1. Memory alignment of instances in the pool
> 2. You can't make unions of non-POD types, so it's hard to thread a
> free-list through memory for instances in the pool

These issues are handled.  boost::pool automatically handles alignment
issues in a portable way, and the free-list overlay is also guaranteed
to be portable.  (I think -- this is the shakiest part of the whole
thing).

Detailed discussion follows.

boost::pool is actually implemented in 3 layers.

The lowest layer, called 'simple_segregated_storage' is an extremely
low-level simple memory allocator for fixed-sized chunks cut out of a
fixed-sized block.  It overlays a free list within its block, and, in
order to do so portably, makes a number of assumptions.  Not meant for
general use.  See the docs for details.

The next layer, called 'array_segregated_storage' is a higher-level
memory allocator that allocates the block used by simple_segregated_sto
rage.  This block is allocated in such a way that all the assumptions
made by simple_segregated_storage are satisfied.  array_segregated_stor
age also introduces the type whose storage we are allocating
(simple_segregated_storage just works with raw char pointers).  It is
also at this level that the destructor travels the free list in
conjunction with the implicit list to determine which chunks have not
been freed, and calls their destructors.  This interface is still
somewhat primitive, though, and is not recommended for general use.

The final layer is 'pool', which maintains a list of
array_segregated_storage's, which may grow as allocation functions are
called.  'pool' also provides 'construct' and 'destroy' functions as
well as the 'malloc' and 'free' functions.  As mentioned above,
'construct' expects a function object.  Other than that, the usage is
obvious.

In a final draft, I would add another layer, placement new & delete
functions.  I think the correct implementation is in the header file
now (inside #if 0...#endif) because it's not supported on many
compilers.  The syntax is still awkward, anyway, so maybe this layer
isn't a good idea and we should just stick with construct/destroy.

Notes:
  T (the type being allocated) must have a non-throwing destructor.
  The order of destruction of objects allocated from the pool is
_unspecified_.  To be specific, it is NOT the reverse order of
construction.
  Non-throwing versions of malloc/free are not provided (yet).

BTW, what is the proposed purpose of 'pool'?  Just a garbage collector?

       -Steve