Thoughts on laziness (long)

[Richard Carlsson]

On Thu, 19 Oct 2000 matthias@REDACTED wrote:

> Doing a quick benchmark doesn't give very encouraging results.
> 
>   Sum: take a list of numbers 1..N and sum them (not Gauss' way ;-)
> 
>   Update: change the 3rd, middle and 3rd-last elements in a list
> 
>          -----list------     ------ra-list--   -------ets-----  gb_tree
>    N     sum     update      sum      update   sum    update    update
>    ----------------------------------------------------------------------
>    100   107     197         962      84      1660    50        87
>    1000  921     3666        9903     127       16k   60        89
>    10k   9324    46k         93k      168      168k   74        96
>    100k  493k    660k        1357k    188     2109k   84        97
> 
>    The table shows execution time, i.e. larger numbers are worse.
>    I can't see why anyone would want to use a gb_tree---ETS is
>    faster at the very operation gb_tree is supposed to be really
>    good at. The picture for ra_list is a little more complex, but
>    it doesn't make me want to jump up and down saying "yay! ra-lists".

Well, you couldn't expect to beat a destructive update with a tree rewrite
(but actually, I'm surprised that the ETS tables were not even faster).

Advantages of gb-trees are that they are much more lightweight (an empty
tree is a tuple {0, nil}, so you can create and throw away as many as you
like on the fly, and that they do no copying, since they reside on the
local heap - you could try the same test inserting/updating/fetching some
bigger things than integers and see the difference.

Myself, I mainly use them for representing environments in program
analysis or interpretation.

>    - I might just be showing that the current Erlang implementation
>      sucks. Maybe ETOS or HIPE can show much better results for
>      purely functional data structures.

They should perform better in native code compared to ETS than under the
BEAM emulator, but in general the complexity of the algorithms would
remain the same.


Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/