Unicode collation NIF работает медленнее, чем реализация Pure Erlang

Question

Я пытаюсь оптимизировать существующую библиотеку сортировки юникода (написанную в Erlang), переписав ее как реализацию NIF. Основной причиной является то, что сортировка - это интенсивная работа процессора.

Ссылка на реализацию: https://github.com/abhi-bit/merger

Unicode сортировки строк 1M с помощью чистого Erlang на основе приоритета очереди:

erlc *.erl; ERL_LIBS="..:$ERL_LIBS" erl -noshell -s perf_couch_skew main 1000000 -s init stop 
Queue size: 1000000 
12321.649 ms 

Unicode сортировки строк 1M с помощью НИФ на основе биномиальной кучи:

erlc *.erl; ERL_LIBS="..:$ERL_LIBS" erl -noshell -s perf_merger main 1000000 -s init stop 
Queue size: 1000000 
15871.965 ms 

Это необычно, я ожидал, что это будет, вероятно, на 10 раз быстрее.

Я включил eprof/fprof, но они не много пользы, когда дело доходит до NIF модулей, ниже, что eprof говорит о выдающихся функциях

FUNCTION           CALLS  %  TIME [uS/CALLS] 
--------           ----- ---  ---- [----------] 
merger:new/0           1 0.00  0 [  0.00] 
merger:new/2           1 0.00  0 [  0.00] 
merger:size/1         100002 0.31 19928 [  0.20] 
merger:in/3          100000 3.29 210620 [  2.11] 
erlang:put/2         2000000 6.63 424292 [  0.21] 
merger:out/1         100000 14.35 918834 [  9.19] 

Я уверен, NIF реализация может быть быстрее, потому что у меня есть чистая реализация кода Unicode, основанная на бинарной куче, использующая динамический массив, и это намного быстрее.

$ make 
gcc -I/usr/local/Cellar/icu4c/55.1/include -L/usr/local/Cellar/icu4c/55.1/lib min_heap.c collate_json.c kway_merge.c kway_merge_test.c -o output -licui18n -licuuc -licudata 
./output 
Merging 1 arrays each of size 1000000 
mergeKArrays took 84.626ms 

Конкретные вопросы Я здесь:

• Сколько замедление ожидается из Erlang < -> C связи в NIF модуле? В этом случае замедление, вероятно, составляет 30x или более между чистой реализацией C и NIF.
• Какие инструменты могут быть полезны для отладки замещения NIF (как в данном случае)? Я попытался использовать perf top, чтобы увидеть вызов функции, верхние (показывали некоторые шестнадцатеричные адреса), поступали из «beam.smp».
• Каковы возможные области, которые я должен посмотреть на оптимизацию NIF? Например: я слышал, что нужно перенести данные между Erlang на C и наоборот, есть ли еще такие области для рассмотрения?

Answer 1

Накладные расходы на вызов NIF крошечные. Когда время выполнения Erlang загружает модуль, который загружает NIF, он исправляет код луча модуля инструкцией эмулятора для вызова в NIF. Сама инструкция выполняет лишь небольшое количество настроек до вызова функции C, реализующей NIF. Это не та область, которая вызывает проблемы с производительностью.

Профилирование NIF - это то же самое, что профилирование любого другого кода C/C++. Судя по вашему Makefile, кажется, что вы разрабатываете этот код на OS X. На этой платформе, предполагая, что у вас установлен XCode, вы можете использовать Instruments application с инструментом CPU Samples, чтобы узнать, где ваш код проводит большую часть своего времени. В Linux вы можете использовать callgrind tool of valgrind вместе с Erlang emulator built with valgrind support для измерения вашего кода.

Что вы найдете, если вы используете эти инструменты на вашем коде, например, что perf_merger:main/1 проводит большую часть своего времени в merger_nif_heap_get, что, в свою очередь, тратит заметное количество времени в CollateJSON. Кажется, что эта функция вызывает convertUTF8toUChar и createStringFromJSON совсем немного. Ваш NIF также, кажется, выполняет много распределения памяти. Это те области, на которых вы должны сосредоточиться, чтобы ускорить ваш код.