Why is a hand-written equal function faster than ( = )?

Learning
1

Hi!

The documentation of ppx_deriving explains that the equal and compare functions derived are faster than the usage of =. Is it really the case? And if so, why? I haven’t been able to find out.

Thanks!

1 Like
2

I believe this is because the default implementations are calling the polymorphic variants of those functions and those are very heavy. A specialized implementation can be much smaller and potentially inlined or have other optimisations.

For example here’s the polymorphic versions implementations:

Here’s a small blog post by Jane Street on the topic:

3 Likes
3

Hi!

Thank you for your answer.
I had read that article, but it is still not exactly clear why this would be slower.

I understand that equal functions can be manually optimised of course, but I am talking about the functions derived by ppx.
Polymorphic compare will compare tags, and if tags are equal, recursively compare the fields. But so will the equal functions derived by ppx won’t it?

But I think I get my answer from the code you linked however: polymorphic compare also has to decide on the type of what it’s comparing before being able to perform comparison, which obviously is slower. I could have guessed it probably hahaha

Thank you!

4

There are two main reasons why the polymorphic comparison is slower. The first one is that it’s implemented in C, not in OCaml. In bytecode it’s not really worse (in fact, it’s likely better in many cases) but for native code switching from OCaml code to C code is relatively slow, so if your comparison function isn’t too complicated it’s usually faster to use a pure OCaml version. Plus, a pure OCaml function can be considered for inlining, which can again improve performance

The second reason is specialisation. The polymorphic version has to consider all possible cases that are valid for any given type, while a hand-written one (or ppx-generated one) only has to deal with the cases allowed for the particular type it’s written for.
It’s not as much a problem as the other point though, in particular since for a number of base types the specialisation is performed automatically by the compiler (i.e. Stdlib.compare (x : int) y is reasonably fast). Even when that doesn’t work, it’s usually only a few comparisons that you can skip by knowing the type.

1 Like
5

Thx for the ref. It’s just what I had always imagined it to be in my head… and more!