自定义内存分配器

为什么堆分配慢（卷 I 6.2、6.2.1）

1. 通用堆分配器要处理 1 字节到 1 GB 的任意请求，管理开销大；
2. 多数操作系统上 malloc() / free() 要从用户态切到内核态再切回，上下文切换极其昂贵（用户态/内核态见 进程、线程与纤程）。
   • 原书问题：「每次 malloc()/free() 都要切入内核」不符合现代通用分配器的实际。以 glibc malloc 为例，绝大多数请求在用户态由线程本地缓存 (tcache)、fastbin/smallbin 等空闲链表满足，只有需要扩展堆（sbrk）或大块请求（超过动态阈值时直接 mmap）时才进行系统调用；free() 通常也只是把块放回用户态的链表，并不把内存还给操作系统（glibc wiki「MallocInternals」）。Windows 堆、jemalloc、mimalloc 等同样如此。通用堆慢的主要原因是第 1 条的通用性开销、加锁/竞争、缓存不友好与碎片，而非每次都陷入内核；GEA 的经验法则本身仍然成立。 GEA 推荐延伸阅读 Christian Gyrling 关于自定义分配器的博客文章（GEA 参考文献 [194]）。自定义分配器更快的两个原因：从预分配的内存块（用 malloc/new 分配或声明为全局数组）中满足请求，全程在用户态；并且可以对使用模式做假设，比通用分配器高效得多。另一方面，数据放在小而连续的内存块中，CPU 处理起来远比分散的数据快（见 计算机硬件与内存层次、数据局部性）。

栈分配器（卷 I 6.2.1.1）

• 适用：关卡加载时分配、关卡期间几乎不分配、关卡结束整体释放这种栈式模式。
• 实现：一大块连续内存（malloc/全局 new，或全局字节数组——此时内存实际来自可执行文件的 BSS 段）加一个栈顶指针；分配就是把指针上移请求的字节数。
• 只能按分配的逆序释放。简单的强制办法是不允许单独释放，而是提供 getMarker() 返回当前栈顶标记、freeToMarker(marker) 回滚到标记处（必须回滚到两个块的边界，否则新分配会覆盖最上面块的尾部），以及 clear() 全部清空。
• 双端栈分配器：同一块内存，一个栈从底部向上分配，一个从顶部向下分配，两者的用量可以此消彼长，只要总量不超过整块即可。Midway 的街机游戏《Hydro Thunder》全部内存都由一个双端栈管理：下栈加载/卸载关卡（赛道），上栈分配每帧申请和释放的临时块；这套方案效果极好，游戏从未遇到内存碎片问题（首席工程师 Steve Ranck 对此有深入介绍，见 GEA 参考文献 [9] 第 1.9 节）。

池分配器（卷 I 6.2.1.2）

• 适用：大量同尺寸小块的分配和释放，如矩阵、迭代器、链表节点、可渲染网格实例。
• 预分配一块大小恰为元素尺寸整数倍的内存（如 4×4 float 矩阵每个 64 字节），所有元素串成空闲链表；分配取链表头，释放挂回链表，都是 $O(1)$。
• 把 next 指针存放在空闲块自身里：空闲块本来就没被使用，所以不浪费内存，前提是 elementSize >= sizeof(void*)。若元素小于指针，用元素索引代替指针，如 16 位整数池用 16 位索引，前提是元素不超过 $2^{16}=65{,}536$ 个。

对齐分配（卷 I 6.2.1.3）

• 对齐要求回顾（见 C++ 内存布局与对齐）：32 位整数/浮点 4 字节对齐（地址末位 0x0/0x4/0x8/0xC），128 位 SIMD 向量通常 16 字节对齐；PS3 上经 DMA 传给 SPU 的块应 128 字节对齐以获得最大吞吐。所有分配器都必须能返回对齐的内存。
• 思路：多分配一点，把地址上移到对齐边界再返回。多数实现额外分配「对齐值减一」($L-1$) 字节，这是最坏情况的偏移（例如要 16 字节对齐而原地址末位是 0x1，需上移 15 字节）。书中第一版 AllocAligned() 就是 new U8[bytes + align - 1] 后直接返回对齐指针——但这样无法正确释放（丢失了原始地址），因此才有下面存放偏移的改进版。对齐地址的位运算： $\text{aligned}=(\text{addr}+(L-1))\ \&\ \sim(L-1)$ $L$ 必须是 2 的幂，$L-1$ 的低 $N=\log_2L$ 位全为 1，取反后与地址按位与即去掉低 N 位。
• 释放时找回原地址：把偏移量 (shift) 存在对齐地址前一个字节 p[-1] 里。为保证总有空间存放，分配 $L$（而不是 $L-1$）个额外字节，并且即使原地址已对齐也上移整整 $L$ 字节，于是偏移在 1 到 $L$ 之间。一字节可存到 128 的偏移；由于偏移永不为 0，可把 0 解释为 256，从而支持到 256 字节对齐；更大的对齐需要更宽的头部。

void* AllocAligned(size_t bytes, size_t align) {      // align 必须是 2 的幂
    U8* pRaw = new U8[bytes + align];
    U8* pAligned = AlignPointer(pRaw, align);
    if (pAligned == pRaw) pAligned += align;          // 总是留出存放偏移的空间
    ptrdiff_t shift = pAligned - pRaw;                 // 1..256
    pAligned[-1] = static_cast<U8>(shift & 0xFF);
    return pAligned;
}
void FreeAligned(void* pMem) {
    if (!pMem) return;
    U8* pAligned = reinterpret_cast<U8*>(pMem);
    ptrdiff_t shift = pAligned[-1]; if (shift == 0) shift = 256;
    delete[] (pAligned - shift);
}

（据书中代码精简）

单帧与双缓冲分配器（卷 I 6.2.1.4）

• 单帧分配器：一个栈分配器，每帧开始 clear()。分配的内存永远不用释放，而且极快。代价是纪律：内存只在本帧有效，绝不能跨帧缓存指向它的指针。
• 双缓冲分配器：两个等大的单帧栈每帧轮换（swapBuffers() 后 clearCurrentBuffer()），第 i 帧分配的内存在第 i+1 帧仍有效。
• 典型用途：在多核主机（Xbox 360/One、PS3/PS4）上缓存异步任务的结果——第 i 帧发起任务并给它一个从双缓冲分配器拿的目标缓冲，任务在第 i 帧结束前写完；第 i+1 帧缓冲交换，结果位于非活动缓冲中不会被覆盖，只要在第 i+2 帧之前用掉即可（任务系统见 多线程渲染与任务系统）。

内存碎片（卷 I 6.2.2）

• 随机顺序、不同大小的分配与释放会让堆变成已用块与空闲「洞」交错的拼布；洞多且小时就是碎片化。问题在于分配必须连续：两个 64 KiB 的洞凑不出一个 128 KiB 的请求，即使总空闲字节够也会失败。
• 虚拟内存把不连续的物理页映射成连续的虚拟地址，并可把不常用的页换到硬盘，碎片问题较轻。GEA 指出 PS5 与 Xbox Series X/S 支持虚拟地址重映射，但都不像 Linux/Windows 那样自动把虚拟内存换页到磁盘，所以主机开发者面对的是固定数量的 RAM，要流式进出数据必须自己实现流送系统。
• 用栈和池避免碎片：栈分配总是连续、且按逆序释放，天然免疫碎片；池会产生碎片，但因为所有块等大，永远不会因为找不到足够大的连续块而提前耗尽内存。

碎片整理与重定位（卷 I 6.2.2.2）

• 大小不一、顺序随机的分配无法用栈或池时，可以定期碎片整理：把高地址的已分配块下移填洞，洞逐渐「冒泡」到高地址，最终合并成一个大洞。简单算法：找到第一个洞，把紧挨在它上面的块下移到洞的起点，重复。
• 难点不在移动，而在指针失效：必须修正所有指向被移动块的指针，即指针重定位 (pointer relocation)。由于没有通用办法找出所有指向某区域的指针，要么手动追踪所有指针，要么改用更易重定位的东西：
  • 智能指针：行为像指针的小类；例如让所有智能指针加入一个全局链表，块移动时扫描链表修正指向该块的指针。
  • 句柄 (handle)：通常是指向一张不可重定位的指针表的索引；块移动时只需更新表中的指针，句柄值本身永不改变，持有句柄的对象完全不受影响。
