Geek asks and answers

Free Boost Pool O (n) or O (1)

I recently opened the Boos Pool library and started adapting it to my code. One thing that was mentioned in the library was missing is the base class, which would override the new / delete statements for any class and use the pool to manage memory. I wrote my own implementation and with some meta-programming templates, it really looked very decent (we support any class from 1 to 1024 bytes in size, just based on the base class)

I mentioned these things because so far it has been really cool and exciting, and then I found this post from the Boost mailing list . It seems that some people really clog the pool library and especially point out the inefficiency of the free () method, which they say works in O (n) time. I went through the code and found that this is an implementation of this method:

void free(void * const chunk)
{
  nextof(chunk) = first;
  first = chunk;
}

For me, it looks like O (1), and I really don't see the inefficiency they are talking about. One thing that I noticed is that if you use multiple instances of singleton_pool (i.e. different tags and / or placement sizes), they all use the same mutex (more precisely, the critical section), and this could be slightly optimized. But if you used the usual heap operations, they would use the same form of synchronization.

- ?

+3
1

. , order_free, :

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;
  }
}

find_prev

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);
  }
}
+5

More articles:


All Articles