« 上一章：10.1. 技术要求 下一章：10.3. 动态参数变化处理 »
返回目录

10.2. 内存池管理机制

基于内存池(arena-based)内存管理背后的思想是在程序中一个已知的时刻分配一块内存，并将其作为一个“小型的、个性化的堆”来管理，其管理策略基于对当前情境或问题领域的了解，从而从中获益。

这一思想有许多变体，包括以下几种常见情况：

解释基于内存池分配如何工作的最好方式，或许就是编写一个使用该机制的示例程序，以展示其功能及其带来的优势。我们将编写一段代码，使其可以使用标准库提供的内存分配函数，也可以使用自己的专用实现 —— 具体取决于是否定义了某个宏。当然，还会对内存分配和释放的代码进行性能测量，以判断我们的努力是否真的带来了收益。

10.2.1 具体示例 —— 基于大小的实现

假设正在开发一款视频游戏，游戏的高潮是一场壮观的决战，兽人(Orcs)和精灵(Elves)在其中展开激烈交锋。没有人真正记得这两个族群为何互相憎恨，但有种传言说：有一天，一个精灵对一个兽人说道：“你知道吗，你今天的气味其实没那么糟糕！”这个兽人被这句话深深地侮辱了，于是引发了一场延续至今的世仇。当然，这只是个传言罢了。

无论如何，在这款游戏中，我们对使用兽人类(Orc)的代码行为有一些已知信息，具体如下：

这两个特性为我们打开了算法上的新选择：

为了说明这个问题，我们用一个 Orc 类作为示例，它包含三个数据成员：name(类型为 char[4]，因为这些怪物词汇量有限);strength(类型为 int);smell(类型为 double，这些家伙毕竟“[臭]名昭著”)。

class Orc {
  char name[4]{ 'U', 'R', 'G' };
  int strength = 100;
  double smell = 1000.0;
public:
  static constexpr int NB_MAX = 1'000'000;
  // ...
};

我们将为 Orc 对象使用一些任意的默认值，本例中只关注内存的分配与释放。当然，也可以编写更复杂的测试代码来使用非默认值。

既然正在讨论通过基于大小的内存池(size-based arena)一次性分配一大块内存，就需要关注 Orc 对象的内存占用情况。假设 sizeof(int) == 4，sizeof(double) == 8，并假设作为基本类型，对齐要求(alignment requirements)等于各自的大小，那么可以认为在此情况下 sizeof(Orc) == 16。

如果打算一次性分配足够的空间来存放所有 Orc 对象，需要确保 sizeof(Orc) 在可用的资源范围内合理，这一点非常重要。例如，定义程序中 Orc 对象的最大数量为 Orc::NB_MAX，并且定义一次性为 Orc 对象分配的最大内存为一个假设的常量 THRESHOLD，可以在源码中添加如下形式的 static_assert，作为对约束条件是否被满足的一种检查手段：

static_assert(Orc::NB_MAX*sizeof(Orc) <= THRESHOLD);

这样，最终将Orc类演化到资源成为问题的程度，代码将停止编译，将能够重新评估情况。以目前约16 MB的内存消耗为例，可以假设仍在预算范围内，可以继续使用自定义内存池。

我们需要将基于内存池的实现与基准实现进行比较，这里基准实现是指标准库提供的内存分配函数。不同标准库对这些函数的实现各不相同，最好在多个标准库实现上运行代码，以便更全面地评估技术的影响。

为了进行有效对比，需要两个独立可执行文件，这是非此即彼的选择(要么使用标准版本，要么使用我们编写的自定义版本)。基于宏的条件编译非常适合这种场景。我们将编写一组源码文件，根据条件替换标准库提供的分配操作符，其余部分则保持基本一致。

这里将使用三个文件：

当然，与大多数微基准测试一样，这些数据需谨慎看待：实际程序中分配操作与其他代码交织，结果会有所不同。但至少对两种分配操作符实现应用了相同的测试，因此比较结果应相对公平。

声明Orc类

首先，来看 Orc.h，之前在展示 Orc 类的数据成员布局时已经部分了解过：

#ifndef ORC_H
#define ORC_H

// #define HOMEMADE_VERSION

#include <cstddef>
#include <new>

class Orc {
  char name[4]{ 'U', 'R', 'G' };
  int strength = 100;
  double smell = 1000.0;

public:
  static constexpr int NB_MAX = 1'000'000;

#ifdef HOMEMADE_VERSION
  void * operator new(std::size_t);
  void * operator new[](std::size_t);
  void operator delete(void *) noexcept;
  void operator delete[](void *) noexcept;
#endif
};

#endif

