今天我学到了

2024 年 9 月 5 日

可快照数据结构

ICFP 24 的论文 Snapshottable Stores 描述了一种可快照的数据结构。

这里可快照的意思就是，可在任意时刻去保存数据结构的一个状态，称之为快照，并允许之后将数据结构恢复到这一快照对应的状态。这两个操作都应该是相对廉价的。（否则你总是可以复制整个数据结构并在之后进行替换，但这样操作的时间和空间开销都太大了！）

本文只考虑了对可变引用的快照。对于不可变引用，其本身就是可持久化的，因此并不需要做特殊的处理。尽管如此，还有有一些可以拓展的地方，比如对可变数组的修改等。

核心算法来自于 Baker 的 Version Tree (1978)。我们需要一个树状的 store 结构来记录历史信息。快照也就是特定时刻的版本树，捕获快照只需要记录特定时刻的树根即可。

对任意可变引用 \([r \mapsto x_1]\)，若要更新其新值为 \(x_2\)，我们创建一个新树根 new_root = ref Mem，将旧树根代表的节点对应内容更新为 Diff(r, \(x_1\), new_root)，同时将 Store 的树根更新为 new_root。因为我们已经记录了引用之前指向的值，此时即可覆写引用指向新值 \(x_2\)。

恢复快照可以分为两种情况，其中一种为快照即是当前状态，所以我们什么都不需要做。

另一种情况下，快照的节点指向了一棵子树（包含快照后所做的修改历史），引用的新值即为快照树节点中记录的值。此外，我们需要遍历历史，将这一历史反向链接。也就是说， 对于修改链 \([r \mapsto x_1][r \mapsto x_2][r \mapsto x_3]\)，若要恢复到 \(x_2\) 状态，我们会生成一个新的树，包含有两条链，分别为 \([r \mapsto x_1][r \mapsto x_2]\) 和 \([r \mapsto x_3][r \mapsto x_2]\)。

以上内容大致概括了 Baker 的工作，而这篇 ICFP 24 的新贡献包括一个被称作 Record Elision 的重要优化。

Record Elision

其核心思想是，如果我们可以确定两次 set 间并没有快照发生，那我们根本不需要分别为两次 set 创建对应的日志节点，而是共享一个节点。

为此我们需要为引用、快照、树节点和 store 树都增加一个 field 记录当前代数。如果进行了快照，则递增代数。当进行 set 操作时，我们先检查当前树根的代数，如果发现相等，则直接进入 fast path，更新引用即可。否则进入 slow path，更新引用、记录修改并更新代数。

2024 年 8 月 26 日

OCaml 的一些新加入或即将加入的语言特性

OCaml 这个语言就是有一点神奇，说古老也古老，但是这几年在 Jane Street 财主的扶持下也开始加了很多有意思的新特性，这里简单总结一下。

代数效果

重量级特性，介绍的文本有很多，就不多说了。

模态内存管理

名字来源自 Graded Modal Calculus 分级模态演算，具体是啥咱也不知道。

在这个类型系统里有三个Mode 模式，分别为 Affinity, Uniqueness, 和 Locality

• Affinity: Many | Once
• Uniqueness: Unique | Shared
• Locality: Global | Local

模式作为类型修饰符的时候，可以放到函数类型的箭头的任意一侧，或者同时两侧。如果没有模式的修饰符，则认为有遗留/默认模式 （分别为 many, shared, global, 对应经典 OCaml 的行为。如 graph @ local -> string @ unique

模式也可以附着于变量绑定时的模式上，如 let f (x @ unique) = ... in ...

但是在没有函数箭头时使用是没有意义的，如 type t = string @ shared

同时定义三个模态 many, shared, global 来表示模式三元组间的变换

shared (a, u, l) = (a, shared, l)
many (a, u, l) = (many, u, l)
global (a, u, l) = (a, shared, global)
    

注意到这里 global 模态会同时将 uniqueness 变为 shared，这是为了允许借用 borrowing 存在的健全性考虑的。

可以给 record 的 field 标注模态，如 type 'a shared = { s : 'a @@ shared }。

如果 record r 本身具有模式 m，且 field f 具有模态 n，则称 r.f 具有模式 n(m)。

Uniqueness 单一性

其中 uniqueness 允许安全的进行 in-place 更新，也就是最近很火的 reuse。 这里不等同于传统 OCaml 的 mut 关键词带来的可变性。 基于 uniqueness 的可变性在语义上仍然是函数式的，不会引起外部状态的改变。

有一个示例如下：

type 'a list = Nil | Cons of { hd : 'a; tl : 'a list }
let rec rev_append xs acc =
  match xs with
  | Nil -> acc
  | Cons x_xs -> rev_append x_xs.tl (Cons { overwrite x_xs with tl = acc })
    

上述片段如果传入的列表并不是 unique 的话，则是有问题的，因此我们希望 reverse 具有如下类型：

let reverse xs = rev_append xs Nil
val reverse : 'a list @ unique -> 'a list @ unique
    

这里的 unique 表明，在任意时间，程序里只存在一个对 unique 值的引用。

Uniqueness 是一个 深 属性，也就是说 unique 值的各个组成部分必须也是 unique 的。

Affinity 仿射性

需要注意到光有 uniqueness 是不够的，因为我们仍然轻松构造出有问题的代码。

