Страницы

вторник, 28 февраля 2012 г.

Pattern matching или перегрузка функций

  
Обязательно прочтите PS ;)

    Итак у Erlang-a замечательная функциональная парадигма. Собственно поэтому некоторые особо  одаренные программисты просто вешаются увидев, когда кто-то пишет на эрланге не в функциональном стиле. Собственно этот пост призван расставить все точки на "И". Пишем абстрактный код вида




-module(func).
-export([test_function_over/1,test_function/1]).

test_function_over(Elem)->
test_function_over_low(Elem rem 2)
.
test_function_over_low(1)->
1;
test_function_over_low(_)->
0.

test_function(Elem)->
case Elem rem 2 of
1 -> 1;
_ -> 0
end



Две функции возвращают четность числа. Далее используем наш любимый модуль

-module(meash_loop).
-export([loop/2]).



loop(Fun,List) when is_list(List) ->
First=now(),
lists:map(Fun,List),
Second=now(),
timer:now_diff(Second,First)
;

loop(Fun,Num)->
First=now(),
lists:map(Fun,lists:seq(1, Num) ),
Second=now(),
timer:now_diff(Second,First)
.



Открываем консоль, и измеряем скорость работы варианта с перегрузкой функции.


Fun={func,test_function_over}.
{func,test_function_over}
2> meash_loop:loop(Fun,1000000).
214185
3> meash_loop:loop(Fun,1000000).
201673
4> meash_loop:loop(Fun,1000000).
172881
5> meash_loop:loop(Fun,1000000).
151168
6> meash_loop:loop(Fun,1000000).
210622
7> meash_loop:loop(Fun,1000000).
175140
8> meash_loop:loop(Fun,1000000).
135384
9> meash_loop:loop(Fun,10000000).


А теперь вариант с обычным case

10> Fun1={func,test_function}.
{func,test_function}
11> meash_loop:loop(Fun1,10000000).
1815741
12> meash_loop:loop(Fun1,10000000).
1395509
13> meash_loop:loop(Fun1,10000000).
1408302
14> meash_loop:loop(Fun1,10000000).
1380560
15> meash_loop:loop(Fun1,1000000).
130111
16> meash_loop:loop(Fun1,1000000).
114137
17> meash_loop:loop(Fun1,1000000).
111419
18> meash_loop:loop(Fun1,100000000).
24698272


Но....это не все! В последней функции мы тестируем 100 миллионов записей..и если запустить его через перегруженную функцию...


meash_loop:loop(Fun,100000000).

Crash dump was written to: erl_crash.dump
eheap_alloc: Cannot allocate 1425410620 bytes of memory (of type "old_heap").


Нода вообще упала. И естественно повторим опыт снова.

Fun={func,test_function_over}.
{func,test_function_over}
2> Fun1={func,test_function}.
{func,test_function}
3> meash_loop:loop(Fun,100000000).

Crash dump was written to: erl_crash.dump
eheap_alloc: Cannot allocate 912262800 bytes of memory (of type "heap").
Aborted


То есть перегрузка перегрузке рознь и надо иметь ввиду, что мы можем вообще упасть к чертовой матери. Ну и если есть возможность использовать таки оператор case вместо перегрузки, то его имеет смысл использовать, так как он просто работает в два раза быстрее. Хотя любого программиста, знающего хотя бы на начальном уровне С, это не должно вызвать удивление. Для чистоты эксперимента расширим наши функции - будем проверять четыре случая.



-module(func).
-export([test_function_over/1,test_function/1]).

test_function_over(Elem)->
test_function_over_low(Elem rem 4)
.
test_function_over_low(1)->
1;
test_function_over_low(2)->
1;
test_function_over_low(3)->
1;
test_function_over_low(_)->
0.

test_function(Elem)->
case Elem rem 4 of
1 -> 1;
2 -> 1;
3 -> 1;
_ -> 0
end

.




Запускаем...



