đź“–Perceus: Garbage Free Reference Counting with Reuse (Extended version)

authors
Reinking, Alex and Xie, Ningning and de Moura, Leonardo and Leijen, Daan
year
2020
url
https://www.microsoft.com/en-us/research/publication/perceus-garbage-free-reference-counting-with-reuse/
  • Perceus: precise reference counting with reuse and specialization
  • implemented in Koka
  • enables reuse analysis, so immutable data can be updated in-place when possible
  • the cost of tracing GC is linear in live data. the cost of ref counting is linear in the number of ref counting operations — Perceus tries to minimize ref counting operations.
    • with concurrency, reference counting needs to be atomic, which is expensive. for concurrency, the algorithm tracks when object can become thread-shared
    • cycles are still an issue, although in Koka they can only occur where mutation is used (which is infrequent in mostly-functional language)
  • Perceus is precise reference counting—the data is dropped as soon as no more references remain. This is different to most other implementation where liveness is tied to lexical scope (typical ref counter implementation. e.g., shared_ptr / Rust’s Rc)

    • Perceus is more aggressive and passes ownership to functions downward.

      In the code below, xs ownership is passed to map, and ys ownership is passed to print (and freed inside print).

      fun foo() {
  val xs = list(1,1000000) // create large list
  val ys = map(xs, inc) // increment elements
  print(ys)
}
  • Reuse analysis allows implicit guaranteed in-place mutations if reference is unique. If reference is shared, it falls back to copying, so persistent data structures can still be used.
  • p.7 Ungar et al. [47] report slowdown up to 50% when atomic reference counting operations are used.
  • p.8 In Koka, reference cycles are still an issues and it’s programmer’s responsibility to break cycles. (similar to Swift)