[erlang-questions] 2D Map Arrays
Wed Sep 13 15:18:45 CEST 2006
Mikael Pettersson wrote:
> 2. It has an extensible index range, but we only construct arrays of
> given sizes and then stay within those boundaries. So do we lose
> any performance due to the extensibility feature we don't use?
No. For 'set', it just does a single test to check if you are
within range or not (and that would be done even if you did not
allow the range to be extended).
Furthermore, the range extension is very cheap; most of the time,
it does nothing except check that the current structure has room for
the new maximum index. If that is not the case, an extra tuple level
is added, which increases the maximum range by a factor 10. In other
words, if you append one element at a time to an initially empty array,
the actual array structure will only change at sizes 1, 11, 101, 1001,
10001, and so on. Since the representation is quite sparse, this does
not waste space for the as-yet-unused part.
More information about the erlang-questions