SGI STL 分配器设计

此文档包含 2 个部分。第一部分讨论在 SGI STL 中实施默认分配器时做出的部分决策。这些决策既影响默认分配器的性能，也影响它在内存泄漏检测器中的表现。

第二部分介绍 SGI STL 分配器的原始设计。当前的 SGI STL 也支持 C++ 标准中的分配器接口。此处介绍的接口特定于 SGI STL，不能用于必须移植到其他 STL 实现的代码中。因此，现在不鼓励使用它。此讨论因历史原因得以保留，并且是因为它暴露出围绕标准接口的一些问题。

SGI 默认分配器

默认分配器alloc为小对象维护其自己的空闲列表。它使用底层系统提供的分配器来满足较大的请求，并获取可以细分小对象的大块内存。两个详细的设计决策已被证明是有争议的，在此进行解释。

`Alloc`从`malloc`

获取内存Malloc用作底层系统提供的分配器。这是一个小型的设计决策。::operator new获取内存也可以使用。用作底层系统提供的分配器。这是一个小型的设计决策。具有允许进行可预测且简单的故障检测的优势。

`Alloc`会使这变得更加复杂，因为存在可移植性和线程安全性约束，以及用户提供的 new 处理程序的可能性。`不会`释放

所有内存malloc为小对象块分配的内存不会返回到。它只能通过后续的alloc::allocatealloc（大约）相同大小的请求重新使用。因此，使用

的程序在由某些简单的泄漏检测器监视时可能会出现内存泄漏。这是有意的。此类“泄漏”不会随着时间推移而累积。此类“泄漏”不会由类似垃圾回收器的泄漏检测器报告。alloc的主要设计准则是不会使其不比 HP STL 每类分配器慢，但具有潜在线程安全性，并且显着降低碎片风险。它与 HP 分配器一样，它不维护执行小对象的完整块时所需的数据结构，其中没有包含的小对象正在使用。这是有意选择执行时间而不是空间使用。它可能不适用于所有程序。在许多系统中malloc_alloc

可能是更节省空间的，并且在至关重要的情况下可以使用它。不会通常必须在操作系统收回它们之前触摸许多长时间未引用的页面。这通常会导致程序退出时延迟很长时间，并且可能会分页出其他应用程序的大部分内容。此操作没有任何好处，因为操作系统通常会在程序退出时回收内存，而且应该在不触碰该内存的情况下回收内存。

一般情况下，我们建议使用小对象的完整块时所需的数据结构，其中没有包含的小对象正在使用。这是有意选择执行时间而不是空间使用。它可能不适用于所有程序。在许多系统中而不是alloc运行泄漏检测测试。这样会产生更精确的结果，同时提供基于 GC 的检测器（例如Pure Atria 的 Purify），并提供可用于计算分配和解除分配次数的检测器的有用结果。

未尝试对空闲列表进行排序

默认分配器不会做出任何特殊尝试以确保连续分配的对象“靠近”彼此，即共享缓存行或页面。解除分配请求将对象添加到空闲列表的头部，并且分配将移除适当大小的最后一个解除分配的对象。因此，分配和解除分配每个至少需要一条指令。

对于小应用程序而言，这似乎能很好地调整到缓存中。对于连续解除分配连续分配的对象的常规应用程序来说，这也是一项很好的操作。对于此类应用程序，空闲列表往往会保持大致按地址顺序。但是毫无疑问，对于需要投入一些精力对空闲列表进行近似排序的应用程序，可以在提高缓存性能方面得到回报。

原始 SGI STL 分配器接口

SGI 特定的分配器接口远远比 HP STL 或 C++ 标准中的接口简单。此处我们概述了设计此接口的考虑因素。

SGI STL 分配器包含一个类，其中包含 3 个必需的成员函数，所有这些函数均为static:

void * allocate(size_t n): 分配具有指定大小（以字节为单位）的对象。对象必须对请求的大小足够对齐。
void deallocate(void *p, size_t n): 解除分配对象 p，该对象必须使用相同分配器分配，并且请求的大小为n.
void * reallocate(void *p, size_t old_sz, size_t new_sz): 调整对象 p（之前分配为包含 old_sz 字节）的大小，使它现在包含 new_sz 字节。返回指向 resulting 对象（大小为 new_sz）的指针。这些函数要么返回 p（在对原位对象适当调整后），要么将从 old object 复制 min(old_sz, new_sz) 字节到新分配的对象中，解除 old object 的分配，并返回指向该 new object 的指针。请注意，复制是按照位进行的；如果对象有用户定义的 copy 构造函数或析构函数，通常不适合这样做。完全通用的容器实现通常不使用 reallocate；然而，对于某些容器特化而言，这可能是一种性能增强。

下面讨论此简单设计背后的设计决策

分配器不是模板

我们的分配器以与 C 的malloc知道对象最终类型的任何信息。这意味着分配器的实现者不需要担心类型；分配器只需处理字节。我们提供了simple_alloc适配器将基于字节的分配器转换为分配 T 类型的 n 个对象的分配器。忽略类型的分配器具有容器不需要模板模板参数或标准中的“rebind”机制的优势。

代价是确实需要类型信息的分配器（例如，用于垃圾收集）变得有些难以实现。可以通过对进行专门化来有限地处理此问题simple_alloc.

(实际上，STL 标准分配器借助模板实现。但主要这样做是为了可以容易地将它们作为 .h 文件分发。)

分配器不封装指针类型

