C++自定义内存分配器（Allocator）设计：实现Polymorphic Allocators与高性能池化策略

C++ 自定义内存分配器（Allocator）设计：实现 Polymorphic Allocators 与高性能池化策略

大家好，今天我们来深入探讨 C++ 中自定义内存分配器（Allocator）的设计与实现。我们将重点关注两个关键方面：Polymorphic Allocators（多态分配器）以及高性能池化策略。

1. C++ Allocator 基础与必要性

C++ 标准库提供了默认的 std::allocator，它通常使用 new 和 delete 来分配和释放内存。虽然简单易用，但在某些场景下，默认分配器可能无法满足性能或特定需求。

考虑以下情况：

• 性能敏感的应用: 频繁的小块内存分配和释放会导致较高的开销，影响程序性能。
• 嵌入式系统: 可能需要对内存分配进行精细控制，以满足资源限制或实时性要求。
• 自定义内存管理: 需要实现自定义的内存管理策略，例如内存池、垃圾回收等。
• 避免内存碎片: 默认分配器可能导致内存碎片，降低内存利用率。
• 多线程环境: 需要线程安全的内存分配器，避免竞争和数据损坏。

因此，自定义 allocator 成为解决这些问题的有效手段。

2. Allocator 接口与基本实现

C++ allocator 必须满足特定的接口要求。以下是 allocator 的基本定义：

template <typename T>
class MyAllocator {
public:
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_reference = const T&;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;

  MyAllocator() noexcept = default;
  template <typename U> MyAllocator(const MyAllocator<U>&) noexcept {}

  [[nodiscard]] pointer allocate(size_type n);
  void deallocate(pointer p, size_type n);

  template <typename U, typename... Args>
  void construct(U* p, Args&&... args);

  void destroy(pointer p);

  template <typename U>
  bool operator==(const MyAllocator<U>&) const noexcept;

  template <typename U>
  bool operator!=(const MyAllocator<U>&) const noexcept;
};

接口说明:

• value_type: 分配器管理的类型。
• pointer, const_pointer, reference, const_reference: 指针和引用的类型定义。
• size_type, difference_type: 大小和差值类型。
• allocate(size_type n): 分配 n 个 value_type 大小的内存块，返回指向已分配内存的指针。
• deallocate(pointer p, size_type n): 释放之前分配的 n 个 value_type 大小的内存块，p 是指向要释放内存的指针。
• construct(U* p, Args&&... args): 在 p 指向的内存位置构造一个 U 类型的对象，使用 args 作为构造函数的参数。
• destroy(pointer p): 销毁 p 指向的对象。
• operator==, operator!=: 比较两个分配器是否相等。

一个简单的基于 new 和 delete 的分配器实现如下：

template <typename T>
class SimpleAllocator {
public:
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_reference = const T&;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;

  SimpleAllocator() noexcept = default;
  template <typename U> SimpleAllocator(const SimpleAllocator<U>&) noexcept {}

  [[nodiscard]] pointer allocate(size_type n) {
    if (n > std::numeric_limits<std::size_t>::max() / sizeof(T)) {
      throw std::bad_alloc();
    }
    pointer p = static_cast<pointer>(::operator new(n * sizeof(T)));
    if (!p) {
      throw std::bad_alloc();
    }
    return p;
  }

  void deallocate(pointer p, size_type n) {
    ::operator delete(p);
  }

  template <typename U, typename... Args>
  void construct(U* p, Args&&... args) {
    ::new (p) U(std::forward<Args>(args)...);
  }

  void destroy(pointer p) {
    p->~U();
  }

  template <typename U>
  bool operator==(const SimpleAllocator<U>&) const noexcept { return true; }

  template <typename U>
  bool operator!=(const SimpleAllocator<U>&) const noexcept { return false; }
};

注意事项:

• allocate 函数应该检查 n * sizeof(T) 是否溢出。
• 使用 ::operator new 和 ::operator delete 可以避免调用重载的 new 和 delete 运算符。
• construct 函数使用placement new在已分配的内存中构造对象。
• destroy 函数显式调用对象的析构函数。
• operator== 和 operator!= 的实现应该根据分配器的语义进行定义。 在这个简单的例子中，我们认为所有 SimpleAllocator 实例都是相等的。

3. Polymorphic Allocators (多态分配器)

Polymorphic Allocators (PMR) 是 C++17 引入的一个重要特性，它允许你在运行时选择分配器，而无需在编译时确定。这提供了更大的灵活性和可配置性。

PMR 的核心是 std::pmr::memory_resource 抽象基类和 std::pmr::polymorphic_allocator 类模板。

