Skip to content

算法Algorithm

弱引用与 Ephemeron 条件追踪

Ephemeron tracing · Conditional reachability · 弱键条件可达

用 holder 与 key 同时存活的规则求最小可达闭包,事件驱动激活值,并在释放前清除弱槽和失效键值对。

形式陈述 ​

哪些指针会让对象活着 ​

根与强边可达性回答普通指针图中哪些对象以后仍可能被程序取得。本页增加两种不同槽位:弱槽可以查询对象,却不独自保证对象存活;ephemeron 保存键 key 与值 value,只有持有这条记录的对象 holder 和键都已存活时,才让值存活。它适合把附加信息关联到对象,而不让附加信息反过来永久养活自己的键。

模型为有限精确堆 H、根集 R0、普通强边 E、弱槽集合 W,以及记录集合 P。每条记录是 (h,k,v),h∈H 是 holder,k,v 是对象或空值;一个 holder 最多有一条这样的记录,但可以另有普通强字段或弱槽。所有 ID、根和槽先验证,指针不得指向堆外。只讨论对象键,不把整数键等立即值隐含当作堆对象。

整个回收期间暂停程序,堆和根不变,没有终结器、回调、对象复活、并发弱读或跨回收保留的未登记引用。定义单调算子

F(X)=R0 ∪ X ∪{y:(x,y)∈E, x∈X} ∪{v:(h,k,v)∈P, h,k∈X, v≠null}.

根中的空值在集合里忽略。存活集是从空集不断应用 F 得到的最小固定点 R。弱边不参与 F。在所有存活 holder 中,普通弱槽的目标不在 R 就清空;ephemeron 的 key 不在 R 就把 key、value 一起清空。完成这些清除后才释放 H∖R,随后恢复程序。

两个触发点,一次标记队列 ​

实现使用标记清扫的入队一次遍历处理普通强字段,另外给每条非空键记录建立两个等待项:一个挂在 holder,另一个挂在 key。对象首次变活后入队,出队时扫描强字段并检查挂在它身上的记录。

text
对每条 (h,k,v),若 k 非空:wait[h].append(record),wait[k].append(record)
mark(x): 若 x 非空且未标记,标记并入队
对每个根执行 mark
while 队列非空:
  x = 出队
  对 x 的每个普通强字段 y:mark(y)
  对 wait[x] 中每条 (h,k,v):
    若此记录尚未激活,而且 h、k 都已标记:
      标记该记录已激活
      mark(v)
按最终标记清除失效弱槽和键值对
释放未标记对象

“已标记”不要求已经出队。若 holder、key 在根扫描时都已标记,先处理哪一个事件都能激活记录;若其中一个较晚发现,它自己的事件会补上检查。holder 与 key 为同一对象时可挂两份项,已激活标志阻止重复动作。空 key 不会触发,空 value 允许激活但不增加对象。

直觉

弱键缓存想表达的是:“只要程序还需要这个键,就帮它保存附加值。”困难在于附加值可能保存键本身。例如分析结果里带着被分析对象的指针;如果把缓存值无条件当作强引用,缓存会通过值绕回键,让键永远不能消失。

条件追踪先询问键有没有独立生存理由。有了这个理由,值才获得生存资格;值又可能引出其他键,继续激活下一条记录。没有起点的一圈互相支持不能凭空得到资格,所以要取最小闭包,而不是随便找到一个满足规则的集合。

例子与边界

两条记录接力,另一条自支持失败 ​

堆有 11 个对象:E1、E2、Ebad、W、K1、K2、V1、V2、Kbad、Vbad、U。根依次是 E1,E2,Ebad,W,K1。仅有的普通强字段是 V1→K2 与 Vbad→Kbad。W 有一个弱槽指 Kbad;三个 ephemeron 为

E1:(K1,V1),E2:(K2,V2),Ebad:(Kbad,Vbad).

初始根给出五个活对象。E1 与 K1 都活,加入 V1;扫描 V1 得到 K2;E2 与 K2 此时都活,再加入 V2。最终标记顺序在参考队列里是

text
E1, E2, Ebad, W, K1, V1, K2, V2

因此保留 8 个、释放 Kbad,Vbad,U。W 的弱槽变空,Ebad 的 key/value 都变空;Ebad 自身仍是根,不能连 holder 一起删掉。程序输出的 activated 按输入记录顺序列集合,本例是 E2、E1;它不是事件发生顺序,实际因果应看 V1、K2、V2 的 cause 记录。

有根的条件链与无根的自支持环

即使记录输入顺序先列 E2 再列 E1,工作表仍得出这个结果。只顺序扫一遍记录、看见 E2 的键未标记就永远跳过,会漏掉 V2;把所有 value 当强边则会把 Vbad 和 Kbad 都错误保留。

