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

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

我在读 Real World OCaml 时发现this https://realworldocaml.org/v1/en/html/lists-and-patterns.html#performance他们将模式匹配的性能与 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

match and 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 is true of false（如果它知道，那么 if 表达式将通过常量折叠进行修剪，所以没关系）。

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

.L104:
    cmpq    $5, %rax
    jbe .L103
    addq    $2, %rax
    ret
.L103:
    sarq    $1, %rax
    cmpq    $1, %rax
    je  .L101
    jg  .L100
.L102:
    movq    $3, %rax
    ret
.L101:
    movq    $5, %rax
    ret
.L100:
    movq    $7, %rax
    ret

这实际上对应于表达式：

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

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

如果你编译一个例子if然后它会发出基本上等于原始 OCaml 代码的代码。因为，根据语义，编译器需要这样做if表达。if表达must是连续的。

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

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