其中的 HOMEMADE_VERSION 宏可以取消注释，以启用我们自己实现的内存分配函数版本。

既然我们是针对 Orc 类及其预期的使用模式应用了一种特殊的策略，在这里使用的是对该类内存分配操作符的成员函数重载形式。(我们不会以同样的方式对待 int 对象，或者更甚者 —— 精灵(Elves)吧？我想不会。)

定义Orc类并实现内存池

使用 char* 还是 Orc*？

Tribe 的实现中使用了 char* 类型作为 p 和 cur 指针的类型，但其实使用 Orc* 也是一个合理的选择。只需要记住一点：就 Tribe 对象而言，内存池中并不存在真正的 Orc 对象，使用 Orc* 类型只不过是一个方便的“谎言”，用来简化指针算术操作。

这种修改所带来的变化包括：

  • 在构造函数中，将 static_cast 替换为 static_cast；

  • 在 allocate() 成员函数的实现中，将 cur += sizeof(Orc) 替换为 ++cur。

这基本上只是风格和偏好的问题。

我们基于大小的内存池实现之所以能从我们对使用模式的先验知识中获益，方式如下：

代码如下所示：

#include "Orc.h"

#ifdef HOMEMADE_VERSION

#include <cassert>
#include <cstdlib>
#include <mutex>

class Tribe {
  std::mutex m;
  char *p, *cur;

  Tribe() : p{ static_cast<char*>(
    std::malloc(Orc::NB_MAX * sizeof(Orc))
  ) } {
    assert(p);
    cur = p;
  }

  Tribe(const Tribe&) = delete;
  Tribe& operator=(const Tribe&) = delete;

public:
  ~Tribe() {
    std::free(p);
  }

  static auto &get() {
    static Tribe singleton;
    return singleton;
  }

  void * allocate() {
    std::lock_guard _ { m };
    auto q = cur;
    cur += sizeof(Orc);
    return q;
  }

  void deallocate(void *) noexcept {
  }
};

// ...

这些内存分配条件已经非常接近最优状态，但在实际应用中，这种情况出现的频率往往出乎我们的想象。一个类似高效的使用模式是模拟一个栈(最后分配的内存块最先被释放)，而在日常编写使用局部变量的代码时，其实就无意中利用了一个常常是最优的底层内存使用模式。

接下来我们来看重载的内存分配操作符。为了保持实现的简洁性，假设不会分配 Orc 对象数组，但可以进一步完善实现以支持数组(这并不是一个困难的任务，只是编写相关的测试代码会更复杂一些)。这些函数的作用是将内存分配工作委托给底层的内存池(arena)，并且它们仅用于 Orc 类(这一点存在一个例外情况，将在本章稍后的“当参数改变时”一节中讨论)，这些函数的实现非常简单：

// ...
void * Orc::operator new(std::size_t) {
  return Tribe::get().allocate();
}

void * Orc::operator new[](std::size_t) {
  assert(false);
}

void Orc::operator delete(void *p) noexcept {
  Tribe::get().deallocate(p);
}

void Orc::operator delete[](void *) noexcept {
  assert(false);
}

#endif // HOMEMADE_VERSION

测试实现

接下来将要使用的测试代码实现。该程序将包含一个名为 test() 的微基准测试函数和一个 main() 函数，将分别查看它们的实现。

test() 函数接受一个非 void 类型的函数 f()，以及一个可变参数包 args，然后调用 f(args...)，并确保在调用中使用完美转发(perfect forwarding)，以保证参数按照原始调用中的语义进行传递。会在调用 f() 前后读取一次时钟，然后返回一个由 f(args...) 的执行结果和该次调用所耗费的时间组成的 pair。我在代码中使用了 high_resolution_clock译者注：在实际编程中，不推荐直接使用high_resolution_clock，会更推荐使用steady_clock。具体原因，读者们可自行查阅资料。，使用 system_clock 或 steady_clock 也是有合理的理由：

#include <chrono>
#include <utility>

template <class F, class ... Args>
auto test(F f, Args &&... args) {
  using namespace std;
  using namespace std::chrono;

  auto pre = high_resolution_clock::now();
  auto res = f(std::forward<Args>(args)...);
  auto post = high_resolution_clock::now();

  return pair{ res, post - pre };
}
// ...

为什么我们要限定只能使用非 void 函数，并返回 f(args...) 的执行结果？即使在某些情况下，这个返回值可能是人为构造的。这样做的目的是确保编译器认为 f(args...) 的结果是有用的，从而不会将该调用优化掉。编译器非常聪明，可以根据所谓的“as-if 规则”(as-if rule)移除看起来无用的代码(简单来说，如果没有可见的副作用，编译器就可以直接把它删掉！)。

