最近,我发现了Boos Pool库,并开始对其进行调整以适应我的代码.库提到它缺少的一件事是基类,它将覆盖任何类的new / delete运算符,并使用该池进行内存管理.我编写了自己的实现,并使用一些元模板编程,看起来非常不错(只需从基类派生即可支持大小在1到1024字节之间的任何类)

我提到这些东西是因为到目前为止,它确实很酷而且令人兴奋,然后我找到了post from Boost mailing list.看来有些人确实对Pool库提出了批评,并特别指出他们说free()方法的效率低下,他们说该方法在O(n)时间内运行.我单步执行代码,发现这是该方法的实现：

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

对我来说,这看起来像O(1),我真的看不到他们在谈论的效率低下.我确实注意到的一件事是,如果您正在使用singleton_pool的多个实例(即不同的标记和/或分配大小),它们都共享相同的互斥量(更精确的是关键部分),可以对此进行一些优化.但是,如果您使用常规堆操作,则它们将使用相同形式的同步.

那么,还有其他人认为Pool库效率低下吗？

解决方法:

对我来说,那个免费的时间确实是不变的.也许帖子的作者指的是ordered_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);
  }
}