optimization tricks ?

Robert Virding <>
Mon May 15 11:12:40 CEST 2000


Hakan Stenholm <> writes:
>* in Prolog the order of the predicate (function) clauses affect the
>speed of selecting the apropriate clause (first match is used). e.g. :
>do_something_per_element([E|Rest]) ->
>        do_something(E),
>        do_something_per_element(Rest);
>do_something_per_element([]) -> ok.
>
>would be faster becouse the first clause is allways the right one expect
>in one case (when it is done).
>Does this apply to Erlang as well ?

Not really!  The pattern matching compiler reorders clauses where it 
safely can so that arguments of the same type are together, it then 
reorders the types with a (very) simple heuristic to try and optimise 
speed.  Basically it orders them as cons, tuples, atomic.

However, within each type it does not reorder the clauses.  So you could 
get some benefit from ordering clauses, BUT we also do hash indexing 
which removes the order dependency.

>* if the functions clauses use pattern matching in their heads e.g. :
>    F1(case_a, D) -> ....
>    F1(case_b, D) -> ....
>
>    F2(D, case_a) -> ....
>    F2(D, case_b) -> ....
>
>Prolog would be faster for F1 as pattern matching would not be needed
>for more than the first argument i.e. keys should be first and placed in
>such an order as to reduce the amount of possibal matching function
>clauses.
>Does this apply to Erlang as well ?

No!  We do match from left to right but all the tricks and 
optimisations are done to all the arguments so there is no gain in 
speed through reordering the arguments.  Prolog does not do this.

>Are there any other non-algoritmic tricks for better perfomance ?
>Is pattern matching with atoms faster than strings (i.e. list of
>integers which will presumebly need to be matched letter for letter) ?

Pattern matching is definitely faster with atomics than with structures
like strings which are matched character by character.  There is *VERY*
little gain, however, in using integers instead of atoms, so be clear.

>And yes I _DO_ know that the choice of algoritms is generaly far more
>important than tricks that can change the Ordo by some constant    : )

Well, my opinion is that it is always better to have clear code which 
works rather than fast optimised code which doesn't.  As someone once 
said, it is easy to optimise as erroneous program.

	Robert

-- 
Robert Virding                          Tel: +46 (0)8 692 22 12
Bluetail AB                             Email: 
Hantverkargatan 78                      WWW: http://www.bluetail.com/~rv
SE-112 38 Stockholm, SWEDEN
"Folk säger att jag inte bryr mig om någonting, men det skiter jag i".





More information about the erlang-questions mailing list