[boost] Re: Challenge: pool allocator

From: Stephen Cleary (scleary_at_[hidden])
Date: 2000-03-07 13:32:38

john maddock wrote: 
> I have written some fairly simple (actually very simple!) allocators
using
> C++ Builder before and haven't had any problems (at least not yet),
if you
> want to share your code I may be able to spot something (fresh pair
of eyes
> etc).

OK.  It's in the vault (pool_allocator/allocator).  The test_alloc
tries to use a std::list with a pool allocator, and the errors I get
suggest that BCB can't see the members of 'pool' after it's been
template typedef'ed for a different type (e.g., the list node type).

> Re: allocator growth stategy - is it worthwhile making the number of
> elements allocated in each block a run time constant (rather than
fixed at
> compile time), that way the allocator could double the number of
elements
> allocated per-block each time that the allocator runs empty. 
Assuming that
> the cost of removing at pre-allocated element from the stack is
negligable
> compared to the cost of asking the system for it, this would reduce
the
> performance to O(lnN) for N blocks.  Now before too many programmers
> explode all over their Pc's at seeing this let me make it clear that
the
> assumption is not true, and that this is an abuse of big-O notation. 
> However there is some truth in there, and it would be interesting to
see
> whether this offered any speed improvement - obviously at the expense
of
> space.

This is a good idea.  Another item to add to my pool list :).  Of
course, amortized time would be O(N), but it *would* be faster:
  A == time to allocate chunk
  B == time to allocate block
  A*N + B*N >= A*N + B*lnN

This is assuming that the time to allocate a block from the system
allocation is about the same for any size block.

        -Steve