一句话：提出嵌入式 RRB-Tree 的 C++ 持久向量实现，把持久数据结构与瞬时批量更新引入系统编程。
持久化数据结构（如 Clojure/Scala 的不可变序列）具备高效查找、更新、拼接和切片，但主要惠及托管的高级语言。本文将其引入系统编程：用 C++ 实现通用高效的不可变向量，支持 transient 批量更新，并可集成到带 C 核心的语言运行时（如 Guile、Racket、Python、Ruby）。论文提出 ERRB-Tree，可高效存储任意非装箱类型；给出与紧凑树表示优化正交的树操作技术；用策略化设计支持多种内存管理与回收机制（GC、引用计数）；定义基于移动语义和引用计数的 transient 模型，并将其扩展至合流 meld 操作。评估显示，许多情况下性能可与可变数组相当，同时保留函数式用法。
Relaxed Radix Balanced Trees (RRB-Trees) is one of the latest members in a family of persistent tree based data-structures that combine wide branching factors with simple and relatively flat structures. Like the battle-tested immutable sequences of Clojure and Scala, they have effectively constant lookup and updates, good cache utilization, but also logarithmic concatenation and slicing. Our goal is to bring the benefits of persistent data structures to the discipline of systems programming via generic yet efficient immutable vectors supporting transient batch updates. We describe a C++ implementation that can be integrated in the runtime of higher level languages with a C core (Lisps like Guile or Racket, but also Python or Ruby), thus widening the access to these persistent data structures. In this work we propose (1) an Embedding RRB-Tree (ERRB-Tree) data structure that efficiently stores arbitrary unboxed types, (2) a technique for implementing tree operations orthogonal to optimizations for a more compact representation of the tree, (3) a policy-based design to support multiple memory management and reclamation mechanisms (including automatic garbage collection and reference counting), (4) a model of transience based on move-semantics and reference counting, and (5) a definition of transience for confluent meld operations. Combining these techniques a performance comparable to that of mutable arrays can be achieved in many situations, while using the data structure in a functional way.
@article{Puente17,
title = {Persistence for the masses: RRB-vectors in a systems language},
author = {Juan Pedro Bolívar Puente},
journal = {Proceedings of the ACM on Programming Languages},
volume = {1},
number = {ICFP},
year = {2017},
doi = {10.1145/3110260}
}