10

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
Improve this question

2 Answers 2

Reset to default
12

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 ordinary 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 built-in comparison function. But for that, compiler need to proof, that the comparison function is the built-in 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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

Of course, it is possible to optimise the if-else test the same way. For example, you could write a new optimiser that works in 2 stages: first transform all if-else tests to pattern matching where possible (still in OCaml) and then run the existing compiler.

Therefore, the answer must be that optimising if-else tests the same way isn't high on the priority list of the compiler developers.

As a future release of the compiler may bring an even better optimisation for the if-else test, I would only change time-critical code now.

Improve this answer

1 Comment

To do this optimization, you need to proof, that = function doesn't have side effects. Even builtin = has side effect: it raises exception. Of course, one can hardcode in the optimizer a heuristics, that will assume, that for integers it will never throw exceptions. But what about other types? But I doubt, that its worth it.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.