概述
数据结构：16维自由链表和内存池（内存池有_S_start_free和_S_end_free两个指针来控制内存池）
使用了这个数据结构，空间配置器解决的是外部碎片的问题
allocate
有两个分支，第一个是一级空间配置器，使用malloc（有一个宏，编译的时候带上就会走一级），但是一般默认走二级空间配置器
二级空间配置器当申请空间大于128B时，还是malloc，当小于128B时，用16维的自由链表和内存池来管理，函数如下
allocate()
- 如果对应自由链表下有内存块，直接从链头取走一块
- 如果没有的话就需要分配内存，实际上调用的是_S_refill()
- _S_refill()首先调用_S_chunk_alloc()去分配空间
- 首先计算需要放到自由链表上的空间大小，为n*20（total_bytes），_S_chunk_alloc()会查看当前内存池的是否有之前malloc存下来的空间
- 如果内存池中的内存大于这个需要放到自由链表的大小时，会直接返回所需的内存，然后内存池相应减少
- 如果内存池中的内存小于这个需要放到自由链表的大小时且大于所需申请的空间n时，会将尽可能多的内存（n的整数倍）返回，然后内存池相应减少
- 如果内存池中的内存小于所需申请的空间n时，这个时候会申请大约两倍的total_bytes，
- 申请成功，一分为二，一半作为返回值返回，一半用两个指针进行控制
- 申请失败，即内存池中和堆中都没有n这么大的连续的内存了，所以会在自由链表向上（后）遍历，也就是找比n更大的块，当找到时则将n大小内存返回，剩下的一点点用两个指针进行控制，也就是放到内存池中
- 首先计算需要放到自由链表上的空间大小，为n*20（total_bytes），_S_chunk_alloc()会查看当前内存池的是否有之前malloc存下来的空间
- 接下来就是将返回的内存进行切割并等分，将其挂在对应的自由链表下，然后将一块内存块返回，申请成功（当然如果是堆空间和内存池中没有内存的情况下，只会返回一块n大小内存块，此时直接返回即可，不用切割了）
- _S_refill()首先调用_S_chunk_alloc()去分配空间
- 最后返回了一块内存块，即申请成功
_S_round_up()
向上取整，得到8的整数倍，如32则返回32，如33则返回40
_S_freelist_index()
取16维自由链表中的下标的函数，如申请32，则返回3，配合_S_round_up使用
_S_refill()
_S_chunk_alloc()
deallocate
- 如果是大于128的话就会free
- 如果是小于128字节的话，就会将内存块头插法插到对应的自由链表
construct
就是用定位new表达式，在指定的空间下构建对象
destroy
调用指定空间下对象的析构函数
补充
1.为什么需要空间配置器，以及它现在是否还在使用
## 1. 这套设计现在还在沿用吗？
这篇笔记讲的是早期 SGI STL allocator 的经典实现：
1. 一级空间配置器：大块内存直接走 `malloc/free`。
2. 二级空间配置器：小块内存使用 `16 个自由链表 + 内存池` 管理。
其中二级空间配置器的规则是：
```text
> 128B 走一级空间配置器，也就是 malloc/free
<= 128B 走二级空间配置器，也就是自由链表 + 内存池这套具体实现现在不一定是现代 C++ 标准库默认 std::allocator 的实现方式。现代主流标准库中的 std::allocator 通常更像是对全局 operator new/operator delete 的薄封装，底层具体分配策略交给系统或运行时内存分配器。
但是，它背后的思想仍然非常重要：
小块内存不要每次都直接 malloc/free，
而是按大小分类，批量申请，缓存起来，释放后复用。现代很多内存分配器仍然使用类似思想，例如：
jemalloctcmallocmimalloc- glibc malloc 的 tcache
- Windows Low Fragmentation Heap
- Linux 内核中的 slab/slub allocator
- 游戏引擎里的 object pool / arena allocator
- C++17 的
std::pmr
所以可以这样理解：
SGI STL 二级空间配置器这套具体代码偏历史经典，但它体现出来的小对象池化、自由链表、按大小分类、批量申请、复用内存块的思想，在现代内存分配器中仍然非常常见。
2. 为什么要设计空间配置器？
STL 容器经常需要动态申请和释放内存。
例如 std::list 每插入一个节点，可能都需要申请一个节点空间。如果每次都直接调用 malloc，释放时再直接调用 free，会带来几个问题。
2.1 减少频繁 malloc/free 的开销
malloc/free 不是零成本操作。它们需要维护堆上的元数据，比如哪些块空闲、哪些块已使用、空闲块是否合并、是否需要向系统申请更多内存等。
二级空间配置器的做法是：
第一次申请 32B 时，不只申请 32B，
而是一次申请多个 32B 块，通常默认尝试取 20 个。
给用户 1 个，剩下的挂到对应自由链表。
下次再申请 32B 时，直接从自由链表取。这样可以减少底层 malloc/free 的调用次数。
2.2 缓解小块内存造成的外部碎片
如果一直在堆上申请和释放各种小块内存，堆可能变得很零散：
[已用][空闲8B][已用][空闲16B][已用][空闲24B][已用]虽然空闲空间总量可能不少，但因为它们不连续，后续可能很难满足较大的连续内存申请。这就是外部碎片问题。
SGI STL 二级空间配置器把小块内存按照固定规格管理：
8B, 16B, 24B, 32B, 40B, 48B, 56B, 64B,
72B, 80B, 88B, 96B, 104B, 112B, 120B, 128B释放后的 32B 块会回到 32B 自由链表，之后再申请 32B 左右的空间时可以直接复用。
不过它也会带来一定内部碎片。例如申请 33B 时，实际会向上对齐到 40B，多出来的 7B 就是内部碎片。
2.3 提高小对象分配速度
从自由链表中取一个节点非常快。
例如：
_S_free_list[3] -> A -> B -> C申请 32B 时，只需要取下链表头节点 A，然后把头指针改成 B：
返回 A
_S_free_list[3] -> B -> C释放时也是头插法：
释放 X
_S_free_list[3] -> X -> B -> C这本质上只是几次指针操作，比通用 malloc/free 更轻量。
3. 为什么要设计成“两级”？
因为小块内存和大块内存适合不同策略。
小块内存的特点是：
数量多、申请频繁、释放频繁、大小有限、管理开销占比高所以适合使用：
自由链表 + 内存池大块内存则不适合统一放入这种固定自由链表中管理。因为大块内存规格更多，占用空间大，复用概率不一定高，如果也强行池化，可能造成更多浪费和管理复杂度。
所以 SGI STL 的策略是：
小于等于 128B：二级空间配置器管理
大于 128B：直接交给一级空间配置器，也就是 malloc/free这是一种性能和空间利用率之间的折中。
4. 是否有更好的方式？
有，但没有一种 allocator 在所有场景下都是最优的。现代通常会根据场景选择不同策略。
4.1 普通业务代码：默认 allocator 通常够用
如果只是普通使用 STL 容器，一般不需要自己手写 allocator。现代底层 malloc/new 已经做了很多优化，例如小对象缓存、线程本地缓存、按大小分类、碎片控制等。
4.2 高频固定大小对象：对象池更合适
如果程序中有大量固定大小对象反复创建和销毁，例如链表节点、树节点、网络包对象、游戏中的子弹和粒子对象，可以使用 object pool。
对象池的思想和二级空间配置器很像：
一次申请一大块内存，切成固定大小对象，
不用时放入空闲链表，需要时再取出复用。4.3 生命周期统一的对象：arena / monotonic allocator 更好
如果一批对象一起创建、一起销毁，例如一次 HTTP 请求中的临时对象、编译器中的 AST 节点、一次 SQL 查询中的临时数据，可以使用 arena allocator 或 monotonic allocator。
这种方式的特点是：
只申请，不单独释放；
最后整个 arena 一次性释放。C++17 中可以使用：
std::pmr::monotonic_buffer_resource它的单次分配通常非常快，接近于移动一个指针。但缺点是不能单独释放某个对象，要求对象生命周期比较统一。
4.4 高并发服务：现代通用分配器可能更好
如果是高并发服务端程序，内存分配压力很大，可以考虑使用：
jemalloctcmallocmimalloc
这些现代分配器一般具有更好的多线程优化，例如 thread cache、per-thread arena、central free list、size class 和低锁竞争设计。
它们可以看作是 SGI STL 二级空间配置器思想的现代增强版。
5. 面试回答总结
如果面试中被问到 STL allocator 或 SGI STL 空间配置器，可以这样回答：
SGI STL 的 allocator 使用两级空间配置器。一级空间配置器直接封装
malloc/free，用于大于 128 字节的内存；二级空间配置器用于小于等于 128 字节的小块内存，它维护 16 个按 8 字节对齐的自由链表，并通过内存池批量申请内存。申请小块内存时，先根据大小找到对应自由链表，如果链表中有空闲块，就直接从链表头取出；如果没有，就调用_S_refill，由_S_chunk_alloc从内存池中取出一大块空间，切分成多个相同大小的小块，第一块返回给用户，其余挂入自由链表。释放小块内存时，不直接free，而是头插回对应自由链表以供下次复用。这样可以减少频繁malloc/free的开销，提高小对象分配速度，并缓解小块内存造成的外部碎片问题。
这套具体实现现在不一定是现代标准库默认 allocator 的实现方式，但它的思想仍然广泛存在于现代内存分配器中，例如
jemalloc、tcmalloc、mimalloc、对象池、slab allocator 和 C++17 的std::pmr。如果没有明确性能瓶颈，普通代码使用默认 allocator 即可；如果有大量固定大小小对象，可以使用对象池；如果对象生命周期统一，可以使用 arena 或std::pmr::monotonic_buffer_resource；如果是高并发服务，可以考虑现代通用分配器。
6. 最核心的理解
这篇笔记不要只记成：
16 个自由链表 + 内存池更应该理解成：
这是针对“小块内存频繁分配和释放”的优化策略。它真正有价值的思想是：
不要每次都向系统申请内存；
先从自己的缓存池里找；
没有再批量申请；
释放时也先放回缓存池；
下次继续复用。代码
//第一个分支：底层直接会走malloc申请空间
//一级空间配置器
//第二个分支（默认的空间配置器）：二级空间配置器
static void* allocate(size_t __n)
{
if (__n > 128)
{
//底层还是会走malloc申请空间
}
else
{
//16维的自由链表 + 内存池
//为何这么设计，原因如下：
//1、防止多次申请空间导致的内存碎片问题
//2、如果申请的空间比较频繁的话，会在内核态与用户态之间进行频繁的切换，效率就不高
}
}
# ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
template <int __inst>
class __malloc_alloc_template
{
public:
static void* allocate(size_t __n)
{
void* __result = malloc(__n);
if (nullptr == __result)
__result = _S_oom_malloc(__n);//oom = out of memory
return __result;
}
static void deallocate(void* __p, size_t /* __n */)
{
free(__p);
}
};
#else
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
template <bool threads, int inst>
class __default_alloc_template {
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
static _Obj* _S_free_list[];
# else
static _Obj* _S_free_list[_NFREELISTS];
# endif
public:
static void* allocate(size_t __n)
{
void* __ret = 0;
if (__n > 128)
{
malloc(__n);
}
else
{
//16维的数组 + 内存池
_Obj** __my_free_list= _S_free_list + _S_freelist_index(__n);
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
static void deallocate(void* __p, size_t __n)
{
if (__n > 128)
malloc_alloc::deallocate(__p, __n);//free
else {
//将节点重新链接回自由链表下进行重复使用
//_S_free_list[3]
_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n)= ;
_Obj* __q = (_Obj*)__p;
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
}
}
};
#endif
template <class _Tp>
class allocator
{
typedef alloc _Alloc;
public:
//申请空间
_Tp* allocate(size_type __n, const void* = nullptr)
{
return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;
}
//释放空间
void deallocate(pointer __p, size_type __n)
{
_Alloc::deallocate(__p, __n * sizeof(_Tp));
}
//构建对象
void construct(pointer __p, const _Tp& __val)
{
//定位new表达式：在指定的空间上构建对象
new(__p) _Tp(__val); //new int(10)
}
//对象的销毁
void destroy(pointer __p)
{
__p->~_Tp();
}
};
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16};
union _Obj
{
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};
template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
__default_alloc_template<__threads, __inst> ::_S_free_list[
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
_NFREELISTS
# else
__default_alloc_template<__threads, __inst>::_NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
//在自由链表中取下标的函数
static size_t _S_freelist_index(size_t __bytes) //__bytes = 32
{
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
(32 + 8 - 1)/8 - 1 = 39/8 - 1 = 4 - 1 = 3
}
//向上取整，得到8的整数倍
static size_t _S_round_up(size_t __bytes) //__bytes = 32
{
return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1));
(32 + 8 - 1) & ~ (8 - 1) = 39 & ~7
39 = 32 + 4 + 2 + 1 = 0010 0111
7 = 4 + 2 + 1 = 0000 0111
~7 = 1111 1000
33-------->40
32-------->32
31-------->32
//....
25-------->32
24-------->24
[33, 40]--->40
[25, 32]--->32 3.x ---4
[17, 24]--->24
0010 0111
& 1111 1000
0010 0000-------->32
0010 0110
& 1111 1000
0010 0000-------->32
0010 0000
& 1111 1000
0010 0000-------->32
0001 1111
& 1111 1000
0001 1000-------->24
0010 1000
& 1111 1000
0010 1000-------->40
}
char* __default_alloc_template::_S_start_free = nullptr;
char* __default_alloc_template::_S_end_free = nullptr;
size_t __default_alloc_template::_S_heap_size = 0;
//1、如果想申请32字节的时候，堆空间与内存池是充足的
//__n = 32
static void* allocate(size_t __n)
{
else {
_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n)
= _S_free_list[3];
_Obj* __result = *__my_free_list;
if (__result == nullptr)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
}
//__n = 32
//该函数不会真正的申请空间，但是会调用_S_chunk_alloc申请空间，并将返回的空间进行切割，切割成
//多个等分并且挂接在对应的自由链表下面
void* __default_alloc_template::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
__my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[3]
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return (__result);
}
//__size = 32;
//__nobjs = 20
//本来想申请32字节，但是现在一次申请了1280字节，其中的640字节通过函数进行返回，剩下的640字节
//通过 _S_end_free与_S_start_free进行控制
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;
size_t __bytes_left = _S_end_free - _S_start_free = 0;
else {
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
= 2 * 640 = 1280 ;
_S_start_free = (char*)malloc(__bytes_to_get) = malloc(1280);
_S_heap_size += __bytes_to_get = 1280;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));//递归
}
//递归调用
char* __result;
size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;
size_t __bytes_left = _S_end_free - _S_start_free = 1280;
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
}
//2、如果想申请64字节的时候，堆空间与内存池是充足的
//__n = 64
static void* allocate(size_t __n)
{
else {
//_S_free_list[7]
_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj* __result = *__my_free_list;
if (__result == nullptr)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
// __n = 64
void* __default_alloc_template::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
__my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[7]
/* Build free list in chunk */
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return (__result);
}
//__size =64
//__nobjs = 20
char*
__default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs = 64 * 20 = 1280;
size_t __bytes_left = _S_end_free - _S_start_free = 640;
else if (__bytes_left >= __size) {
__nobjs = (int)(__bytes_left/__size) = 640/64 = 10;
__total_bytes = __size * __nobjs = 64 * 10 = 640;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
}
//3、如果想申请96字节的时候，堆空间与内存池是充足的
//__n = 96
static void* allocate(size_t __n)
{
else {
//_S_free_list[11]
_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj* __result = *__my_free_list;
if (__result == nullptr)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
// __n = 96
void* __default_alloc_template::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
__my_free_list = _S_free_list + _S_freelist_index(__n);
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return (__result);
}
//__size = 96
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;
size_t __bytes_left = _S_end_free - _S_start_free = 0;
else {
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
= 2 * 1920 + _S_round_up(1280 >> 4)
= 3840 + 80 = 3920;
_S_start_free = (char*)malloc(__bytes_to_get) = malloc(3920);
_S_heap_size += __bytes_to_get = 1280 + 3920 = 5200;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));//递归调用
}
//递归调用
char* __result;
size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;
size_t __bytes_left = _S_end_free - _S_start_free = 3920;
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
}
//4、如果想申请72字节的时候，堆空间与内存池没有连续的72字节
//__n = 72
static void* allocate(size_t __n)
{
else {
//_S_free_list[8]
_Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj* __result = *__my_free_list;
if (__result == nullptr)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
// __n = 72
void* __default_alloc_template::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if (1 == __nobjs) return(__chunk);
}
//__size = 72
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;
size_t __bytes_left = _S_end_free - _S_start_free = 0;
else {
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
= 2 * 1440 + _S_round_up(5200 >> 4)
> 2880;
_S_start_free = (char*)malloc(__bytes_to_get);
if (nullptr == _S_start_free)
{
size_t __i;
_Obj** __my_free_list;
_Obj* __p;
//__i = 72 80 88 96
for (__i = 72; __i <= 128; __i += 8)
{
//_S_free_list[8] _S_free_list[9] _S_free_list[10] _S_free_list[11]
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p)
{
*__my_free_list = __p -> _M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));//递归调用
}
}
}
//递归调用
char* __result;
size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;
size_t __bytes_left = _S_end_free - _S_start_free = 96;
else if (__bytes_left >= __size) {
__nobjs = (int)(__bytes_left/__size) = 96/72 = 1;
__total_bytes = __size * __nobjs = 72 * 1 = 72;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
}