https://news.ycombinator.com/item?id=31139610是关于 Chris Lattner 在Accidental Tech Podcast对GC与自动引用计数ARC的看法。

ARC的未来

传统的引用计数，其主要性能开销在于每次创建或销毁引用时，都需要对引用计数进行原子性的加减操作。这个操作虽然看起来简单，但会带来几个问题：

  • 循环引用：在没有程序员干预的情况下无法回收循环引用的对象。

  • 高频操作：即使是简单的函数调用，也可能涉及大量的引用传递，导致频繁的计数修改。

  • 多线程瓶颈：在多线程环境下，为保证数据同步，计数修改必须是原子操作，这比普通操作要慢得多。这也是 Swift 等语言在多线程环境下性能受影响的原因之一。

  • 缓存未命中：当操作一个不经常访问的冷对象时，修改它的引用计数需要将该对象从主内存加载到CPU缓存中，这会造成昂贵的缓存未命中。

传统的、朴素的ARC确实有性能问题，但通过编译器的静态分析和新的编程模型，我们可以消除绝大部分开销，使其性能逼近甚至超越传统的GC。

当前一些的尝试

Lobster语言

https://aardappel.github.io/lobster/memory_management.html

Lobster语言认为传统的垃圾回收（GC）是一种“不优雅”的解决方案，因为它回避了直接追踪对象所有权的问题，而是退而求其次，通过反复扫描大部分堆内存来回收资源。

Lobster语言相信内存管理的未来在于所有权模型。这是对线性类型（每个对象只有一个指针）的泛化，即一个指针“拥有”一个对象并负责其释放，而其他指针仅仅是“借用”它。

内联、值类型结构体

该特性被描述为最好的内存管理形式，因为它完全避免了管理的需要。

  • 使用 struct 关键字声明的对象会被“内联”分配在其父容器（另一个对象、一个向量或栈）的内存中，这与 C/C++ 或 Rust 的做法相似。

  • 这种方法提供了“零抽象成本”，访问结构体字段的开销和访问一个局部变量一样低。

  • 这些结构体通过复制进行赋值，所以不适合大型对象，但对于小型对象则非常高效。

静态所有权分析

  • 观察：一个引用的生命周期完全包含在另一个引用之内，或者它不会逃逸出当前的作用域，那么就没有必要在运行时去增加或减少引用计数了。

  • 工作原理：对于每一个新的堆分配，算法会为其指定一个唯一的“所有者”（通常是第一个被赋值的变量或字段）。所有后续的使用都被视为“借用”。

  • 初始的所有权和所有的借用都不需要任何运行时的引用计数操作。

  • 只有当代码的另一部分需要获得该值的共同所有权时，编译器才会在那个特定的地方插入一次引用计数增加的操作。

  • 效果：这种分析成功地从 Lobster 程序中移除了大约 95% 的运行时引用计数操作。

  • 函数特化：Lobster 的类型检查器有一个独特的功能，它会根据调用者对其参数的所有权需求来“特化”函数。这意味着同一个函数可以有不同的、经过优化的版本，分别处理参数被拥有或被借用的情况，从而最大化效率并防止错误。

Vale 语言

https://verdagon.dev/blog/zero-cost-refs-regions

Vale 编程语言通过结合使用区域和单一所有权来实现零成本引用，目标是在保证内存安全的前提下，达到甚至超越 C++ 的性能。

核心思想：如果我们可以保证一个内存区域内的所有对象在一段时间内是不可变的（只读的），那么在这段时间里，任何指向该区域内对象的引用都是完全零成本的。我们不需要进行任何引用计数操作，因为我们知道这些对象绝不会在这期间被释放。

隐式锁定

当调用一个纯函数（不修改外部状态的函数）时，Vale 编译器可以隐式地将所有外部内存锁定为只读区域。这样，在纯函数内部对这些外部数据的任何读取和引用传递，都没有任何RC开销。这对于处理大量冷数据尤其有效，完全避免了缓存未命中问题。