对于测试程序本身，需要注意以下几个关键点：

下面是测试代码的实现：

// ...
#include "Orc.h"
#include <print>
#include <vector>

int main() {
  using namespace std;
  using namespace std::chrono;

#ifdef HOMEMADE_VERSION
  print("HOMEMADE VERSION\n");
#else
  print("STANDARD LIBRARY VERSION\n");
#endif

  vector<Orc*> orcs;
  auto [r0, dt0] = test([&orcs] {
    for(int i = 0; i != Orc::NB_MAX; ++i)
      orcs.push_back(new Orc);
    return size(orcs);
  });

  // ...
  // CARNAGE (CENSORED)
  // ...

  auto [r1, dt1] = test([&orcs] {
    for(auto p : orcs)
      delete p;
    return size(orcs);
  });

  print("Construction: {} orcs in {}\n",
    size(orcs), duration_cast<microseconds>(dt0));

  print("Destruction: {} orcs in {}\n",
    size(orcs), duration_cast<microseconds>(dt1));
}

此时，你可能会怀疑：这样做是否值得？毕竟，标准库实现很可能已经非常高效。要判断这种优化是否值得，唯一的方法就是运行测试代码，亲自看一看结果。

观察测试数据

我在一个在线的 GCC 15 编译器环境中，使用 -O2 优化级别，运行了两次该测试代码：一次使用标准库的内存分配方式，另一次使用我们自己实现的基于内存池的版本(使用 Meyers 单例)。

对于 Orc::NB_MAX(此处为 $10^6$)次 new 和 delete 操作的调用，我得到了如下数据(单位为微秒 µs)：

自制的
N=$10^6$ 标准库 Meyers 单例
operator new() 23433μs 17906μs
operator delete() 7943μs 638μs
表 10.1 —— 使用 Meyers 单例实现的速度对比

当然，实际的数值会因各种因素而有所不同，但真正值得关注的是比例关系：我们自己实现的 operator new() 所花费的时间仅占标准库版本的 76.4%，而我们自己实现的 operator delete() 所花费的时间仅占基准版本的 8.03%。

这是一个相当令人满意的结果，但其实并不令人意外：我们执行的是常数时间复杂度的分配，以及几乎为零的释放成本。虽然每次分配时我们确实会加锁和解锁一个 std::mutex 对象，但大多数标准库实现的互斥锁(mutex)在预期低竞争(low contention)的情况下都非常高效。而我们程序中的分配和释放操作是单线程的，根本不存在竞争，代码运行得非常顺畅。

不过，可能有聪明的读者对“释放操作并没有像预期那样快”感到疑惑。毕竟我们调用的是一个空函数，那是什么占用了 CPU 时间呢？答案是……我们的单例(singleton)机制，更确切地说，是访问 Meyers 实现中使用的静态局部变量所引入的开销。

还记得第 8 章中提到的这种技术吗？旨在确保单例在需要时才创建，而静态局部变量在其所在函数第一次调用时才会构造。

C++ 中的“魔法静态变量”(magic statics)机制会通过同步机制保护静态局部对象的构造过程，以确保对象只构造一次。虽然这种同步机制非常高效，但它并不免费。在我们当前的场景中，如果能保证在 main() 函数运行之前，没有其他全局对象会调用 Tribe::get()，就可以用一种更传统的实现方式替代 Meyers 技术：即将单例实现为 Tribe 类的一个静态数据成员，该成员在类的作用域内声明，并在全局作用域中定义：

// ...
// “全局”单例的实现(其余代码保持不变)
class Tribe {
  std::mutex m;
  char *p, *cur;

  Tribe() : p{ static_cast<char*>(
    std::malloc(Orc::NB_MAX * sizeof(Orc))
  ) } {
    assert(p);
    cur = p;
  }

  Tribe(const Tribe&) = delete;
  Tribe& operator=(const Tribe&) = delete;

  static Tribe singleton;

public:
  ~Tribe() {
    std::free(p);
  }

  static auto &get() {
    return singleton;
  }

  void * allocate() {
    std::lock_guard _ { m };
    auto q = cur;
    cur += sizeof(Orc);
    return q;
  }

  void deallocate(void *) noexcept {
  }
};

// 在.cpp文件的某个地方，使用#ifdef HOMEMADE_VERSION和#endif块包围
Tribe Tribe::singleton;
// ...

将单例对象的定义从函数内部移出，放置在全局作用域中，可以消除对其构造函数调用时所需的同步机制。这样一来，就可以将这种实现方式与之前的版本进行对比，从而评估其开销以及可能带来的性能提升(如果有的话)。

