Boost logo

Boost :

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
> 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
> 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
> share the same underlying pool, different allocator types which have
> same memory/alignment requirements should share the same pool, the
> allocator must be usable in program startup/exit code: this more or
> mandates that the pool is an aggregate type so that it can be
> 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
> its own allocator, but copies of allocators share the same pool.
> can be allocated with one allocator instance and freed with another
> (standard requirement), consequently the lifetime of memory allocated
> 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)
> With respect to object factories I would favour Dave's template member
> functions for create - note that this is a superset of the copy
> 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!


Boost list run by bdawes at, gregod at, cpdaniel at, john at