Оптимизация. Меньше насколько лучше?

Предыдущий вариант оптимизации арифметического сжатия с 8-битным алфавитом использовал таблицу накопленных частот с элементами UInt32. Идея ускорения состояла в том, что бы хранить элементы в формате UInt16, что в два раза уменьшит размер памяти и количество элементов, обрабатываемых одной командой процессора.

Давайте посмотрим, что это даст. Предыдущий вариант показывал производительность 10.0 и 6.7 МиБ/с на AMD FX-4350.
Новый вариант ускорился, но все же не так сильно, как я ожидал: 10.7 и 7.4 МиБ/с соответственно.

Что будет, если вместо классических команд SIMD (в моем случае на технологии SSE) использовать в этом режиме команды SISD?
А вот что: 10.6 и 7.2 МиБ/с, то есть в общем-то особого смысла использования команд SIMD в самых простых случаях нет.

На уровне ассемблера вкратце это выглядит так: команды
  movdqu XMM0, [RCX+Limits+R11*2];
  paddw XMM0, XMM3;
  movdqu XMM0, [RCX+Limits+R11*2];
заменятся на
  add [RCX+Limits+R11*2], R8;
  add [RCX+Limits+R11*2+8], R8;
Здесь в регистрах XMM3 и R8 хранятся упакованные массивы из единиц длиной в слово: $1000100010001 для R8 и то же самое,  только в два раза длиннее, для XMM3.

Проблемы переноса старших разрядов в младшие у соседних элементов не возникает, так как модель адаптируется, как только последний элемент с максимальным значением достигнет значения $FFFF.

При адаптации мы просто делим все элементы массива на два, после чего дополнительным проходом гарантируем монотонное увеличение всех элементов от первого до последнего.
Деление просто реализуется как на SIMD, так и на инструкциях общего пользования (GPI). Команда на ассемблере
  psrlw XMM0, 1;
заменятся на две пары из двух команд вида
  shr R9, 1;
  and R9, R8;
Вторая команда AND нужна для того, что бы очистить случайно залетевшие младшие биты элементов с большими индексами в старшие биты с элементами с меньшими индексами. Значение для R8 такое: $7FFF7FFF7FFF7FFF.
Спросите меня, зачем я в командах общего пользования использую регистры с константами вместо указания констант в самих командах? Ответ очень прост: в X64 нет возможности указывать константы в командах длиной 64 бита.

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

Ладно, хорошо, но мой FX-4350 уже достаточно старенький процессор. Возможно, SSE  на нем реализовано не так уж оптимально?
Сравним с Ryzen 7 5800X: SIMD - 19.56 и 12.61 МиБ/с, GPI - 19.63 и 12.46 МиБ/с. Как видим, разницы никакой, следовательно, использовать SIMD оправдано только в случае несколько более сложных вычислений, которые никак не укладываются в инструкции общего назначения.

Ну и кстати, вариант с уменьшенным количеством делений и короткой таблицей чуть-чуть обошел вариант с пирамидой (17.8 и 13.3 МиБ/с). Есть подозрение, что если реализовать вариант с пирамидой с уменьшенным количеством делений, то удастся выйти на современных процессорах за 20 МиБ/с при сжатии данных.
А вот при распаковке, видимо нет, даже при переходе на 16-битный алфавит. 

Оптимизация. Первый вариант

Как говорится, скоро сказка сказывается, да не скоро дело делается.

Наконец-то переделал под ассемблер первый вариант арифметического сжатия: пока что классический вариант, без каких-либо принципиальных изменений, только для хранения модели используется усеченная пирамида в моем варианте реализации.

В основном я делал регистровую оптимизацию. И вот что меня удивляет в текущем компиляторе Delphi: они не стали сильно заморачиваться, просто содрали кальку с соглашении о вызовах Win64. Параметры передаются в 4 регистрах, если их больше, то они передаются на стеке, большую часть регистров при необходимости использовать в функции, нужно предварительно сохранять.
Такой подход вполне оправдан при вызове приложением системных функций. Но зачем его использовать при вызовах, не выходящих за пределы приложений?