显式锁定

除了隐式锁定，开发者还可以使用互斥锁Mutex进行更精确的显式锁定。例如，Vale 编译器在工作时，可以将前一阶段生成的抽象语法树放入一个只读的 Mutex 中，如果一个区域被加上了只读锁，那么编译器就可以百分之百确定，在这个锁被解开之前，区域里的所有东西都是绝对安全和不变的。同时在另一个可读写的 Mutex 中构建新的 AST, 这对所有对只读区域中 AST 的引用也都是零成本的。

显式锁定就是通过 Mutex，手动创建出一些被“只读保护”的内存区域。一旦一个区域被只读锁定，那么所有指向该区域内部对象的引用操作都将不需要额外操作，从而极大地提升了性能，尤其是在处理那些需要被频繁读取但不需要修改的大型数据结构时。

池式/竞技场式分配

Vale 还允许为函数内部创建的临时区域指定池式分配器或Arena Allocator。在这个区域内的所有内存分配都变得极其快速（Bump Pointer），并且区域内的对象之间的引用也同样是零成本的。当函数结束时，整个区域的内存被一次性回收，没有单独释放每个对象的开销。

池式分配的好处包括：

  • 极快的分配速度，因为它通常只是移动一个指针，而不是调用昂贵的 malloc。
  • 缓存友好，因为新分配的对象在内存中是相邻的。
  • 可以完全优化掉区域内部所有引用的计数开销。

Koka语言

Koka 是一种强类型、函数式的编程语言，其核心设计理念在于对计算“效果”的精确追踪与管理。它由微软研究院的 Daan Leijen 等人开发，旨在将纯函数式编程的优点与现实世界中不可避免的副作用（如 I/O、异常、状态变化等）进行优雅的结合。

Perceus 引用计数

https://www.microsoft.com/en-us/research/wp-content/uploads/2020/11/perceus-tr-v4.pdf?msockid=370178bfd9b762e1381a6e9ad865639a

Koka 采用了一种名为 Perceus 的先进引用计数算法。Perceus通过一系列创新的编译期优化，如内存复用和代码特化，能够显著减少运行时引用计数的开销，并能优化函数式代码，在可能的情况下自动进行原地更新（in-place update），从而大幅提升性能。这一特性使得 Koka 在保持函数式编程风格的同时，也能达到与 C++ 等底层语言相媲美的内存性能。作者称之为 函数式但原地执行（Functional but In-Place, FBIP）, 这种范式允许程序员用纯函数式风格编写代码，而编译器能自动将其转换为高效的、直接修改内存的指令。

精确引用计数

问题：传统的引用计数（如C++的shared_ptr）通常将对象的生命周期绑定到其“词法作用域”（lexical scope），这意味着对象可能在不再需要后仍然占据内存，直到代码块结束才被释放。这会增加峰值内存使用，并可能降低缓存效率。

Perceus的方案：Perceus采用了更激进的策略，它通过传递引用的所有权，确保对象在最后一次使用后立即被释放。例如，在处理一个大列表时，旧列表的节点会随着新列表的创建而被逐一释放，从而将峰值内存使用量减半。

Drop特化

问题：引用计数的dup（增加计数）和drop（减少计数）操作会带来运行时开销。

Perceus的方案：Perceus通过编译期分析，将drop操作针对特定的数据结构构造器进行“特化”和“内联”。之后，通过dup/drop融合等优化手段，可以消除大量冗余的计数操作。在最常见的情况下（即对象只有一个引用），几乎所有的引用计数开销都能被消除，从而形成一个非常高效的“快速路径”。

基础的drop函数

fun drop(x) {
  if (is-unique(x)) then   // 检查x的引用计数是否为1
    drop children of x;    // 如果是，递归drop它的所有子节点
    free(x)                // 然后释放x自身的内存
  else
    decref(x)              // 如果不是，仅将引用计数减1
}

特例化