Erlang R14B (erts-5.8.1) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.8.1 (abort with ^G)
1> Fun={func,test_function_over}.
{func,test_function_over}
2> meash_loop:loop(Fun,1000000).
220398
3> meash_loop:loop(Fun,1000000).
233658
4> meash_loop:loop(Fun,1000000).
189970
5> meash_loop:loop(Fun,1000000).
154579
6> meash_loop:loop(Fun,10000000).
3249755
7> Fun1={func,test_function}.
{func,test_function}
8> meash_loop:loop(Fun1,10000000).
1890353
9> meash_loop:loop(Fun1,10000000).
1445280
10> meash_loop:loop(Fun1,10000000).
1457562
11> meash_loop:loop(Fun1,1000000).
112326
12> meash_loop:loop(Fun1,1000000).
141889
13> meash_loop:loop(Fun1,1000000).
119721
14> meash_loop:loop(Fun1,1000000).
115111
15>




Собственно отставание перегруженной функции примерно в два раза - к слову сказать это весьма не плохой результат, но все же быстрее простой оператор case.

P.S
  В комментариях тема раскрывается еще больше, не знаю подводит ли итог. Как оказалось много позже собственно благодаря вот этому,
Erlang раскатывает перегрузку функции в последовательность CASE.
Ну и обозначенные выше тесты  были слишком просты, каюсь был грешен, что бы склонить  чашу весов в чью-то сторону. Собственно, и склонять их в чью-то сторону не хотел. Тут вопрос остается лишь в том, кто лучше оптимизирует исходный код ты или компилятор, пока человек наверно выигрует раз case до сих пор не упразднили.

P.S.S
Это не призыв применять только оператор case и забыть вообще про функциональное программирование. Это призыв не фанатеть от убойной функциональности эрланга.

14 комментариев:

Костюшкин Сергей комментирует...

Статья левая в ней почти нет никакой правды, начиная от способа тестирования и заканчивая выводами автора.

Богдан комментирует...

больше конкретики ааа?!

Костюшкин Сергей комментирует...

Тест из статьи:

14> clause_vs_case_false:test(10000).
Fun:2560
Case:2013
ok
15> clause_vs_case_false:test(100000000).

Crash dump was written to: erl_crash.dump
eheap_alloc: Cannot allocate 1140328500 bytes of memory (of type "old_heap").
Aborted

Одна из операций пристутсвуюящая в тесте:
1> lists:seq(1, 10000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29|...]
2> lists:seq(1, 100000000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29|...]

Crash dump was written to: erl_crash.dump
eheap_alloc: Cannot allocate 912262800 bytes of memory (of type "heap").
Aborted
Я думаю на данном этапе уже можно было бы не продолжать
но я доведу идею до конца

Пару минут, напишу корректный тест.

Костюшкин Сергей комментирует...
Этот комментарий был удален автором.
Костюшкин Сергей комментирует...

Мой тест:

Eshell V5.8.4 (abort with ^G)
1> c(clause_vs_case_true).
{ok,clause_vs_case_true}
2> clause_vs_case_true:test(10000).
Fun: 1541µs
Case: 1551µs
ok
3> clause_vs_case_true:test(100000000).
Fun: 8551834µs
Case: 8522188µs
ok

Исходники моего теста:
-module(clause_vs_case_true).
-compile(export_all).

function_over(1) ->
1;
function_over(_) ->
0.

function_case(Elem) ->
case Elem of
1 -> 1;
_ -> 0
end.

loop(Fun, Data, 0) ->
Fun(Data rem 2);
loop(Fun, Data, N) ->
Fun(Data rem 2),
loop(Fun, N - 1, N - 1).

test(N) ->
Data = N,
{Fun, _} = timer:tc(?MODULE, loop, [{?MODULE, function_over}, Data, N]),
{Case, _} = timer:tc(?MODULE, loop, [{?MODULE, function_case}, Data, N]),
io:format("Fun:~8wµs~nCase:~8wµs~n", [Fun, Case]).

Богдан комментирует...

Это лишь доказывает что перегрузка функция еще и больше памяти жрет

Богдан комментирует...

Чем обычный case ....статья была о том, что лучше использовать,а не возможно ли завалить ноду или нет..

Костюшкин Сергей комментирует...

