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),
> want to share your code I may be able to spot something (fresh pair
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
> compile time), that way the allocator could double the number of
> allocated per-block each time that the allocator runs empty.
> 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
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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk