5.2 块分配器与大小类
上一节的 ObjectPool<T> 是按类型池化的：每种实体（子弹、粒子、音效）各有一个池子，池子里的对象是 JS 对象。但引擎里还有一类东西没有「类型」——变长的裸内存块：一段顶点数据、一张贴图的临时缓冲、一次网络包的解码区。它们的长度各不相同，却又需要像池子那样「用完还回来、下次接着用」。
这一节我们把它下沉到字节层：在一块固定的 ArrayBuffer 上，按 2 的幂切出大小类（size class），每类挂一条空闲链表。分配 n 字节时，向上取到能装下它的最小类，从那一类的链表里摘一块；释放时把块压回它所属类的链表。这样既能任意顺序回收，又不会像 arena 那样被「只前进」卡死。
2 的幂切块：大小类怎么分
为什么用 2 的幂？因为算得快。给定请求字节 n，向上取到最近的 2 的幂可以用一条位运算完成，不需要查表、不需要循环。helio 里最小块 16 B、最大块 1024 B，一共 7 个类（2^4 到 2^10）。
// snippet: 大小类索引（向上取到最近的 2 的幂）
export function sizeClassIndex(sizeBytes: number): number {
if (!Number.isInteger(sizeBytes) || sizeBytes <= 0) {
throw new RangeError(`size must be a positive integer, got ${sizeBytes}`);
}
if (sizeBytes <= MIN_SIZE_CLASS) return 0; // ≤16 全归 16 B 类
if (sizeBytes > MAX_SIZE_CLASS) {
throw new RangeError(`size ${sizeBytes} exceeds max size class ${MAX_SIZE_CLASS}`);
}
return 32 - Math.clz32(sizeBytes - 1) - 4; // 17→32, 33→64, 1000→1024
}
Math.clz32 数的是 32 位里「前导零」的个数。sizeBytes - 1 再取 clz32，等价于「向上取到 2 的幂再取 log2」——减 4 是因为最小类是 16（2^4）。举个例子：请求 17 字节，17-1=16，clz32(16)=27，32-27-4=1，落到第 1 类即 32 B。请求 16 字节则直接命中第 0 类。这套算术决定了后面每个类的块大小，是分配器最快的路径。
每个类拿到一段连续的区域（region），区域内再切成等大的块。类的区域大小由总容量均分，块数就是 区域字节 / 块大小。一个类的块全部用完时，它只能拒绝分配——这正是「固定 buffer」的代价，也是我们想观察的边界。
把区域均分而不是按需共享，是个刻意的简化：它让「偏移落在哪个区域」直接等价于「这个块属于哪个类」，free 时不用额外存元数据就能找回链表。代价是某个类用光了、别的类却还空着时无法互相借调——这类跨类调剂的复杂分配器（如 dlmalloc 的 bin 机制）不在本卷范围。
可运行产物：PoolAllocator
下面这个文件是 helio 的块分配器实现，纯 TS、Node 直跑，是本节第一块可运行产物。它包含 sizeClassIndex、7 个类的区域切分、每类一条空闲链表，以及一套碎片统计。
// file: src/core/pool-allocator.ts
// tier: L1
// verify: npx vitest run src/core/pool-allocator.test.ts
//
// helio 内核：按 2 的幂分「大小类」（size class）的块分配器。
// 与 4.x 的 arena（只前进）不同，这里支持任意顺序的 free——
// 每个大小类维护自己的空闲链表，分配-释放-再分配能复用同一块，
// 这是 5.1 对象池在「裸内存」层面的对应物。
/** 最小块 16 B，最大 1024 B；类 = 2^k，k = 4..10。 */
export const MIN_SIZE_CLASS = 16;
export const MAX_SIZE_CLASS = 1024;
export interface SizeClassStat {
readonly sizeClass: number;
readonly blocks: number;
readonly used: number;
/** 该类内已分配块请求字节 / 已保留字节，1 表示零内部碎片。 */
readonly utilization: number;
}
export interface AllocatorStats {
readonly capacityBytes: number;
readonly reservedBytes: number;
readonly requestedBytes: number;
/** 1 - 请求字节/保留字节：越小越省（但过小说明大小类太粗）。 */
readonly internalFragmentation: number;
readonly perClass: readonly SizeClassStat[];
}
/** 大小类索引：16→0, 32→1, ..., 1024→6；size<=16 归 0。 */
export function sizeClassIndex(sizeBytes: number): number {
if (!Number.isInteger(sizeBytes) || sizeBytes <= 0) {
throw new RangeError(`size must be a positive integer, got ${sizeBytes}`);
}
if (sizeBytes <= MIN_SIZE_CLASS) return 0;
if (sizeBytes > MAX_SIZE_CLASS) {
throw new RangeError(`size ${sizeBytes} exceeds max size class ${MAX_SIZE_CLASS}`);
}
return 32 - Math.clz32(sizeBytes - 1) - 4;
}
export class PoolAllocator {
readonly #buffer: ArrayBuffer;
readonly #bytes: Uint8Array;
readonly #classes: number[];
readonly #regionStart: number[];
readonly #blockSize: number[];
readonly #blockCount: number[];
readonly #freeLists: number[][];
readonly #used: number[];
readonly #requested: Map<number, number>;
constructor(capacityBytes: number, maxSizeClass = MAX_SIZE_CLASS) {
if (!Number.isInteger(capacityBytes) || capacityBytes <= 0) {
throw new RangeError(`capacity must be a positive integer, got ${capacityBytes}`);
}
this.#buffer = new ArrayBuffer(capacityBytes);
this.#bytes = new Uint8Array(this.#buffer);
this.#classes = [];
for (let s = MIN_SIZE_CLASS; s <= maxSizeClass; s <<= 1) this.#classes.push(s);
const n = this.#classes.length;
const region = Math.floor(capacityBytes / n);
this.#regionStart = [];
this.#blockSize = [];
this.#blockCount = [];
this.#freeLists = [];
this.#used = [];
this.#requested = new Map();
let cursor = 0;
for (let i = 0; i < n; i++) {
const size = this.#classes[i]!;
const count = Math.floor(region / size);
this.#regionStart.push(cursor);
this.#blockSize.push(size);
this.#blockCount.push(count);
this.#used.push(0);
const list: number[] = [];
for (let b = 0; b < count; b++) list.push(cursor + b * size);
this.#freeLists.push(list);
cursor += region;
}
}
get capacity(): number {
return this.#buffer.byteLength;
}
byteView(offset: number, count: number): Uint8Array {
return this.#bytes.subarray(offset, offset + count);
}
/** 分配：选能装下 `sizeBytes` 的最小大小类，从该类空闲链表弹出。 */
alloc(sizeBytes: number): number {
const ci = sizeClassIndex(sizeBytes);
const free = this.#freeLists[ci];
if (!free) throw new RangeError(`no size class for ${sizeBytes} B`);
const offset = free.pop();
if (offset === undefined) {
throw new RangeError(`size class ${this.#blockSize[ci]} B exhausted`);
}
this.#used[ci]!++;
this.#requested.set(offset, sizeBytes);
return offset;
}
/** 释放：把块压回它所属大小类的空闲链表。 */
free(offset: number): void {
const ci = this.#classOf(offset);
this.#freeLists[ci]!.push(offset);
this.#used[ci]!--;
this.#requested.delete(offset);
}
#classOf(offset: number): number {
for (let i = this.#classes.length - 1; i >= 0; i--) {
if (offset >= this.#regionStart[i]!) return i;
}
throw new RangeError(`offset ${offset} outside allocator`);
}
get stats(): AllocatorStats {
// 先按大小类归集「真实请求字节」，用于算内部碎片。
const reqPerClass = new Array<number>(this.#classes.length).fill(0);
let requested = 0;
for (const [offset, sizeBytes] of this.#requested) {
reqPerClass[this.#classOf(offset)]! += sizeBytes;
requested += sizeBytes;
}
let reserved = 0;
const perClass: SizeClassStat[] = [];
for (let i = 0; i < this.#classes.length; i++) {
const size = this.#blockSize[i]!;
const used = this.#used[i]!;
const usedBytes = used * size;
reserved += usedBytes;
perClass.push({
sizeClass: size,
blocks: this.#blockCount[i]!,
used,
utilization: usedBytes === 0 ? 1 : reqPerClass[i]! / usedBytes,
});
}
return {
capacityBytes: this.#buffer.byteLength,
reservedBytes: reserved,
requestedBytes: requested,
internalFragmentation: reserved === 0 ? 0 : 1 - requested / reserved,
perClass,
};
}
/** 某类当前空闲块数。 */
freeCount(sizeBytes: number): number {
return this.#freeLists[sizeClassIndex(sizeBytes)]!.length;
}
}
两个细节值得留意。第一，偏移量就是句柄。alloc 返回一个 number——块在 buffer 里的字节偏移。调用方拿到它之后，用 byteView(offset, count) 得到视图读写，用 free(offset) 归还。偏移天然可序列化、可比较，比 JS 对象引用更适合做「引擎内部的内存句柄」。
第二，#classOf 用「区域起点倒着找」定位块属于哪一类。因为区域是按类顺序排布的，偏移落在哪个区域就属于哪个类。倒序遍历是因为较大的类区域靠后，命中更快。释放时靠它把块压回正确的链表——这一步保证了「分配-释放-再分配」能复用同一块。
碎片率与复用断言
块分配器有个绕不开的代价：内部碎片。请求 40 字节，只能拿到 64 字节的块，那 24 字节就浪费在块内部了。stats 里的 internalFragmentation = 1 - 请求字节 / 保留字节，正是量化这件事。
下面这段测试（完整文件 src/core/pool-allocator.test.ts）把复用与碎片两条语义都钉死，是本节第二块可运行产物：
// snippet: src/core/pool-allocator.test.ts 的关键断言
it('分配-释放-再分配复用同一块', () => {
const a = new PoolAllocator(4096);
const p = a.alloc(40); // → 64 B 类
a.free(p);
const q = a.alloc(40);
expect(q).toBe(p); // LIFO 空闲链表 → 拿到同一偏移
});
it('碎片率统计：请求 40 B 占用 64 B 块 → 内部碎片 > 0', () => {
const a = new PoolAllocator(8192);
a.alloc(40);
const s = a.stats;
expect(s.requestedBytes).toBe(40);
expect(s.reservedBytes).toBe(64);
expect(s.internalFragmentation).toBeCloseTo(1 - 40 / 64, 5);
});
it('全部释放后碎片率归零', () => {
const a = new PoolAllocator(8192);
const p = a.alloc(100);
a.free(p);
const s = a.stats;
expect(s.reservedBytes).toBe(0);
expect(s.internalFragmentation).toBe(0);
});
本机实测 npx vitest run src/core/pool-allocator.test.ts：Test Files 1 passed (1)、Tests 8 passed (8)。其中第一条断言（q === p）是块分配器与 arena 的分界线：arena 的偏移只会单调前进，而这里同一地址被反复发放。
内部碎片这件事没有免费解。类分得越细（比如 16/24/32/…），碎片越小但类越多、管理越复杂；类分得越粗（只有 16 和 1024 两档），管理简单但小请求浪费严重。helio 选了 2 的幂这一档折中——最坏情况下一次请求浪费接近 50%（比如请求 33 字节拿到 64 字节的块），但换来的是 O(1) 的类定位与极简的实现。真实引擎（如 mimalloc、tcmalloc）会在 2 的幂之间再插细档来压碎片，那是工程化话题，超出本节范围。
小结
- 块分配器 = 固定
ArrayBuffer+ 按 2 的幂切大小类 + 每类一条空闲链表。 sizeClassIndex用32 - clz32(n-1) - 4一步定位类，无需查表。alloc返回字节偏移当句柄；free靠「区域倒查」把块压回正确的链表。- 复用断言
q === p证明同一块被反复发放，这是它区别于 arena 的核心。 - 代价是内部碎片：2 的幂分类最坏浪费接近 50%，换来 O(1) 与极简实现。
分配器能高效复用内存了，但它还回答不了一个问题：这些内存到底是谁在占？下一节我们给每笔分配挂上标签、设好预算，并用分配计数快照把「忘记释放」的泄漏当场抓出来。
阅读导航：上一节：5.1 对象池与 freelist · 下一节：5.3 内存标签、预算与泄漏检测 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。