[erlang-questions] Why are arrays faster than tuples?

[Richard Carlsson]

ryeguy wrote:
> I was looking at the benchmark at
> http://thinkerlang.com/2008/08/25/optimizing-erlang-a-death-match-of-arrays-and-tuples.html
> and it looks like arrays are many many times faster than tuples. Why
> is this?

Note that the arrays are implemented using tuples. It's just that
instead of using a single huge tuple (which has fast read access
but very slow updates since the entire tuple needs to be copied), it
uses nested tuples of around 10 elements each. This allows the array
representation to have a good balance between read and update
performance, and also lets it represent sparse arrays efficiently.

It's still a functional data structure: updating an entry gives you
a reference to a conceptually "new" array (although most of the data
is reused and shared with the previous version).

(Note that there is no performance difference between "fixed" and
"extensible" arrays; it's just a flag that specifies the behaviour
in the event of accesses outside the current range: grow or fail.)

Function calls do not cause copying of heap data. Message passing
does, in general.

     /Richard