#linux #ассемблер #математика
Начал недавно проект по разработке SIMD бибилиотек для С++ на Fasm под 64-bit Linux. Интересно услышать мнение матерых программеров как о самом проекте, так и качестве кода. Вот вебсайт, где можно качнуть исходники и посмотреть документацию, которая уже есть. Сайт проекта на sourceforge
Ответы
Ответ 1
Вот есты для библиотек LinAsm: Numbers (Преобразование чисел из популярных систем счисления), Time (Преобразвание времени в unix формат и обратно в календарную дату) Array (алгоритмы для работы с массивами). Тесты проведены на Core I5-2500. ################################################################################ # Numbers conversion library speed test # ################################################################################ This test converts 1000000 numbers in 100 rounds. Integer numbers conversion: =========================== Octal numbers conversion: 'sscanf' time: 19.755847 sec 'strtoul' time: 5.476777 sec 'LinAsm' time: 2.952698 sec Hexadecimal numbers conversion: 'sscanf' time: 19.364499 sec 'strtoul' time: 6.264688 sec 'LinAsm' time: 4.190943 sec Decimal numbers conversion: 'sscanf' time: 18.347976 sec 'strtoul' time: 5.220468 sec 'LinAsm' time: 2.785372 sec Floating-point numbers conversion: ================================== Hexadecimal numbers conversion: 'sscanf' time: 26.137860 sec 'strtod' time: 10.961610 sec 'LinAsm' time: 5.795652 sec Decimal numbers conversion: 'sscanf' time: 27.214856 sec 'strtod' time: 15.222347 sec 'LinAsm' time: 2.954274 sec Вторая библиотека ################################################################################ # Time conversion library speed test # ################################################################################ This test converts 1000000 time stamps in 100 rounds. Unix time to Gregorian date conversion: 'gmtime' time: 4.228890 sec 'LinAsm' time: 2.284649 sec Gregorian date to unix time conversion: 'mktime' time: 122.046674 sec # Это не ошибка. Это реальная цифра. 'LinAsm' time: 1.005384 sec Unix time to wall clock time conversion: 'LinAsm' time: 0.871296 sec Wall clock time to unix time conversion: 'LinAsm' time: 0.202490 sec Обе эти бибилиотеки реализуют последовательные вычисления. Там нет SIMD инструкций. Вот тест векторного кода реализованного в Array библиотеке. ################################################################################ # Array library speed test # ################################################################################ This test operates on 10000000 elements wide flt64_t arrays in 100 rounds. Addition: Classic scalar code time: 1.407980 sec LinAsm vector code time: 1.379985 sec Subtraction: Classic scalar code time: 1.426498 sec LinAsm vector code time: 1.379655 sec Multiplication: Classic scalar code time: 1.397805 sec LinAsm vector code time: 1.386163 sec Division: Classic scalar code time: 6.425936 sec LinAsm vector code time: 3.445004 sec Absolute value: Classic scalar code time: 1.008767 sec LinAsm vector code time: 0.921362 sec Square root value: Classic scalar code time: 11.988184 sec LinAsm vector code time: 2.745969 sec Min value: Classic scalar code time: 1.329877 sec LinAsm vector code time: 0.665184 sec Max value: Classic scalar code time: 1.320772 sec LinAsm vector code time: 0.665314 sec Convolution value: Classic scalar code time: 1.269394 sec LinAsm vector code time: 1.083574 sec Sorting: Classic Quick Sort code time: 1.848767 sec LinAsm Quick Sort code time: 0.770507 sec LinAsm Radix Sort code time: 0.332851 sec Занятно то, что простые операции типа сложения, вычитиания и умножения не дает заметного прироста скорости, а вот деление уже быстрее в 2 раза. Нетривиальная задача по извлечению квадратного корня быстрее в 4.5 раза. Min и Max, которые традиционно реализуются через сравнение и обмен, в векторном коде быстрее 2 раза. Все потому что паралельный код не содержит инструкций ветвления. Свертка двух массивов чуть быстрее в векторном исполнении, а вот быстрая сортировка на ассемблере быстре GNU Quick Sort в 2.5 раза. Radix Sort быстрее в 5.5 раз. Все тесты с массивами проводились с двойной точность, которая нужна в вычислительных алгоритмах. Можно конечно попробовать еще прогнать тесты с одинарной точность, но я не думаю, что результат будет сильно отличаться, хотя возможно всякое. Итог всего тестирования: Чем сложнее и нетривиальнее алгоритм, тем больший прирост производительности мы можем получить переписав его на ассемблере. Совсем простые алгоримы не дают того прироста скорости, который получается для более сложных, но тоже выигрывают от параллелизации. Кому интересна детальная информация о процедуре тестирования алгоритмов, вот страничка в интернете, с графиками производительности различных функций. http://linasm.sourceforge.net/about/performance.php }}}Просто возраст уже не позволяет верить в сказки об эффективности ассемблерных программ. Мне тоже. Именно поэтому все нужно проверять. Вот ссылка на исходные тексты для тестов, которые пока успел сделать SpeedTests. Можете их скомпилировать и запустить. Заодно и мне будет интересно как оно отработает на вашем железе. Потому что провести тесты на всех процессорах - просто не могу, т.к. их у меня нет. }}}Насколько исполняемый код Вашей библиотеки учитывает модель процессора (superscalar, multithreading) Они сейчас все superscalar, а multithreading никак на скорость однопоточных приложений не влияет. Прирост будет только если будет несколько параллельных потоков. Библиотеки сами не плодят дополнительные потоки. Но вы можете создать еще один поток а там запустить код бибилиотеки. Все функции реентерабельны, так что одна другой мешать не будет. Разве что некоторые могут полезть читать данные из одних и тех же областей. }}} Как Вы сами объясняете такой результат - загрузкой конвейера? Или Вы используете существенно отличное от компилятора "множество" инструкций? Правильно выбранный алгоритм Оптимизация кода Использование тех инструкций процессора которые наиболее полно реализуют алгоритм Хакерские трюки в коде как в книге Hacker's Delight Henry S. Warren, Jr Знание архитектуры процессора и методов оптимизациий кода. Книг Куча. Агнер Фог - отлично для начала. Но он на английском. Желание этим заниматься и правильно растущие руки. Список можно продолжать до бесконечности. Одним словом опыт и понимание апаратной части. }}} Если будете делать сравнительные тесты, то очень интересны были бы также Ваши комментарии к их результатам. Какие могут быть комментарии. Библиотека gnu С написана ужасно и очень бородатая. Ее делали еще тогда когда не было никаких векторные расширений и многоядерных процессоров. Плюс код писали те кто мог, а не те кто хорошо в программированнии разбирается. Весь GNU Linux почти написан студентами и энтузиастами. Так что там куча возможностей для оптимизации. }}} Какие у вас успехи в анализе временных рядов? Какие именно ряды анализируете? Случайные нестациорнарные временные ряды типа белого шума с негаусовыми приращениями. В качестве приращений используются случайные значения из распределения Лапласса + методы робастной статистики для оценки их статистических параметров, так как это распределения с т.н. тяжелыми хвостами и там нужны другие методы. update-2 Я использовал другую функцию ядра. Она позволяет считать с наносекундной точность. Да,я кстати исправил функцию расчета времени. Выслал обновленный вариант вам на почту. Если будет интересно могу сделать С-шную функцию которая даже вам такты процессора посчитает потраченного на код. Правда туда войдет и время потраченное процессором на выполнение других задач, поскольку тот счетчик не уникальный для процесса, а просто счетчик тактов процессора, так сказать его внутренние часы.Ответ 2
@Jack Black, скачал, собрал и установил Вашу linasm-0.96(beta). Собрал тесты. Компиляция NumbersTest с warnings. У Вас так же, или это особенности моей системы? avp@avp-ubu1:~/src/libasm/SpeedTests$ make g++ NumbersTest.cpp -O2 -llinasm -lrt -o NumbersTest NumbersTest.cpp: In function ‘void GenerateOctInt()’: NumbersTest.cpp:42: warning: format ‘%lo’ expects type ‘long unsigned int’, but argument 3 has type ‘long long unsigned int’ NumbersTest.cpp: In function ‘void GenerateHexInt()’: NumbersTest.cpp:52: warning: format ‘%lx’ expects type ‘long unsigned int’, but argument 3 has type ‘long long unsigned int’ далее аналогично Но сами тесты отработали. Результаты затарил на http://zalil.ru/33705562 Для интересующихся: avp@avp-ubu1:~/src/libasm/SpeedTests$ cat i5-2500/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 42 model name : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz stepping : 7 cpu MHz : 3161.218 cache size : 6144 KB physical id : 0 siblings : 4 core id : 0 cpu cores : 4 далее понятно avp@avp-ubu1:~/src/libasm/SpeedTests$ cat i5-2500/Numbers.txt ################################################################################ # Numbers conversion library speed test # ################################################################################ This test converts 1000000 numbers in 100 rounds. Integer numbers conversion: =========================== Octal numbers conversion: 'sscanf' time: 19 s, 638078632 ns 'strtoul' time: 6 s, 18446744073164380191 ns 'LinAsm' time: 2 s, 738194303 ns Hexadecimal numbers conversion: 'sscanf' time: 19 s, 18446744073670940123 ns 'strtoul' time: 6 s, 252103962 ns 'LinAsm' time: 4 s, 288213175 ns Decimal numbers conversion: 'sscanf' time: 19 s, 18446744073282007241 ns 'strtoul' time: 5 s, 302852802 ns 'LinAsm' time: 3 s, 18446744073404664426 ns Floating-point numbers conversion: ================================== Hexadecimal numbers conversion: 'sscanf' time: 25 s, 435994369 ns 'strtod' time: 11 s, 18446744073587023786 ns 'LinAsm' time: 6 s, 18446744073556690963 ns Decimal numbers conversion: 'sscanf' time: 27 s, 18446744073201001699 ns 'strtod' time: 15 s, 210128276 ns 'LinAsm' time: 3 s, 31213370 ns avp@avp-ubu1:~/src/libasm/SpeedTests$ cat i5-2500/Time.txt ################################################################################ # Time conversion library speed test # ################################################################################ This test converts 1000000 time stamps in 100 rounds. Unix time to Gregorian date conversion: 'gmtime' time: 4 s, 212403207 ns 'LinAsm' time: 2 s, 190016211 ns Gregorian date to unix time conversion: 'mktime' time: 117 s, 102470253 ns 'LinAsm' time: 1 s, 16951672 ns avp@avp-ubu1:~/src/libasm/SpeedTests$ @Jack Black, Вы планируете делать вариант для Си, а не только для крестов? А то писать вещи типа, //gcc libasmqs.c -llinasm #define sortint_32_asc _ZN5Array12QuickSortAscEPjm #define sort(a,n) sortint_32_asc((a),(size_t)(n)) отыскивая их в *.asm несколько неудобно И вычисление времени выполнения в тестах подправьте. update-1 /* avp время в миллисекундах */ #include#include long long mtime() { struct timeval t; gettimeofday(&t, NULL); long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000; return mt; }
Комментариев нет:
Отправить комментарий