if (is-unique(xs)) then       // 内联的检查
  drop(x); drop(xx); free(xs) // 对应 "is-unique" 为 true 的情况
else
  decref(xs)                  // 对应 "is-unique" 为 false 的情况

例子

fun map(xs: list<a>, f: a -> e b): e list<b> {
  match(xs) {
    Cons(x, xx) -> Cons(f(x), map(xx, f)) // Cons(x, xx)（即一个非空节点，包含头元素x和尾列表xx），
                                          // 它会创建一个新的Cons节点。这个新节点的头是f(x)（对原头元素应用函数f的结果），
                                          // 尾是递归调用map处理xx的结果 。
    Nil         -> Nil
  }
}

插入drop指令之后

fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      dup(x); dup(xx); drop(xs)
      Cons(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}

drop特例化

fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      dup(x); dup(xx)
      if (is-unique(xs))
        then drop(x); drop(xx); free(xs)
        else decref(xs)
      Cons(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}

融合 : dup操作被“下推”到if/else分支中。

  • 快速路径：在if (is-unique(xs))为真的分支里，下推的dup(x)和dup(xx)正好与特化产生的drop(x)和drop(xx)相互抵消了。最终，这个分支里只剩下free(xs)！几乎所有的引用计数开销都被消除了 。
  • 慢速路径：在else分支里，所有必要的引用计数操作都被保留，以正确处理共享数据 。
fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      if (is-unique(xs))
        then free(xs)
        else dup(x); dup(xx); decref(xs)
      Cons(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}
复用分析

编译器会分析代码，寻找可以复用内存的机会。具体来说，在模式匹配（match）一个对象时，如果这个对象即将被废弃，并且在分支代码里又创建了一个大小相同的新对象，Perceus会直接复用旧对象的内存来构造新对象。

效果：当被操作的对象是唯一引用时，这种优化能将看似“不可变”的函数式代码，自动转换为高效的原地修改（in-place update）。这极大地减少了内存分配，显著提升了性能，尤其是在处理树等复杂数据结构时。

fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      dup(x); dup(xx);
      val ru = drop-reuse(xs)
      Cons@ru(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}

drop(xs)被替换为val ru = drop-reuse(xs) 。

drop-reuse是一个特殊操作：如果xs是唯一的，它会返回一个指向xs内存的“复用令牌”（reuse token）ru；否则返回NULL 。

Cons@ru(...)：创建新节点时，如果ru不是NULL，就会直接复用ru指向的内存，而不是重新分配 。

复用特化

当一个对象的内存被复用时，如果它的某些字段没有发生变化，编译器会避免对这些字段进行不必要的重新赋值。

fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      dup(x); dup(xx);
      val ru = if (is-unique(xs))
                 then drop(x); drop(xx); &xs
                 else decref(xs); NULL
      Cons@ru(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}

最终融合

fun map(xs, f) {
  match(xs) {
    Cons(x, xx) {
      val ru = if (is-unique(xs))
                 then &xs
                 else dup(x); dup(xx); decref(xs); NULL
      Cons@ru(dup(f)(x), map(xx, f))
    }
    Nil { drop(xs); drop(f); Nil }
  }
}

快速路径：当is-unique(xs)为真时，经过dup/drop融合，所有引用计数操作都消失了。ru直接被赋值为&xs 。这意味着，程序不再释放旧节点再分配新节点，而是直接在旧节点的内存上进行修改 。这个纯函数式的map操作，在运行时变成了高效的原地更新 (in-place update)。

慢速路径：当xs是共享的时，ru为NULL，程序会回退到分配新内存并执行必要的引用计数操作，保证了正确性 。

实际例子：在对红黑树进行插入和平衡操作时，很多节点只有少数指针会改变。通过复用特化，代码在快速路径下只会更新变化的字段，从而节省了大量赋值操作。

其他难题