3.1 std::pmr::memory_resource:

memory_resource 定义了分配和释放内存的抽象接口。它包含以下纯虚函数：

• void* do_allocate(std::size_t bytes, std::size_t alignment): 分配 bytes 字节的内存，并按 alignment 对齐。
• void do_deallocate(void* p, std::size_t bytes, std::size_t alignment): 释放之前分配的 bytes 字节的内存。
• bool do_is_equal(const memory_resource& other) const noexcept: 比较两个 memory_resource 对象是否相等。

3.2 std::pmr::polymorphic_allocator:

polymorphic_allocator 是一个 allocator 类模板，它使用 memory_resource 来分配和释放内存。它接受一个 memory_resource 指针作为构造函数的参数，并在内部使用该 memory_resource 来执行内存操作。

3.3 示例:

#include <memory_resource>
#include <vector>
#include <iostream>

// 自定义 memory_resource 实现
class MyMemoryResource : public std::pmr::memory_resource {
public:
  MyMemoryResource(std::size_t capacity) : buffer_(new char[capacity]), capacity_(capacity), current_size_(0) {}
  ~MyMemoryResource() override { delete[] buffer_; }

protected:
  void* do_allocate(std::size_t bytes, std::size_t alignment) override {
    // 简单的分配实现，没有考虑 alignment
    if (current_size_ + bytes > capacity_) {
      throw std::bad_alloc();
    }
    void* p = buffer_ + current_size_;
    current_size_ += bytes;
    return p;
  }

  void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override {
    // 简单的释放实现，实际上不释放内存
    (void)p; (void)bytes; (void)alignment; // Suppress unused parameter warnings
  }

  bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override {
    return this == &other;
  }

private:
  char* buffer_;
  std::size_t capacity_;
  std::size_t current_size_;
};

