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 read Real World OCaml and I came across this section where they compared the pattern matching performance with if-else test results. It turned out that pattern matching in their example was significantly faster than if-else tests. Despite the fact that the code does not use any special cases of pattern matching that would not be possible with if-else tests, it simply compares the integers.

They attribute compiler optimizations for pattern matching as the cause of performance differences. The compiler will be able to generate machine code that jumps directly from the agreed case based on an effectively selected set of runtime checks.

I understand this, but I do not understand why the compiler cannot do the same for if-else tests. In the end, the code simply compares integers with integers. Is it because OCaml has not optimized if-else tests yet, or is it because it is not possible to optimize if-else tests similar to capabilities using pattern matching?

The pattern matching code is as follows:

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 serial. If you have an expression:

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

Then it can compare branches in any order. In the above example, I can compile to binary search using the fact that the constructors are represented as ordinary numbers.

In expression

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

it is required by the semantics of the language that e3 evaluates strictly after e1 , and iff e1 evaluates to false. This means that the compiler cannot reorder the order of comparisons, since it cannot know if e1 true of false (and if it does, it does not matter with an expression that will be trimmed with a constant fold).

Back to your example. If you compile your matching 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 

This really matches the expression:

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

Pretty efficient code that uses only two comparisons at all. And at runtime, it usually (depending on the distribution of the data) ends with one comparison.

If you compile the example with if , then it produces code that is basically equal to the original OCaml code. Because the compiler must do this, according to the semantics of the if . if expression must be consistent.

It can be argued that the if example can be compiled into the same code, given that the comparison function is a built-in comparison function. But for this, the compiler needs to prove that the comparison function is built-in or has no side effects. This is only for one special case with int . I doubt that someone will write such an optimization, because it is not worth it.

Another distinguishing feature of the match expression is that matching can be performed on a very limited set of objects that share one common feature, all of them are ordinals or can be ordered. In if we have an arbitrary expression.

Answer 2

Of course, you can optimize the if-else test in the same way. For example, you can write a new optimizer that works in 2 stages: first, convert all if-else tests to the pattern where possible (still in OCaml), and then run the existing compiler.

Therefore, the answer should be that the optimization of if-else tests is equally small in the priority list of compiler developers.

Since a future release of the compiler may bring even better optimizations for the if-else test, I would just change the time-critical code now.