Perceus利用Koka语言的静态保证来解决引用计数的常见痛点。

  • 并发 (Concurrency)：对跨线程共享的数据进行引用计数需要昂贵的原子操作。Koka的类型系统可以静态追踪哪些数据可能被线程共享。只有在数据被显式传递给新线程时，才会被标记为“线程共享”，并使用原子操作。
  • 循环引用 (Cycles)：在Koka中，由于数据默认是不可变的，循环引用通常只在显式使用“可变引用”时才会出现，而这种情况很少见。此外，由于FBIP的存在，程序员很少需要手动使用可变引用来实现原地修改，进一步减少了循环的可能性。目前，和Swift一样，打破循环的责任留给了程序员。
  • 非线性控制流 (例如异常)：像异常这样的控制流跳转可能导致drop操作被跳过，从而造成内存泄漏。Koka的“类型和效应系统”能将所有非线性控制流（包括异常）在编译时转换为显式的、线性的控制流。例如，可能抛出异常的函数会被编译成返回一个明确的Ok或Error结果的函数。这保证了任何路径下引用计数都是准确的，不会发生泄漏。

HVM Higher-order Virtual Machine

https://github.com/HigherOrderCO/HVM

HVM 是一种为大规模并行计算设计的纯函数式运行时。它的“静态懒克隆”是一种更为激进的优化策略，其核心思想是：只要数据是不可变的，就永远不要急着去复制它，尽可能地共享它。

工作原理如下：

  • 克隆即引用：当 HVM 需要“克隆”一个不可变的数据结构时，它并不会真的去复制内存中的数据。相反，它只是简单地创建了一个指向原始数据的新引用（指针）。

  • 不可变性的保证：因为原始数据是不可变的，所以让多个引用指向同一块内存是绝对安全的。无论谁通过引用来读取数据，读到的内容都是一样的，且永远不会改变。

  • 按需复制（Copy-on-Write 的变体）：真正的复制操作被推迟到绝对必要的时候。在纯函数式的 HVM 中，这个“必要的时候”甚至可能永远不会到来。如果是在一个支持可变性的混合模型中，那么只有当某个持有引用的代码试图修改数据时，才会触发一次真正的物理复制（这就是所谓的“写时复制”）。

ARC 与 Tracing GC的比较

性能与开销的争论

  • Tracing GC 的优势：现代的Tracing GC在吞吐量上通常优于ARC。GC可以移动和压缩内存，从而提高缓存局部性并解决内存碎片问题。此外，其写入屏障的开销比ARC所需的原子性引用计数操作要低。

  • ARC 的优势：现代ARC（如Swift中的实现）通过所有权和借用检查等技术，可以优化掉绝大多数的引用计数操作，使得许多对象可以直接在栈上分配。这使得ARC在性能上可以与GC竞争。此外，苹果的M1芯片等硬件对ARC操作进行了硬件优化，使其执行速度非常快。

fun fact: retaining and releasing an NSObject takes ~30 nanoseconds on current gen Intel, and ~6.5 nanoseconds on an M1

确定性还是速度

  • ARC提供了确定性的、即时的对象销毁，这对于管理非内存资源（如文件句柄、锁、数据库连接）至关重要，因为资源可以被立即释放。
  • GC则提供了更高的整体吞吐量，但其回收时机是不确定的，可能会引入不可预测的暂停（pause），这对于实时系统（如音频处理）是不可接受的，并且依赖 GC 来释放关键外部资源是一种糟糕的做法。

开发者体验与循环引用

  • 虽然ARC简化了手动内存管理，但开发者仍需手动使用weak或unowned引用来打破循环引用，否则会导致内存泄漏。
  • 相比之下，追踪式GC能自动处理循环引用的问题，让开发者完全不必担心对象生命周期，一些人认为这带来了更简单的开发体验。

总结

ARC因其确定性和对系统资源的即时释放而在系统编程和客户端应用（尤其是苹果生态）中备受青睐。而GC则因其高吞吐量和自动处理循环引用的便利性，在服务器端和企业级应用中占据主导地位。