Я лично исхожу из того предположения, что 80% работы выполняют листовые функции. А значит, именно им необходимо предоставить все ресурсы (в первую очередь регистры) для обеспечения максимальной производительности.
Также листовые функции не имеют никакой информации о том, откуда они будут вызываться и какие регистры в месте вызова используются.
В то же время вызывающая функция прекрасно знает, какие регистры она использует, а компилятор может передать ей информацию о том, какие регистры использует вызываемая функция. Поэтому мне кажется логичным, что листовая функция должна свободно пользоваться любым регистром, а сохранять используемые должна вызывающая функция.
По крайне мере, я именно так всегда делаю.

Еще с удивлением обнаружил, что в составе Delphi нет профайлера вообще. Да и был ли он? Я вот честно не помню, последние воспоминания о нем связаны с Borland Pascal. Но возможно он был в ранних моделях Delphi и я просто про него забыл (а может и не знал?), потому что никогда не пользовался.
Тем не менее, в столь простой ситуации, как со структурой алгоритма арифметического кодирования, можно понять, какие там будут узкие места и без профайлера. Во-первых, сама процедура кодирования (или декодирования) символа, которая вызывается столько раз, сколько символов в кодируемом тексте. Ну и связанная с нею один ко одному процедура обновления модели.
Но еще большее влияние может оказать процедура записи (чтения) бита сжимаемой (декодируемой) информации, так как она вызывается несколько раз на символ.

В Delphi, в отличие от Java, нет никаких инструментов для работы с массивом бит, поэтому приходится программировать их вручную и использованием побитовых операций и сдвигов.
А вот на ассемблере всё гораздо интереснее. Все же есть определенные преимущества у архитектуры CISC, и в X86/X64 уже давно есть команды для манипуляции с битами. Они на мой взгляд немного странные, но все равно существенно облегчают жизнь программиста.
Первоначально я сделал операции именно над битами в массиве в памяти. Но, с учетом того, что эта операция встречается очень часто, решил ее слегка оптимизировать, поэтому в конечном варианте кэширую часть массива в регистре и битовые операции произвожу над ним, по мере необходимости сохраняя/обновляя значения из памяти.
Видимо, на языке высокого уровня такая оптимизация трудно достижима.

Что же у меня получилось? На моем FX-4350 мне удалось достичь лишь жалких 10 МиБ/с при сжатии и 7 при распаковке. Это, конечно, серьезное улучшение с исходным вариантом, но мечталось о большем 😀.
Посмотрим, что получилось на более современном процессоре Ryzen 7 5800X: 17.8 и 13.3 МиБ/с соответственно! Недурно вроде вышло: быстрее всех вариантов, которые протестировал Иван Колесников на Java, кроме распаковки на 16-битном варианте с пирамидой.
А ведь у меня еще остались в запасе "тайные варианты" алгоритмической оптимизации, которые раскопал Иван: уменьшение количества делений и разбивка одного цикла со сложными условиями в теле на несколько независимых. Правда, я не уверен, что последний вариант даст сильный приход в ассемблерной реализацией.
Получается, что современные оптимизаторы хороши, но человек при желании сможет лучше. Конечно, трудозатраты при этом не в пользу человеческого варианта 😀.

Итак, 17 и 13 МиБ/с – много это или мало? Иван считает, что числа эти – детские, то есть, маловато будет. Смотря для чего. Я вижу одно применение арифметического сжатия, где такой производительности явно недостаточно: кодирование видео очень высокой четкости.
Но и в этой области скорость арифметического кодирование важная, но не самая главная проблема. Насколько я смог понять, решают ее в современных стандартах путем использования короткого алфавита и снижения точности вычислений. Это приводит к увеличение производительности и некоторому ухудшению коэффициента сжатия. Тема интересная, но пока не очень понятная.

Теперь фрагменты кода, которые я использую для кодирования/декодирования символов. Сначала кодирование:

procedure TArithmeticCoder.Encode_symbol(Symbol : byte);
var
  Range : cardinal;
  Prev : cardinal;
label  StartLoop, ExitLoop;
begin
  Range := HighLimit - LowLimit + 1;
  HighLimit := LowLimit + (UInt64(Range)*GetLimit(Symbol, Prev)) div TotalLimit - 1;
  LowLimit := LowLimit + (UInt64(Range)*Prev) div TotalLimit;

