http://erlang.dmitriid.com/news/item/301

Надеюсь, тэг ANN здесь уместен, и что неутомимый Joel Reymont все таки сделает серию постов об оптимизации Эрланга.

Итак. Неутомимый Joel Reymont решил сделает серию постов об оптимизации Эрланга. Первый пост можно прочитать здесь: http://www.wagerlabs.com/blog/2008/08/optimizing-erlang-a-death-match-of-arrays-vs-tuples.html

В первом посте Джоэль решил поверить, насколько новый модуль array эффективнее, чем кортежи. В тесте (пусть и синтетическом) создавался массив из 10 000 элементов. В забеге участвовали:
— массив фиксированного размера (fixed-size array)
— массив (extensible array)
— кортеж (tuple)
— деревья (gb_trees, реализованые поверх кортежей)

Результат:

Erlang (BEAM) emulator version 5.6.3 [source] [64-bit] [smp:8] [async-threads:0] [kernel-poll:false]

27> arr:test().
Fixed-size array: get:     2921µs, set:     5902µs
Extensible array: get:     3336µs, set:     8144µs
Tuple:            get:      632µs, set:   107467µs
Tree:             get:     4321µs, set:    45256µs
ok

30> arr:test(100000).
Fixed-size array: get:    35314µs, set:    74653µs
Extensible array: get:    35349µs, set:    74059µs
Tuple:            get:     6411µs, set: 24304490µs
Tree:             get:    53681µs, set:   632795µs
ok

Вот код тестового модуля:

-module(arr).

-compile([export_all]).

data1(N) ->
    %% size implies fixed-size array 
    %% but lets be explicit
    array:new([{size, N}, {default, 0}, {fixed, true}]).

data2(N) ->
    %% extensible array
    array:new([{size, N}, {default, -1}, {fixed, false}]).

data3(N) ->
    erlang:make_tuple(N, 0).

data4(_) ->
    gb_trees:empty().

array_set(Array, I, Value) ->
    %% array indexing starts at 0
    array:set(I - 1, Value, Array).

tuple_set(Tuple, I, Value) ->
    %% tuple indexing starts at 1
    setelement(I, Tuple, Value).

tree_set(Tree, I, Value) ->
    gb_trees:enter(I, Value, Tree).

array_get(Array, I) ->
    array:get(I - 1, Array).

tuple_get(Tuple, I) ->
    element(I, Tuple).

tree_get(Tree, I) ->
    gb_trees:get(I, Tree).

get(_, _, 0) ->
    ok;

get(Fun, Data, N) ->
    Fun(Data, N),
    get(Fun, Data, N - 1).

set(_, Data, 0) ->
    Data;

set(Fun, Data, N) ->
    Data1 = Fun(Data, N, N),
    set(Fun, Data1, N - 1).

test() ->
    test(10000).

test(N) ->
    %% fixed-size array
    {S1, D1} = timer:tc(arr, set, [{arr, array_set}, data1(N), N]),
    {G1, _} = timer:tc(arr, get, [{arr, array_get}, D1, N]),
    %% extensible array
    {S2, D2} = timer:tc(arr, set, [{arr, array_set}, data2(N), N]),
    {G2, _} = timer:tc(arr, get, [{arr, array_get}, D2, N]),
    %% tuple
    {S3, D3} = timer:tc(arr, set, [{arr, tuple_set}, data3(N), N]),
    {G3, _} = timer:tc(arr, get, [{arr, tuple_get}, D3, N]),
    %% gb_trees
    {S4, D4} = timer:tc(arr, set, [{arr, tree_set}, data4(N), N]),
    {G4, _} = timer:tc(arr, get, [{arr, tree_get}, D4, N]),
    %% results
    io:format("Fixed-size array: get: ~8wµs, set: ~8wµs~n", [G1 , S1]),
    io:format("Extensible array: get: ~8wµs, set: ~8wµs~n", [G2 , S2]),
    io:format("Tuple:            get: ~8wµs, set: ~8wµs~n", [G3 , S3]),
    io:format("Tree:             get: ~8wµs, set: ~8wµs~n", [G4 , S4]),
    ok.

Оказалось, что новый модуль array эффективнее наивной реализации на кортежах из-за особенности реализации (массив реализован в виде древоподобной структуры). Благодаря этому, массив не выделяет память сразу под все элементы, и не делает это каждый раз (как в случае с кортежами), а выделяет память маленькими кусочками.

В комментариях было отмечено, что:
— нет разницы между fixed-size array и extensible array, если мы сразу знаем, сколько элементов нам нужно. Если начинать с 0 элементов и постепенно увеличивать массив, то результаты могли оказаться другими (Richard Carlsson)
— использование массива оправдано, если массив часто обновляется. Если же массив в основном предназначен только для чтения, то реализация на кортежах в 5 раз дешевле в плаен доступа и менее требовательна к памяти (Ulf Wiger)