let rejected =
  let xs @ unique : int list = [1;2;3] in
  let f = fun zs -> rev_append xs zs in
  let ys = f [4] in
  let zs = f [5] (* Oh no! zs and ys refer to the same memory! *)
  in ...
    

例如这里的函数闭包 f，持有了唯一的对 xs 的引用； 即便我们让 f 亦为 unique，我们也不能阻止对 unique 调用两次，最终获得预期之外的结果（因为 xs 被反转了两次）。

因此引入了 affinity，我们使用此模式来限制对值使用的次数。

它和 uniqueness 的核心区别在于，uniqueness 是对过去的总结；而 affinity 是对未来的限制。

为了让上文代码正确，我们选择让 f 变为 once 模式，从而拒绝以上代码。

... let f @ once = fun zs -> rev_append xs zs in ...
    

Locality 局部性

最后一个模式为 locality, 用于控制值的生命周期不能超过当前 region。

如果能确保这一性质，那就自然地可以将不逃逸出 region 的值分配在 stack 上，获取一定的性能优势并降低对 GC 的压力。

Borrowing 借用

由于现在我们可以确保值不会逃逸出区域，我们可以在某个 region 内安全地借用一个 unique 的值。

例如我们可以定义如下的 borrow 函数

val borrow : 'a @ unique -> ('a @ local -> 'b) -> ('a * 'b shared) @ unique
let borrow x f =
  let result = f &x in
  x, { s = result }
    

之前我们提到 global 隐含了 shared, 这是为了避免我们将一个 unique 值放入具有 global 模态的 record field, 然后又将其作为 unique 值提取出来，从而导致 unsound 的程序语义。

or_null 类型

很多语言都会使用可以为 null 的值来作为 option 类型的一种替代品，但是对于 int option option 这种嵌套类型来说只有一个 null 就显得无能为力了。

那如果反其道而行之，我们只需要一个 null，应该如何设计对应的类型呢？这个 or_null 类型的设计很好地体现了相关的一些考量。

为了区分我们是否还可以使用 null，我们将类型分为两类，一种被称作 no-null type， 也就是说其对应的底层表示中并没有使用和 null 相同的模式（例如为一个全 0 的值）， 例如 string, int 等。 另一种是 with-null type，和上述内容刚好相反。 所以对于 'a or_null 类型，我们希望 'a 是 no-null 的。

在拥有 or_null 类型后，自然地我们可以利用 OCaml 里全 0 表示并不对应任何值的现状，使用该模式表示 null，有效减少了堆分配。

不过在抽象类型和类型参数的默认类别应该是 no-null 还是 with-null 的问题上，还有一些问题需要澄清。 另外 OCaml 的 float array 非常特别，也需要特殊处理。

扁平化字段

这是一个比较简单的改动，允许用户手动指定一些 field 为未装箱或不需要扫描的。代价是牺牲了 generic 的 compare 操作。

实现上需要在对象头里记录一个数值指定需要扫描的 field 数量。此外需要 layout 重排，将不需要 scan 和需要 scan 的 field 分为两个区域。

2024 年 8 月 24 日

关键词：SIMD, SWAR, Parsing

问：给定二进制串 \(00010010\)，如何获取两个 1 之间的位全置为 1 的二进制串？

答：使用 \(\oplus\) 操作计算前缀和： $$ 00010010 \oplus 00100100 \oplus 01001000 \oplus 10010000 \oplus 00100000 \oplus 01000000 \oplus 10000000 = 00001110 $$ 这一操作也等价于 Carry-less Multiplication 或 Xor Multiplication。

问：给定二进制串 \(00110100\), 如何判断一或多个 1 的起点（终点）？

答：左（右）移取反后按位与即可。 $$ \~~(00110100 \verb|<<| 1)~\&~00110100 = 10010111~\&~00110100 = 00010100 \\ \~~(00110100 \verb|>>| 1)~\&~00110100 = 11100101~\&~00110100 = 00100100 $$

关于内联优化：有一个 g x，其中我们将 j x 视为一个汇合点

      
g x = let j x = f x
      in case x of A → j 1
                   B → j 2
      
    

如果在另一个函数 a 中我们调用 h (g x)，那么在内联 g 后可能会想到将的调用推入 g 的分支：

      
a x = h (g x)
→
a x = let j x = f x
      in case x of A → h (j 1)
                   B → h (j 2)
      
    

但这样我们就失去了对汇合点可以尾调用的性质。为了避免这种情况，我们需要将 h 直接推入汇合点。

      
a x = let j x = h (f x)
      in case x of A → j 1
                   B → j 2
      
    

从另一个角度理解（将跳转到汇合点视为跳转到一个 basic block）：

flowchart TD;
he(h _) --> ge
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> gexit(f x)
cB --> gexit
    

正确的变换会产生如下的控制流图：

flowchart TD;
he(h _) --> gexit(f x)
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> he
cB --> he
    

而只推一半意味着（在保证是跳转到汇合点而不是调用函数的前提下）会产生如下的不可能存在的控制流图：

flowchart TD;
gexit(f x) -->|case A?| heA(h _)
gexit --> |case B| heB(h _)
ge(g x = case x) -->|case A| cA(j 1)
ge -->|case B| cB(j 2)
cA --> gexit
cB --> gexit