StartLoop:
    if HighLimit < Half then
      bit_plus_follow(0, Bits_to_follow)
    else
      if LowLimit >= Half then
      begin
        Bit_plus_follow(1, Bits_to_follow);
        LowLimit := LowLimit - Half;
        HighLimit := HighLimit - Half;
      end
      else
        if (LowLimit >= First_qtr) and (HighLimit < Third_qtr) then
        begin
          Bits_to_follow := Bits_to_follow + 1;
          LowLimit := LowLimit - First_qtr;
          HighLimit := HighLimit - First_qtr;
        end
        else
          goto ExitLoop;
    LowLimit := LowLimit + LowLimit;
    HighLimit := HighLimit + HighLimit + 1;
    goto StartLoop;
ExitLoop:
end;

Декодирование:

var
  Range : cardinal;
  Cum, Prev, Current : cardinal;
label  StartLoop, ExitLoop;
begin
  Range := HighLimit - LowLimit + 1;
  Cum := ((UInt64(Value)-LowLimit+1)*Limits[0]-1) div Range;
  Result := GetLimitIndex(Cum, Prev, Current);
  HighLimit := LowLimit + (UInt64(Range)*Current) div TotalLimit-1;
  LowLimit := LowLimit + (UInt64(Range)*Prev) div TotalLimit;
StartLoop:
    if HighLimit>=Half then
      if LowLimit >= Half then
      begin
        Value := Value - Half;
        LowLimit := LowLimit - Half;
        HighLimit := HighLimit - Half;
      end
      else
        if (LowLimit >= First_qtr) and (HighLimit < Third_qtr) then
        begin
          Value := Value - First_qtr;
          LowLimit := LowLimit - First_qtr;
          HighLimit := HighLimit - First_qtr;
        end
        else
          goto ExitLoop;
    LowLimit := LowLimit + LowLimit;
    HighLimit := HighLimit + HighLimit + 1;
    Input_bit(Value);
    goto StartLoop;
ExitLoop:
end;

Что же дальше? Дальше я попробую реализовать на ассемблере версию с простой таблицей частот с накоплением с расчетом с использованием SIMD и уменьшенным количество делений. Судя по тому, что получилось у Ивана, на 8-битном алфавите такой вариант должен быть самым быстрым за счет некоторого снижения точности.
Такое снижение точности приведет к некоторому снижению коэффициента сжатия. Насколько сильному? Очень незначительному. Реализация на чистом Delphi дает вот такую картину (см. последнюю строчку):

Как видим, снижение есть, но оно практически незаметно. При этом очевидно, что оно будет расти по мере увеличения размера кодируемых данных (если не сбрасывать регулярно модель путем деления на два), за счет прогрессирующего снижения точности. Значительных величин такое снижение может достигнуть при размере в районе ГиБ и больше, но вряд ли кто-то на практике будет использовать такие объемы для чисто арифметического сжатия.

Лабиринт - оптимизация на ассемблере

Предыдущая реализация поиска волновым алгоритмом в лабиринте была неплоха, но работала не так уж и быстро. Иван Колесников предположил, что дело в медленной работе памяти и попробовал реорганизовать хранения данных так, что бы рядом расположенные данные в двухмерном пространстве оказались относительно близко друг к другу и в одномерном пространстве. Для этого он использовал Z-порядок (по русски почему-то в вики статья называется кривая Мортона) для перехода от двухмерных координат к одномерным.

Подход показал очень хорошие результаты по производительности, обеспечивая почти двукратное превосходство для сложных случаев на интеловском процессоре.
Так же Иван протестировал программку на M1, который показал очень неплохую производительность, превышающую производительность топового мобильного процессора Intel 9-го поколения.

Итак, скорость работы волнового алгоритма сильно зависит от памяти, но вроде же для частичного решения этой проблемы и предназначен кэш? Которого в современных процессорах много, да еще и его, этого кэша, три уровня обычно.
Тут проблема в том, кэш для этой задачи очень "горячий". Фронт волны проходит в сложных случаях проходит по совершенно разным участкам лабиринта (читай, памяти, так как лабиринт в ней и хранится), что приводит к тому, что расчет одного участка волны приводит к неминуемому удалению из кэша другого участка волны, что сильно увеличивает промахи мимо кэша и драматически снижает производительность работы с памятью.
Реорганизация памяти в Z-порядке существенно снижает эту проблему, но можно попытаться решить проблему и по-другому, просто оптимизировав программу.

