[erlang-questions] Performance of matches

Bjorn Gustavsson <>
Fri May 30 10:04:38 CEST 2008


Thomas Lindgren <> writes:

> It depends on the implementation, but pattern matching
> compilers often try to visit each subterm only once,
> so the first case might be something like
> 
> table1([C0|Cs]) ->
>    case C0 of
>       $h -> ... continue matching ello ...
>       $b -> ... continue matching yebye ...
>       $m -> ... continue matching orning ...
>    end
>
> If there are several cases beginning with $b, then the
> clause in the middle will perform further
> discrimination.

The Beam compiler indeed generates that kind of code for matching.

> In the second case, all the terms are atoms, so the
> compiler can generate the equivalent of a switch.
> However, atom id:s used to identify atoms are usually
> assigned at runtime (e.g., when a module with
> previously unseen atoms is loaded). So the compiler
> will normally convert such a switch into some
> optimized tree of comparisons rather than a jump
> table. (Sloppy compilers do a linear sequence of
> matches; reasonably conscientous ones at least build a
> binary tree.)

Beam sorts the atoms when the code is loaded; a binary search
is used when the code is executed. (Atom id:s are generally
spaced too far apart for a jump table to be feasible.)

/Bjorn
-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB



More information about the erlang-questions mailing list