Comments 44
В очередной раз показано как в Delphi, предназначенном для быстрой разработки GUI-приложений с доступом к БД, можно делать абсолютно разные вещи, в том числе быстрые математические расчёты.
Кстати, ассемблерные команды SSE с расширениями 4.2, завезли в одну из недавних версий Delphi. До этого приходилось писать ассемблерные вставки в опкодах. Команд AVX в Delphi до сих пор нет. https://m.habr.com/en/post/441392/
Я: «Полнолуние».
Оборотень: «Спасибо».
Я: «Не за что, обращайтесь».
Кстати, я пробовал еще EasyCode c UASM64 в паре с Delphi, тоже весьма удобно, особенно для инструкций, которые Delphi asm не поддерживает. В Delphi линкуется obj файлик из UASM64 без проблем.
OurASMObj.asm
...
TestProc1 Proc FastCall Frame i:Byte
Xor Rax, Rax
Mov Al, i
Xor Al, 0xFF
Ret
TestProc1 EndP....
{$L OurASMObj.obj}
function TestProc1(a: Byte): Byte; external;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var res: byte;
begin
res := TestProc1($AA);
Edit1.Text := inttostr(res);
end;
end.Использовать внешние редакторы ассемблера- на мой взгляд дело вкуса. но для tutorial'а- это было бы через чур. Да и для себя я в этом не вижу смысла- IDE, редактор и дебагер меня вполне устраивают.
Не думали для работы с матрицами 3х3 и 4х4 использовать видеокарту? Вроде как они адаптированы для работы с подобными матрицами...
В матрице 4x4 всего 16 элементов, столько же, сколько у автора машина умеет за одну инструкцию. А вот для видеокарты мне кажется размер матрицы маловат (и эффективность будет низкая)
на карте хорошо гонять очень большие матрицы, когда алгоритм можно распараллелить хотя бы на сотню-другую потоков, и особенно- если еще данные из карты не надо забирать на каждом шаге, а когда загрузили, сделали чисто на карте тыщу шагов, и забрали результат.
Согласен… Лет 15 назад воял на делфи 7 трехмерную игру. Как раз в то время появились шейдеры. Работа с ними осуществлялась через язык HLSL, исполняемый в том числе в делфи. В нем как раз можно было работать с матрицами 3х3 и 4х4. Во что это выросло сейчас — сказать не могу. Делфи в основном использую для управления лабораторными приборами и обработки поступающих с них данных.
Я сначала подумал про Intel IPP, но пишут, что для операций с мелкими матрицами надо использовать MKL. Эти библиотеки сейчас бесплатные. Можно даже найти не очень старые заголовки для Дельфи (2019 года).
Во-вторых, если всё-таки хотите писать самостоятельно, рекомендую обратить внимание на компиляторы Си. Они могут генерировать эффективный ассемблер (в т.ч. с векторизацией) даже из самого примитивного кода безо всяких зачатков оптимизации. Вот например ваши формулы для расчёта обратной матрицы 3*3 обычным методом, просто «в лоб» скопированные в Си-код: gcc.godbolt.org/z/8c4b1G
Получилось с виду неплохо, около половины команд в ассемблере векторная (c окончанием на «pd»), по длине примерно так же, как у вас. Если хотите, можем сравнить реальную скорость.
Предлагать перейти на компиляторы Си- это, простите, моветон, во-первых- это очевидная мысль, а во-вторых- можно, но переписывать проект ради оптимизации десятка-другого мелких функций, когда результат- не гарантирован- плохая затея. Что до M4x4- так тут вообще ситуация патовая- не разложив элементы по регистрам лично я вообще не догадывался, что обращение можно делать не вылезая за пределы исходной матрицы- а без этого- никакая векторизация компилятором не поможет, потому что он отлично векторизует отвратительный алгоритм- с посредственным итоговым результатом.
Они могут генерировать эффективный ассемблер (в т.ч. с векторизацией) даже из самого примитивного кода безо всяких зачатков оптимизации
так в этом-то и соль- примитивный код можно эффективно оптимизировать и векторизовать, но код не всегда примитивный- не зря же Intel придумала свои интринсики software.intel.com/sites/landingpage/IntrinsicsGuide/#
А в случае с обращением матрицы- я в принципе не могу родить код (ни на С, ни на Fortran, ни на Pascal), который можно упаковать в одни регистры- хоть как там будет компилятор оптимизировать его- у меня даже мысли не возникало кидать элементы результата вместо получившихся нулей под диагональю исходной матрицы, чтобы не лезть в стек и минимизировать операции.
Если хотите, можем сравнить реальную скорость
хочу. меня интересует скорость обращения массива из 1млн матриц 4*4*FP64 в 1 поток на 1 ядре Ryzen3900 или любого близкого конкурента- используйте любой компилятор, любой алгоритм обращения, любой язык.
ассемблерный код с gcc.godbolt.org/z/8c4b1G я пока тестирую, и че-то я удивлен- он у меня выдает 490МБ/с, в то время как прямой дельфишный- 3300.
пробежав по коду- у CLANG-а- 63 инструкции, у меня- 64 всего, (это с префетчами + 6 инструкций проверка обусловленности). Но главное- у меня только один divsd, а по Вашей ссылке- два дива, а divsd- очень медленная. просто ужасно медленная- в ней 40 тактов можно потерять как нефиг делать. ну и чтение данных- я использую movupd, а CLANG везде поставил movsd, + невыровненность данных режет скорость чтения с памяти. Вот и получается, что на таком простом коде компилятор сделал простой ассемблер, который, как Вы сказали, «с виду не плохо».
библиотеки-то как раз нашлись, сырцов не нашлось.А почему нельзя без сырцов?
Вы неявно используете массу dll из Винды, и для них тоже нет сырцов.
Предлагать перейти на компиляторы Си- это, простите, моветонНу да, дельфистам сразу слышатся отголоски холиваров «Дельфи vs С++».
Нет, я предлагаю менять не Дельфи, а ассемблер на Си.
А в случае с обращением матрицы- я в принципе не могу родить код (ни на С, ни на Fortran, ни на Pascal), который можно упаковать в одни регистрыВ регистры AVX (или скажем AVX-512) влезает гораздо больше.
хочу. меня интересует скорость обращения массива из 1млн матриц 4*4*FP64 в 1 поток на 1 ядреПоскольку это ваша задача, то давайте вы напишете тестовую программу на Дельфи, а я к ней прикручу сишный вызов. Вам виднее, какие матрицы должны быть, какие примеры данных. Это и как приложение к статье будет полезно.
Но главное- у меня только один divsd, а по Вашей ссылке- два диваС делением нехорошо получилось, да. Но это же легко правится вручную, дописать одну строку D = 1 / D и поменять деление на умножение. Или переключиться на систему команд AVX (-mavx) или AVX2/FMA (-march=haswell), будет одно деление.
В целом я не исключаю, что может быть медленнее, в конце концов, я на эту «оптимизацию» потратил 2-3 минуты. А вы на свою сколько дней?
Даже если придётся векторизовать вручную, на Си это будет компактнее, читабельнее и более гибко, можно легко переключаться между 32/64 битами и относительно легко — между наборами команд.
Вы неявно используете массу dll из Винды, и для них тоже нет сырцов
потому-что дальний вызов. а я где-то выше написал, что просто за вызов у меня штраф, да, я использую виндовые dll- но где? что-то редкое вывести, поток запустить-остановить, раз в пол-часа- данные на диск скинуть, то есть- очень редкие операции- потрачу я по две лишних секунды раз в пять минут- и не замечу. А векторы я свои делю на матрицы- миллиарды раз во все доступные потоки- и на этих миллиардах каждая мкс задержки- накапливается вполне ощутимо.
Еще потому-что сильно не хочется завязываться на чьи-то лицензии- сейчас нас стали проверять на чистоту всего используемого.
Ну и третье- очень было интересно на личном опыте пощупать: с одной стороны, общее мнение «в интернете»- что компиляторы стали такие умные, что оптимизируют лучше любого программиста, а с другой стороны- периодически выходят скромные статьи с разбором профайлингов и сказками про то, как какие-то одинокие самоучки делают умножение матриц на CUDE лучше, чем отдел разработки NVidia. На хабре было несколько примеров: умножение больших матриц, ракетный велосипед для преобразования FP64.toString.
про время- ниже написал- потратил на все- 2 недели, правда, до этого опыта в ассемблере было около нуля, поэтому кодил параллельно с чтением мануалов и описания архитектуры.
про читабельность на Си- я смотрел всякие портянки из интринсиков- честно- не вижу я там читабельности ни в одном месте.
Поскольку это ваша задача, то давайте вы напишете тестовую программу на Дельфи, а я к ней прикручу сишный вызов. Вам виднее, какие матрицы должны быть, какие примеры данных. Это и как приложение к статье будет полезно.
заметано. за выходные выложу сюда линк на гитхаб для игрища.
Можно и просто архивом выложить, без Гитхабов.
периодически выходят скромные статьи с разбором профайлингов и сказками про то, как какие-то одинокие самоучки делают умножение матриц на CUDE лучше, чем отдел разработки NVidia. На хабре было несколько примеровМне кажется, конкретно операции с матрицами — очень ходовая и часто используемая штука, код стандартных библиотек должен быть вылизан до блестящего состояния и соревноваться с ними сложно.
Даже Ермолаев, при всей продвинутости его оптимизации, пишет в комментариях, что предположительно уступает MKL 5-10%.
Возможно, в вашем случае действительно будут влиять накладные расходы на вызов, у вас матрицы мелкие. В MKL для них предусмотрен какой-то хитрый инлайн, но при вызове из Дельфи он конечно работать не будет. Хотя можно написать промежуточную dll на Си, которая реализует функцию обработки массива матриц, с заинлайненной ф-ей MKL.
Мне также попадался одиночка, который заявляет, что у него быстрее, но для матриц общего вида — незначительно, те же 10% (transform inverse это, как я понимаю, упрощённый алгоритм для матриц трансформации в 3D-графике)
про читабельность на Си- я смотрел всякие портянки из интринсиков- честно- не вижу я там читабельностиИнтринсики не особо читабельны, согласен.
Я обычно либо пытаюсь подтюнить код под автовекторизацию (это возможно, если понимать её логику и ограничения), либо использую векторные расширения Clang/GCC, они позволяют писать в «шейдерном» стиле. Ну знаете, в шейдерах/OpenCL/CUDA есть типы вроде float4, с которыми можно делать математику как с обычными float. Здесь тот же принцип.
__m128 sss = _mm_set1_ps(0.5);
for (x = xmin; x < xmax; x++) {
__m128i pix = _mm_cvtepu8_epi32(*(__m128i *) &lineIn[x]);
__m128 mmk = _mm_set1_ps(k[x - xmin]);
__m128 mul = _mm_mul_ps(_mm_cvtepi32_ps(pix), mmk);
sss = _mm_add_ps(sss, mul);
} float4 sss = (0.5);
for (x = xmin; x < xmax; x++) {
float4 pix = __builtin_convertvector(lineIn[x], float4);
sss += pix * k[x - xmin];
}Никак не могу заставить делфи класть передаваемый аргумент в RSP. Я не доконца понял, но судя по ассемблерному коду, CLang складывает копию матрицы в стек, а потом из стека забирает их снова- на этом должен быть штраф, но какой конкретно- не могу сейчас оценить. Дельфи упорно передает через регистр адрес первого элемента матрицы, и внутри выдергивает данные напрямую из памяти. Когда я Ваш пример заставил работать с RCX- он стал вполне себе быстрый:
«M3: Invert.compiler»: CalcTime =227263 mks; throutput 3543,5 MB/s
«M3: Invert_delphi_assembler_cleared»: CalcTime =196167 mks; throutput 4105,2 MB/s
«M3: Invert_gauss»: CalcTime =240986 mks; throutput 3341,7 MB/s
«M3: T_SSE.Invert_gauss»: CalcTime =182678 mks; throutput 4408,3 MB/s
«M3: T_SSE.Invert.direct»: CalcTime =135077 mks; throutput 5961,8 MB/s
«M3: T_SSE.Invert(N)»: CalcTime =145853 mks; throutput 5521,4 MB/s
«M3: Invert(packed matrix M3x3, compiler)»: CalcTime =195586 mks; throutput 3088,1 MB/s
«M3: T_SSE.Invert_CLANG»: CalcTime =161272 mks; throutput 3745,1 MB/s
Пока мои выводы такие:
a. (из разряда- удивительное рядом) компилятор делфи на простых математиках неплох.
б. если из ассемблера, сгенерированного делфи, выкинуть лишние операции (он там накидвает каких-то бесполезных пересылок)- то получается еще лучше.
в. ручная оптимизация с SSE- даже на простой математике дает заметный прирост, и получается лучше, чем у компилятора.
г. СLANG- дает вполне компактный и эффективный код, но все равно может пропустить очевидные вещи (как с повторным divsd на одних и тех же данных). между CLang v5.0 и CLang v11.0.1- разница видна невооруженным взглядом.
д. CLang v11.0.1 лучше ICC- то, чего нагенерил ICC- вообще никому показывать нельзя- там 5 divpd/sd вместо 1го!
е. выровненность данных дает небольшой прирост. M3: «M3: Invert.compiler» vs Invert(packed matrix M3x3, compiler)"
г. СLANG- дает вполне компактный и эффективный код, но все равно может пропустить очевидные вещи (как с повторным divsd на одних и тех же данных)div — это так, досадное недоразумение. Не в div-ах суть. Я даже не буду спрашивать, сколько div-ов на таком коде генерирует Дельфи :) Нормальный разработчик делает замену в коде множественного деления на умножение «на автопилоте».
А суть вот в чём: я переделал код на обработку массива матриц, и теперь векторизатор отработал лучше. Он считает по 2 матрицы за итерацию, за счёт этого все команды цикла векторные.
Причём можно сделать загрузку матриц в регистры эффективнее, если хранить их по-другому: не как массив структур, а как раздельные массивы для каждого элемента матрицы. Смотрите сами, насколько это допустимо в вашей ситуации.
Раздельные массивы хороши тем, что лучше масштабируются на любую систему команд, можно считать по 4 матрицы за итерацию с AVX.
И всё это в 20-30 строчках максимально простого кода, никаких ассемблерных портянок вручную.
мне такое очень не желательно, я часто сохраняю инвертированную матрицу поверх исходной.
Я согласен с Вами в том смысле, что можно сделать простой код, который будет хорошо компилироваться специальным компилятором (CLang 11.0.1, но не GCC10.2 например, и не msvc или icc, я до общения с Вами пребывал в уверенности, что лучшая оптимизация- в ICC- как никак, компилятор от производителя процессора! а оно вот оно че оказывается). Вполне себе оправданный подход в определенных условиях (например, когда можно ради упрощения жизни компилеру переломать базовые структуры данных- ведь на эту самую Mat3x3 завязана половина кода, ее тронь- там столько всего полезет!). Но совершенно спокойно можно прямо в родной старючей delphi xe4 (не слезая с кактуса) на старючем SSE4.2 без AVX забить всю ПСП и пережевывать данные быстрее, чем они через нее пролазят. КМК, туториалы для того и нужны, чтобы показывать разные способы решения одних и тех же задач, чтоб можно было выбирать под свои нужды. Лично для меня одной из причин залезть именно в ассемблер было то, что предыдущий опыт использования «ускоряющей» dll был полон мучительной отладки, когда какие-то данные вызвали ошибку в потрохах ДЛЛ, а дебагер не может до них докопаться. А когда залез- то оказалось, что это совсем не страшно. :-)
до общения с Вами пребывал в уверенности, что лучшая оптимизация- в ICC- как никак, компилятор от производителя процессора!ICC тоже хорош, но у него своя система параметров, и не все из них работают через godbolt. Попробуйте -fast, и будет таки fast, но принудительно включится FMA/AVX2. В общем, я толком не знаю, как с ним обращаться.
когда можно ради упрощения жизни компилеру переломать базовые структуры данныхДа всё уже, отбой, не надо ломать. На практике раздельные массивы «не взлетели». Наверное, виноват не последовательный доступ к памяти, лезем в память по 9-и разным указателям вместо 1-го. Может быть, если бы хранить элементы мини-массивами по 4 штуки, было бы лучше, но это совсем уже неудобно в работе.
От новых инструкций (AVX, FMA) тоже толку немного.
Но в результате я всё-таки обогнал ваш ассемблер примерно на 30%, а для компактной матрицы сильно, раза в 3.
Аккаунта на Гитхабе нет, поэтому архивом, там же и результаты.
забить всю ПСП и пережевывать данные быстрее, чем они через нее пролазятНе уверен, что если вы забиваете ПСП, то это повод для гордости. Может слишком мало арифметики на чтение/запись? Но да-а, теперь уже не хочется ничего менять, когда всё захардкожено ассемблером.
Лично для меня одной из причин залезть именно в ассемблер было то, что предыдущий опыт использования «ускоряющей» dll был полон мучительной отладки, когда какие-то данные вызвали ошибку в потрохах ДЛЛ, а дебагер не может до них докопаться.Если это ваша dll-ка, то отлаживать её можно из сишной IDE c дельфийским host application.
Это добавляет сложности, но и отладка ассемблера — тоже так себе удовольствие, особенно через пару лет после того, как вы этот ассемблер писали.
Но совершенно спокойно можно прямо в родной старючей delphi xe4 (не слезая с кактуса)Хорошо, не слезайте, больше не буду уговаривать :)
Здесь я взял за основу 3x3, может сами допишете?
gcc.godbolt.org/z/1KKG9a
Про подкапотное пространство не скажу- на работе лицензия XE4, там все грустно, llvm еще даже в проектах не было, и современный FPC дает существенно более быстрый код. Что щас в Берлине- не смотрел, на ноуте он стоит, но чисто символически- как запасной аэродром, тестить на нем производительность даже не пробовал (N4200 не для расчетов никак).
Классная статья, но жаль что практически не затронута тема выравнивания. Для векторного SSE на Паскале это весьма болезненная тема (особенно в Delphi, ибо в FPC хотя бы есть директивы выравнивания).
Хм, правда болезненная?
По-моему на современных процессорах выравнивание уже не особо влияет. Я получал разницу порядка 10% (для небольшого промежуточного буфера). Если уж хочется выжать эти 10%, то в Delphi FastMM умеет выравнивать на 16 со специальной опцией, при желании можно сделать выравнивание вручную.
При этом в коде можно всегда использовать команды без выравнивания, начиная с первых Core i на реально выровненных данных у movups такая же скорость, как у movaps.
Боль в том, что все SSE-инструкции, кроме movups и её подобной, требуют выравненных операндов, а это труднодостижимо. Например для глобальных переменных в Delphi вообще нет способа выравнивания, с локальными переменными и структурами тоже есть нюансы.
У меня не возникало никаких проблем с выравниванием. Я потестил на скорую руку выровненные и невыровненные данные, разница оказалась в какие-то проценты по скорости, и больше я к этому не возвращался. А haddpd или divpd выровненности не ттребуют.
Ну как же не требует:
"When the source operand is a memory operand, the operand must be aligned on a 16-byte boundary or a general-protection exception (#GP) will be generated." (https://www.felixcloutier.com/x86/haddpd)
Другое дело, что haddpd немного не та операция, которую удобно применять к операндам в памяти.
Но раз не возникало, тогда ok.
А арифметика с операндом в памяти вот прямо заметно лучше, чем movups в регистр и та же операция с регистром?
Я не проверял, но мне кажется, что разница будет пара процентов. Выборка из памяти никуда не денется в любом случае. И это имеет большее значение, чем +1 инструкция.
И кстати, как в 64-битном режиме - тоже ничего не выравнивает? Могу ошибаться, но там вроде есть требование от ОС по выравниванию стека.
По скорости может и не так уж сильно лучше, но минус свободный регистр, и если он non-volatile, то надо его сохранять/восстанавливать.
Да, стек в x64 выравнен - хоть тут хорошо :) Правда только FPC зачем-то в любую asm-функцию добавляет пролог/эпилог в виде add rsp,8, а Delphi нет, поэтому в Delphi на входе rsp всегда заканчивается на 8, а в FPC - на 0.
у меня числодробилка, которая пережевывает по 50 ГБ данных в секунду, это накладывает некоторые особенности на сам процесс обработки этих данных.
Во-первых, они лежат в памяти почти всегда "плотнячком", поэтому хорошо кэшируются, случайный доступ к памяти почти отсутствует, и особо выигрыша от операндов в памяти нет.
Во-вторых, регистров почти всегда в избытке (кроме работы с матрицей 4*4, но у меня половина статьи про то, как я из этого выкрутился :-)).
В-третьих- так как пачка обрабатываемых данных всегда большая, то push/pop регистра занимают пренебрежимо мало времени на фоне собственно вычислений.
ну и "нельзя объять необъятного"- и так объемный текст получился.
Ну и выше я много писал о том, что давно забросил использование SIMD через дельфийский ассемблер (кроме совсем мелких функций), использую для этого компиляторы Си. Там если что-то передаётся в функцию, то как правило крупными кусками - массивы, структуры. Их можно либо выровнять вручную, либо заставить сишный компилятор использовать movups.
Кстати, можно и в чисто дельфийском коде этот метод применить - собираем все глобальные переменные в структуру (запись) и вручную её выравниваем. Точнее, используем указатель на запись, который выравнен в блоке памяти [размер+16].
О, кстати, было бы любопытно узнать как у вас организован этот процесс. Какая IDE, какой компилятор, как устроена итоговая сборка?
Ну не скажу, что хорошо организован, автоматической сборки нет. И не такие большие объёмы кода переписаны на Си.
Для прототипирования очень удобен онлайн-компилятор https://gcc.godbolt.org/
Тем более, что я не люблю интринсики и упираю на (полу)автоматическую векторизацию - там сразу видно качество этой векторизации.
Компиляторы - gcc или Clang, Clang обычно предпочтительнее, т.к. лучше поддерживает векторные расширения. Но иногда gcc выдаёт лучший результат.
А в оффлайне делается dll-ка с помощью IDE CodeBlocks + опять же gcc или Clang. Последние версии компиляторов ставятся на Винду через пакетный менеджер msys2. gcc можно также скачать из проекта mingw-w64, но не последней версии.
Как вариант, можно линковать obj, причём в 64 битах вроде бы линкуется вообще безо всяких конверсий. Но давно не использовал этот метод, отладка совсем никакая (dll можно отлаживать из CodeBlocks с дельфийским host application).
Почему не MSVC? Ну, gcc/Clang мне кажутся позадорнее в плане оптимизации (но возможно, я плохо знаю опции MSVC), и в MSVC нет векторных расширений.
Есть возможность поставить в IDE MSVC компилятор Clang, но я пока не пробовал и не знаю, насколько этот Clang полноценный, поддерживает ли расширения.
Я понимаю, что всё это кажется сложным и муторным, но поиграешься с онлайн-компилятором и обнаружишь, с какой легкостью он выдаёт огромные SIMD-простыни, которые ты раньше писал вручную... причём для любой разрядности и системы команд... и возвращаться к Дельфи-ассемблеру уже совсем тоскливо.
Стероидный велосипед: векторная алгебра, на ассемблере, в Delphi