Erlang и Great Computer Language Shootout
Залез на страницу Shooutout-а, с целью поупражняться в Эрланге, чтоб быстро, и не совсем штоб зазря. Выбрал вот этот тест:
Reverse-complement
http://shootout.alioth.debian.org/gp4/benchmark.php?test=revcomp&lang=hipe&id=2
И с сожалением обнаружил, что после установки Leopard (это новая версия МакОса) и пересборки (сдуру, не иначе) Эрланга перестал работать HiPE. Пока это недоразумение не решено - прошлось отлаживаться на интерпретаторе, но я теперь не знаю, насколько мой код быстрее.
А он быстрее. В BEAM он правда не намного быстрее - процентов на 5, но на последнем релизе в HiPE я ожидаю, что он окажется заметно быстрее. И он однозначно понятнее, я думаю, быстрее его сделать сложно - разве что тонкости какие-нибудь прощелкал, вроде Хайповского вывода типов, которых я не знаю.
Что я сделал -
1) Перевел чтение на бинарный режим. Это довольно прямолинейно, заметного выигрыша дать не должно, но немного дало, так, по мелочи, так как все равно используется тормозной модуль io, a быстрым file стандартный ввод вроде как читать нельзя. Это, кстати, причина, по которой сосут многие Эрланговские тесты на этом сайте - они все работают через стандартный ввод-вывод. Доверять им особо не надо.
2) Код был запутанный. Написал по человечески - выделил функцию, перекодирующую символы в отдельную функцию. Так - правильно. И, кстати, должно быть быстрее, так как позволит Хайпу вывести тип этой функции. К тому же, она все равно проинлайнится, так что бояться этого не надо.
3) Полностью переделал форматирование перекодированной строки - в оригинале оно было сделано через задницу, я минут десять вкуривал по коду, что происходит, чуть голову не сломал. Теперь - просто и понятно, да и должно быть быстрее.
4) постарался собрать всю грязь в одном месте, выделив чистый код в отдельные функции - не могу я, когда по другому, это на скорость не влияет - но просто ужасно некрасиво.
В результате, имею только 5% выигрыша в BEAM :). Ну, это и понятно - там до меня люди тоже не просто так писали, вылизывали поди код под профайлером, сильно такое обогнать тяжело. А сколько будет в HiPE - не знаю, он у меня не работает. Может, и медленнее, черт его знает :).
Собственно, код - я его отправил, но на сайт его пока не выложили:
-module(revcomp).
%% The Computer Language Shootout
%% http://shootout.alioth.debian.org/
%%
%% contributed by Vlad Balin
-compile( [ native, { hipe, o3 } ] ).
-compile( [ inline, { inline_size, 100 } ] ).
-export([main/1]).
main([_Args]) ->
io:setopts( [ binary ] ),
loop(),
halt().
loop() -> loop( [] ).
%% Buffer = iolist()
loop( Buffer ) ->
case io:get_line('') of
eof -> flush( Buffer, << >> );
<< ">", _/bytes >> = Head ->
flush( Buffer, Head ),
loop( [] );
Line -> loop( rev_comp_line( Line, Buffer ) )
end.
%% Buffer, Suffix ) -> iolist().
%% Buffer = Suffix = iolist().
%% Format and write Buffer with sequence followed by Suffix text
flush( Buffer, Suffix ) ->
Text = format( list_to_binary( Buffer ), Suffix ),
io:put_chars( Text ).
%% format( Buffer, Suffix ) -> iolist().
%% Buffer = bytes(), Suffix = iolist().
%% Split Buffer into 60-char lines, append Suffix to the end of buffer.
format( << Line:60/bytes, Rest/bytes >>, Suffix ) -> [ Line, 10 | format( Rest, Suffix ) ];
format( << >>, Suffix ) -> Suffix;
format( Line, Suffix ) -> [ Line, 10, Suffix ].
%% rev_comp( Line, Buffer ) -> Buffer.
%% Line = bytes().
%% Buffer = string().
rev_comp_line( << _:8 >>, Buffer ) -> Buffer;
rev_comp_line( << H, Rest/bytes >>, Buffer ) -> rev_comp_line( Rest, [ rev_comp( H ) | Buffer ] ).
%% rev_comp( char() ) -> char().
rev_comp( $A ) -> $T;
rev_comp( $C ) -> $G;
rev_comp( $G ) -> $C;
rev_comp( $T ) -> $A;
rev_comp( $U ) -> $A;
rev_comp( $M ) -> $K;
rev_comp( $R ) -> $Y;
rev_comp( $Y ) -> $R;
rev_comp( $K ) -> $M;
rev_comp( $V ) -> $B;
rev_comp( $H ) -> $D;
rev_comp( $D ) -> $H;
rev_comp( $B ) -> $V;
rev_comp( $a ) -> $T;
rev_comp( $c ) -> $G;
rev_comp( $g ) -> $C;
rev_comp( $t ) -> $A;
rev_comp( $u ) -> $A;
rev_comp( $m ) -> $K;
rev_comp( $r ) -> $Y;
rev_comp( $y ) -> $R;
rev_comp( $k ) -> $M;
rev_comp( $v ) -> $B;
rev_comp( $h ) -> $D;
rev_comp( $d ) -> $H;
rev_comp( $b ) -> $V;
rev_comp( $N ) -> $N;
rev_comp( $S ) -> $S;
rev_comp( $W ) -> $W;
rev_comp( $n ) -> $N;
rev_comp( $s ) -> $S;
rev_comp( $w ) -> $W.
Reverse-complement
http://shootout.alioth.debian.org/gp4/benchmark.php?test=revcomp&lang=hipe&id=2
И с сожалением обнаружил, что после установки Leopard (это новая версия МакОса) и пересборки (сдуру, не иначе) Эрланга перестал работать HiPE. Пока это недоразумение не решено - прошлось отлаживаться на интерпретаторе, но я теперь не знаю, насколько мой код быстрее.
А он быстрее. В BEAM он правда не намного быстрее - процентов на 5, но на последнем релизе в HiPE я ожидаю, что он окажется заметно быстрее. И он однозначно понятнее, я думаю, быстрее его сделать сложно - разве что тонкости какие-нибудь прощелкал, вроде Хайповского вывода типов, которых я не знаю.
Что я сделал -
1) Перевел чтение на бинарный режим. Это довольно прямолинейно, заметного выигрыша дать не должно, но немного дало, так, по мелочи, так как все равно используется тормозной модуль io, a быстрым file стандартный ввод вроде как читать нельзя. Это, кстати, причина, по которой сосут многие Эрланговские тесты на этом сайте - они все работают через стандартный ввод-вывод. Доверять им особо не надо.
2) Код был запутанный. Написал по человечески - выделил функцию, перекодирующую символы в отдельную функцию. Так - правильно. И, кстати, должно быть быстрее, так как позволит Хайпу вывести тип этой функции. К тому же, она все равно проинлайнится, так что бояться этого не надо.
3) Полностью переделал форматирование перекодированной строки - в оригинале оно было сделано через задницу, я минут десять вкуривал по коду, что происходит, чуть голову не сломал. Теперь - просто и понятно, да и должно быть быстрее.
4) постарался собрать всю грязь в одном месте, выделив чистый код в отдельные функции - не могу я, когда по другому, это на скорость не влияет - но просто ужасно некрасиво.
В результате, имею только 5% выигрыша в BEAM :). Ну, это и понятно - там до меня люди тоже не просто так писали, вылизывали поди код под профайлером, сильно такое обогнать тяжело. А сколько будет в HiPE - не знаю, он у меня не работает. Может, и медленнее, черт его знает :).
Собственно, код - я его отправил, но на сайт его пока не выложили:
-module(revcomp).
%% The Computer Language Shootout
%% http://shootout.alioth.debian.org/
%%
%% contributed by Vlad Balin
-compile( [ native, { hipe, o3 } ] ).
-compile( [ inline, { inline_size, 100 } ] ).
-export([main/1]).
main([_Args]) ->
io:setopts( [ binary ] ),
loop(),
halt().
loop() -> loop( [] ).
%% Buffer = iolist()
loop( Buffer ) ->
case io:get_line('') of
eof -> flush( Buffer, << >> );
<< ">", _/bytes >> = Head ->
flush( Buffer, Head ),
loop( [] );
Line -> loop( rev_comp_line( Line, Buffer ) )
end.
%% Buffer, Suffix ) -> iolist().
%% Buffer = Suffix = iolist().
%% Format and write Buffer with sequence followed by Suffix text
flush( Buffer, Suffix ) ->
Text = format( list_to_binary( Buffer ), Suffix ),
io:put_chars( Text ).
%% format( Buffer, Suffix ) -> iolist().
%% Buffer = bytes(), Suffix = iolist().
%% Split Buffer into 60-char lines, append Suffix to the end of buffer.
format( << Line:60/bytes, Rest/bytes >>, Suffix ) -> [ Line, 10 | format( Rest, Suffix ) ];
format( << >>, Suffix ) -> Suffix;
format( Line, Suffix ) -> [ Line, 10, Suffix ].
%% rev_comp( Line, Buffer ) -> Buffer.
%% Line = bytes().
%% Buffer = string().
rev_comp_line( << _:8 >>, Buffer ) -> Buffer;
rev_comp_line( << H, Rest/bytes >>, Buffer ) -> rev_comp_line( Rest, [ rev_comp( H ) | Buffer ] ).
%% rev_comp( char() ) -> char().
rev_comp( $A ) -> $T;
rev_comp( $C ) -> $G;
rev_comp( $G ) -> $C;
rev_comp( $T ) -> $A;
rev_comp( $U ) -> $A;
rev_comp( $M ) -> $K;
rev_comp( $R ) -> $Y;
rev_comp( $Y ) -> $R;
rev_comp( $K ) -> $M;
rev_comp( $V ) -> $B;
rev_comp( $H ) -> $D;
rev_comp( $D ) -> $H;
rev_comp( $B ) -> $V;
rev_comp( $a ) -> $T;
rev_comp( $c ) -> $G;
rev_comp( $g ) -> $C;
rev_comp( $t ) -> $A;
rev_comp( $u ) -> $A;
rev_comp( $m ) -> $K;
rev_comp( $r ) -> $Y;
rev_comp( $y ) -> $R;
rev_comp( $k ) -> $M;
rev_comp( $v ) -> $B;
rev_comp( $h ) -> $D;
rev_comp( $d ) -> $H;
rev_comp( $b ) -> $V;
rev_comp( $N ) -> $N;
rev_comp( $S ) -> $S;
rev_comp( $W ) -> $W;
rev_comp( $n ) -> $N;
rev_comp( $s ) -> $S;
rev_comp( $w ) -> $W.