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

Question

最近，我发现了 Boos Pool 库，并开始将其应用到我的代码中。库提到它缺少的一件事是一个基类，该基类将覆盖任何类的新/删除运算符并使用池进行内存管理。我编写了自己的实现并使用一些元模板编程，它实际上看起来非常不错(通过简单地从基类派生来支持大小在 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 库效率低下且过时吗？

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