Erlang Efficiency quesitons

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Francesco Cesarini
I was wondering if there is any documentation on how to write efficient
Erlang programs based on the virtual machine delivered in with OTP R7?
Many odds and ends have been discussed on this list, but I have been
unable to find something comprehensive.

Here are some examples from one of Bogumil's early beam implementations
used in 1995 - 96. Are they still valid today after Bj?rn's rewrite?

At the time it was better to group clauses according to the matching
which had to be done. For example

case X of
  {a,b,c} -> ..
  {b,c,A} -> ..
  {A,B,C} -> ...
  {a,b}   -> ...
  {A,b}   -> ..
  true    -> ..
end

was more efficient than :

case X of
  {a,b,c} -> ..
  true    ->  
  {a,b}   -> ...
  {A,b}   -> ..
  {b,c,A} -> ..
  true    -> ..
  {A,B,C} -> ...
end

(The above apparently also applied to ifs, receives and function
clauses).

Another example had to do with avoiding the dynamic creation of atoms as
there was no GC for them. Is that still the case?

I could go on and on with more examples, but i'll leave it to that. Any
feedback on where I can find more comprehensive info is welcome.

Regards,
Francesco

--
Francesco Cesarini

Erlang/OTP consultant
Cellular: INT+44-7776 250381
ECN: 832-707192
http://welcome.to/cesarini.consulting


Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Ulf Wiger-4
On Wed, 14 Mar 2001, Francesco Cesarini wrote:

>I was wondering if there is any documentation on how to write efficient
>Erlang programs based on the virtual machine delivered in with OTP R7?

Why, Francesco, don't you know that we shouldn't worry about making
our programs fast?!  ;-)

To my knowledge, there is no such document.

>Many odds and ends have been discussed on this list, but I have been
>unable to find something comprehensive.

I've attached some old documents that we wrote a while back on
performance. I must warn you that we don't stand by some of the
recommendations made within anymore. Special warning against foregoing
gen_server for hard-coded servers. This is really not a good idea, and
not nearly as relevant now as it was then. The overhead of gen_server
is pretty insignificant.

Other bad advice is using integers instead of atoms.

Having said this, there are some good ideas in there as well. (:

The compiler nowadays does a pretty good job of optimizing case
and function clauses and also removes dead code. This is good news
for those of us who are interested in squeezing every drop of
performance out of our Erlang programs.

I also know that higher-order functions are very efficient now. This
also means that old warnings about list comprehensions are no longer
quite as valid.

All in all, the document helps to demonstrate that any advice on
writing fast code, other than selecting efficient algorithms, is
something that needs to be updated frequently. Nonetheless, this kind
of document is needed.


>Another example had to do with avoiding the dynamic creation of
>atoms as there was no GC for them. Is that still the case?

Yes, this is still true.

However, if I recall correctly, BEAM doesn't have a hard limit on the
size of the atom table, so you can have quite a few atoms, provided
you have enough memory.

/Uffe
--
Ulf Wiger                                    tfn: +46  8 719 81 95
Senior System Architect                      mob: +46 70 519 81 95
Strategic Product & System Management    ATM Multiservice Networks
Data Backbone & Optical Services Division      Ericsson Telecom AB
-------------- next part --------------
A non-text attachment was scrubbed...
Name: performance.tar.gz
Type: application/x-gzip
Size: 19493 bytes
Desc: performance.tar.gz
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20010314/f8600b9f/attachment.bin>

Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Francesco Cesarini
> Why, Francesco, don't you know that we shouldn't worry about making
> our programs fast?!  ;-)

Search some of my earlier posts on this list and you will find the:

First make it work. Then make it beautiful. Then if you really really
have to, make it fast (While keeping it beautiful and correct).

(And as I say when teaching, in 95% of the cases, your application will
be fast enough. For the remaining 5%, you do not have the time to
rewrite it... At least it is beautiful :-)

> To my knowledge, there is no such document.

Let us put one together. Here are some more hints:

