Erlang NIF wrapper for CRC16 algorithm.

[Анна Мошкина]

Столкнулась с необходимостью подсчета контрольной суммы с помощью алгоритма CRC-16.

В стандартной библиотеке Erlang'а этот алгоритм не реализован. Единственное найденное готовое решение:

https://github.com/ctennis/erlang-modbus/blob/master/src/crc16.erl

оказалось очень медленным (из-за медленной выборки n-ого элемента из списка), поэтому от него пришлось отказаться.

Это привело меня к реализации Erlang NIF, которая оказалась быстрым и простым решением.

Исходники здесь: https://github.com/amoshkina/erlang_crc16/

[Max Lapshin]

Только вот у меня не сходятся цифры из nif и из crc16.erl

[Max Lapshin]

Но вообще я немного поправил crc16.erl и получились такие цифры:

nif:  1455 us

slow: 499148 us

fast: 6646 us

Код crc16.erl:

https://gist.github.com/maxlapshin/7830701

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

[Danil A. Zagoskin]

Выносить подсчет хешей в NIF целиком может быть чревато. Если нужно считать хеш от многих мегабайт (или даже гигабайт) данных, использование NIF сразу на всем блобе вызовет пичальку в шедулере. Имеет смысл еще в эрланге нарезать ввод на фрагменты нужной длины, и скармливать их NIFу или воспользоваться новым модным enif_consume_timeslice

Кроме того прежде чем отказываться от реализации на эрланге по причине производительности я бы попробовал заменить список на тьюпл и lists:nth/2 на element/2 – это должно сильно ускорить выборку. Это может оказаться даже быстрее, чем предложенный Максом вариант на клозах.

6 декабря 2013 г., 23:03 пользователь Анна Мошкина <a.v.mo...@gmail.com> написал:

--
Вы получили это сообщение, поскольку подписаны на группу Erlang по-русски.
 
Чтобы отказаться от подписки на эту группу и перестать получать из нее сообщения, отправьте электронное письмо на адрес erlang-russia...@googlegroups.com.
Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу erlang-...@googlegroups.com.
Настройки подписки и доставки писем: https://groups.google.com/groups/opt_out.

[Анна Мошкина]

Eshell V5.10.3  (abort with ^G)

1> crc:crc16(<<1,2,3>>).

24929

2> crc16:calc(<<1,2,3>>).

24929

3> crc:crc16(<<1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0>>).

53750

4> crc16:calc(<<1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0>>).

63185

5> integer_to_list(53750, 16).

"D1F6"

6> integer_to_list(63185, 16).

"F6D1"

Выходит, что для достаточно длинных последовательностей меняются местами байты.

пятница, 6 декабря 2013 г., 23:26:10 UTC+4 пользователь Max Lapshin написал:

[Ilya I. Ashchepkov]

Для crc16 есть несколько различных алгоритмов.

У меня при расчете используется не список, а кортеж и n-ный элемент из него достается.

Правда замеров я не проводил.

2013/12/7 Анна Мошкина <a.v.mo...@gmail.com>

Eshell V5.10.3  (abort with ^G)

1> crc:crc16(<<1,2,3>>).

24929

2> crc16:calc(<<1,2,3>>).

24929

3> crc:crc16(<<1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0>>).

53750

4> crc16:calc(<<1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0>>).

63185

5> integer_to_list(53750, 16).

"D1F6"

6> integer_to_list(63185, 16).

"F6D1"

 

1> integer_to_list(24929, 16).
"6161"

Вероятно тут тоже меняется.

Очень похоже на использование в одном случае little (C/C++), а в другом - big endian (Erlang)

 

Выходит, что для достаточно длинных последовательностей меняются местами байты.

пятница, 6 декабря 2013 г., 23:26:10 UTC+4 пользователь Max Lapshin написал:

Только вот у меня не сходятся цифры из nif и из crc16.erl

--

Вы получили это сообщение, поскольку подписаны на группу Erlang по-русски.
 
Чтобы отказаться от подписки на эту группу и перестать получать из нее сообщения, отправьте электронное письмо на адрес erlang-russia...@googlegroups.com.
Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу erlang-...@googlegroups.com.
Настройки подписки и доставки писем: https://groups.google.com/groups/opt_out.

--
С уважением,
Ащепков Илья koc...@gmail.com

[Evgeny Khramtsov]

Fri, 6 Dec 2013 23:30:05 +0400

"Danil A. Zagoskin" <da...@st-olen.ru> wrote:

> Выносить подсчет хешей в NIF целиком может быть чревато. Если нужно
> считать хеш от многих мегабайт (или даже гигабайт) данных,
> использование NIF сразу на всем блобе вызовет пичальку в шедулере.

Накидай миллион мессаг в процесс - это тоже вызовет печальку в шедулере.

[begemot_sun]

Оффтоп:

Товарищи, за 1.5 года чтения рассылки я ни разу не видел девушек-erlang'исток в качестве топик-стартера. Приветствуем в нашим рядах такую замечательную особу. :)

[Анна Мошкина]

1> integer_to_list(24929, 16).
"6161"
Вероятно тут тоже меняется.
Очень похоже на использование в одном случае little (C/C++), а в другом - big endian (Erlang)

Забавное совпадение :)

 Если нужно считать хеш от многих мегабайт (или даже гигабайт) данных, использование NIF сразу на всем блобе вызовет пичальку в шедулере. Имеет смысл еще в эрланге нарезать ввод на фрагменты нужной длины, и скармливать их NIFу

Я передаю в функцию небольшие объемы данных, байт по 100. Но когда происходит слишком частое обращение к этой функции даже с небольшими данными, производительность сильно падает -- это видно и в профайлере и просто по загрузке CPU. А при использовании NIF эта проблема отпала. Остальные решения тоже проверю.