[boost] Re: Challenge: pool allocator

From: Stephen Cleary (scleary_at_[hidden])
Date: 2000-03-03 12:30:07

Say, I think I figured out how to fix the inefficiencies in pool!

pool, as it stands right now, has a list of storage units.  The problem
is that each of these storage units is just two pointers (the "first"
pointer for the free list and a pointer to reference the allocated
memory block):
  pool  ->  storage0 -> block
            storage1 -> block
            storage2 -> block

However, each time another storage unit is needed, the allocator must
be called *twice*, once for the small storage unit and once for the
block.  Since each storage unit can only have one block, it seems
wasteful, in both run-time and memory terms.

I've re-written two of the layers of pool (the array_segregated_storage
and pool layers), and combined them into one.  Also, I've changed
simple_segregated_storage to be a mayfly object.  The memory block and
the "storage unit" are now both contained inside a single POD type,
with the memory block first (so it's properly aligned).  The pool
object now uses mayfly simple_segregated_storage objects to manage the
PODs.  Alignment is still guaranteed, and pool now has no unnecessary
memory or run-time overhead!

pool now looks like this:
  pool  ->  { block first next }
                           |
            { block first next }
                   ...

where "first" is pointing into "block" (the next available chunk), and
"next" is pointing to the next POD in pool's list.

The new pool (which I've tested with the same program as the old pool)
is in the vault under pool_allocator/new.

        -Steve