C++ 中的 O(1) 对象池

• 下载 AllocationDeallocationTest.2014_04_12.zip - 6.3 KB

引言

我开始写一篇关于 C++ 中垃圾回收的文章，其中一个比较是，在某些情况下，真正的垃圾回收语言可能比 C++ 更快，因为它们以块的形式分配内存，这使得大量小对象的分配变得极其快速，而这在 C++ 中却不会发生。

嗯，实际上我们可以在 C++ 中做到这一点，但它不是自动的，所以需要我们自己使用。要做到这一点，我们应该使用某种内存或对象池。

我查找了一些现有实现，实际上并不喜欢它们。例如，Boost 有一个池，分配内存很快，但如果我们想控制何时销毁每个对象，释放内存会很慢。所以，我决定创建自己的实现，我将在下面介绍。

解决方案

这个解决方案由一个单一的模板类组成，名为 ObjectPool。可以说，在命名类为“对象池”和“内存池”之间选择有点困难。由于该解决方案不预先初始化一定数量的对象，所以可以说它只是一个内存池，因此调用单个对象的构造函数和析构函数的开销仍然会发生。但我不想称之为“内存池”，因为用户将从池中请求对象，而不是原始内存。也许我应该找一个不会引起混淆的名字，但目前，它叫做 ObjectPool。

实现如下

• 分配初始数量的内存（默认情况下，它是一个可以容纳 32 个对象的块，按指针对齐 [32 位计算机为 4 字节，64 位计算机为 8 字节]），并且有一个指向“第一个已删除”对象的引用，设置为 NULL；
• 每次请求新对象时，代码首先检查是否有指向第一个已删除对象的指针。如果有，那么这就是将要使用的地址，并且第一个指针将指向“下一个”空闲对象（即该指针位置的内容）。如果没有可用的已删除对象，我们会检查内存块中是否还有空间。如果没有，则请求一块新内存（大小翻倍，有一个特定限制）。无论哪种情况，我们都将调用所选地址对象的构造函数，然后返回它；
• 要删除一个对象，非常简单。我们调用析构函数，然后将该对象视为指针。该指针将设置为指向实际的“第一个空闲”对象，然后其地址将被设置为第一个已删除项；
• 当池本身被删除时，它将释放第一个块，并且由于每个块会释放下一个块，最终会释放所有块。

所以，我们可以这样总结：

• 所有对象分配都是 **O(1)**。当然，在某些情况下需要分配内存，这可能需要一些时间，但这种分配的性能不受已分配项目数量的直接影响，因为我们限制了块可以变得多大；
• 所有对象销毁都是 **O(1)**，因为我们调用析构函数并简单地“交换指针”；
• 我们删除了多少个对象并不重要。池将保留所有已分配的内存块，直到池本身被删除；
• 当删除池时，内存块会被释放，但内部项的析构函数不会被调用，因此我们需要在销毁池之前（如果需要调用对象析构函数的话）删除每个项。

还有一些*替代*方法，实际上不会初始化或销毁对象。这些方法负责将对象从池中“分配”或“释放”出去，但不会调用构造函数或析构函数。如果我们想调用一个特定的、非默认的构造函数，或者知道对象没有析构函数（或者出于某种原因我们不想调用它），这可能会很有用。

这个池什么时候有用？

• 当我们有一个需要分配/释放大量对象的“工作”时，并且知道我们可以将内存保留到该工作结束（大多数循环都属于这一类）；
• 当我们知道同一时间内存中会有有限数量的对象，但我们却不断地“分配”和“释放”它们。

使用代码

要使用该代码，我们必须初始化池，提供初始容量和其他块的最大大小。如果不提供任何参数，将使用默认值 32（初始容量）和 100 万（最大块大小）。

因此，下面这样的行将使用这些默认值在堆栈（或静态）上初始化我们的池

ObjectPool<Test> pool;

然后，要分配一个对象，我们这样做：

Test *test = pool.New();

要释放一个对象，我们这样做：

pool.Delete(test);

如果我们不想使用默认构造函数，我们可以这样做：

T *unitializedObject = pool.GetNextWithoutInitializing();

// And then we can call an appropriate constructor:
Test *test = new (uninitializedObject) Test(/*... parameters here...*/);

如果我们不想允许调用析构函数，但想将内存返回给池，我们可以使用：

pool.DeleteWithoutDestroying(test);

显然，我们应该使用适当的类而不是 Test，并使用适当的变量名而不是 test。

池的源代码是：

