展开后折叠的 OCaml 优化

Question

有一个众所周知的编译器优化，展开后跟折叠，称为 hylomorphism（换句话说：循环）。简单地说，不是构建一个结构并在之后立即销毁它，而是将折叠函数直接插入结构的生成器，这会导致一个就地循环，根本不会在内存中创建结构。

例如，要对用户输入的一些数字求和，我们可以这样做

let sumInput () : int =
  List.fold_left (+) 0
    (List.init 1875 (fun _ -> read_int ()))

中间结构是存储输入数字的列表，由List.init构建。我希望 OCaml 的本机编译器 ocamlopt 将其优化为尾递归循环，如

let optimSumInput () : int =
  let rec optimInput_rec count sum =
    if count = 0 then sum
    else optimInput_rec (count-1) (sum + read_int ()) in
  optimInput_rec 1875 0

然而，ocamlopt -s 生成此汇编代码，我们在其中看到 camlStdlib__list__init 和 camlStdlib__list__fold_left：

camlTestOptim__sumInput_80:
    .cfi_startproc
    subq    , %rsp
    .cfi_adjust_cfa_offset 8
.L102:
    movq    camlTestOptim__3@GOTPCREL(%rip), %rbx
    movq    51, %rax
    call    camlStdlib__list__init_204@PLT
.L100:
    movq    %rax, %rdi
    movq    , %rbx
    movq    camlTestOptim__2@GOTPCREL(%rip), %rax
    addq    , %rsp
    .cfi_adjust_cfa_offset -8
    jmp camlStdlib__list__fold_left_250@PLT
    .cfi_adjust_cfa_offset 8
    .cfi_adjust_cfa_offset -8
    .cfi_endproc
    .type camlTestOptim__sumInput_80,@function
    .size camlTestOptim__sumInput_80,. - camlTestOptim__sumInput_80

是否有可以优化列表的编译器开关？在此特定示例中，它不会加速太多，但对于比列表更复杂的结构，它会有所作为。

Answer 1

目前没有这样的开关。您可能需要使用 Stream Fusion 库，例如 Strymonas Streams (see OCaml implementation).

When the execution reaches the run method, an optimized version of the stream will be compiled (emitted) and executed [...]. The resulted code will consist of a tight, for-loop.

库无法访问编译器的内部，这可能会限制它与语言集成的程度以及字节码或本机代码的生成方式。但这也使核心语言变得简单且具有直截了当的语义。

作为编译器中的优化通道，它会优化一些表达式而不是其他表达式；用户（开发人员）可能更难提前猜测代码在运行时的行为方式（例如，看看尾调用消除已经有多混乱）。在维护方面（例如测试、forward/backward 兼容性），它作为编译器功能也有成本。

这是一些可能的原因，加上缺乏资源，目前还没有直接在编译器中进行优化，也许一开始就不可取。

Answer 2

不，OCaml 的优化编译器没有进行此类优化，而且可能永远不会进行。这回答了发布的问题。以下是我个人的意见，这不是答案，而是我认为对于正确理解语言以及为什么不应期望进行此类优化所必需的评论。

OCaml 的优化编译器以其可预测性和高效地将功能程序编译为机器代码的能力而闻名。然而，它不会将糟糕的程序翻译成好的程序，因为编译器严格遵循语言的语义并相信程序员知道他们在做什么。与 Haskell 不同，OCaml 是一种严格的命令式语言，具有更强的语义。与 Haskell 相比，它为程序员提供了对执行过程更多的控制权，但这当然是有代价的，因为某些优化即使不是不可能实现也很难实现。在 OCaml 中，默认情况下所有表达式都是不纯的（有效的），因此为了删除表达式并用其值替换它，编译器必须证明在此过程中没有丢失任何效果。来自 Haskell 领域时我们应该牢记的另一个重要方面是 OCaml 是严格的并且 OCaml 列表也是严格的归纳数据类型。因此，虽然在 Haskell 中使用按名称调用语义和惰性列表，这种优化可以看作是自然的，但在 OCaml 中，它就太过分了，本质上会违反程序员和编译器之间的契约。

由于 OCaml 为我们程序员提供了对执行过程更多的控制，我们有许多不同的数据结构，它们在数学上是同构的，但提供了不同的权衡。作为程序员，我们的任务是选择最能反映我们的需求和约束的表示。鉴于您的具体示例，选择列表作为基础数据结构有点奇怪且不合理。但是，编译器信任程序员，如果程序员决定在这里使用列表，它会按照要求执行。

经验丰富的程序员会在这里选择更好的数据结构，例如 Core 的 Sequence.t 或 Lwt 的流，或者只是标准的 Seq.t 迭代器，

let rec ints () = match read_int () with
  | exception End_of_file -> Seq.Nil
  | s -> Seq.Cons (s,ints)

我们可以定义整数和为

let sum = Seq.fold_left (+) 0

因此我们的 main 函数看起来像

let main () =
  print_int (sum ints);
  print_newline ()

此代码不会创建任何中间列表，因此会自然地应用森林砍伐，我们不必依赖晦涩的编译器优化。

这种与 Haskell 的区别划清了编程和纯数学之间的界限，因为虽然不同种类的列表在数学上是等价的，但从程序员的角度来看，有大量不同的实现。

因此，OCaml 依靠程序员做出这个选择，而不是试图比人类更聪明。另一方面，它提供了一个非常强大的抽象机制，它是 Sigma-algebras 的具体化，它让我们可以反对抽象编程，并且在我们想要的时候留在纯数学的世界，而在需要的时候 return 回到地球。是绝对必要的。

展开后折叠的 OCaml 优化

OCaml optimization of unfold followed by fold

ocaml

compiler-optimization