8

Начал недавно проект по разработке SIMD бибилиотек для С++ на Fasm под 64-bit Linux. Интересно услышать мнение матерых программеров как о самом проекте, так и качестве кода. Вот вебсайт, где можно качнуть исходники и посмотреть документацию, которая уже есть.

Сайт проекта на sourceforge

18
  • 2
    Очень круто. Особенно впечатлен реализацией Бойер-Мура. У вас есть какой-нибудь roadmap и приоритетные планы? Хотелось бы включиться в разработку, так что ждите pull request'a :) 23 авг 2012 в 17:13
  • 1
    А почему Вы решили писать на чистом ассемблере? Почему бы не написать на Си с ассемблерными вставками?
    – skegg
    23 авг 2012 в 21:09
  • 1
    >QuickSort Вы какой брали gnu или apple? Ни то ни другое. Я вас понимаю что лучше взять готовый алгоритм чем писать с нуля. И вы правильно мыслите. Но я пошел другим путем. За основу взял идеи Вирта из его книги Алгоритмы и Структуры данных и написал свои инварианты, которые быстрее, поскольку понимают архитектуру процессора. Вывод: инварианты сортировки и ее реализация полность авторские. Это мой собственный код. Проблема N^2 решается через RadixSort. Я специально реализовал 2 метода, чтобы можно было выбрать подходящий под задачу. Для RadixSort нужен двойной объем памяти и линейное время.
    – Jack Black
    23 авг 2012 в 21:24
  • 1
    Насколько Ваш ассемблерный код позволяет ускорить вычисления?
    – skegg
    23 авг 2012 в 21:50
  • 1
    >Насколько Ваш ассемблерный код позволяет ускорить вычисления? К сожалению куда-то исчезла кнопка комментарий. Пишу сюда. Все зависит от алгоритма. На некоторых в 3-4 раза (там где вычисления строго последоваетельные) на других раза в 2. Там где код можно запараллелить раз в 5. Я так понял что мне нужно сделать какие-то сравнительные тесты и выложить их вместе с проектом.
    – Jack Black
    23 авг 2012 в 22:22

2 ответа 2

6

Вот есты для библиотек 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 Я использовал другую функцию ядра. Она позволяет считать с наносекундной точность. Да,я кстати исправил функцию расчета времени. Выслал обновленный вариант вам на почту. Если будет интересно могу сделать С-шную функцию которая даже вам такты процессора посчитает потраченного на код. Правда туда войдет и время потраченное процессором на выполнение других задач, поскольку тот счетчик не уникальный для процесса, а просто счетчик тактов процессора, так сказать его внутренние часы.

12
  • Библиотеки GNU действительно местами написаны отвратительно. Однажды обнаружил макрос длиной около 100 строк. Однако не забывайте, что они написаны на Си и с расчетом на минимизацию усилий для портирования на разные архитектуры. А теперь попробуйте портировать Ваш код, очень оптимизированный и использующий многие возможности x86_64, на другую архитектуру, на тот же х86. Может, подумать об улучшении GCC?
    – skegg
    24 авг 2012 в 18:03
  • 1
    Потом, мне кажется, представленный Вами тест не совсем честен. Вы сравниваете такую громоздкую функцию как sscanf, которая кроме лексического приведения типов должна заниматься еще кучей вещей, чтобы работать как ей положена, с легонькой "однофункциональной" функцией, заточенной строго под одну архитектуру. Лучше напишите на Си аналог вашего ассемблерного кода (насколько это возможно) и уже его сравнивайте.
    – skegg
    24 авг 2012 в 18:13
  • 1
    }}}Может, подумать об улучшении GCC? Доктор сказал в морг - значит в морг. Там сам черт ногу сломит в том коде. У меня была конкретная задача. И проще было решить ее чем перепилить весь GCC и GNU С lib. К тому же нельзя сеть одним программерским местом сразу на оба стула: портабельности и скорости. Приходится делать выбор в пользу чего-то одного. За портабельность платим скоростью - за скорость - непортабельностью. И тут как говорится все зависит от поставленной задачи. Если бы мне нужно было чтобы работало везде-везде, то тут Python вне конкуренции. А так ассемблер.
    – Jack Black
    24 авг 2012 в 18:16
  • Там для честности представлены еще функция strtoul и strtod. Сравнивайте с ними. Особенно четко видна разница там где используются вещественные числа. Там уже начинается использование XMM регистров процессора, хотя код по прежнему скалярный. А целочисленные варианты используют целочисленные инструкции процесора, так что там нет такого простанства для оптимизации.
    – Jack Black
    24 авг 2012 в 18:27
  • 1
    И опять же: за счет чего достигнуто ускорение, за счет использование более оптимального алгоритма или недоступных из Си возможностей процессора? Кстати, gcc операции с плавающими числами проводит на XMM.
    – skegg
    24 авг 2012 в 18:33
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 <stdio.h>
#include <sys/time.h>

