Открыть список
Как стать автором
Обновить

Комментарии 33

В очередной раз показано как в Delphi, предназначенном для быстрой разработки GUI-приложений с доступом к БД, можно делать абсолютно разные вещи, в том числе быстрые математические расчёты.


Кстати, ассемблерные команды SSE с расширениями 4.2, завезли в одну из недавних версий Delphi. До этого приходилось писать ассемблерные вставки в опкодах. Команд AVX в Delphi до сих пор нет. https://m.habr.com/en/post/441392/

SSE4.2 в ней давненько- все выше описанное компилируется даже в XE4
Да, вы правы, не так и недавно. Кстати, в Delphi 10.5 (2-я половина 2021) запланированы Math Performance Improvements. Не знаю, что это, но надеюсь то что я думаю.
Замечательно! Среагировал на статью, так как сам на днях (точнее лунной ночью) обращал матрицу 4х4. Результат использовался для некоторого урматфиза.
Юмор
Оборотень: «Не подскажете, какая сегодня фаза луны?»
Я: «Полнолуние».
Оборотень: «Спасибо».
Я: «Не за что, обращайтесь».
Зачем в первом примере xor'ы для r13-15, они же гарантировано перепишутся полностью?
Кстати, я пробовал еще EasyCode c UASM64 в паре с Delphi, тоже весьма удобно, особенно для инструкций, которые Delphi asm не поддерживает. В Delphi линкуется obj файлик из UASM64 без проблем.

Например в EasyCode пишем -
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.

если поддерживать сразу две версии- 32 и 64, то проще принудительно обнулять все используемое в полном объеме, но Вы правы, в данном случае это избыточная операция.
Использовать внешние редакторы ассемблера- на мой взгляд дело вкуса. но для tutorial'а- это было бы через чур. Да и для себя я в этом не вижу смысла- IDE, редактор и дебагер меня вполне устраивают.

Не думали для работы с матрицами 3х3 и 4х4 использовать видеокарту? Вроде как они адаптированы для работы с подобными матрицами...

В матрице 4x4 всего 16 элементов, столько же, сколько у автора машина умеет за одну инструкцию. А вот для видеокарты мне кажется размер матрицы маловат (и эффективность будет низкая)

за инструкцию машина может поменьше- только 2 элемента.
на карте хорошо гонять очень большие матрицы, когда алгоритм можно распараллелить хотя бы на сотню-другую потоков, и особенно- если еще данные из карты не надо забирать на каждом шаге, а когда загрузили, сделали чисто на карте тыщу шагов, и забрали результат.

Ах да, у вас даблы… жирненько. А чем обусловлено использование double? Нет ли возможности хотя бы на float/single заменить?

на fp32 расчет деформаций идет с точностью порядка 10-6- а это по уровню- соответствует термическим деформациям от нагрева на 2-5 градусов. если хотим рассчитывать термодеформации- то приходится сидеть на fp64.
пробовали. но матрица у меня fp64, видеокарта такое не любит, это раз, а во вторых- я в любом случае на десяти-двенадцати ядрах полностью утилизирую ПСП и еще остается- поэтому карта мне не дает ускорения, она тоже упирается в ПСП. чтобы иметь прирост с карты- мне нужно закинуть в нее пару гигов данных, долго-долго их на ней крутить, и забрать с нее потом конечный результат. а если я постоянно гоняю данные туда-сюда- то профита нет, наоборот- медленнее получается.

Согласен… Лет 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 недели, правда, до этого опыта в ассемблере было около нуля, поэтому кодил параллельно с чтением мануалов и описания архитектуры.
про читабельность на Си- я смотрел всякие портянки из интринсиков- честно- не вижу я там читабельности ни в одном месте.

Поскольку это ваша задача, то давайте вы напишете тестовую программу на Дельфи, а я к ней прикручу сишный вызов. Вам виднее, какие матрицы должны быть, какие примеры данных. Это и как приложение к статье будет полезно.

заметано. за выходные выложу сюда линк на гитхаб для игрища.
ой. я его по ошибке приватным сделал, теперь публичный
github.com/RCherepanov/SSE_bench_habr
периодически выходят скромные статьи с разбором профайлингов и сказками про то, как какие-то одинокие самоучки делают умножение матриц на 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];
        }

Кстати, подобную штуку пытаются сделать разработчики FPC, но у них она практически не работает, только на элементарных примерах вроде a=b+c.
Я погонял на выходных код, который Вы прислали (ассемблер вставил в дельфи).
Никак не могу заставить делфи класть передаваемый аргумент в 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 строчках максимально простого кода, никаких ассемблерных портянок вручную.
#pragma clang loop vectorize(assume_safety)
мне такое очень не желательно, я часто сохраняю инвертированную матрицу поверх исходной.
Я согласен с Вами в том смысле, что можно сделать простой код, который будет хорошо компилироваться специальным компилятором (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 (не слезая с кактуса)
Хорошо, не слезайте, больше не буду уговаривать :)
коллега! не уходите так рано! помните- у меня главная засада была не в 3х3, а в 4х4!
У вас для Гаусса 4x4 нет готового кода на Дельфи, который можно взять за образец, либо ассемблер, либо словесное описание.
Здесь я взял за основу 3x3, может сами допишете?
gcc.godbolt.org/z/1KKG9a
Скажите пожалуйста сколько времени потратили на переписывание итого?
Покрывали ли как либо тестами? Как я понимаю по хорошему надо тестами и проверять что корректно восстанавливаются регистры при выходе и не портят не используемые данные?
Идентичны ли результаты полученным на обычном фпу?

LittleAlien
Во-вторых, если всё-таки хотите писать самостоятельно, рекомендую обратить внимание на компиляторы Си. Они могут генерировать эффективный ассемблер (в т.ч. с векторизацией) даже из самого примитивного кода безо всяких зачатков оптимизации.

Разве щас не под капотом дельфи компилятор llvm?
чистого времени на все SSE было потрачено около двух недель- это порядка 70-ти различных функций. Но большая часть из них очень похожа (типа, a.i += b.ij*cj and a.i += b.ij*c.j*k)- они копипастились с минимальными правками, и основная возня была именно с матрицей 4*4. Корректность расчетов покрыта unit-тестами, идентичность результатов с fpu- 50/50, где-то побитовая точность, где-то- в пределах погрешности округления, ибо перемена порядка действий влияет на последние знаки результата.
Про подкапотное пространство не скажу- на работе лицензия XE4, там все грустно, llvm еще даже в проектах не было, и современный FPC дает существенно более быстрый код. Что щас в Берлине- не смотрел, на ноуте он стоит, но чисто символически- как запасной аэродром, тестить на нем производительность даже не пробовал (N4200 не для расчетов никак).
Да сейчас уже не Берлин давно… Уже несколько лет не Берлин (10.1). Сейчас Сидней (10.4).
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.