Boost logo

Boost :

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
> 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
> allocated per-block each time that the allocator runs empty.
Assuming that
> the cost of removing at pre-allocated element from the stack is
> compared to the cost of asking the system for it, this would reduce
> 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
> 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
> whether this offered any speed improvement - obviously at the expense
> 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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at