[boost] Re: Challenge: pool allocator

From: John Maddock (John_Maddock_at_[hidden])
Date: 2000-03-04 07:16:02

Steve,

>This method of getting around offsetof() is questionable at best. 
Since p->m is defined to be (*p).m [5.2.5/3], the result may well be
the dereferencing of a null pointer (implementation-defined).  C:ARM
[11.1] suggests using a predefined, non-null pointer to get around
this.  Even with that, though, this form of expression cannot be used
in an integral constant expression [5.19/1, last sentence], or even in
an address constant expression [5.19/4, 2nd-to-last sentence].
<

I had thought that I had already read that section carefully, but perhaps
not, I agree that it is non-standard for non-POD types at least, although
all the compilers I've tried accept this with good grace.

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".

I tried to use:

  ::boost::pool<std::string> bp;
  bp.construct(std::string()); 

but ran into compile errors - is this me or you?

****

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.

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.

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

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.

BTW if the pool meats the requirements for (1), I think that all the others
can be satisfied.

- John.