[boost] Re: Challenge: pool allocator

From: Stephen Cleary (scleary_at_[hidden])
Date: 2000-03-06 16:26:55

john maddock wrote: 
> Steve,
> 
> Going on to your pool allocator I have a couple of gripes:
> 
> I think that as it stands you maintain a separate free list in each
block -
> as a result the code for malloc has to enumerate through the blocks
until
> it finds one with one or more free elements.  As a result the
complexity of
> your code for N allocations is O(N^2), when it should be O(N).  Most
pool
> allocators avoid this by having a single free list for all "blocks".

Good point.  I'll re-evaluate pool sometime soon and see how easy it
would be to merge all the "first" pointers into one, etc.  Shouldn't be
too hard.

> 
> I tried to use:
> 
>   ::boost::pool<std::string> bp;
>   bp.construct(std::string()); 
> 
> but ran into compile errors - is this me or you?
> 

I don't know!  I tried the same thing (it rather suprised that it would
fail) on BCB, and, sure enough, it tries to compile the call to
'construct' as a call with a function object, not a "const string &"! 
(In fact, I *did* find a bug in the construct() function that makes a
copy_constructor -- the parameter is not passed; but the compiler never
found that bug because it's not using that function!)

When we add the family-of-template-functions approach, we will avoid
this problem.  However, we have another.  Let's put aside the
constructor function object completely for the moment -- we're going to
name it something other than 'construct', anyway, so it won't get in
the way.

So the problem is: BCB chokes on the following code:

template <typename T>
void f(T & x) { }

void test()
{
  int tmp;
  f(tmp);  // works OK: calls f<int>(int & x);
  f(13);   // chokes: does NOT find f<const int>(const int & x);
}

This may be just a problem with BCB, because they do not consider
'const' as part of the type.  I've briefly looked in the Standard, but
it's confusing me, and I can't prove that the above is conformant. 
Anyone else want to try?  Will this compile on other compilers? 
*Should* it?

> 
> I think that it is worthwhile to look forward to uses also,
personally I
> can see the following uses for a generic pool allocator:
> 
> 1) To implement a standard allocator - all instances of the allocator
must
> share the same underlying pool, different allocator types which have
the
> same memory/alignment requirements should share the same pool, the
> allocator must be usable in program startup/exit code:  this more or
less
> mandates that the pool is an aggregate type so that it can be
statically
> initialised.
> 

I've already started work on this.  AFAICT, I have conformant code, but
BCB chokes on it every time. . .  I plan to look at RW's std::allocator
to see how they got around it.

> 2) To implement an instance based standard allocator - each instance
gets
> its own allocator, but copies of allocators share the same pool. 
Memory
> can be allocated with one allocator instance and freed with another
> (standard requirement), consequently the lifetime of memory allocated
from
> an allocator is independant of the lifetime of the allocator - more
or less
> requires a reference counted pool.

This is also a planned addition, but be wary: Standard containers are
allowed to assume that their allocators (of the same type) always
compare equal.  In other words, std::vector<int, my_alloc> may not work
(portably) for an instance-based my_alloc.

> 
> 3) To implement overloaded new/delete at class scope.

Another future direction.  My original post had global new/delete
overrides, but they were quickly dropped due to improper compiler
support.  Maybe in the future :).

> 
> 4) To implement object factories - using either model (1) or (2)
above. 
> With respect to object factories I would favour Dave's template member
> functions for create - note that this is a superset of the copy
constructor
> approach - it may also be *much* more effecient than relying on a copy
> constructor alone.  I don't think it matters that its limited to maybe
> 0,1,2 or 3 arguments, if the limitation proves too much one can always
> revert to your approach and pass a temporary as a single parameter.
> 

I haven't thought of an object factory class.  That's one pattern I
actually don't use often.  Of course, a little down the road we should
design this as well.

Thanks a *lot* for your comments, John!

        -Steve