[devel] ускорение lzma декомпрессии (XZ Utils)

[Ilya Kurdyukov]

Для понимания что делает патч:

В LZMA используется адаптивное арифметическое кодирование каждого бита.

А именно: ru.wikipedia.org/wiki/Интервальное_кодирование

После того как бит раскодирован из потока данных - обновляется несколько 
переменных, причём в зависимости от того какой бит прочитали (0 или 1) 
делается это по разному. То есть в конце чтения бита стоит конструкция 
вида if-else, а это условные прыжки в бинарном коде. Ветвление в 
программе тормозит её выполнение, потому что процессору нужно очистить 
конвейер с заранее декодированными инструкциями и заполнить его 
инструкциями по новому адресу, короче говоря прыжок это дорогая инструкция.

Патч убирает это ветвление за счёт того, что оба пути исполнения if-else 
вычисляются одновременно, но код получается без ветвления.

Это усложняет код, так что процессор исполняет чуть больше инструкций. 
Но время уменьшается. Всё зависит от цены прыжков для конкретного 
процессора.

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

Поэтому на более простых процессорах (мобильных или просто старых) 
ускорение от патча будет ниже. Как Intel Atom на котором проверил Андрей.


On 14.12.2021 01:59, Andrey Savchenko wrote:
>
>> Я проверю на x86 (Intel Atom N270). Займёт некоторое время, т.к.
>> машина старенькая и слабенькая. Проверю распаковку имеющихся под
>> рукой исходников ядра и бинарного пакета firefox (там zstd,
>> перепакую в xz -9e --x86).
> 		old,s		new,s		delta,%
> kernel src	33.522±0.077	32.515±0.087	3.01±0.34
> firefox pkg	14.645±0.030	14.256±0.023	2.66±0.25
>
> Погрешности приведены для одного стандартного отклонения.
> Тесты делались на tmpfs для уменьшения эффекта i/o.
>
> Результат небольшой, но значимый и статистически достоверный.
>
> Best regards,
> Andrew Savchenko