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)