[erlang-questions] Is function clause selection O(n)?

[Joe Armstrong]

On 7/17/07, Daniel Goertzen <daniel.goertzen@REDACTED> wrote:
> I am considering the design of a filtering function that will prevent some
> function calls and allow others.  For example, such a function might look
> like this:
>
> filter(M,F,Args) -> apply(M,F,Args).
>
> Of course the above does no actual filtering, but for the use I'm
> envisioning there will be dozens or even hundreds of clauses for the filter
> function.  So, I am wondering what the algorithmic complexity of runtime
> clause selection is.  O(n)?  O(log n)? O(1)?

It depends upon the set of patterns - how much they overlap. It might be
O(1) it might be O(N). It also depends upon how large the patterns are.

The pattern matching compiler tries to build an optimal decision tree, how well
it does this depends upon the set of patterns.

In your case, clause selection should be very fast - one hash lookup for the
module and one for the function - assuming they are atoms and not variables.
(It might be a linear search if the number of atoms is small - the system will
choose the best method depending upon the number of atoms)

"Hundred of clauses" is what I'd call a very small pattern set - it's
always going to
be faster compiling this than using ets. If know the number of arguments
you can do away with the apply and make it even faster

filter(foo,bar,A,B,C) -> foo:bar(A,B,C)

But then you'd need a filter/2, filter/3, ... etc to take care of the
different numbers of arguments.

Basically I wouldn't out-guess the compiler. Try using clauses even if there are
thousands, or millions of them. If you manage to break the system by
writing a function
with a million clauses then file a bug report. This has often happened
in the past, often
a simple fix to the compiler corrects the problem - but we need to
know about the pathological cases.



/Joe



>
> I've also considered an ets table lookup for this, but it does the opposite
> of what I want.  With ets you can specify a pattern to match against a set
> of values, but I need a value to match against a list of patterns.
>
> Any other ideas?
>
> Thanks,
> Dan.
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>