# TAKT-Showcase: bzip2-Dekompression (Silesia-Korpus)

Ein Programm in zwei Builds: `bz2dec` entpackt `.bz2`-Dateien auf die Standardausgabe, wie `bzip2 -dc`.
`bz2dec-original` verwendet das Crate [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 (ein
bzip2-Decoder in reinem Rust) in der auf crates.io veröffentlichten Fassung; `bz2dec-takt` verwendet
dasselbe Crate nach der TAKT-Optimierung. Der Treiber ist dieselbe Quelldatei, das Build-Rezept ist
dasselbe, und die Ausgabe beider Programme ist bis aufs Byte identisch. Das Paket enthält beide
fertigen Programme, den Quellcode des ursprünglichen Builds, ein Skript, das das Korpus herunterlädt,
sowie die Skripte, mit denen sich Messung und Prüfungen wiederholen lassen.

## Was der Benchmark macht

Die zwölf Dateien des [Silesia-Korpus](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(Text, ausführbare Dateien, Datenbanken, Bilder, XML; 211.938.580 Bytes), jeweils mit Pythons
`bz2.compress(data, 9)` komprimiert (libbz2 1.0.8, ein Stream pro Datei, insgesamt 54.506.769 Bytes),
werden in einem Prozess entpackt:

```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
```

Zum Vergleich führt das System-`bzip2 -dc` (die C-Referenzimplementierung) dieselbe Aufgabe aus.

## Messung (TAKT-Messstand)

AMD Threadripper PRO 5975WX (Zen 3), Linux, ein dedizierter Kern (sein zweiter SMT-Thread bleibt im
Leerlauf, sein CCX ist für die Messung reserviert). `perf stat` zählt die Takte und Instruktionen des
Dekodierprozesses im User-Modus sowie seine Laufzeit (Wall-Time); 9 abwechselnde Runden (die
Reihenfolge der Programme rotiert von Runde zu Runde), Median. Gemessen wurden genau diese Dateien.
Alle drei Programme sind dynamisch gelinkte glibc-Executables; beide `bz2dec`-Builds verwenden
dasselbe Rezept: Rust 1.96.0, LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, gestrippt.

Der gesamte Satz, ein Prozess pro Programm:

| Programm | Decoder | Takte, Mio. | Instruktionen, Mio. | Zeit, ms | MB/s | Beschleunigung |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 von crates.io | 17.867,0 | 22.191,1 | 4.129 | 51,3 | 1,00× |
| `bzip2 -dc` | C-bzip2 / libbz2 1.0.8 (Paket aus Ubuntu 24.04) | 21.148,9 | 25.378,5 | 4.884 | 43,4 | 0,84× |
| `bz2dec-takt` | dasselbe Crate nach der TAKT-Optimierung | 5.104,7 | 10.028,5 | 1.204 | 176,0 | 3,50× |

`bz2dec-takt` gegenüber dem C-Programm `bzip2 -dc`: 4,14× nach Takten, 4,06× nach Zeit.
Gegenüber `bz2dec-original` nach Zeit: 3,43×. Die Beschleunigung ist das Verhältnis der Mediane der
Takte; MB/s sind entpackte Megabytes (10⁶ Bytes) pro Sekunde Wall-Time.

Jede Datei in einem eigenen Prozess (dieselben Runden; Zeit in ms, Beschleunigung nach Takten):

| Datei | Unkomprimiert, MB | Original, ms | TAKT, ms | `bzip2 -dc`, ms | ggü. Original | ggü. `bzip2 -dc` |
|---|---:|---:|---:|---:|---:|---:|
| dickens | 10,2 | 247,3 | 65,8 | 286,7 | 4,16× | 4,82× |
| mozilla | 51,2 | 1048,6 | 370,9 | 1272,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× |

Die Beschleunigung hängt von den Daten ab: auf diesen Dateien von 2,96× bis 4,32× gegenüber dem
Original und von 3,43× bis 4,87× gegenüber `bzip2 -dc`. Die Wall-Time umfasst außerdem Prozessstart,
Lesen der Eingabe und Kernel-Arbeit, die für alle Programme gleich sind; deshalb fallen die
Verhältnisse nach Zeit etwas niedriger aus als nach Takten. Andere Daten und andere CPUs ergeben
andere Zahlen. Details und alle Einzelmessungen stehen in `measurements.json`.

## Ausführen

```sh
python3 tools/fetch_silesia.py      # lädt silesia.zip (68 MB) herunter, prüft es, schreibt data/raw und data/bz2
tools/run_bench.sh 7 2              # prüft jedes Ausgabebyte, dann 7 abwechselnde Runden auf Kern 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # bis aufs Byte identisch
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` benötigt nur Python 3 und prüft das Archiv (sha256) und jede Datei (Größe,
die auf der Korpus-Seite veröffentlichte MD5, sha256); außerdem meldet es, ob Ihre `.bz2`-Eingaben
exakt die von uns gemessenen Bytes sind. `tools/run_bench.sh` zählt auch Takte, wenn `perf`
verfügbar ist.

Aufruf: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Exit-Codes: 0 Erfolg; 1 Aufruf-, E/A- oder
CPU-Fehler; 2 ungültiger Stream (die Fehlermeldung des Decoders wird auf stderr ausgegeben);
3 interner Decoder-Fehler.

Linux x86-64 (glibc). Beide Programme sind für x86-64-v3 gebaut: AVX2, BMI1, BMI2, FMA (Intel Haswell
und neuer, AMD Zen und neuer); auf älteren CPUs laufen sie nicht.

## Äquivalenz

- Die zwölf Silesia-Dateien: Die Ausgabe von `bz2dec-original`, `bz2dec-takt` und `bzip2 -dc` stimmt
  Byte für Byte mit der unkomprimierten Datei überein, Datei für Datei und als ein Lauf über alle
  zwölf Dateien.
- 12.900 weitere Streams: 1.200 gültige (zufällige Ausschnitte der Korpusdateien, Kompressionsstufen
  1–9) und 11.700 beschädigte (900 beschädigte Kopien der vollständigen Eingaben, der Rest beschädigte
  Ausschnitte: Bit-Flips, Abschneiden, Byte-Ersetzung, genullte Bereiche, eingefügte und gelöschte
  Bereiche). Für jeden Stream sind stdout, stderr und Exit-Code beider Programme identisch (Exit-Code 0:
  1.360 Streams, Exit-Code 2: 11.540); 0 Abweichungen. Wiederholen lässt sich das mit
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (verwendet wurden die Seeds 1 und 2,
  siehe `measurements.json`).

## Original bauen

```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
```

Bei unserer Prüfung ergab dies `bin/bz2dec-original` Bit für Bit (Rust 1.96.0 aus rustup, in einem
anderen Verzeichnis). `bin/bz2dec-takt` ist dieselbe `source/src/main.rs`, gelinkt mit dem TAKT-Build
des Crates, der die öffentliche API, den Fehlertyp und die Meldungen des Crates beibehält.

## Inhalt

- `bin/`: `bz2dec-original` und `bz2dec-takt`;
- `source/`: der Treiber und die Cargo-Dateien, aus denen `bz2dec-original` gebaut wird;
- `tools/`: `fetch_silesia.py` (Korpus und Eingaben), `run_bench.sh` (Prüfung und Zeitmessung),
  `compare_corrupted.py` (gültige und beschädigte Streams);
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

Der Quellcode des TAKT-Builds von bzip2-rs wird nicht veröffentlicht: Wir liefern Builds.