How does Erlang index clause heads?

Question

I come from a Prolog background. Prolog normally indexes on the first argument of a predicate (most decent systems allow you to change this around, index on multiple arguments, etc). At any rate, knowing how the engine indexes clauses allows you to arrange the arguments and predicates to get better performance.

I've been coding in Erlang some recently, but haven't seen any information out there on how it indexes clause heads, and how I should arrange arguments and clauses. Anyone know?

Thanks.

Answer 1

Erlang indexes on all arguments from left to right, to any depth and for all types. The basic algorithm we use is described in, and was taken from, The Implementation of Functional Programming Languages by Simon Peyton Jones and I modified it to suit how Erlang handles types. This is a good book even if it is a bit old now, a real AHA experience for me.

This means that there is no real need to reorder arguments to try an optimise pattern matching, at least not for speed. It is much better to be consistent and clear, here is how I do it, Is there an idiomatic way to order function arguments in Erlang?. This means that there are no problems with code like:

foo(X, [{a,A}|Rest], ...) -> ... ;
foo(X, [{b,B}|Rest], ...) -> ... ;
foo(X, [{c,C}|Rest], ...) -> ... ;
foo(X, [{d,D}|Rest], ...) -> ... ;
...

There is never any need to try and "help" the compiler by breaking this into nested case expressions, it will usually be worse. The only reason to do this would be if it made the code clearer in showing what you intend.

If you do want to try and optimise pattern matching try to reorder clauses so that all cases where a literal occurs are bunched together. For example:

foo(1, ...) -> ... ;
foo(2, ...) -> ... ;
foo(7, ...) -> ... ;
foo(8, ...) -> ... ;
foo(I, ...) when is_integer(I), I >= 3, I =< 6 ->
    ... .

is better than

foo(1, ...) -> ... ;
foo(2, ...) -> ... ;
foo(I, ...) when is_integer(I), I >= 3, I =< 6 ->
    ... ;
foo(7, ...) -> ... ;
foo(8, ...) -> ... .

Indexing will be better, but again don't overdo it as the difference is not that great, keep it clear. This is also valid at any depth, for example in the first code example with the first element of the tuple in the list.

Most of this is pretty standard for functional languages.