第二轮与 holder 条件 ​

在第一轮完成的实际堆上去掉 K1 根,再完整执行一轮。其余四根 E1、E2、Ebad、W 仍在,但没有键能启动条件链。于是释放 K1,K2,V1,V2,E1、E2 的键值对也清空。不是只删除 K1:由它支撑的两个值和下游键都会失去依据。

另取 H={E,K,V},唯一根是 K,唯一记录是 E:(K,V)。E 不可达,所以 V 也不应保留,结果只剩 K。仅检查 key、漏掉 holder 的实现会多留 V。反过来,把 E 作为根、记录设为 E:(K,K),K 不会凭自己成为活对象,效果等同一个指向 K 的弱盒。

清空是可观察行为 ​

回收结束后读取 W 的弱槽会得到空;若只释放 Kbad 而保留旧 ID,弱读取就变成悬空访问。弱引用因此改变语言观察,不能直接套用“GC 完全不可观察”的普通强引用结论。

若在下一次回收前读取一个尚存弱目标并准备继续使用它,程序必须把读出的强临时值登记为根。实际语言还可能要求显式保活操作以限制优化器提前结束键的生命周期。[3] 本模型在一个完整停止世界转换后观察槽值,没有实现跨线程弱读、保活 API 或终结回调。

推论与应用

最小性和完整性分别怎样证明 ​

先证不会多标:根属于 R;从已经在 R 的对象追踪强边仍在 R;激活时 holder、key 均已在 R,所以加入 value 也在 R。对每次首次入队归纳,算法标记集始终包含于最小固定点。

再证不会漏标:队列终止时,每个已标记对象都已处理,因此其强后继都标记。若某条记录的 holder、key 均标记,二者中最后被处理的事件发生时,两者一定都已经标记,记录会激活;于是它的非空 value 也标记。终态集合包含根且对全部规则封闭,最小固定点包含于它。两边包含给出相等。

每个对象只入队一次,每次只枚举自己的强字段及等待项,有限性保证终止。即使没有可激活记录,主例坏环也只是留在未标记集合,不会让算法一直等待。释放前清槽与固定点闭合共同保证:存活对象的强字段、保留的 ephemeron 值以及非空弱槽都指向存活对象。

成本与适用范围 ​

设 N 为对象数,E 为普通强字段槽数,K 为 ephemeron 数,W 为弱槽数,r 为根槽数。在定长 ID、散列表期望常数操作模型中,连同输入验证、建立等待表、扫描、清槽和输出堆副本,时间为

O(1+N+E+K+W+r).

等待项最多 2K,每项随所挂对象出队检查至多一次;标记队列与集合为 O(1+N),等待结构为 O(1+N+K)。输出堆及所有槽副本还要占 O(1+N+E+K+W+r),不能只报告工作表大小。本例检查等待项 5 次、扫描普通强槽 1 次;未活的 Vbad 不扫描,但入口仍验证它的字段。

反复完整扫描所有未激活记录也能求同一闭包,却可能在逆序长度 K 的依赖链上用二次工作。按触发对象保存等待项避免了这种重复搜索;原论文在 p.181 注2 已给出按键组织延迟队列的线性改进思路。[1] 本页双事件版本还直接处理预先登记但 holder 尚不可达的记录。

本页与增量强边标记是两个独立执行模型。前者冻结堆并精确求条件闭包;后者允许强边变化并容许浮动垃圾。把弱槽、条件记录塞进后者,必须重新设计阶段与屏障,不能由两篇各自正确就推出联合收集器正确。

终点见变化的强边与有条件保留,可用参考程序打印实际保留堆、清槽结果与每个新对象的来源。迁移可给 Kbad 增添根使坏环获得真实起点,再去根执行下一轮;必须在上一轮输出堆上继续,而非每次偷偷恢复原输入。

参考资料

[1] Barry Hayes,Ephemerons: A New Finalization Mechanism,OOPSLA 1997,176–183,pp.179–180 条件追踪与属性环,p.181 注2 的按键延迟队列。原文还含终结通知阶段;本页只实现无回调的清槽与回收变体。论文明确将设计归于 George Bosworth。

[2] Racket Reference,§16.2 Ephemerons,2026-10-09 核查,“More precisely”两项明确 holder 与 key 的可达条件及跨记录值的处理。

[3] Marc Nieper-Wißkirchen,SRFI 254: Ephemerons and Guardians,2026-06-30 定稿,Specification / Ephemerons 中的 reference-barrier 与 ephemeron-ref。它接替已撤回的 SRFI 124;本页仅据此核对读取后的保活责任,不实现 guardians 或完整 Scheme 接口。

关系图谱10 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系