Первое, с чего я начала – с банальной регистровой оптимизации. Так как в 64-битном режиме в архитектуре x64 доступно 16 регистров, то результат оказался ощутимым – примерно 30% ускорения за счет того, что я избавился от сохранения служебной информации в памяти.
К сожалению, компилятор Delphi, видимо, не сильно умеет в такую оптимизацию. Зато он позволяет достаточно легко и удобно писать часть кода на ассемблере. Не так удобно, как в 32-битной версии, когда можно было вставлять ассемблерные кусочки в любую часть кода. В 64-битной можно лишь писать целиком ассемблерные функции. Но отладка осталось все также очень удобной.

30% хорошо, но можно ли лучше? Что еще требует обращения к памяти, кроме переменных? Конечно же, вызов процедур и функции, которые даже при регистровой передачи параметров сохраняют/извлекают в/из стек(а) адрес возврата.
Помню, я даже бывало рассказывал на лекциях о забавном случае, когда ответственного руководителя направления разработки процессоров IBM отправили в корпоративную "ссылку" за то, что в очередном процессоре (в те времена это были монстры для мейнфреймов) не оказалось команд для работы со стеком.
Видимо, очень давно производительность памяти была сравнима с производительностью процессоров, да и в общем-то она была не велика, поэтому выделение отдельных команд для управления стеком было оправданным.
Но что мы видим сейчас? Если не ошибаюсь, в RISC V адрес возврата сохраняется не в памяти, а в регистре! В случае, если глубина вложенности вызовов функций не велика, а память существенно медленнее, чем процессор (в современном мире это почти всегда так), то это может существенно поднять производительность программы.
При необходимости же всегда можно организовать работу стека программным образом, а отсутствие дополнительных команд отлично вписывается в концепцию RISC.

К сожалению, в архитектуре x64 возможности сохранять адрес возврата в регистрах нет, поэтому просто приходится "раскатывать" тело вызываемой функции в код основной процедуры. У меня это была относительно маленькая функция проверки возможности хода и, если он возможен, сохранения фронта волны и порядка обхода на следующей итерации.
После избавления от лишних вызовов удалось поднять производительность почти в два раза относительно исходной.
Еще оптимизировал дисковые операции за счет буферизированного ввода/вывода. Правда, тут по хорошему надо бы еще оптимизировать и преобразование исходных данных в удобный для решения массив, но не это моя основная цель.

Итак, результаты:

AMD FX-4350:
загрузка примерно 15-16 секунд, но так как на компьютере используется HDD, то сильно зависит от фрагметированности файла; в худшем случае было 26 секунд. В среднем загрузка ускорилась в два раза;
kvy в прямом направлении и обратном направлении: 19 сек;
A – 10 сек;
B – 26 сек.

Ryzen 7 5800X:
загрузка 6 сек;
kvy в прямом 9.4 сек, в обратом – 10.3 сек;
A – 5.9 сек;
B – 6.8 сек.

В общем, можно сказать, что оптимизация удалась. На данных, хранящихся в обычных массивах, FX-4350 обогнал более свежий, хоть и мобильный Intel, проиграв на Z-порядке. Впрочем, на процессоре с аналогичной производительность, думаю этого проигрыша бы не было.
Ну а на Ryzen 7 производительность оказалась даже выше, чем у такого монстра, как M1. Жаль, нельзя их сравнить в равных условиях, так как вполне вероятно, что более жесткая оптимизация под M1 позволила бы ему обогнать Ryzen. Все же 31 регистр общего  назначение должен дать жару!

Только набирая текст, обратил внимание на несколько феноменальный результат Ryzen на файле B. Для всех прочих тестов вариант B был самым тяжелым для процессора и выполнялся медленнее всего. Удивительно, что для Ryzen он оказался проще, чем обычно более легкий вариант kvy.

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

Лабиринт

Ностальгирую тут немного...