• 不可重定位的块（如不使用智能指针/句柄的第三方库）：最好让该库从可重定位区域之外的专用缓冲分配；或者接受少量不可重定位的块——数量和尺寸都小时重定位系统仍然表现良好。
• Naughty Dog 的所有引擎都支持碎片整理：尽可能用句柄；无法避免的原始指针被仔细追踪并手动重定位；少数游戏对象类因各种原因不可重定位，但数量很少、尺寸相对可重定位区域极小，不造成实际问题。
• 摊销：不必一次整理完，每帧最多移动 N 个块（N 如 8 或 16）。30 帧/秒时，堆通常不到一秒就能整理完而不影响帧率；只要分配释放速度不超过整理速度，堆始终基本无碎片。前提是单个块足够小，移动一块的时间不超过每帧的预算；大块可拆成可独立移动的子块。Naughty Dog 只对动态游戏对象做重定位，它们从不超过几 KiB，通常小得多。

选型速查

PBRT 的视角：渲染器里的暂存缓冲与多态分配器（PBRT 4e 1.3.4、1.5.6）

• ScratchBuffer：积分器为每条光线计算 BSDF 等临时对象时会产生大量小分配，通用分配器（如 new）要在多线程下维护复杂的空闲内存结构，可能占掉相当比例的计算时间。pbrt 的 ScratchBuffer 是一小块预分配内存，分配只是把偏移加上请求大小；不能单独释放，只能一次全部释放（重置偏移）。每个像素样本算完就 Reset()。它不是线程安全的，所以用 ThreadLocal 为每个线程按需各建一个。这与 GEA 的栈分配器/单帧分配器（见上文）是同一思路，只是生命周期从"一帧"缩短到"一个像素样本"。
• Allocator：场景对象几乎都通过 Allocator（即 C++17 std::pmr::polymorphic_allocator）创建，常用 allocate_bytes()、allocate_object()、new_object() 及对应的释放函数。好处：便于统计总内存、可以换成适合大量小分配的分配器（构建加速结构时）、可以把场景放进 GPU 可见的内存。
• 坑：标准容器的分配器在构造后就固定了，容器之间赋值（包括移动）不会换分配器，所以 pbrt 的构造函数常在成员初始化列表里就把分配器传给容器，哪怕暂时还不填数据。

PBRT 的视角：ScratchBuffer 与驻留（PBRT 4e B.4）

• ScratchBuffer 是竞技场 (arena) 分配器：从一大块预分配内存中按对齐要求推进 offset 分配，不单独释放；Reset() 通常只把 offset 清零，不调用析构函数。空间不够时换更大的块，旧块暂存在 smallBuffers，到 Reset() 时归还系统。它不支持多线程共享，每个线程通过 ThreadLocal 各持一个；类用 alignas 对齐到缓存行以免伪共享。用于路径追踪中动态创建的 BxDF、BSSRDF、RayMajorantIterator。
• 驻留 (interning)：InternCache 对相同对象只存一份，用互斥锁支持并发 Lookup()，返回共享指针，因此可以用指针比较代替值比较；pbrt 对场景描述中的变换和场景实体中的字符串（InternedString）这样处理，复杂场景能省下大量内存。
• 其他容器：InlinedVector（短向量不做动态分配）、自带 HashMap（标准库 unordered_map 要求元素指针在扩容后不变，因此每个元素都要单独分配；且 GPU 代码也要能用）。
• TaggedPointer：64 位指针的高位实际不用于寻址（常见 48 位、新近 57 位地址空间），pbrt 把类型标签放在高 7 位，Dispatch() 用一个 switch 完成动态分发（每组最多 8 种类型，超出部分递归处理），可在 GPU 上替代虚函数。
• 原书问题（笔误）：B.4.5 "It offsets a few constructors" 应为 "offers"。