[erlang-questions] Performance of matches

[Thomas Lindgren]

--- Darren New <dnew@REDACTED> wrote:

> Speaking of table-driven decisions...
> 
> Is a function like this efficiently matched?
> 
> table1("hello") -> ...;
> table1("byebye") -> ...;
> table1("morning") -> ...;
>    ... and so on for dozens more ...
> 
> How about
> table2(hello) -> ...;
> table2(byebye) -> ...;
> table2(morning) -> ...;
>     ... And so on for dozens more ...
> 
> Is either of those O(1) lookup time?

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.

(But note that Erlang/OTP might do things differently;
I can't remember. "erlc -S" provides a way station on
this quest :-)

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.)

Best,
Thomas