From: Ilya Kurdyukov <ilyakurdyukov@basealt.ru>
To: devel@lists.altlinux.org
Subject: Re: [devel] ускорение lzma декомпрессии (XZ Utils)
Date: Tue, 14 Dec 2021 10:16:31 +0700
Message-ID: <f5f60432-145c-ae13-82b9-10e2717da14c@basealt.ru> (raw)
In-Reply-To: <20211213215900.4f1a71bb7107d47bacb69c50@altlinux.org>
Для понимания что делает патч:
В 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
next prev parent reply other threads:[~2021-12-14 3:16 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-12-13 1:52 ` [devel] [#291873] EPERM (try 2) rpmrebuild-arepo.git=3.1.13-alt1 Dmitry V. Levin
2021-12-13 1:56 ` Vitaly Lipatov
2021-12-13 9:02 ` [devel] ускорение lzma декомпрессии (XZ Utils) Ilya Kurdyukov
2021-12-13 11:59 ` Ilya Kurdyukov
2021-12-13 14:52 ` Ilya Kurdyukov
2021-12-13 15:08 ` Vitaly Chikunov
2021-12-13 15:42 ` Ilya Kurdyukov
2021-12-13 16:49 ` Andrey Savchenko
2021-12-13 18:59 ` Andrey Savchenko
2021-12-14 3:16 ` Ilya Kurdyukov [this message]
2021-12-13 16:58 ` Vitaly Chikunov
2021-12-14 2:53 ` Ilya Kurdyukov
2021-12-14 6:11 ` Ilya Kurdyukov
2021-12-14 7:25 ` Ilya Kurdyukov
2021-12-14 15:22 ` Andrey Savchenko
2021-12-14 17:12 ` Alexey V. Vissarionov
2021-12-14 17:34 ` Andrey Savchenko
2021-12-15 1:07 ` Alexey V. Vissarionov
2021-12-15 7:29 ` Ilya Kurdyukov
2021-12-15 15:55 ` Andrey Savchenko
2021-12-15 15:57 ` Andrey Savchenko
2021-12-16 4:22 ` Ilya Kurdyukov
2021-12-14 0:22 ` [devel] [#291873] EPERM (try 2) rpmrebuild-arepo.git=3.1.13-alt1 Dmitry V. Levin
2021-12-14 5:04 ` Alexey V. Vissarionov
2021-12-14 8:57 ` Dmitry V. Levin
2021-12-14 17:31 ` Vitaly Lipatov
2021-12-14 20:50 ` Dmitry V. Levin
2021-12-14 22:44 ` Vitaly Lipatov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f5f60432-145c-ae13-82b9-10e2717da14c@basealt.ru \
--to=ilyakurdyukov@basealt.ru \
--cc=devel@lists.altlinux.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
ALT Linux Team development discussions
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
public-inbox-index devel
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.devel
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git