what's the difference between boost::pool<>::malloc and boost::pool<>::ordered_malloc, and when should I use boost::pool<>::ordered_malloc?

Question

I'm using boost.pool, but I don't know when to use boost::pool<>::malloc and boost::pool<>::ordered_malloc?

so,

1. what's the difference of boost::pool<>::malloc and boost::pool<>::ordered_malloc?

2. when should I use boost::pool<>::ordered_malloc?

Answer 1

First, we should know the basic idea behind the Boost Pool library: simple_segregated_storage, it is similar to a singly linked list, and responsible for partitioning a memory block into fixed-size chunks:

A memory pool keeps a free list of memory chunks. So we mentioned blocks and chunks: the memory pool uses new or malloc to allocate a memory block and divides it into many memory chunks which have same size.
Assume the address is aligned by 8, 4 bytes for storing the address of next chunk, so a memory block(8 bytes * 32 chunks) is as below(the memory address is just for illustrating the question, not a real one):

Now, suppose the user allocates 8 bytes memory twice, so the chunks: [0xDD00,0xDD08), [0xDD08,0xDD10) are used. After a while, the user releases the memory at [0xDD00,0xDD08), so this chunk will go back to the free list. Now the block is like this:

Afterwards the user releases the memory at [0xDD08,0xDD10), the simplest way to place this chunk back in the list is to update the first to point to it, constant time complexity. the simple_segregated_storage<T>::free() is doing this exactly:

void free BOOST_PREVENT_MACRO_SUBSTITUTION(void * const chunk)
{ //! Free a chunk.
  //! \pre chunk was previously returned from a malloc() referring to the same free list.
  //! \post !empty()
   BOOST_POOL_VALIDATE_INTERNALS
  nextof(chunk) = first;
  first = chunk;
  BOOST_POOL_VALIDATE_INTERNALS
}

After that, the list would be like this:

Now we noticed the list of chunks are not ordered by their address after these operations! If we want to preserve the order while de-allocating, call pool<>::ordered_free() instead of pool<>::free() to places the memory back in the list in its proper order. Now we've known what's the order in the memory pool, let's dig into the source code of boost::pool<>::malloc and boost::pool<>::ordered_malloc:

void * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
{
  if (!store().empty())
    return (store().malloc)();
  return malloc_need_resize();
}

void * ordered_malloc()
{
  if (!store().empty())
    return (store().malloc)();
  return ordered_malloc_need_resize();
}

As we can see, they differ only when there is no free chunk in the list of memory blocks. In this scenario, it allocates a new memory block, merges its free list to pool's free list, the difference between these two methods is that boost::pool<>::ordered_malloc preserves order while merging the free lists.
Above is for question 1.
So, why does the order matter?! It seems the memory pool works perfectly with the unordered chunks!
First, if we want to find a contiguous sequence of n chunks, the ordered free list would make it easier. Second, Let's have a look at the derived class of boost::pool: boost::object_pool, it provides automatic destruction of non-deallocated objects on destruction of the object_pool object while you can also destroy the object manually, for example:

class X { … };

    void func()
    {
        boost::object_pool<X> alloc;

        X* obj1 = alloc.construct();
        X* obj2 = alloc.construct();
        alloc.destroy(obj2);
    }

the code above is OK, no memory leak or double delete! How does boost::object_pool do this magic? Let's find the implementation of destructor of boost::object_pool(I have boost 1.48 on my machine):

template <typename T, typename UserAllocator>
object_pool<T, UserAllocator>::~object_pool()
{
#ifndef BOOST_POOL_VALGRIND
  // handle trivial case of invalid list.
  if (!this->list.valid())
    return;

  details::PODptr<size_type> iter = this->list;
  details::PODptr<size_type> next = iter;

  // Start 'freed_iter' at beginning of free list
  void * freed_iter = this->first;

  const size_type partition_size = this->alloc_size();

  do
  {
    // increment next
    next = next.next();

    // delete all contained objects that aren't freed.

    // Iterate 'i' through all chunks in the memory block.
    for (char * i = iter.begin(); i != iter.end(); i += partition_size)
    {
      // If this chunk is free,
      if (i == freed_iter)
      {
        // Increment freed_iter to point to next in free list.
        freed_iter = nextof(freed_iter);

        // Continue searching chunks in the memory block.
        continue;
      }

      // This chunk is not free (allocated), so call its destructor,
      static_cast<T *>(static_cast<void *>(i))->~T();
      // and continue searching chunks in the memory block.
    }

    // free storage.
    (UserAllocator::free)(iter.begin());

    // increment iter.
    iter = next;
  } while (iter.valid());

  // Make the block list empty so that the inherited destructor doesn't try to
  // free it again.
  this->list.invalidate();
#else
   // destruct all used elements:
   for(std::set<void*>::iterator pos = this->used_list.begin(); pos != this->used_list.end(); ++pos)
   {
      static_cast<T*>(*pos)->~T();
   }
   // base class will actually free the memory...
#endif
}

it goes through all the chunks in the list of memory blocks(list, the data member of boost::pool<>, holds the locations and sizes of all memory blocks allocated from the system) to find whether any chunk in it also shows in the free list, if not, calls the destructor of the object, then free the memory. So it's kind of getting the intersection of two sets, just as std::set_intersection() does! If the list is sorted, it would be much faster to do that. Actually in the boost::object_pool<>, the order is required, the public member functions: boost::object_pool<>::malloc() and boost::object_pool<>::free() just call the boost::pool<>::ordered_malloc() and boost::pool<>::ordered_free() respectively:

element_type * malloc BOOST_PREVENT_MACRO_SUBSTITUTION()
{ //! Allocates memory that can hold one object of type ElementType.
  //!
  //! If out of memory, returns 0. 
  //!
  //! Amortized O(1).
  return static_cast<element_type *>(store().ordered_malloc());
}
void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk)
{ //! De-Allocates memory that holds a chunk of type ElementType.
  //!
  //!  Note that p may not be 0.\n
  //!
  //! Note that the destructor for p is not called. O(N).
  store().ordered_free(chunk);
}

So for the queston 2: You needn't use boost::pool<>::ordered_malloc in most situations.