Boost Pool的自由效率是O(n)还是O(1)

Question

最近我发现了Boos Pool库,并开始根据我的代码进行调整.库提到它缺少的一件事是一个基类,它将覆盖任何类的new/delete操作符并使用池进行内存管理.我编写了自己的实现,并使用了一些元模板编程,它实际上看起来非常不错(通过简单地从基类派生,支持大小在1到1024字节之间的任何类)

我提到了那些东西,因为到目前为止,这真的非常酷,令人兴奋,然后我从Boost邮件列表中找到了这篇文章.看起来有些人真正打击了Pool库,特别指出了free()方法的低效率,他们说这些方法在O(n)时间运行.我逐步完成了代码,发现这是该方法的实现:

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

对我来说,这看起来像O(1),我真的没有看到他们所说的低效率.我注意到的一件事是,如果你使用的是singleton_pool的多个实例(即不同的标签和/或分配大小),它们都共享相同的互斥锁(关键部分更精确),这可以稍微优化一下.但是如果你使用常规堆操作,他们会使用相同的同步形式.

那么其他人是否认为Pool库效率低下且过时了？

Answer 1

这种自由的确定对我来说看起来是不变的.也许这篇文章的作者指的是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);
  }
}