(在很大程度上与 SGI 标准分配器共享。该标准允许分配器封装指针类型，但不保证标准容器与使用非标准指针类型的分配器配合使用时有效。）不同于 HP STL，我们的分配器不尝试允许使用不同的指针类型。它们仅在标准 void * 指针中进行通信。放弃 HP 方法的原因有以下几个

在没有明确的编译器支持的情况下，实际上无法在 C++ 中定义指针的备用概念。这样做的要求还包括定义相应的“引用”类型。但是，没有任何类表现得像引用。只能对引用应用“.” 字段选择操作。当使用代理引用类型进行实例化时，期望 T& 的模板函数（例如 max）通常不起作用。甚至代理指针类型也存在问题。构造函数需要一个真正的 this 指针，而不是代理。
现有的 STL 数据结构通常不应在需要完全不同的指针概念的环境中使用，例如对于基于磁盘的数据结构。基于磁盘的集合或映射将需要一个更了解局部性问题的数据结构。该实现或许还必须处理两种不同的指针类型：指向分配的内存暂存区的实际指针和指向基于磁盘的对象的引用。因此，即便是封装指针类型的 HP STL 概念也可能不够用。
这会留下编译器支持大小不同的指针（例如 DOS/win16 “far” 指针）。对于通用库来说，这些似乎不再有太大用处了。Win32 不再进行此类区分。我们所了解的其他任何现代（即 32 或 64 位指针）环境也不再进行此类区分。此问题很可能有继续影响低端嵌入式系统，但无论如何，这些系统通常需要一些非标准的编程环境。此外，上面提到的同样的模板实例化问题也适用。

没有任何分配器对象

分配器的行为完全由其类型决定。分配器的所有数据成员都是静态的。

这意味着容器无需分配器成员来从正确的源分配内存。这避免了不必要的空间开销和/或容器代码中的复杂性。

它还避免了关于涉及多个容器的操作中内存分配的大量棘手问题。例如，否则将不清楚使用两个不同的分配器构建的绳索连接是否应该是可接受的，如果是，应该为结果使用哪个分配器。

这有时是一个重要的限制。例如，通过向容器构造函数传递不同的分配器实例，无法安排不同的容器分配映射到不同文件的内存。相反，必须使用以下备选方案之一

必须用不同的分配器实例化容器类，每个文件一个。这会导致不同的容器类型。这强制可能映射到不同文件的容器具有不同的类型，这可能会成为一个麻烦的限制，尽管它也导致对错误的编译时检测，而这些错误可能难以诊断。
可以通过单个分配器实例化容器，该分配器可以通过调用附加成员函数重定向到不同的文件。在可能分配的容器调用之前，必须将分配器适当地重定向。

分配器分配各个对象

（与标准分配器共享）某些 C++ 编程文本建议各个类保留频繁分配的各类对象的释放列表，以便大多数分配请求都能从该类各自的释放列表中得到满足。当分配请求遇到一个空的释放列表时，将调用一个潜在的较慢的分配器（例如 new 或 malloc）一次分配几个必需的对象，然后用这些对象来补充释放列表。

HP STL 就是沿着这些思路设计的。分配器被用作较慢的备用分配器。诸如 list之类的容器被假定为维护自己的释放列表。

根据一些小实验，这在直接为单个对象调用 allocate 函数方面没有性能优势。事实上，生成的代码基本上是相同的。我们提供的默认分配器很容易内联。因此，任何调用开销都被消除了。如果对象大小是静态已知的（在这种情况下，可以假定按类释放列表可能有所帮助），则还可以由编译器确定释放列表标头的地址。

然而，按类释放列表有很多缺点

它们引入了碎片。类 A 的释放列表中的内存不能被另一个类 B 重用，即使只为剩余的程序执行分配类 B 对象。如果这里有许多模板类的实例而不是一个类 A，而每个模板类都有自己的释放列表，这将尤其令人遗憾。
它们使得构建线程安全容器变得更加困难。维护自己的独立列表的类必须确保在不同容器内由不同线程进行的分配不会相互干扰。这通常意味着每个类都必须知道底层同步机制。如果分配器分配各个对象，则只有分配器本身需要解决此问题，而大多数容器实现可以独立于线程机制。
垃圾回收分配器很难适应。垃圾回收器会将基于类的独立列表视为可访问的内存。如果这些独立对象的指针没有明确清除，则它们引用的所有内容也将被回收器保留，从而降低了回收器的效率，有时会严重降低。

释放需要大小参数

我们选择要求显式的大小参数，对于释放，以及描述对象的原始大小，在重新分配调用。这意味着不需要隐藏每个对象的开销空间；小对象只使用客户端显式请求的空间。因此，即使不出现碎片，空间使用量与基于类的分配器相同。

这种选择还去除了一些特殊情况中的时间开销，即固定大小分配。在这种情况下，对象的大小，以及独立列表头的地址，变成明确的可识别的编译时常量。因此，生成代码应该与基于类独立列表分配器需要的代码相同，即使类只需要单个大小的对象也是如此。

我们在接口中包含了 realloc 样式的重新分配

这可能是最令人质疑的设计决策。提供

reallocate 的版本可能更有用，该版本在不复制的情况下更改现有对象的大小或返回 NULL。这会让它直接对带有复制构造函数的对象有用。当原始对象尚未完全填充时，这也避免了不必要复制。

不幸的是，这会禁止使用realloc来自 C 库。这反过来会给许多分配器实现增加复杂度，并会使得与内存调试工具的交互更加困难。因此我们决定不采用这种选择。

实际版本的重新分配对于特定元素类型的容器专业化仍然非常有用。STL 实现开始利用它。