并行折叠

# 并行折叠 来源：https://okmij.org/ftp/Algorithms/map-monoid-reduce.html ## 与幺半群一起的并行乐趣 玩弄幺半群，并亲自发现它们如何频繁地以各种伪装出现，以及有多少东西可以用它们来表达，这是一种乐趣。它不仅让那些重要但坦率地说很无聊的数据分析工作变得明亮起来。它不仅仅挑战我们去发现高效的（具有常数时间和空间操作的）幺半群，这需要 ingenuity。用 Guy Steele 的话来说，发明高效的结合性组合运算符是*一件大事*。一个高效的幺半群开启了并行实现——不仅仅是并行，而是令人尴尬的并行：输入序列任意地分发给工作进程，所有工作进程并行运行，没有竞争、依赖，甚至没有内存 bank 冲突。这是多核、GPU 或分布式处理的理想情况。 我们将展示为什么幺半群是一件大事，也是一种巨大的乐趣——甚至比预期的还要大。Horner 规则和 Boyer-Moore 多数投票——通常被认为是典型的内在顺序算法——结果却是幺半群，因此可以令人尴尬地并行化。当我们把幺半群推广到可观察幺半群时，我们发现了一种新的、垂直的组合方式，使得能够直接在反序列化的（大）数据上进行高效的迭代分组和聚合，无论是在多核还是多处理器上。 - 引言：折叠 vs 幺半群规约 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#intro) - 折叠作为 map-reduce，平凡的 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#trivial) - 折叠作为 map-reduce，更有趣的 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#simple) - 广义 Horner 规则 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#Horner) - Boyer-Moore 多数投票 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#BM) - 嵌套分组-聚合：垂直幺半群组合 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#nested-agg) - 热身 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#nga.warm-up) - 一点代数 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#monoid-algebra) - 垂直幺半群组合 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#vertical-composition) - 为嵌套分组-聚合生成并行 map-reduce (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#nga.gen) - 结论 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#conclusions) --- ## 引言：折叠 vs 幺半群规约 在 ICFP 2009 上，Guy Steele 做了一个主题演讲，称 \`\`foldl 和 foldr 被认为有点有害''，并提倡 (map)reduce 来替代。 回想一下，对一个序列进行折叠是一个固有的顺序有状态累积；为了具体起见，使用列表，定义为： `` fold_left : ('z -> 'a -> 'z) -> 'z -> 'a list -> 'z fold_right : ('a -> 'z -> 'z) -> 'a list -> 'z -> 'z `` 实际上有两种操作：左折叠和右折叠。它们的含义应该从以下例子中清楚： `` fold_left (+) 0 [1;2;3;4] ≡ (((0 + 1) + 2) + 3) + 4 fold_right (+) [1;2;3;4] 0 ≡ 1 + (2 + (3 + (4 + 0))) `` 在这种情况下，折叠函数是加法，结果是相同的：两个表达式都对列表求和。一般来说，左折叠和右折叠会产生不同的结果：例如，尝试用减法作为折叠函数。列表元素类型`'a`和累加器类型`'z`不必相同：例如， `` fold_left (fun z _ -> z + 1) 0 l `` 计算任何列表的长度， `` fold_left (fun z x -> x :: z) [] l `` 反转列表`l`，以及 `` fold_right (fun x z -> if p x then x::z else z) l [] `` 过滤列表：忽略谓词`p`返回`false`的元素。许多其他对列表的操作（事实上，所有操作）都可以表示为折叠。折叠确实是序列顺序有状态处理的一般模式。 折叠还有其他定义：有时右折叠的最后两个参数会交换。如果右折叠函数的参数也相应交换，那么左折叠和右折叠具有相同的签名。但它们的行为，即结合模式，仍然是不同的。Olivier Danvy，见下文，追溯了列表折叠和参数顺序的历史。 为了具体起见，我们展示了列表上的折叠，但在数组、流、文件、树、字典和任何其他集合上也有类似的操作。 在本文中，我们所说的规约总是指幺半群上的规约。幺半群是一个集合（称为 \`载集'），带有一个结合性二元操作，该操作有一个中性（也称为单位或零）元素。具体来说，在 OCaml 中： `` type 'a monoid = {zero: 'a; op: 'a -> 'a -> 'a} `` 其中`'a`是幺半群元素的类型，`op`必须是结合性的，并且 `` op zero x = op x zero = x `` 必须对幺半群中的每个元素`x`成立。在 Google MapReduce 中，操作`op`通常也被认为是可交换的。我们不施加这样的要求。 对序列（此处为列表）进行规约是操作 `` reduce : 'a monoid -> 'a list -> 'a `` 它的行为可以示例如下： `` reduce monoid [] ≡ monoid.zero reduce monoid [x] ≡ x (* 对于任何 x 和幺半群 *) reduce {zero=0;op=(+)} [1;2;3;4] ≡ 1 + 2 + 3 + 4 `` 可以说，规约将幺半群操作“楔入”序列的连续元素之间。由于`op`是结合性的，括号不是必需的。因此，与左折叠和右折叠不同，只有一个规约。 我们将看到规约通常与 map 预先组合。这两个操作总是可以融合成 `` map_reduce : ('a -> 'z) -> 'z monoid -> 'a list -> 'z `` 尽管如此，为了清晰起见，我们将分别编写 map 和 reduce，假设实际实现使用高效的融合操作。（map 和 reduce 经常一起出现并非偶然：正如 Fegaras 和 Maier 所解释的，`map_reduce`是一个幺半群同态。） 折叠必须顺序求值，因为对累加器存在数据依赖。事实上，左折叠只是另一种`for`循环的表示： `` type 'a array_slice = {arr:'a array; from:int; upto:int} let fold_left_arr : ('z -> 'a -> 'z) -> 'z -> 'a array_slice -> 'z = fun f z {arr;from;upto} -> let acc = ref z in for i=from to upto do acc := f !acc arr.(i) done; !acc `` 这里，为了多样化，我们使用数组切片作为序列。另一方面，规约有多种实现方式。它可以顺序执行： `` let seqreduce_arr (m: 'a monoid) (arrsl: 'a array_slice) : 'a = fold_left_arr m.op m.zero arrsl `` 或者可以并行完成（请参见嵌套分组-聚合：垂直幺半群组合 (https://okmij.org/ftp/Algorithms/map-monoid-reduce.html#nested-agg) 末尾的真实示例）： `` let rec parreduce_arr (m: 'a monoid) {arr;from;upto} : 'a = match upto+1-from with | 0 -> m.zero | 1 -> arr.(from) | 2 -> m.op arr.(from) arr.(from+1) | 3 -> m.op (m.op arr.(from) arr.(from+1)) arr.(from+2) | n -> let n' = n / 2 in (* 这里，两个 parreduce_arr 调用可以并行完成！ *) m.op (parreduce_arr m {arr;from;upto=from+n'-1}) (parreduce_arr m {arr;from=from+n';upto}) `` 递归情况下的两个`parreduce_arr`调用可以并行运行——令人尴尬地并行，没有竞争，甚至没有读依赖。它们是否应该并行执行是另一个问题——我们可以根据具体情况决定。例如，如果数组切片很短，两个`parreduce_arr`调用最好顺序完成（因为并行求值始终存在的开销会占主导地位）。如果切片的两半也被并行规约，我们会得到一种层次分解：二叉树般的处理。 我们不必递归地分解切片。我们可以将输入数组切分成一系列不重叠的切片，任意地，并将它们分配给可用的核心。核心可以随心所欲地完成分配的工作，无需与其他核心同步。最后，我们使用幺半群操作组合它们的结果。 由于（左或右）折叠使我们局限于顺序求值，Guy Steele 称其为“有点有害”。他敦促尽可能使用规约，因为它很灵活，并将算法与执行策略解耦。策略（顺序、并行、分布式）和数据分区可以在以后根据情况和可用资源来选择。 因此，主要问题是：我们能否将折叠转换为规约？文章的其余部分将回答这个问题。 #### 参考文献 Guy Steele: Organizing Functional Code for Parallel execution or, foldl and foldr considered slightly harmful August 2009 (ICFP 2009, Keynote) Olivier Danvy: \`\`Folding left and right matters: direct style, accumulators, and continuations'' Journal of Functional Programming, vol 33, e2. Functional Pearl, February 2023 Appendix A: A brief history of folding left and right over lists 根据 Danvy 的说法，`fold_left` 和 `fold_right` 的第一个实例是由 Christopher Strachey 在 1961 年（！）研究的。Reduce 是 APL 的一部分（Iverson, 1962），在那里它被称为 '/'：因此 `+/x` 对数组 `x` 求和。系统 T 中的 Goedel 递归子 R 是折叠（现在称为 para-fold）的更一般版本。Church 数字是折叠。 monoid_reduce.ml (https://okmij.org/ftp/Algorithms/monoid_reduce.ml)[26K] 文章的完整代码 How to zip folds (https://okmij.org/ftp/Streams.html#zip-folds) 一个完整的折叠表示列表库，演示所有列表处理操作都可以表示为折叠 Accumulating tree traversals, a better tree fold (https://okmij.org/ftp/Scheme/xml.html#Papers) with applications to XML parsing 幺半群规约有时被称为 \`大运算符'（类似于求和与乘法的资本 Σ 和 Π）。另一个名称是 \`埃因霍温量词'。 人们可能认为 Haskell `Foldable` 类中的 `foldMap` 也相关：它也涉及幺半群规约。然而，`foldMap` 被指定为显式的右结合运算符，因此缺乏 Guy Steele 强调的 map-reduce 的主要特性：将规范与实现解耦。有人可能会说 `Foldable` 类型类本身应该受到指责：根据它，一个集合只有一个 `foldMap`，而实际上对于同一个集合可能存在许多规约实现。 ## 折叠作为 map-reduce，平凡的 主要问题是用 `reduce` 来表达 `fold_left` 和 `fold_right`。在本节中，我们看到了两个平凡的答案。事实上，我们看到折叠*总是*可以用规约来表达——但以一种无用或无趣的方式。 如果折叠函数（折叠的第一个参数）是可结合的（这意味着序列元素的类型与累加器/结果类型相同）并且有一个零元素，那么折叠显然是规约的一个实例。我们已经看到了例子： `` fold_left (+) 0 l ≡ fold_right (+) l 0 ≡ reduce {op=(+);zero=0} l `` 对于任何列表 `l`。 第二个平凡答案是折叠总是可以用幺半群规约无条件地表达： `` fold_right f [1;2;3;4] z = f 1 (f 2 (f 3 (f 4 z))) = (f 1 · f 2 · f 3 · f 4) z = map f [1;2;3;4] |> reduce fun_monoid |> (fun h -> h z) `` 其中 `` let fun_monoid = {op=(fun g h -> fun x -> g (h x)); zero=Fun.id} `` 对于任何 `f`、`z` 和适当类型的集合。可以写出非常类似的表达式用于左折叠（留给读者作为练习）。关键思想是函数组合是可结合的。 不幸的是，这个平凡的答案几乎没有实际用途。正如例子所示，`map (f:'a -> 'z -> 'z) [1;2;3;4]` 创建了一个闭包列表 `[f 1; f 2; f 3; f 4]`，`reduce` 将它们组合成一个大的闭包 `(f 1 · f 2 · f 3 · f 4)`，最后应用于 `z`。组合后的闭包 `(f 1 · f 2 · f 3 · f 4)` 具有与原始列表相同的结构——因此大小相同（实际上要更大几倍：我们不仅要存储列表元素本身，还要存储函数指针 `f`，再加上开销）。实际上，我们构建了一个大小无界的中间数据结构。尽管组合闭包可以并行化，但只有在最终将大的闭包组合应用于初始累加器 `z` 时，才完成有用的工作——此时折叠函数 `f` 逐步应用，顺序地，就像在原始的 `fold_right f l z` 中一样。这种对折叠的平凡规约只是浪费时间和空间。 因此，问题不仅仅是将折叠表达为规约，而是要高效地做到这一点，没有过度的或无界的开销。只有这样，我们才能有利可图地并行折叠。 #### 参考文献 Jeremy Gibbons: Origami Programming for Fun and Profit <https://www.cs.ox.ac.uk/publications/publication16637-abstract.html> 将折叠解释为 `fun_monoid` ## 折叠作为 map-reduce，更有趣的 因此，我们的问题是*高效地*将折叠表示为规约，没有无界的中间数据，也不花费过多的时间。换句话说，如果折叠对每个序列元素以常数时间和常数（工作）空间工作，那么规约也应该如此。 有时这个问题可以简单地解决。我们已经看到了一个这样的案例：折叠函数是可结合的并且有中性元素。那么左折叠和右折叠就是规约的实例。更有趣一点的是折叠函数 f 可以分解为另外两个函数 `op` 和 `g`： `` f z x = op z (g x) `` 对于任何序列元素 `x` 和累加器 `z`。这里 `op` 是一个可结合的操作，并且有一个零元素。作为一个例子，回忆一下求列表的长度，用折叠表示为： `` List.fold_left (fun z _ -> z + 1) 0 l `` 折叠函数确实可以分解： `` z + 1 = z + (Fun.const 1 x) `` 因此长度可以重写为： `` map (Fun.const 1) l |> reduce {op=(+);zero=0} `` 或者作为 `map_reduce`。因此，长度可以并行计算。 这样的分解是 Guy Steele 演讲中称为 \`\`共轭变换''的一般原理的一个实例。该原理要求将折叠表示为： `` fold_left (f:'z->'a->'a) (z:'z) l = map g l |> reduce m |> h `` 对于右折叠类似。这里 `m:'u monoid` 是某个类型 `'u` 的幺半群，而 `g:'a->'u` 和 `h:'u->'z` 是一些函数。它们通常依赖于 `f` 和 `z`。非正式地说，该原理建议我们寻找一个 \`\`更大的''类型 `'u`，它可以嵌入 `'a` 和 `'z`，并且承认一个合适的可结合操作，带有中性元素。 正如我们在上一节中看到的，人们总是可以用这种方式表示折叠：我们选择了 `fun_monoid` 作为 `m`，以 `'z->'z` 作为类型 `'u`。 共轭变换是一个原理，或者一个模式。它并没有告诉如何实际找到*高效的*幺半群，甚至没有说明它是否存在。事实上，找到高效的幺半群通常是不平凡的，需要 ingenuity。作为一个例子，考虑前面提到的减法折叠。减法不是可结合的，因此 `fold_left (-)` 不是规约的一个实例。稍加思考，可以看出： `` fold_left (-) z l = z - fold_left (+) 0 l = z - reduce {op=(+);zero=0} l `` 根据共轭变换模式，函数 `g` 是取反，`h` 是加上 `z`。再稍加思考，可以看出 `fold_right (-)` 不能如此容易地（或者根本不能？）被规约。实际上，右减折叠也可以高效地并行执行，作为一个幺半群规约。鼓励读者找到这个幺半群——以赞赏