[boost] Re: Proposal: boost::pool fast pointer

From: scleary_at_[hidden]
Date: 2002-07-30 12:04:44

> > - Introduces memory overhead for *every* dynamically-allocated object
not
> > placed in a ptr<>.
> 
> Yeah but is it really that bad when you know that shared_ptr<> is already
> taking two integers in length?  And also by considering the highly
probable
> fact that more than one pointer will point to the same object:
> sizeof(shared_ptr<int>) x 2 + sizeof(malloc(int)) *>* sizeof(ptr<int>) x 2
+
> sizeof(malloc(int + 1))

What I meant is that not all dynamically-allocated objects are placed in a
ptr<>.  Displacing the global new & delete forces the count to be allocated
every time new is called; for example, every node allocated by every
std::list<..> would then take up more memory than necessary.

> > - Cannot be used in any project where the end user wishes to displace
the
> > global operator new & delete.
> 
> This would depend on the project you are working on.

Yes, but the underlying concept is that there are a few places where the
Standard allows a restricted form of end-user program-level extensibility.
In areas like these, IMO, libraries should not interfere.  Examples:
displacing global new/delete, registering functions with atexit,
set_unexpected, set_terminate, etc.

> > If you're really dead-serious about removing the allocation of the
shared
> > count in shared_ptr<>, you might want to consider a pool-based approach.
> > That will get you an amortized single-allocation-per-object.
> >
> > Back when shared_ptr<> was being designed, Dave Abrahams (I think it was
> > him, anyway) did some speed testing with a shared_ptr<> that took its
> > counter from a handmade pool -- and IIRC, it showed some favorable
results.
> > Since then, no-one has ever seriously explored making a shared_ptr<>
that
> > used a pool allocator; you might wish to try that approach.
> 
> I'm not familiar with this allocator but in your opinion would it be as
> simple to use in the end?

The end-user syntax should be about the same as a shared_ptr<>.

The most straightforward way to implement it is to have the ptr<> have two
pointers, similar to shared_ptr<>.  Only instead of allocating the count via
"new int", allocate it from a pool.  This is essentially what Dave did.  A
pool allocator for T (e.g., int) works by:
 1) Allocating space for an array of T.
 2) Keeping a "free list" that actually exists inside the space for this
array of T.
 3) Responding to an allocation request for a single T by returning the
first element of the free list.
 4) Responding to a deallocation request for a single T by adding it onto
the front of the free list.

As you can see, once the first allocation is made, all the pool "allocation"
and "deallocation"s are just some fast pointer operations.  It gets a bit
more complex when the free list is empty or if you want to free memory back
to the system, but a pool allocator can still provide amortized constant
time.

For more information about pool allocators, check out the Boost.Pool
documentation.

        -Steve