# 为什么没有垃圾回收器 U 没有垃圾收集器。所有权是一个有向无环图（DAG）——强引用从父级指向子级，从不向上或循环。 当一个所有者的引用计数达到零时，它的整个子树会死亡。没有追踪，没有标记-清扫，也没有暂停。 释放的成本与那个所有者分配的内存成正比，而不是与总堆大小成正比。反向引用使用 +R（parent）注释。编译器将其视为弱引用：它们不贡献到引用计数，并在被引用对象死亡时解析为无。Linter 使用 Tarjan 的强连通分量算法对类型引用图施加 DAG 结构——任何循环必须至少有一个 +R（parent）边，否则程序将被拒绝。 # Slab 链分配器 每个所有者都有一个 slab 链。分配在当前 slab 内移动指针。当一个 slab 填满时，链接一个新的双倍大小的 slab。 所有者 └─ slab_ptrs: [ptr0, ptr1, ptr2, ...] │ │ │ ▼ ▼ ▼ 4KB 8KB 16KB ... 用于 n 字节总数的链最多有 ⌈log₂(n/initial)⌉ 个 slabs。每个 slab 是一个二次幂的分配，系统分配器可以通过大小类别空闲链表高效服务。 分配是一个增量指针：递增，与结束进行比较。 不需要为单个所有者范围内的对象进行逐个对象空闲列表遍历，也不需要一般用途的分配元数据。释放操作遍历链并释放每个 slab。 对于普通请求大小的分配，这仅仅是少量的释放。对于 n 字节总数，成本为 O(log n) 的 slab 释放，且对于典型作用域有效地为常数。 # NaN-包装标记值 列表、映射和树中的动态值可以通过 NaN-包装使用单个 8 字节标记表示。 实数双精度 → 原始 IEEE 表示，NaN 被标准化 小整数 → 标记整数字段 指针 → 标记指针字段 布尔值 true → 保留的标记模式 布尔值 false → 保留的标记模式 none → 保留的标记模式 tombstone → 保留的标记模式 精确的标记布局是一个 ABI 细节。 浮点 NaN 必须被标准化，以便标记负载不能与数值 NaN 混淆。 动态 U 值在其值适合于标记表示时是一个机器字。 因此，叶值无需单独的堆分配。 使用掩码、转移和比较来提取标记和负载。 # 列表 列表使用稳定的二次幂 slabs。 元素不会仅仅因为列表增长而移动。 slab 0: 4 个元素 slab 1: 8 个元素 slab 2: 16 个元素 slab 3: 32 个元素 ... 一旦一个元素收到逻辑索引，后续元素的附加不会改变该索引或重新定位现有元素。 O(1) 随机访问 对于索引 k ，可以使用最高有效位、clz 、位移和算术来确定 slab。 slab_index = 31 - clz((k >> 2) + 1) base = (4 << slab_index) - 4 pointer = slab_ptrs[slab_index] address = pointer + (k - base) * element_size slab 指针头非常小，通常驻留在缓存中。 迭代 迭代保存当前 slab 指针、当前元素指针和 slab 中剩余的元素。 它遍历连续内存直到 slab 结束，然后前进到下一个 slab。因此，顺序迭代接近于普通的连续内存带宽，并且与硬件预取自然配合。 O(1) 附加 在当前 slab 内附加是一个增量。当该 slab 填满时，分配下一个二次幂的 slab 并在那里继续。现有元素绝不会仅仅因为容量增长而被复制。因此，附加在现有列表长度方面的最坏情况是 O(1)，而不仅仅是摊销 O(1)。 # 映射：稳定有序存储 U 映射在根本上是有序的稠密存储，而不是散列表。 它的权威表示是两个并行稳定的列表： Map<K,V> 索引 1 2 3 4 5 │ │ │ │ │ 键 [K1] [K2] [K3] [K4] [K5] 值 [V1] [V2] [V3] [V4] [V5] 定义不变量是插入索引 i ↔ keys[i] ↔ values[i] 。 索引按顺序递增。现有的活跃条目不会仅仅因为插入后续条目而移动。 权威的方向是索引 → (key, value) 。 反向方向 key → index 是派生加速数据。 # 映射优化的第一法则：避免反向查找 一般的散列表假设 key → hash → 存储位置是基础的。 U 不这样认为。许多重要的 PHP、JavaScript、JSON、路由、配置和应用模式已经通过迭代、插入、编译器常量键、共享形状、先前的解析或编译器数据流揭示了相关的稳定索引。在优化 key → index 之前，先确定是否根本有必要进行该操作。通用动态解析器仅处理剩余情况。 # 迭代器的来源 foreach ($a as $b => $c) { use($a[$b]); } 迭代器已经知道 b 、c 和当前稳定索引 bi 。因此， $a[$b] 变成 a.values[bi] 。没有反向查找。 嵌套迭代遵循相同的规则： foreach ($a as $b => $c) { foreach ($c as $d => $e) { use($a[$b][$d]); } } 编译器保留外部稳定索引 bi 和内部稳定索引 di ，因此 $a