# Витрина TAKT: распаковка bzip2 (корпус Silesia)

Одна программа в двух сборках: `bz2dec` распаковывает файлы `.bz2` в стандартный вывод, как `bzip2 -dc`.
`bz2dec-original` использует крейт [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 (декодер bzip2
на чистом Rust) в том виде, в каком он опубликован на crates.io; `bz2dec-takt` — тот же крейт после
оптимизации TAKT. Драйвер — один и тот же исходный файл, рецепт сборки тот же, вывод обеих программ
совпадает до байта. Здесь — обе готовые программы, исходник оригинальной сборки, скрипт, который
скачивает корпус, и скрипты, повторяющие замер и проверки.

## Что делает бенчмарк

Двенадцать файлов [корпуса Silesia](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(тексты, исполняемые файлы, базы данных, изображения, XML; 211 938 580 байт), каждый из которых сжат
вызовом Python `bz2.compress(data, 9)` (libbz2 1.0.8, один поток на файл, всего 54 506 769 байт),
распаковываются в одном процессе:

```sh
bz2dec -c dickens.bz2 mozilla.bz2 mr.bz2 nci.bz2 ooffice.bz2 osdb.bz2 reymont.bz2 \
          samba.bz2 sao.bz2 webster.bz2 xml.bz2 x-ray.bz2 > /dev/null
```

Для сравнения ту же работу выполняет системный `bzip2 -dc` (эталонная реализация на C).

## Замер (стенд TAKT)

AMD Threadripper PRO 5975WX (Zen 3), Linux, одно выделенное ядро (его SMT-сосед простаивает, его CCX
зарезервирован под замер). `perf stat` считает такты и инструкции пользовательского режима процесса
декодирования и его реальное время; 9 чередующихся раундов (порядок программ сдвигается от раунда к
раунду), медиана. Замерены ровно эти файлы. Все три программы — динамически скомпонованные
исполняемые файлы под glibc; обе сборки `bz2dec` собраны по одному рецепту: Rust 1.96.0, LTO,
codegen-units 1, `target-cpu=x86-64-v3`, panic abort, символы удалены.

Весь набор, один процесс на программу:

| Программа | Декодер | Такты, млн | Инструкции, млн | Время, мс | МБ/с | Ускорение |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 с crates.io | 17 867,0 | 22 191,1 | 4 129 | 51,3 | 1,00× |
| `bzip2 -dc` | C bzip2 / libbz2 1.0.8 (пакет Ubuntu 24.04) | 21 148,9 | 25 378,5 | 4 884 | 43,4 | 0,84× |
| `bz2dec-takt` | тот же крейт после оптимизации TAKT | 5 104,7 | 10 028,5 | 1 204 | 176,0 | 3,50× |

`bz2dec-takt` против `bzip2 -dc` на C: 4,14× по тактам, 4,06× по времени.
Против `bz2dec-original` по времени: 3,43×. Ускорение — отношение медиан тактов; МБ/с — распакованные
мегабайты (10⁶ байт) в секунду реального времени.

Каждый файл в отдельном процессе (те же раунды; время в мс, ускорение по тактам):

| Файл | Без сжатия, МБ | Оригинал, мс | TAKT, мс | `bzip2 -dc`, мс | Против оригинала | Против `bzip2 -dc` |
|---|---:|---:|---:|---:|---:|---:|
| dickens | 10,2 | 247,3 | 65,8 | 286,7 | 4,16× | 4,82× |
| mozilla | 51,2 | 1 048,6 | 370,9 | 1 272,9 | 2,96× | 3,64× |
| mr | 10,0 | 177,2 | 48,4 | 206,1 | 4,04× | 4,64× |
| nci | 33,6 | 461,7 | 111,0 | 516,6 | 4,32× | 4,81× |
| ooffice | 6,2 | 169,4 | 59,0 | 205,5 | 3,20× | 3,95× |
| osdb | 10,1 | 229,3 | 63,0 | 265,5 | 3,92× | 4,68× |
| reymont | 6,6 | 136,0 | 35,8 | 152,9 | 4,25× | 4,87× |
| samba | 21,6 | 333,1 | 115,0 | 404,9 | 3,08× | 3,75× |
| sao | 7,3 | 241,3 | 85,7 | 270,0 | 3,05× | 3,43× |
| webster | 41,5 | 843,6 | 216,1 | 972,2 | 4,10× | 4,79× |
| xml | 5,3 | 72,3 | 20,9 | 82,6 | 4,04× | 4,64× |
| x-ray | 8,5 | 236,4 | 80,1 | 255,6 | 3,22× | 3,50× |

Ускорение зависит от данных: на этих файлах — от 2,96× до 4,32× против оригинала и от 3,43× до 4,87×
против `bzip2 -dc`. Реальное время включает также запуск процесса, чтение входа и работу ядра ОС,
одинаковые для всех программ, поэтому отношения по времени немного ниже отношений по тактам. На
других данных и других процессорах числа будут другими. Подробности и все отсчёты — в
`measurements.json`.

## Запуск

```sh
python3 tools/fetch_silesia.py      # скачивает silesia.zip (68 МБ), проверяет его, пишет data/raw и data/bz2
tools/run_bench.sh 7 2              # проверяет каждый байт вывода, затем 7 чередующихся раундов на ядре 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # совпадает до байта
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` нужен только Python 3; скрипт проверяет архив (sha256) и каждый файл (размер,
MD5 со страницы корпуса, sha256), а также сообщает, совпадают ли ваши входы `.bz2` побайтно с теми,
что замеряли мы. `tools/run_bench.sh` считает и такты, если доступен `perf`.

Использование: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Коды возврата: 0 — успех; 1 — ошибка
использования, ввода-вывода или CPU; 2 — некорректный поток (сообщение декодера печатается в stderr);
3 — внутренняя ошибка декодера.

Linux x86-64 (glibc). Обе программы собраны для x86-64-v3: AVX2, BMI1, BMI2, FMA (Intel Haswell
и новее, AMD Zen и новее); на более старых процессорах они не запускаются.

## Эквивалентность

- Двенадцать файлов Silesia: вывод `bz2dec-original`, `bz2dec-takt` и `bzip2 -dc` побайтно совпадает
  с несжатым файлом — и для каждого файла отдельно, и при прогоне всех двенадцати файлов одним вызовом.
- Ещё 12 900 потоков: 1 200 корректных (случайные фрагменты файлов корпуса, уровни сжатия 1–9)
  и 11 700 повреждённых (900 повреждённых копий полных входов, остальные — повреждённые фрагменты:
  инверсия битов, усечение, замена байтов, обнулённые диапазоны, вставленные и удалённые диапазоны).
  Для каждого потока stdout, stderr и код возврата у двух программ совпадают (код возврата 0:
  1 360 потоков, код возврата 2: 11 540); расхождений 0. Повторить проверку:
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (использовались seed 1 и 2,
  см. `measurements.json`).

## Сборка оригинала

```sh
cd source
RUSTFLAGS="-C target-cpu=x86-64-v3 --remap-path-prefix=$(ls -d ~/.cargo/registry/src/index.crates.io-*)=. \
  --remap-path-prefix=$HOME/.rustup=. --remap-path-prefix=$PWD=." cargo +1.96.0 build --release --locked
strip --strip-all target/release/bz2dec
```

В нашей проверке так получился `bin/bz2dec-original`, совпадающий бит в бит (Rust 1.96.0 из rustup,
в другом каталоге). `bin/bz2dec-takt` — тот же `source/src/main.rs`, скомпонованный со сборкой TAKT
этого крейта; она сохраняет публичный API крейта, тип ошибки и сообщения.

## Состав

- `bin/`: `bz2dec-original` и `bz2dec-takt`;
- `source/`: драйвер и файлы Cargo, из которых собирается `bz2dec-original`;
- `tools/`: `fetch_silesia.py` (корпус и входы), `run_bench.sh` (проверка и замер времени),
  `compare_corrupted.py` (корректные и повреждённые потоки);
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

Исходный код сборки TAKT для bzip2-rs не публикуется: мы поставляем сборки.