int main() {
  MyMemoryResource mr(1024);
  std::pmr::polymorphic_allocator<int> alloc(&mr);
  std::pmr::vector<int> vec({1, 2, 3}, alloc); // 使用自定义分配器

  for (int x : vec) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

代码解释:

1. MyMemoryResource: 我们创建了一个自定义的 memory_resource，它使用一个固定大小的缓冲区来分配内存。do_allocate 只是简单地增加 current_size_ 指针，而 do_deallocate 则什么也不做（这只是一个简单的示例，实际应用中需要更完善的内存管理）。
2. polymorphic_allocator: 我们使用 MyMemoryResource 创建了一个 polymorphic_allocator。
3. std::pmr::vector: 我们使用 polymorphic_allocator 创建了一个 std::pmr::vector。 注意，我们需要使用 std::pmr::vector，它是 std::vector 的 PMR 版本。

PMR 的优势:

• 运行时选择分配器: 可以在运行时根据需要选择不同的 memory_resource，例如，根据不同的内存区域或分配策略。
• 简化容器的分配器管理: 容器只需要存储一个 memory_resource 指针，而不是多个模板参数，降低了代码的复杂性。
• 可扩展性: 可以方便地添加新的 memory_resource 实现，而无需修改现有的代码。

4. 高性能池化策略

内存池是一种常用的高性能内存管理技术。它预先分配一块大的内存块，然后将该内存块分割成多个固定大小的小块，用于满足后续的内存分配请求。

4.1 内存池的优点:

• 减少内存分配和释放的开销: 避免了频繁调用 new 和 delete，降低了系统调用的开销。
• 提高内存分配速度: 从预先分配的内存块中分配内存通常比从系统堆中分配内存更快。
• 减少内存碎片: 可以有效地减少内存碎片，提高内存利用率。
• 确定性: 内存分配和释放的时间复杂度是 O(1)，这在实时系统中非常重要。

4.2 内存池的基本实现:

#include <iostream>
#include <vector>
#include <cassert>

template <typename T>
class SimplePoolAllocator {
public:
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_reference = const T&;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;

  SimplePoolAllocator(size_type pool_size) : pool_size_(pool_size) {
    chunk_size_ = sizeof(T);
    pool_ = new char[pool_size_ * chunk_size_];
    free_list_ = reinterpret_cast<T*>(pool_);
    T* current = free_list_;
    for (size_type i = 0; i < pool_size_ - 1; ++i) {
      current = reinterpret_cast<T*>(reinterpret_cast<char*>(current) + chunk_size_);
      reinterpret_cast<char*>(current)[0] = ''; // 简单的标记
      reinterpret_cast<char**>(current)[0] = reinterpret_cast<char*>(free_list_) + (i+1) * chunk_size_; // 下一个空闲块的地址

    }
    //最后一个节点指向nullptr
    current = reinterpret_cast<T*>(reinterpret_cast<char*>(current) + chunk_size_);
    reinterpret_cast<char**>(current)[0] = nullptr;
  }

  ~SimplePoolAllocator() {
    delete[] pool_;
    pool_ = nullptr;
    free_list_ = nullptr;
  }

  [[nodiscard]] pointer allocate(size_type n) {
    if (n != 1) {
      throw std::bad_alloc(); // 简单实现只支持分配一个对象
    }

    if (!free_list_) {
      throw std::bad_alloc(); // 内存池已满
    }

    pointer p = free_list_;
    free_list_ = reinterpret_cast<T*>(reinterpret_cast<char**>(free_list_)[0]); // 更新 free_list_
    return p;
  }

  void deallocate(pointer p, size_type n) {
    if (n != 1) {
      return; // 简单实现只支持释放一个对象
    }

    // 将 p 添加到 free_list_ 的头部
    reinterpret_cast<char**>(p)[0] = reinterpret_cast<char*>(free_list_);
    free_list_ = p;

  }

  template <typename U, typename... Args>
  void construct(U* p, Args&&... args) {
    ::new (p) U(std::forward<Args>(args)...);
  }

  void destroy(pointer p) {
    p->~T();
  }

  template <typename U>
  bool operator==(const SimplePoolAllocator<U>& other) const noexcept {
    return (pool_size_ == other.pool_size_);
  }

  template <typename U>
  bool operator!=(const SimplePoolAllocator<U>& other) const noexcept {
    return !(*this == other);
  }

private:
  char* pool_;
  T* free_list_;
  size_type pool_size_;
  size_type chunk_size_;

};

struct MyObject {
    int data;
    MyObject(int value) : data(value) {}
    ~MyObject() {
        //std::cout << "MyObject destroyed" << std::endl;
    }
};

int main() {
    SimplePoolAllocator<MyObject> pool(10); // 创建一个可以容纳 10 个 MyObject 对象的内存池
    std::vector<MyObject*, SimplePoolAllocator<MyObject>> objects;
    objects.reserve(10);
    for (int i = 0; i < 10; ++i) {
        MyObject* obj = pool.allocate(1);
        pool.construct(obj, i);
        objects.push_back(obj);
    }
    for (MyObject* obj : objects) {
        std::cout << obj->data << " ";
    }
    std::cout << std::endl;

    // 释放内存
    for (MyObject* obj : objects) {
        pool.destroy(obj);
        pool.deallocate(obj, 1);
    }

    return 0;
}

代码解释:

1. SimplePoolAllocator: 内存池分配器，用于分配 MyObject 类型的对象。
2. pool_: 指向预先分配的内存块的指针。
3. free_list_: 指向空闲内存块链表的头部的指针。
4. allocate(size_type n): 从 free_list_ 中分配一个内存块，并更新 free_list_。
5. deallocate(pointer p, size_type n): 将 p 指向的内存块添加到 free_list_ 的头部。
6. 初始化 在构造函数中，我们创建一个链表，其中的每个节点都指向池中下一个可用的内存块。
7. construct 和 destroy 确保在分配和释放内存时正确地构造和析构对象。

4.3 内存池的改进:

• 线程安全: 使用互斥锁或其他同步机制来保护 free_list_，避免多线程环境下的竞争。
• 动态调整大小: 当内存池已满时，可以动态地增加内存池的大小。
• 支持不同大小的内存块: 可以使用不同的策略来管理不同大小的内存块，例如，使用多个内存池，每个内存池管理特定大小的内存块。
• 对齐: 考虑内存对齐以提升性能，尤其是在处理 SIMD 指令时。

4.4 PMR 和内存池的结合

可以将内存池实现为 memory_resource，并与 polymorphic_allocator 结合使用，从而实现更灵活的内存管理。

5. 其他优化策略

除了内存池之外，还有一些其他的优化策略可以用于提高内存分配器的性能：

• 延迟释放: 延迟释放可以减少频繁的内存分配和释放的开销。例如，可以使用一个延迟释放队列，将释放的内存块添加到队列中，然后在稍后的时间再真正释放这些内存块。
• 对象池: 对象池是一种特殊的内存池，它用于管理特定类型的对象。对象池可以预先创建一些对象，并将这些对象添加到池中。当需要使用对象时，可以从池中获取一个对象；当不再需要使用对象时，可以将对象返回到池中。
• 定制化分配策略: 根据应用程序的特点选择合适的内存分配策略。比如，对于生命周期短的对象，可以使用栈分配；对于生命周期长的对象，可以使用堆分配。

6. 代码示例：线程安全的内存池

以下是一个简单的线程安全的内存池实现：

#include <iostream>
#include <mutex>
#include <cassert>

template <typename T>
class ThreadSafePoolAllocator {
public:
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;
  using reference = T&;
  using const_reference = const T&;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;

  ThreadSafePoolAllocator(size_type pool_size) : pool_size_(pool_size) {
    chunk_size_ = sizeof(T);
    pool_ = new char[pool_size_ * chunk_size_];
    free_list_ = reinterpret_cast<T*>(pool_);
    T* current = free_list_;
    for (size_type i = 0; i < pool_size_ - 1; ++i) {
      current = reinterpret_cast<T*>(reinterpret_cast<char*>(current) + chunk_size_);
      reinterpret_cast<char**>(current)[0] = reinterpret_cast<char*>(free_list_) + (i+1) * chunk_size_;

    }
    current = reinterpret_cast<T*>(reinterpret_cast<char*>(current) + chunk_size_);
    reinterpret_cast<char**>(current)[0] = nullptr;
  }

  ~ThreadSafePoolAllocator() {
    delete[] pool_;
    pool_ = nullptr;
    free_list_ = nullptr;
  }

  [[nodiscard]] pointer allocate(size_type n) {
    if (n != 1) {
      throw std::bad_alloc(); // 简单实现只支持分配一个对象
    }

    std::lock_guard<std::mutex> lock(mutex_);
    if (!free_list_) {
      throw std::bad_alloc(); // 内存池已满
    }

    pointer p = free_list_;
    free_list_ = reinterpret_cast<T*>(reinterpret_cast<char**>(free_list_)[0]); // 更新 free_list_
    return p;
  }

  void deallocate(pointer p, size_type n) {
    if (n != 1) {
      return; // 简单实现只支持释放一个对象
    }

    std::lock_guard<std::mutex> lock(mutex_);
    // 将 p 添加到 free_list_ 的头部
    reinterpret_cast<char**>(p)[0] = reinterpret_cast<char*>(free_list_);
    free_list_ = p;
  }

  template <typename U, typename... Args>
  void construct(U* p, Args&&... args) {
    ::new (p) U(std::forward<Args>(args)...);
  }

  void destroy(pointer p) {
    p->~T();
  }

  template <typename U>
  bool operator==(const ThreadSafePoolAllocator<U>& other) const noexcept {
    return (pool_size_ == other.pool_size_);
  }

  template <typename U>
  bool operator!=(const ThreadSafePoolAllocator<U>& other) const noexcept {
    return !(*this == other);
  }

private:
  char* pool_;
  T* free_list_;
  size_type pool_size_;
  size_type chunk_size_;
  std::mutex mutex_;
};

int main() {
  ThreadSafePoolAllocator<int> pool(100);

  // 模拟多线程环境
  std::vector<std::thread> threads;
  for (int i = 0; i < 4; ++i) {
    threads.emplace_back([&pool]() {
      for (int j = 0; j < 25; ++j) {
        int* ptr = pool.allocate(1);
        pool.construct(ptr, j);
        std::cout << "Thread " << std::this_thread::get_id() << " allocated: " << *ptr << std::endl;
        pool.destroy(ptr);
        pool.deallocate(ptr, 1);
      }
    });
  }

  for (auto& thread : threads) {
    thread.join();
  }

  return 0;
}

这个例子中，我们使用 std::mutex 来保护 free_list_，从而保证多线程环境下的线程安全。

7. 选择合适的Allocator

选择合适的 allocator 需要考虑多个因素，包括：

因素	说明
性能要求	如果性能是关键，那么需要选择高性能的 allocator，例如内存池。
内存限制	如果内存有限制，那么需要选择内存利用率高的 allocator，例如紧凑型分配器。
线程安全性	如果是多线程环境，那么需要选择线程安全的 allocator。
代码复杂性	选择复杂度适当的 allocator，避免过度设计。
可维护性	选择易于维护和扩展的 allocator。
PMR 的应用场景	如果需要在运行时选择 allocator，或者需要简化容器的 allocator 管理，那么可以使用 PMR。

8. 总结：灵活的内存管理策略

自定义Allocator允许我们针对特定应用场景进行内存优化，通过Polymorphic Allocators可以在运行时动态选择分配器，而高性能池化策略则可以减少内存碎片并提升分配效率。 结合PMR与池化策略，可以构建出既灵活又高效的内存管理系统。

更多IT精英技术系列讲座，到智猿学院