Во первых это ничего не доказывает, потому что вы не написали нормальный тест. То что вы написали это лишь пародия.
Во вторых в эрланге нет перегрузок. Слово перегрузка описывает не способ написания кода, а реализацию на низком уровне.
В третих в эрланге ничто не жрет память, этот язык спроектирован таким образом чтобы каждый отдельно взятый процесс работал с небольшим объемом данных. Большие массивы данных должны хранится в бинарном виде или в разделяемой памяти коей по сути является ets.
В четвертых либо не говорите о высоких материях, либо разберись в предмете перед тем как что-то писать.

Костюшкин Сергей комментирует...

По теме вопроса.
Клозы функций и кейс на низком уровне реализованы идентично. Разница во времени в моих тестах в пределах нормальной погрешности.
В вашем же тесте клозы функций отрабатывали дольше по той причине что сама по себе операция вызова функции более тяжелая чем кейс. Т.е. выбор нужной клозы функции и вызов функции это операции не равнозначные.

Богдан комментирует...

как раз бинари и могут сожрать память...когда я говорю про жрет память,я не имею ввиду, что она течет, а говорю что выполнение операции через перегруженную функцию похоже заняло больше памяти( что в принципе не является сюрпризом )....Насчет клозы функции - конечно дольше, о чем и пишется...насчет в моем тесте...Сергей 10 тыс - это даже не показательная выборка - раз уж пошло это как ты любишь говорить некорректно !!!и ли ты думаешь мне просто делать было нехрен прогонять тесты на миллионе записей...

Костюшкин Сергей комментирует...

Еще раз:
1. Бинарные данные хранятся более компактно, иначе в них просто не было бы смысла.
2. Выбор клозы функции и case равнозначные операции, причем данная операция делается оооочень быстро, и нужно очень хорошо подумать перед тем как написать тест который это докажет.
3. Вызов функции абсолютно в любом языке является достаточно тяжелой операцией, но это не значит что от них нужно отказываться, ибо если мы хотим суперскорость то ассемблер никто не отменял, но в то же время вызов функции операция намного более быстрая чем создание объекта, например.

Богдан комментирует...

Еще раз читай заголовки...

Dmitry Klionsky комментирует...

perldev,

Ваш исходный тест на самом деле не раскрывает тему.

>> Клозы функций и кейс на низком уровне реализованы идентично.

Как Сергей и написал Вам на самом деле нужно сравнивать функции типа:

function_over(1) ->
1;
function_over(_) ->
0.

function_case(Elem) ->
case Elem of
1 -> 1;
_ -> 0
end.

Возьмите его пример и скомпилируйте с флагом 'S':

> c("clause_vs_case_true.erl", ['S']).

Посмотрите результат в clause_vs_case_true.S

Обе функции идентичны:

{function, function_over, 1, 2}.
{label,1}.
{line,[{location,"clause_vs_case_true.erl",4}]}.
{func_info,{atom,clause_vs_case_true},{atom,function_over},1}.
{label,2}.
{test,is_eq_exact,{f,3},[{x,0},{integer,1}]}.
return.
{label,3}.
{move,{integer,0},{x,0}}.
return.


{function, function_case, 1, 5}.
{label,4}.
{line,[{location,"clause_vs_case_true.erl",9}]}.
{func_info,{atom,clause_vs_case_true},{atom,function_case},1}.
{label,5}.
{test,is_eq_exact,{f,6},[{x,0},{integer,1}]}.
return.
{label,6}.
{move,{integer,0},{x,0}}.
return.

Разбег в тестах Сергея, как я понимаю, это результат работы сборщика мусора. Я менял местами вызовы т.е.

{Case, _} ...
{Fun, _} ...

И получал что Fun выполняется быстрее чем Case.

В Вашем же тесте, при тестировании перегруженной функции, присутствует косвенный вызов функции. Поэтому тест и выполняется медленнее.

Богдан комментирует...

Не раскрывает на низком уровне
они реализованы идентичны действительно:)
Первое тесты очень простые, что не мою сторону говорит.
Компилятор преобразует эти перегрузки в case, что вы и написали - а вот тут вопрос как?
тут тут можно почитать как.
Для себя делал выбор что case целесообразно использовать если не уверены что компилятор преобразует правильно ваши перегруженные функции, или если перегрузка довольно сложна.

ну и про принудительное erlang:garbage_collect() я не знал