模式匹配和if-else之间的性能差异 [英] Performance difference between pattern matching and if-else

问题描述

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

Why can OCaml generate efficient machine code for pattern matching and not for if-else tests?

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

I was reading Real World OCaml and I came across this section where they compared the performance of pattern matching to the performance of if-else tests. It turned out that pattern matching in their example was significantly faster than if-else tests. Even though the code doesn't utilize any special pattern match cases that would not be possible with if-else tests, it just compares integers.

他们将编译器的模式匹配优化归因于性能差异.编译器将能够基于有效选择的一组运行时检查来生成机器代码，该机器代码直接在匹配的情况下跳转.

They ascribe compiler optimization for pattern matching as the reason for the performance difference. The compiler would be able to generate machine code that jumps directly ot the matched case based on an efficiently chosen set of runtime checks.

我理解这一点，但是我真的不明白为什么编译器不能对if-else测试做同样的事情.毕竟，代码只是将整数与整数进行比较.这是因为OCaml尚未(尚未)优化if-else测试，还是因为不可能像模式匹配那样优化if-else测试?

I understand this, but I don't really see why the compiler isn't able to do the same thing for the if-else tests. After all, the code is just comparing integers to integers. Is this because OCaml hasn't (yet) optimized if-else tests, or is it because it's impossible to optimize if-else tests like it's possible with pattern matching?

模式匹配代码如下:

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

if-else代码如下:

The if-else code looks like this:

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和if的语义不同:match是并行的，if是严格顺序的.如果您有表达:

match and if has different semantics: match is parallel, if is strictly sequential. If you have expression:

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

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

Then it may compare branches in any order. In the example, I provided, it may compile to a binary search, utilizing the fact, that constructors are represented as an oridinary numbers.

在表达式

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

语言的语义要求

，严格在e1之后对e3进行评估，并且将iff e1评估为false.这意味着，编译器无法重新排列比较的顺序，因为它不知道e1是否为false的true(如果知道，则表达式是否会被常量折叠修剪，所以它没关系).

it is required by semantics of the language, that e3 is evaluated strictly after e1 and iff e1 is evaluated to false. That means, that compiler can't rearrange the order of comparisons since it can't know whether e1 is true of false (and if it knows, then with if expression will be pruned with constant folding, so it doesn't matter).

回到您的示例.如果您编译匹配函数，您将获得以下代码(在x86_64上):

Back to your example. If you compile your match function you will get, the following code (on 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

非常有效的代码，它仅使用两个比较.而且在运行时，通常(取决于数据分布)将进行一次比较.

Quite efficient code, that uses only two comparisons at all. And in runtime it will usually (depending on data distribution) finish with one comparison.

如果使用if编译示例，则它将发出代码，该代码基本上等于原始的OCaml代码.因为，if表达式的语义要求编译器这样做. if表达式必须是顺序的.

If you compile an example with if then it will emit the code, that basically equal to the original OCaml code. Because, compiler is required to do so, by the semantics of the if expression. if expression must be sequential.

假设比较函数是内置的比较函数，则可以认为if示例可以编译为相同的代码.但是为此，编译器需要证明比较函数是内置函数或没有副作用.在这种情况下，仅适用于int的一种特殊情况.我怀疑有人会写这样的优化，因为它不值得.

One can argue, that the if example, can be compiled to the same code, given that the comparison function is a builtin comparison function. But for that, compiler need to proof, that the comparison function is the builtin or doesn't have side-effects. In that only for one particular case with int. I doubt, that someone will write such optimization, because it doesn't worth.

match表达式的另一个区别特征是，可以对一组非常有限的对象执行匹配，这些对象共享一个共同的东西，它们都是序数，或者可以排序.在if表达式中，我们具有任意表达式.

Other distinguishing feature of a match expression, is that matching can be performed on a very restricted set of objects, that share one thing in common, they are all ordinal numbers, or can be ordered. In if expressions, we have arbitrary expression.

这篇关于模式匹配和if-else之间的性能差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！