How does boost.pool achieve re-use of allocated memory?

Question

Background

My previous question about boost.pool led me to investigate boost.pool in detail, and now I have a supplementary question to finalize my understanding.

Prelude

This reference states the following about the object pool pattern:

The object pool pattern is a software creational design pattern that uses a set of initialized objects kept ready to use, rather than allocating and destroying them on demand.

From what I can tell, boost.pool (simplified) implements the object pool pattern by means of memory allocation and management mostly based on the size of an element_type, and returns a simple pointer to an allocated object:

element_type * malloc();
void free(element_type * p);

A simple boost example also shows that it is not necessary to explicitly free the acquired element:

X * const t = p.malloc();
... // Do something with t; don't take the time to free() it.

Question

I understand that the allocated memory will be safely freed on destruction of the pool object, but how does the pool know when a block of memory acquired by a client has been released back into the pool and is reusable if its interface hands back a direct pointer to element_type, yet a call to free() is still not required? i.e. How can the boost pool re-use this memory if it cannot be certain that the memory is not still in use? And if it does not re-use this memory, is this even considered the same pattern as the one explained by the wiki reference?

Answer 1

How can the boost pool re-use this memory if it cannot be certain that the memory is not still in use?

It can't. In fact it won't reuse that memory. It only guarantee that you will have no leaks when the pool is destroyed.

And if it does not re-use this memory, is this even considered the same pattern as the one explained by the wiki reference?

The article you linked says: Object pooling can offer a significant performance boost in situations where the cost of initializing a class instance is high

While from Boost pool introduction: Pools are generally used when there is a lot of allocation and deallocation of small objects.

So no, they are not the same pattern. One is meant to re-use objects which are expensive to construct (threads, opengl resources, etc.). The other is meant to manage a lot of small objects, giving you more control than the standard allocator gives.

As you pointed out, there are two ways of using pools:

1. As an allocator, calling malloc()/free() when appropriate. This is the basic pool-allocator usage, it helps to reduce memory fragmentation
2. Construct a ton of temporary objects and don't bother to delete them.

Example for the second case: imagine you have a graph class, where each node stores its neighbors using pointers. Now you have to make a deep copy of your graph. You will allocate a bunch of new nodes and copy the data from the old ones to the new ones, but now you have to initialize neighbors pointers, so you need a map from old pointers to new pointers:

std::map<node*,node*> old_ptr_to_new_ptr;

This is a good example where pool allocators are useful (I won't go into detail about how to use pool allocators with std containers): a lot of small objects (map nodes) which are going to be deleted all together.

Answer 2

The boost pool library provides STL allocators that are more efficient when allocating objects of the same type (as opposed to std::allocator which simply uses new and delete). This is what Stroustrup or Alexandrescu would call a small-object allocator.

As any custom allocator class, it works with essentially four separate functions: allocate, deallocate, construct, and destroy. I think their names are self-explanatory (unless you are confused about allocation vs. construction). To obtain a new object from the pool, you first call allocate(1) to get a pointer and then you call construct( ptr, value ) on that pointer ptr to get it constructed as a copy of value (or moved). And you do the reverse when you want the delete that object. These are the mechanism that all STL containers use under-the-hood to allocate-construct-destroy-deallocate their objects.

You shouldn't trust the wikipedia article that you referred to (and not in general either), it is very poorly phrased, uses very vague and inaccurate language, and takes somewhat narrow view on the object-pool pattern. And btw, quoting wikipedia is worthless, you don't who wrote it, have no reason to trust it, always go to the source.

The pattern described in the wiki (and especially in the source article) has a very different objective from what the boost pool allocators try to accomplish. As described in the wiki, the emphasis is on reusing the objects without really destroying them (e.g., a thread-pool is a good example because it would be expensive to create and destroy threads frequently, and the source article is interested in pooling database service providers for similar reasons). In boost pool allocators, the emphasis is on avoiding invoking the heap (freestore) to allocate many small objects, a task that the heap cannot perform very efficiently and will cause it to become fragmented. It maybe should have been called "small-object allocators" instead, to avoid any confusion.

how does the pool know when a block of memory acquired by a client has been released back into the pool and is reusable if its interface hands back a direct pointer to element_type, yet a call to free() is still not required?

I don't think that it can. I believe that the story goes like this. You can choose to just allocate a bunch of objects from the pool, without ever deallocating them, and that is still safe in the sense that when you destroy the pool-allocator, all its memory is flushed with it, including all the objects that you left lingering in the pool. That's what they mean by "it is not required to free the objects", simply that your application will not leak memory beyond the life-time of the pool-allocator object if you forget to free all the objects from the pool.

But, if you don't tell the pool-allocator to deallocate the objects that you no longer need (and thus, can be reused) it will not be able to reuse those memory slots, that's just impossible (given that the allocators don't deliver any kind of special smart-pointer that would be able to track the allocated objects).

How can the boost pool re-use this memory if it cannot be certain that the memory is not still in use?

If it cannot be certain that the memory is not still in use, then there is no way that it can re-use the memory. Any piece of code that would make such a reckless thing as to "assume that an object is no longer needed without being sure" would be a worthless piece of code as it would obviously have undefined behavior and no programmer could possibly use it, ever.

And if it does not re-use this memory, is this even considered the same pattern as the one explained by the wiki reference?

No, it does not implement what is explained in the wiki. You'll have to get used to the fact that terminology sometimes clash in unfortunate ways. It is more common to refer to what boost pool implements either as a "memory pool" or as a "small object allocator". This is a structure optimized for somewhat small objects that are fairly cheap to construct and to copy. Because the heap (freestore) is tailored for larger blocks of memory and tends to deal poorly with trying to find a place for small objects, using it for that purpose is not a great idea, and can lead to heap fragmentation. So, pool-allocators essentially replace the heap with something that is more efficient at allocating many small objects of the same type. It doesn't re-use objects, but it can re-use memory that has been freed, just like the heap does. And it generally allocates its memory (that it allocates away) from the heap as a large contiguous block (e.g., with std::vector). There are many other performance benefits to using a small-object allocator when appropriate. But what boost pool implements is in fact very different from what is described in the wiki. Here is the implementer's description of what pool-allocators are good for:

A good place to use a Pool is in situations where many (noncontiguous) small objects may be allocated on the heap, or if allocation and deallocation of the same-sized objects happens repeatedly.