long long
mtime()
{
  struct timeval t;

  gettimeofday(&t, NULL);
  long long mt = (long long)t.tv_sec * 1000 + t.tv_usec / 1000;
  return mt;
}
6
  • 1
    }}}@Jack Black, скачал, собрал и установил Вашу linasm-0.96(beta). Собрал тесты. Компиляция NumbersTest с warnings. Зависит от версии компилятора и настроек предупреждения. Результаты впечатлили. Нужно будет на втором компьютере прогнать тесты. В принципе тенденция сохраняется. }}}Вы планируете делать вариант для Си, а не только для крестов? Да это вообще не проблема. Просто нужно добавить синонимы к именам функции и все. Будет работать и на С. Если у вас есть вопросы или предложения лучше пишите мне на почту [email protected]. Тут лимиты на текстовые сообшения. Ммного не напишешь.
    – Jack Black
    25 авг 2012 в 19:45
  • Да, лимиты. Я обычно преодолеваю их путем дополнений в ответе. Если будут вопросы (если соберусь что-то покрутить), то напишу. Мой email [email protected] Сортировка тоже очень быстро работает (быстрее всех, что я пробовал). Я ее по быстрому собрал для 10000000 int_32, замер дает около 720 msec. Наверное попробую прикрутить ее к своему "измерителю сортировок". Там ближайший конкурент (тоже QuickSort) показывает 930. А попробовать стиле void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); не хотите? Это будет сильно
    – avp
    25 авг 2012 в 20:15
  • Сегодня уже пробовал. И Вот результат: Sorting: 'Classic Quick Sort code' time: 4.382870 sec 'LinAsm Quick Sort code' time: 1.706434 sec 'LinAsm Radix Sort code' time: 1.481228 sec Поробуйте RadixSort. Она еще быстрее, но нужен второй временный буфер такой же длины как и массив. У нее время работы K * N, где К размер ключа (размер элемента массива в байтах). Для int32_t он равен 4. Так что должно быть очень быстро.
    – Jack Black
    25 авг 2012 в 20:25
  • 1
    Разниц много. Кеш. Архитектура, латентность памяти, и самое главное - у Core i5 втроенный контроллер памяти. А RadixSort делает случайные обращения в память и может изгадить процессору весь кеш. Ему постоянно придется его перезатирать. Так что это скорее всего именно благодаря контроллеру памяти Core i5.
    – Jack Black
    25 авг 2012 в 21:09
  • 1
    Вчера выпустил еще один релиз v0.97, где по предложению @avp добавил поддержку языка "С" для всех библиотек. Теперь код функций может линковаться и нормально вызываться из С-шных программ, а не только из С++. Также обновил документацию по всему проэкту и указал имена функций для вызова их из языка С. Подробности тут: linasm.sourceforge.net/news.php
    – Jack Black
    28 авг 2012 в 14:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.