一句话:提出 drop-guided 重用算法,使引用计数下的对象原地重用更简单稳健,并证明其帧受限性,在 Koka 中获得显著加速。
Perceus 算法可自动插入引用计数指令,使无环程序达到「无垃圾」(garbage free):对象在不再被引用时立即释放。其重要扩展是重用分析:把已知大小的对象与同大小的新分配配对,若该对象在运行时唯一,则尝试原地重用。然而现有重用分析实现脆弱,对微小的程序变换敏感,还可能任意增大堆峰值。本文提出一种新的 drop-guided 重用算法,比先前方法更简单、更稳健;同时将线性资源演算推广,以精确刻画无垃圾与帧受限(frame-limited)求值——每次函数调用可以更久地持有内存,只要其大小受常数因子限制。基于该框架,作者证明 drop-guided 重用满足帧受限性,并发现该新方法在 Koka 中的实现能带来显著加速。
The recently introduced _Perceus_ algorithm can automatically insert reference count instructions such that the resulting (cycle-free) program is _garbage free_: objects are freed at the very moment they can no longer be referenced. An important extension is reuse analysis. This optimization pairs objects of known size with fresh allocations of the same size and tries to reuse the object in-place at runtime if it happens to be unique. Unfortunately, current implementations of reuse analysis are fragile with respect to small program transformations, or can cause an arbitrary increase in the peak heap usage. We present a novel _drop-guided_ reuse algorithm that is simpler and more robust than previous approaches. Moreover, we generalize the linear resource calculus to precisely characterize garbage-free and frame-limited evaluations. On each function call, a frame-limited evaluation may hold on to memory longer if the size is bounded by a constant factor. Using this framework we show that our drop-guided reuse _is_ frame-limited and find that an implementation of our new reuse approach in Koka can provide significant speedups.