模式匹配和 if-else 的性能差异

Question

为什么 OCaml 可以为模式匹配生成高效的机器码而不是 if-else 测试？

我在阅读 Real World OCaml 时遇到了 this 部分，他们将模式匹配的性能与 if-else 测试的性能进行了比较。事实证明，他们示例中的模式匹配比 if-else 测试快得多。尽管代码没有使用任何 if-else 测试无法实现的特殊模式匹配情况，它只是比较整数。

他们将模式匹配的编译器优化归因于性能差异的原因。编译器将能够生成机器代码，根据一组有效选择的运行时检查直接跳转到匹配的大小写。

我明白这一点，但我真的不明白为什么编译器不能为 if-else 测试做同样的事情。毕竟，代码只是比较整数和整数。这是因为 OCaml 还没有（还）优化 if-else 测试，还是因为不可能像模式匹配那样优化 if-else 测试？

模式匹配代码如下所示：

let plus_one_match x =
    match x with
    | 0 -> 1
    | 1 -> 2
    | 2 -> 3
    | _ -> x + 1

if-else 代码如下所示：

let plus_one_if x =
    if      x = 0 then 1
    else if x = 1 then 2
    else if x = 2 then 3
    else x + 1

Answer 1

当然，可以用同样的方式优化if-else测试。例如，您可以编写一个分两个阶段工作的新优化器：首先尽可能将所有 if-else 测试转换为模式匹配（仍在 OCaml 中），然后运行现有编译器。

因此，答案肯定是以同样的方式优化 if-else 测试在编译器开发人员的优先级列表中并不高。

由于编译器的未来版本可能会为 if-else 测试带来更好的优化，我现在只会更改时间关键代码。

Answer 2

match 和 if 具有不同的语义：match 是并行的，if 是严格顺序的。如果你有表达：

 match expr with
 | A -> e1
 | B -> e2
 | C -> e3
 | ...

然后它可以按任何顺序比较分支。在我提供的示例中，它可以编译为二进制搜索，利用构造函数表示为普通数字的事实。

在表达式中

if e1 then e2 else if e3 then e4 else ...

语言语义要求 e3 在 e1 之后严格求值，当且仅当 e1 求值为 false。这意味着，编译器无法重新排列比较顺序，因为它不知道 e1 是否是 false 的 true（如果知道，则 with if 表达式将被删减不断折叠，所以没关系。

回到你的例子。如果你编译你的匹配函数，你会得到以下代码（在 x86_64 上）：

.L104:
    cmpq    , %rax
    jbe .L103
    addq    , %rax
    ret
.L103:
    sarq    , %rax
    cmpq    , %rax
    je  .L101
    jg  .L100
.L102:
    movq    , %rax
    ret
.L101:
    movq    , %rax
    ret
.L100:
    movq    , %rax
    ret

实际对应表达式：

if x > 2 then x + 1 
else match compare x 1 with 
| 0 -> 2
| 1 -> 3
| _ -> 1

非常高效的代码，它只使用了两次比较。在运行时，它通常（取决于数据分布）以一次比较结束。

如果你用 if 编译一个例子，那么它会发出代码，基本上等同于原始的 OCaml 代码。因为，if 表达式的语义要求编译器这样做。 if 表达式必须是连续的。

可以争辩说，if 示例可以编译为相同的代码，因为比较函数是内置比较函数。但是为此，编译器需要证明比较函数是内置的或者没有副作用。在那只针对 int 的一种特殊情况。我怀疑有人会写这样的优化，因为它不值得。

match 表达式的另一个显着特征是可以在一组非常有限的对象上执行匹配，这些对象有一个共同点，它们都是序数，或者可以排序。在 if 表达式中，我们有任意表达式。

模式匹配和 if-else 的性能差异

Performance difference between pattern matching and if-else

performance

ocaml

pattern-matching