在使用相同测试环境的前提下，我们将“全局单例”版本加入到对比实现集合中，得到如下结果：

N=$10^6$ 自制的
标准库 Meyers单例 全局单例
Operator new() 23433μs 17906μs 17573μs
Operator delete() 7943μs 638μs 0μs

现在，这才更接近理想的结果！

现在调用 operator new() 的速度比使用标准库版本时快了 74.99%(即仅需标准库版本 25.01% 的时间)，比使用 Meyers 单例版本时也快了 98.14%。而调用 operator delete() 现在几乎变成了一个空操作(no-op)，很难再做得更好了！

这样做值得吗？当然，这取决于具体需求。速度是一个重要因素：在某些程序中，这种速度提升可能是必要的；但在另一些程序中，可能无关紧要。此外，内存碎片的减少在某些应用中也能带来显著差异，有些开发者正是出于这个原因而使用内存池(arena)。关键在于：如果确实需要进行这类优化，现在已经知道该如何实现了。

10.2.2 泛化为 SizeBasedArena<T,N>

尽管目前编写的 Tribe 类看起来是专属于 Orc 类的，但它只是专属于大小与 Orc 相同的对象。因为该类从未调用过 Orc 类的任何成员函数，也没有构造或析构任何一个 Orc 对象，所以可以将这个类改造成一个泛型类，以便在其他具有相似使用约束的类型上复用。

为了实现这一点，需要将内存池(arena)的代码从 Orc 类中解耦出来，并将其放入一个独立的文件中。例如，可以将其命名为 SizeBasedArena.h：

#ifndef SIZE_BASED_ARENA_H
#define SIZE_BASED_ARENA_H

#include <cassert>
#include <cstdlib>
#include <mutex>

template <class T, std::size_t N>
class SizeBasedArena {
  std::mutex m;
  char *p, *cur;

  SizeBasedArena() : p{ static_cast<char*>(
    std::malloc(N * sizeof(T))
  ) } {
    assert(p);
    cur = p;
  }

  SizeBasedArena(const SizeBasedArena&) = delete;
  SizeBasedArena&
  operator=(const SizeBasedArena&) = delete;

public:
  ~SizeBasedArena() {
    std::free(p);
  }

  static auto &get() {
    static SizeBasedArena singleton;
    return singleton;
  }

  void * allocate_one() {
    std::lock_guard _ { m };
    auto q = cur;
    cur += sizeof(T);
    return q;
  }

  void * allocate_n(std::size_t n) {
    std::lock_guard _ { m };
    auto q = cur;
    cur += n * sizeof(T);
    return q;
  }

  void deallocate_one(void *) noexcept {
  }

  void deallocate_n(void *) noexcept {
  }
};
#endif

我们为什么使用 T 和 N 作为模板参数。如果并不在内存池(arena)中使用类型 T，那为什么还要用，而不是用一个以 sizeof(T) 初始化的整数类型参数呢？

原因在于：假设 Elf 类(例如)也使用了基于大小的内存池，并且如果不够幸运地遇到 sizeof(Orc) == sizeof(Elf) 的情况，如果仅根据类型的大小来区分内存池，并且它们各自的模板参数 N 又相同的话，就可能导致 Orc 和 Elf 错误地共用同一个内存池……这是我们(以及它们)绝对不希望看到的情况！

为了在这个泛型示例中简化单例的初始化，我们又回到了 Meyers 技术。在编写泛型代码时，比起编写特定于 Orc 的代码，更难保证全局对象在构造时没有相互依赖关系。因为泛型代码的引入，大大扩展了其潜在的使用范围。

现在 Orc.cpp 中的实现大致如下所示：

#include "Orc.h"
#ifdef HOMEMADE_VERSION
#include "SizeBasedArena.h"

using Tribe = SizeBasedArena<Orc, Orc::NB_MAX>;

void * Orc::operator new(std::size_t) {
  return Tribe::get().allocate_one();
}

void * Orc::operator new[](std::size_t n) {
  return Tribe::get().allocate_n(n / sizeof(Orc));
}

void Orc::operator delete(void *p) noexcept {
  Tribe::get().deallocate_one(p);
}

void Orc::operator delete[](void *p) noexcept {
  Tribe::get().deallocate_n(p);
}
#endif

由于SizeBasedArena<T,N>实现了针对单个对象或对象数组的内存分配函数，我们已将Orc类的成员函数分配操作符重载扩展至operator new[]()和operator delete[]()。

返回目录
« 上一章：10.1. 技术要求 下一章：10.3. 动态参数变化处理 »