template<typename T>
class DefaultMemoryAllocator
{
public:
  static inline void *Allocate(size_t size)
  {
    return ::operator new(size, ::std::nothrow);
  }
  static inline void Deallocate(void *pointer, size_t size)
  {
    ::operator delete(pointer);
  }
};

template<typename T, class TMemoryAllocator=DefaultMemoryAllocator>
class ObjectPool
{
private:
  struct _Node
  {
    void *_memory;
    size_t _capacity;
    _Node *_nextNode;

    _Node(size_t capacity)
    {
      if (capacity < 1)
        throw std::invalid_argument("capacity must be at least 1.");

      _memory = TMemoryAllocator::Allocate(_itemSize * capacity);
      if (_memory == NULL)
        throw std::bad_alloc();

      _capacity = capacity;
      _nextNode = NULL;
    }
    ~_Node()
    {
      TMemoryAllocator::Deallocate(_memory, _itemSize * _capacity);
    }
  };

  void *_nodeMemory;
  T *_firstDeleted;
  size_t _countInNode;
  size_t _nodeCapacity;
  _Node _firstNode;
  _Node *_lastNode;
  size_t _maxBlockLength;

  static const size_t _itemSize;

  ObjectPool(const ObjectPool<T, TMemoryAllocator> &source);
  void operator = (const ObjectPool<T, TMemoryAllocator> &source);

  void _AllocateNewNode()
  {
    size_t size = _countInNode;
    if (size >= _maxBlockLength)
      size = _maxBlockLength;
    else
    {
      size *= 2;

      if (size < _countInNode)
        throw std::overflow_error("size became too big.");

      if (size >= _maxBlockLength)
        size = _maxBlockLength;
    }

    _Node *newNode = new _Node(size);
    _lastNode->_nextNode = newNode;
    _lastNode = newNode;
    _nodeMemory = newNode->_memory;
    _countInNode = 0;
    _nodeCapacity = size;
  }

public:
  explicit ObjectPool(size_t initialCapacity=32, size_t maxBlockLength=1000000):
    _firstDeleted(NULL),
    _countInNode(0),
    _nodeCapacity(initialCapacity),
    _firstNode(initialCapacity),
    _maxBlockLength(maxBlockLength)
  {
    if (maxBlockLength < 1)
      throw std::invalid_argument("maxBlockLength must be at least 1.");

    _nodeMemory = _firstNode._memory;
    _lastNode = &_firstNode;
  }
  ~ObjectPool()
  {
    _Node *node = _firstNode._nextNode;
    while(node)
    {
      _Node *nextNode = node->_nextNode;
      delete node;
      node = nextNode;
    }
  }

  T *New()
  {
    if (_firstDeleted)
    {
      T *result = _firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      new(result) T();
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    T *result = new(address) T();
    _countInNode++;
    return result;
  }

  // This method is useful if you want to call a non-default constructor.
  // It should be used like this:
  // new (pool.GetNextWithoutInitializing()) ObjectType(... parameters ...);
  T *GetNextWithoutInitializing()
  {
    if (_firstDeleted)
    {
      T *result = (T *)_firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    _countInNode++;
    return (T *)address;
  }
  void Delete(T *content)
  {
    content->~T();

    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
  void DeleteWithoutDestroying(T *content)
  {
    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
};

template<typename>
const size_t ObjectPool<t,>::_itemSize = ((sizeof(T) + sizeof(void *)-1) / sizeof(void *)) * sizeof(void *);
</t,>

线程安全

所提供的代码不是线程安全的，但这实际上使其速度更快。因此，如果我们将其用作静态变量或传递给其他线程，则需要我们自己使用某种锁定机制。

我个人认为不应该有真正的静态池，如果需要，我们应该为每个线程设置一个池。这将避免由锁定引起的性能下降。

示例

示例是一个应用程序，它将 100 个对象创建和删除 100 万次，然后显示使用池和使用普通的 new 和 delete 调用完成工作所需的时间。

当然，这并非真实场景，但它表明了池与普通 new/delete 调用相比有多快。您可以将其用于更好的情况。

版本历史

• 2014 年 4 月 12 日：为模板添加了内存分配器参数，默认使用 new/delete 运算符而不是 malloc/free，将复制构造函数/复制运算符声明为私有以避免默认实现，将构造函数声明为 explicit，并将内存块的删除改为使用 while 循环而不是递归以避免过度使用堆栈；
• 2014 年 3 月 21 日：修正了构造函数中的一个错误（重复分配）；
• 2014 年 3 月 19 日：初始版本。