* Use binaries when shuffling around large amounts of data between
processes.
* Some one on the list had mentioned that appending binaries results in
them being copied, thus avoid it.
* In the documentation for the 4.4 extensions I found a note that
  f(X) when X == #rec{x=1, y=a} -> ... is less efficient than
 f(#rec{x=1, y=a} = X) -> ...

I assume because in A X is bound before the guard test, in B, the
pattern match fails as soon as one of the conditions does not match.
Back in the good old days, the recommendation was to use guards in Beam,
while with the Jam there was no difference...

If you have found more through timing or somewhere hidden in the
documentation, send them directly to me and I will put together a web
page.

Regards,
Francesco
--
Francesco Cesarini

Erlang/OTP consultant
Cellular: INT+44-7776 250381
ECN: 832-707192
http://welcome.to/cesarini.consulting


Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Robert Virding-4
In reply to this post by Francesco Cesarini
Francesco Cesarini <cesarini> writes:

>At the time it was better to group clauses according to the matching
>which had to be done. For example
>
>case X of
>  {a,b,c} -> ..
>  {b,c,A} -> ..
>  {A,B,C} -> ...
>  {a,b}   -> ...
>  {A,b}   -> ..
>  true    -> ..
>end
>
>was more efficient than :
>
>case X of
>  {a,b,c} -> ..
>  true    ->  
>  {a,b}   -> ...
>  {A,b}   -> ..
>  {b,c,A} -> ..
>  true    -> ..
>  {A,B,C} -> ...
>end

Today there is no difference with type of grouping.  The compiler rearranges
clauses after type of match argument anyway.  The only rule that would aid
speed is to group clauses where there is a variable to match on instead of
interspersing them among other clauses.  Avoid if possible:

case X of
  {a,b,c} -> ..
  Sune when ...   ->  
  {a,b}   -> ...
  Curt when ...   -> ..
  {b,c,A} -> ..
  Other when ..   -> ..
  {A,B,C} -> ...
end

Of course this is often not possible to do but is worth remembering.

        Robert




Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Robert Virding-4
In reply to this post by Francesco Cesarini
Francesco Cesarini <cesarini> writes:

>
>Let us put one together. Here are some more hints:
>
>* Use binaries when shuffling around large amounts of data between
>processes.
>* Some one on the list had mentioned that appending binaries results in
>them being copied, thus avoid it.
>* In the documentation for the 4.4 extensions I found a note that
>  f(X) when X == #rec{x=1, y=a} -> ... is less efficient than
> f(#rec{x=1, y=a} = X) -> ...
>
>I assume because in A X is bound before the guard test, in B, the
>pattern match fails as soon as one of the conditions does not match.
>Back in the good old days, the recommendation was to use guards in Beam,
>while with the Jam there was no difference...

A is inefficient because you build a new record and then do an equals test on
the two structures.  It is also EXTREMELY unsafe as you get the default values
on all unmentioned fields!

B just test the type of term and values of the given fields.  It is infact
more efficient to do:

f(#rec{x=X,a=A}=Rec) ->

than

f(Rec) when record(Rec, rec) ->
    ...
    Rec#rec.x  Rec#rec.a

and it is more efficient to just test for a rec record with the first case
than with the second.

        Robert




Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Alexander Williams
In reply to this post by Francesco Cesarini
On Wed, Mar 14, 2001 at 05:38:59PM +0000, Francesco Cesarini wrote:
> * Use binaries when shuffling around large amounts of data between
> processes.
> * Some one on the list had mentioned that appending binaries results in
> them being copied, thus avoid it.

You know, I'm wondering why no one's suggested before (and I suppose
I'm suggesting now) why the underlying representation of strings
hasn't been changed to Binaries instead of Lists (or at least
discussion thereof).  If the functions in string: were changed, that'd
be 80% of the tweaking necessary right there.  One can already do
pattern-matching on Binaries, so you don't lose much there.

>From an efficency PoV, the main drawback would seem to be that
Binaries copy when appended, but going to a different programming
pattern that involves building lists of Binary-strings and then
joining them should be able to get around that problem; Python's
strings are "immutable," much as Binaries seem to be, and so share the
quality of being copied to create a new entity when +'d, but if one
constructs a List of strings, calling string.join() on the List will
return a single string without much overhead.

Thoughts?

--
Alexander Williams (thantos)               | In the End,
  "Blue Jester needs food."                             | Oblivion
  "Blue Jester needs fuku-wearing cuties."              | Always
  http://www.chancel.org                                | Wins


Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Claes Wikström
On Wed, Mar 14, 2001 at 05:45:29PM -0500, Alexander Williams wrote:

> On Wed, Mar 14, 2001 at 05:38:59PM +0000, Francesco Cesarini wrote:
> > * Use binaries when shuffling around large amounts of data between
> > processes.
> > * Some one on the list had mentioned that appending binaries results in
> > them being copied, thus avoid it.
>
> You know, I'm wondering why no one's suggested before (and I suppose
> I'm suggesting now) why the underlying representation of strings
> hasn't been changed to Binaries instead of Lists (or at least
> discussion thereof).  If the functions in string: were changed, that'd
> be 80% of the tweaking necessary right there.  One can already do
> pattern-matching on Binaries, so you don't lose much there.
>
> >From an efficency PoV, the main drawback would seem to be that
> Binaries copy when appended, but going to a different programming
> pattern that involves building lists of Binary-strings and then
> joining them should be able to get around that problem; Python's
> strings are "immutable," much as Binaries seem to be, and so share the
> quality of being copied to create a new entity when +'d, but if one
> constructs a List of strings, calling string.join() on the List will
> return a single string without much overhead.
>
> Thoughts?


This was one of the original goals of the bitsyntax as well, i.e.
to be able to with ease use Binaries as an efficent replacement
for strings. I even once wrote a bstring.erl which was a module
with an equivalent interface as string.erl

This idea still holds. Possibly some explicit support for
string management should be added to the runtime as well.

String handling has been (and still is) one of the really
weak points of Erlang. At least from a performance point
of view, strings as lists (as we have it today) are slow, but
very flexible and nice. Right !!. Probably we want both.


/klacke



--
Claes Wikstrom                        -- Caps lock is nowhere and
Alteon WebSystems                     -- everything is under control          
http://www.bluetail.com/~klacke       --



Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Mickael Remond-2
Klacke (klacke) wrote:
>
> This was one of the original goals of the bitsyntax as well, i.e.
> to be able to with ease use Binaries as an efficent replacement
> for strings. I even once wrote a bstring.erl which was a module
> with an equivalent interface as string.erl

Did you make some performance comparisons ?
Would you mind releasing this module ?

> String handling has been (and still is) one of the really
> weak points of Erlang. At least from a performance point
> of view, strings as lists (as we have it today) are slow, but
> very flexible and nice. Right !!. Probably we want both.

Yes. We want probably both.
These days with the rise of XML, efficient string support will become
much more critical.

--
Micka?l R?mond



Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Claes Wikström
On Thu, Mar 15, 2001 at 10:36:21AM +0100, Mickael Remond wrote:
> Klacke (klacke) wrote:
> >
> > This was one of the original goals of the bitsyntax as well, i.e.
> > to be able to with ease use Binaries as an efficent replacement
> > for strings. I even once wrote a bstring.erl which was a module
> > with an equivalent interface as string.erl
>
> Did you make some performance comparisons ?
> Would you mind releasing this module ?

I'll attach it here, It's written in our original
bit syntax and it woun't compile today.

>
> > String handling has been (and still is) one of the really
> > weak points of Erlang. At least from a performance point
> > of view, strings as lists (as we have it today) are slow, but
> > very flexible and nice. Right !!. Probably we want both.
>
> Yes. We want probably both.
> These days with the rise of XML, efficient string support will become
> much more critical.
>

Yup,


/klacke


--
Claes Wikstrom                        -- Caps lock is nowhere and
Alteon WebSystems                     -- everything is under control          
http://www.bluetail.com/~klacke       --

-------------- next part --------------
%%%----------------------------------------------------------------------
%%% File    : bstring.erl
%%% Author  : Claes Wikstrom <klacke>
%%% Purpose : Manipulation of binary strings
%%% Created :  2 Oct 1998 by Claes Wikstrom <klacke>
%%%----------------------------------------------------------------------

-module(bstring).
-author('klacke').

-compile(export_all).

len(S) -> size(S).


equal(S, S) -> true;
equal(_, _) -> false.


concat(S1, S2) ->
    <S1/binary | S2>.

%% chr(String, Char)
%% rchr(String, Char)
%%  Return the first/last index of the character in a string.

chr(S, C) when binary(S) ->
    case S of
        <_:Size/binary, C:8/char |_> ->
            Size + 1;
        _ ->
            0
    end.

rchr(S, C) -> rchr(S, C, 1, 0).

rchr(<C/char|Cs>, C, I, L) -> %Found one, now find next!
    rchr(Cs, C, I+1, I);
rchr(<_/char|Cs>, C, I, L) ->
    rchr(Cs, C, I+1, L);
rchr(<>, C, I, L) -> L.

%% Return
ix(B, Pos) ->
    <_:(Pos-1)/binary, Ch:8/char |_> = B,
    Ch.

%% str(String, SubString)
%% rstr(String, SubString)
%% index(String, SubString)
%%  Return the first/last index of the sub-string in a string.
%%  index/2 is kept for backwards compatibility.


str(S, Sub) ->
    case S of
        <_:Ix/binary, Sub/binary | _> ->
            Ix + 1;
        _  ->
            0
    end.

rstr(S, Sub) ->
    rstr(S, Sub, 0).

rstr(S, Sub, I) ->
    case S of
        <_/binary, Sub/binary |T> ->
            rstr(T, Sub, I+1);
        _ ->
            I
    end.

index(S, Sub) -> str(S, Sub).


bmember(C, Cs) ->
    case chr(Cs, C) of
        0 ->  false;
        _ ->  true
    end.


%% span(String, Chars) -> Length.
%% cspan(String, Chars) -> Length.

span(S, Cs) -> span(S, Cs, 0).

span(<C/char|S>, Cs, I) ->
    case bmember(C, Cs) of
        true -> span(S, Cs, I+1);
        false -> I
    end;
span(<>, Cs, I) -> I.

cspan(S, Cs) -> cspan(S, Cs, 0).

cspan(<C/char|S>, Cs, I) ->
    case bmember(C, Cs) of
        true -> I;
        false -> cspan(S, Cs, I+1)
    end;
cspan(<>, Cs, I) -> I.

%% substr(String, Start)
%% substr(String, Start, Length)
%%  Extract a sub-string from String.

substr(Str, Len) ->
    <_:(Len-1)/binary | Tail> = Str,
    Tail.

substr(Str, Start, Len) ->
    <_:(Start-1)/binary, B:Len/binary |_> = Str,
    B.

%% tokens(String, Seperators).
%%  Return a list of tokens seperated by characters in Seperators.

token(S, Seps) ->
    tokens1(S, Seps, []).


tokens1(S, [], Ack) ->
    Ack;
tokens1(S , [Sep|Seps], Ack) ->
    A2 = tokens2(S, Sep, Ack),
    tokens1(S, Seps, A2).

tokens2(S, Sep, Ack) ->
    case S of
        <B:Sz/binary, Sep/char | Tail> when Sz > 0 ->
            tokens2(Tail, Sep, [B|Ack]);
        _ ->
            Ack
    end.


chars(C, N) -> chars(C, N, <>).

chars(C, N, Tail) when N > 0 ->
    Btail = chars(C, N-1, Tail),
    <C/char| Btail>;
chars(C, 0, Tail) ->
    Tail.


%%% COPIES %%%

copies(_, 0) -> <>;
copies(S, Num) ->
    Btail = copies(S, Num-1),
    <S/binary | Btail>.

%%% WORDS %%%

words(String) -> words(String, $ ).

words(String, Char) ->
    case String of
        <B/binary, Char/char | Tail> ->
            1 + words(Tail, Char);
        _ ->
            0
    end.

%%% SUB_WORDS %%%

sub_word(String, Index) ->
    sub_word(String, Index, $ ).

sub_word(String, Ix, Char) ->
    sub_word(String, Ix, Char, 0).

sub_word(String, Ix, Char, Sofar)  ->
    case String of
        <B/binary, Char/char |_> when Sofar == Ix ->
            B;
        <B/binary, Char/char |Tail> ->
            sub_word(Tail, Ix, Char, Sofar+1);
        _ ->
            <>
    end.

%%% STRIP %%%

strip(String) -> strip(String, both).

strip(String, left) -> strip_left(String, $ );
strip(String, right) -> strip_right(String, $ );
strip(String, both) ->
    strip_right(strip_left(String, $ ), $ ).

strip(String, right, Char) -> strip_right(String, Char);
strip(String, left, Char) -> strip_left(String, Char);
strip(String, both, Char) ->
    strip_right(strip_left(String, Char), Char).


strip_left(<C/char|Tail>, C) ->
    strip_left(Tail, C);
strip_left(B, _) ->
    B.

strip_right(<B/binary, Char/char>, Char) ->
    strip_right(B, Char);
strip_right(B, Char) ->
    B.


%%% LEFT %%%

left(String, Len) -> left(String, Len, $ ).

left(String, Len, Char)  ->
    Slen = length(String),
    if
        Slen > Len -> substr(String, 1, Len);
        Slen < Len -> l_pad(String, Len-Slen, Char);
        Slen == Len -> String
    end.

l_pad(String, Num, Char) ->
    Btail = chars(Char, Num),
    <String/binary | Btail>.

%%% RIGHT %%%

right(String, Len) -> right(String, Len, $ ).

right(String, Len, Char) ->
    Slen = size(String),
    if
        Slen > Len -> substr(String, Slen-Len+1);
        Slen < Len -> r_pad(String, Len-Slen, Char);
        Slen == Len -> String
    end.

r_pad(String, Num, Char) -> chars(Char, Num, String).

%%% CENTRE %%%

centre(String, Len) -> centre(String ,Len, $ ).

centre(String, 0, _) -> []; %Strange cases to centre string
centre(String, Len, Char) ->
    Slen = size(String),
    if
        Slen > Len -> substr(String, (Slen-Len) div 2 + 1, Len);
        Slen < Len ->
            N = (Len-Slen) div 2,
            r_pad(l_pad(String, Len-(Slen+N), Char), N, Char);
        Slen == Len -> String
    end.
           

%%% SUB_STRING %%%

sub_string(String, Start) -> substr(String, Start).

sub_string(String, Start, Stop) -> substr(String, Start, Stop - Start + 1).

%% The Regular Expression Matching Functions.
%%
%%  These have been rewritten. As their interface has changed slightly
%%  (much to the better) I have moved them to a new module 'regexp' to
%%  avoid another "interface war" about something which doesn't
%%  serioulsy affect that many people. This interface is kept for
%%  backwards compatibility so I don't get shot for that as well.
%%
%%  /Robert Virding

re_sh_to_awk(ShellRegExp) ->
    regexp:sh_to_awk(ShellRegExp).

re_parse(RegExp) ->
    case bregexp:parse(RegExp) of
        {ok,RE} -> {regexp,RE};
        {error,E} -> {error,E}
    end.

re_match(String, RegExp) ->
    case bregexp:match(String, RegExp) of
        {match,Start,Len} -> {match,substr(String, Start, Len),Start};
        nomatch -> nomatch;
        {error,E} -> {error,E}
    end.

re_sub(String, RegExp, New) ->
    case bregexp:sub(String, RegExp, New) of
        {ok,Res,N} -> {ok,Res};
        {error,E} -> {error,E}
    end.

re_gsub(String, RegExp, New) ->
    case bregexp:gsub(String, RegExp, New) of
        {ok,Res,N} -> {ok,Res};
        {error,E} -> {error,E}
    end.

re_split(String, RegExp) -> bregexp:split(String, RegExp).


Reply | Threaded
Open this post in threaded view
|

Erlang Efficiency quesitons

Ulf Wiger-4

On Thu, 15 Mar 2001, Klacke wrote:

>I'll attach it here, It's written in our original
>bit syntax and it woun't compile today.

One thing that could be done right now is to provide a BIF which
is equivalent to your bstring:chr(Char, Binary) function, i.e.
return the position of the first location of Char in Binary
(or 0 if Char was not found.)

Since the current bit syntax doesn't allow constructs like:

chr(S, C) when binary(S) ->
    case S of
        <_:Size/binary, C:8/char |_> ->
            Size + 1;
        _ ->
            0
    end.

then perhaps the string:str/2 function should also have a BIF
equivalent for binaries?

and, while we're at it, a binary:reverse(Binary) BIF would also
be useful.

/Uffe
--
Ulf Wiger                                    tfn: +46  8 719 81 95
Senior System Architect                      mob: +46 70 519 81 95
Strategic Product & System Management    ATM Multiservice Networks
Data Backbone & Optical Services Division      Ericsson Telecom AB