Performance difference between pattern matching and if-else

Question

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

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.

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?

The pattern matching code looks like this:

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

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

Answer 1

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.

In the expression

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

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).

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

That actually corresponds to expression:

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 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.

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.

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.