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

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

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

В основном я делал регистровую оптимизацию. И вот что меня удивляет в текущем компиляторе 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 дает вот такую картину (см. последнюю строчку):

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