Вспоминаю еще те времена, когда учился на старших курсах в СМИ, ныне СибГИУ. Студенты обычных специальностей, типа металлургов или металловедов вешались, обучаясь информатики. Уж не помню как тогда кафедра эта называлась, на которой мучили студентов, потом она долго была кафедрой прикладной информатики.
И обучали там студентов-металлургов, литейщиков и прочих в те далекие времена... программированию. В СССР, а потом и России компьютеризация только начиналось, компьютеров-то толком не было, не говоря уже о прикладных программах. Поэтому программировали все подряд.

Одна из задачек для студентов там была про поиск пути в лабиринте. Металловедам и строителям это было просто невыносимо скучно и непонятно, а нам, обучающимся именно программированию, было страсть как интересно.

Интернетов тогда в Сибири не было, да наверно и во всей России тоже, хорошей специализированной литературы  также не хватало, поэтому алгоритмы мы придумывали сами. Для этой задачки самый оригинальный вариант решения придумал Алексей Щелоков, с очень забавной биологической аналогией.
В реальности же это был старый добрый, сто лет как известный волновой алгоритм.

Я потом с ним много изгалялся. В контексте биологического описания реализовывал его с помощью ООП, хотя по сути волнового алгоритма никакой ООП там не требуется, гораздо эффективнее просто поиск в ширину на массиве.
Кстати, тогда же я и выяснил, что выделение динамической памяти под NT происходит гораздо, наверное, на два порядка, медленнее, чем на Windows 9x.
Поэтому когда выяснилось, что операции 4 КиБ блоками при копировании файла сильно загружает процессорное ядро, я предложил, что эта та самая "неэффективность" системных вызовов на платформе NT.
Но думаю, я был не прав. Все же с времен NT много воды утекло, думаю, сейчас большинство системных вызовов происходит гораздо быстрее. Так что наиболее вероятная причина, как заметил Иван Колесников, в издержках межпоточной синхронизации. Надо будет потестить, но пока руки не доходят.

В общем, ностальгируя накидал быстренько программку поиска пути в лабиринте на окрестностях фон Неймана. Сначала хотел решить задачу в квадрате размером 100 000, но потом понял, что для решения памяти не хватит, и остановился на 40 000.

Правда, надо было еще лабиринт каким-то образом сделать. Сделал случайным образом. Лабиринт получился не очень красивым, но зато достаточно сложным для решения волновым алгоритмом.
Мой рабочий FX-4350 на архитектуре PileDriver и жестких дисках загрузил лабиринт примерно за 40 секунд, а нашел кратчайший путь за 52.4 секунды.
А вот Ryzen 7 5800X на архитектуре Zen 3 и с SSD на PCI Gen 3 x4 сделал те же операции за 22.5 и 21.5 секунды.

По сравнению с началом 90-х годов прошлого века эта, конечно, потрясающая производительность. Тогда и 100х100 лабиринт не сильно быстро решался.
Удивило лишь то, что замена HDD на SSD не сильно ускорила процесс загрузки. Честно говоря, я ожидал большего.

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

Ryzen 7 5800X

Походу, это последний американский процессор 😟, что мне удалось оттестировать. В системе 32 ГиБ ОЗУ DDR4 3200 МГц.

Сейчас пойдут графики, а потом кратенький анализ.

 

Можно сказать, что в области плавающей точки увеличение производительности весьма значительно, как за счет экстенсивных мер (увеличение количества ядер, кэша и исполнительных устройств), так и интенсивных (увеличение производительности  исполнительных устройств и шин передачи данных).

Средняя производительность за 7 лет увеличилась в четыре с лишним раза (от архитектуры PileDriver в 2013 году до Zen3 в 2020).
Однопоточная производительность выросла более чем в два раза на скалярных операциях и в 3.5 раза на векторных. Очень неплохо!

 

Немного скромнее обстоит дело с целочисленными скалярными операциями. Среднее ускорение всего лишь в 3.4 раза.

Однопоточное – "всего лишь" в 1.72 раза. При этом ускорение операции деления более значительно – в 1.81 раза, а вот более простые операции типа сложения и побитовых, ускоряются гораздо хуже – в 1.66 раза. Видимо, эти операции и ранее были оптимизированы неплохо.

Видно, что и многопоточность реализована в новом процессоре более эффективно. Правда, есть странный провал на решении систем из 12 уравнений на типе double, где Ryzen 7 поколения Zen3 сливает Ryzen 5 поколения Zen2. Честно говоря, не знаю даже, как его можно объяснить