Arrays implementation in erlang

Question

My question is, how are arrays implemented in Erlang, as opposed to lists.

With immutable types doing things like,

move ([X | Xs], Ys) ->
    [X | Ys].

Ls = move([1,2,3], [2,3,4])

would take up constant mem in the heap, since this is all reference work.

But for the same stuff in arrays

move (A1, A2) ->
    array:set(0, array:get(0,A1),A2).

A1 = array:from_list([1,2,3]).
A2 = array:from_list([0,2,3,4]).
A3 = move(A1,A2).

Will move here use size proportional to A2 or will it be able to do this in constant space like with the arrays?

Answer 1

To (hopefully) clear things up a little. Remember that in Erlang ALL data is immutable! This profoundly affects how you manipulate data.

The array module builds a structure of nested tuples where all the array slots containing data are at the same level. The size of each tuple is 10 so for array access we have O(lg10(N)). Using nested structure like this is common in languages with immutable data. You could keep an array in a flat tuple which would give you fast reads, but writes would become slow and memory hogging for large arrays/tuples as every write would entail creating a new tuple. Using a tree structure means that much less data is created in a write.

How your move/2 function affects memory usage depends a little on whether you are writing to a used or unused slot in the array. If the slot is already in use then the resultant memory usage will be the same. If you are writing to a previously unused slot then you may need to grow the array which mean that more memory will be used.

This is exactly the same as for your list case.

It also depends on whether there are any remaining references to the old data structure.