[erlang-questions] Arrays and setelement

[Mikael Pettersson]

On Fri, 29 Dec 2006 01:19:17 +0000, Joel Reymont wrote:
>According to the setelement docs, it returns an array that is a copy  
>of the original, with the element at index N replaced with new value.  

I doubt it says that. "array" is not a native Erlang data type,
and apart from a failed experiment, it's not a data type in any
Erlang/OTP implementation either.

setelement works on tuples, and returns new tuples.
However, tuples != arrays.

>How is this implemented in the VM, though?

setelement works by copying, except when the BEAM compiler
can prove that intermediate copies are redundant, in which
cases it simple performs assignments.

>Does setelement actually allocate a new array of the same size?

No, since Erlang has no arrays. setelement works on tuples,
and it works as if it allocated new tuples.

>What is the most efficient (speed-wise) implementation of arrays in  
>Erlang?

Define "array". Seriously, there have been several proposals
with different APIs and different implementations. For bounded
integer indices the best bet IMO is B-trees or something like them.
An "array" module was indeed posted this fall based on that idea.

>My arrays themselves would be very small, less than 100 elements. I  
>do need very fast assignment and fetching, though. The arrays are  
>dense, no holes.

You should also consider the relative frequencies of assignments
and references.

Arrays for Erlang is a difficult problem. Not because their
semantics is difficult, but because their efficient implementation
depends on API details and specific support from the runtime system.
And that support is missing. (I'm referring to write barriers or
remembered sets or equivalent techniques for handling wrong-way
pointers in generational garbage collected heaps.)

/Mikael