Is Boost Pool free efficiency O(n) or O(1)

Recently I've discovered Boos Pool library and started adapting it to my code. One thing that library mentions it was missing was a base class that would override new/delete operators for any class and use the pool for memory management. I wrote my own implementation and with some meta-template programming, it actually came out looking very decent (support any class with size between 1 and 1024 bytes by simply deriving from the base class)

I mentioned those things because so far this was really cool and exciting and then I found this post from Boost mailing list. It appears some people really hammer the Pool library and especially point out the inefficiency of free() method which they said runs in O(n) time. I stepped through the code and found this to be the implementation of that method:

void free(void * const chunk)
{
  nextof(chu开发者_Go百科nk) = first;
  first = chunk;
}

To me this looks like O(1) and I really don't see the inefficiency they are talking about. One thing I did notice is that if you are using multiple instances of singleton_pool (i.e. different tags and/or allocation sizes), they all share the same mutex (critical section to be more precise) and this could be optimized a bit. But if you were using regular heap operations, they'd use the same form of synchronization.

So does anyone else consider Pool library to be inefficient and obsolete?

That free sure does look constant time to me. Perhaps the author of the post was referring to ordered_free, which has this implementation:

void ordered_free(void * const chunk)
{
  // This (slower) implementation of 'free' places the memory
  //  back in the list in its proper order.

  // Find where "chunk" goes in the free list
  void * const loc = find_prev(chunk);

  // Place either at beginning or in middle/end
  if (loc == 0)
    (free)(chunk);
  else
  {
    nextof(chunk) = nextof(loc);
    nextof(loc) = chunk;
  }
}

Where find_prev is as follows

template <typename SizeType>
void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
{
  // Handle border case
  if (first == 0 || std::greater<void *>()(first, ptr))
    return 0;

  void * iter = first;
  while (true)
  {
    // if we're about to hit the end or
    //  if we've found where "ptr" goes
    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
      return iter;

    iter = nextof(iter);
  }
}