# Vitrine TAKT : décompression bzip2 (corpus Silesia)

Un même programme en deux builds : `bz2dec` décompresse des fichiers `.bz2` vers la sortie standard,
comme `bzip2 -dc`. `bz2dec-original` utilise la crate [bzip2-rs](https://crates.io/crates/bzip2-rs)
0.1.2 (un décodeur bzip2 en Rust pur) telle que publiée sur crates.io ; `bz2dec-takt` utilise la même
crate après optimisation par TAKT. Le programme pilote est le même fichier source, les options de
compilation sont les mêmes, et la sortie des deux programmes est identique à l’octet près. Vous
trouverez ici les deux programmes prêts à l’emploi, le code source du build d’origine, un script qui
télécharge le corpus et les scripts qui reproduisent la mesure et les vérifications.

## Ce que fait le benchmark

Les douze fichiers du [corpus Silesia](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(texte, exécutables, bases de données, images, XML ; 211 938 580 octets), chacun compressé avec
`bz2.compress(data, 9)` de Python (libbz2 1.0.8, un flux par fichier, 54 506 769 octets au total),
sont décompressés dans un seul processus :

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

Le `bzip2 -dc` du système (l’implémentation C de référence) exécute la même tâche à titre de
comparaison.

## Mesure (banc TAKT)

AMD Threadripper PRO 5975WX (Zen 3), Linux, un cœur dédié (son jumeau SMT inactif, son CCX réservé à
la mesure). `perf stat` compte les cycles et les instructions en mode utilisateur du processus de
décodage, ainsi que son temps écoulé ; 9 tours entrelacés (l’ordre des programmes change d’un tour à
l’autre), médiane. Ce sont exactement ces fichiers qui ont été mesurés. Les trois programmes sont des
exécutables glibc liés dynamiquement ; les deux builds de `bz2dec` utilisent les mêmes options :
Rust 1.96.0, LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, symboles supprimés.

L’ensemble complet, un processus par programme :

| Programme | Décodeur | Cycles, M | Instructions, M | Temps, ms | Mo/s | Accélération |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 depuis crates.io | 17 867,0 | 22 191,1 | 4 129 | 51,3 | 1,00× |
| `bzip2 -dc` | bzip2 en C / libbz2 1.0.8 (paquet Ubuntu 24.04) | 21 148,9 | 25 378,5 | 4 884 | 43,4 | 0,84× |
| `bz2dec-takt` | la même crate après optimisation par TAKT | 5 104,7 | 10 028,5 | 1 204 | 176,0 | 3,50× |

`bz2dec-takt` face au `bzip2 -dc` en C : 4,14× en cycles, 4,06× en temps.
Face à `bz2dec-original` en temps : 3,43×. L’accélération est le rapport des médianes de cycles ;
Mo/s correspond aux mégaoctets décompressés (10⁶ octets) par seconde de temps écoulé.

Chaque fichier dans son propre processus (mêmes tours ; temps en ms, accélération en cycles) :

| Fichier | Brut, Mo | Original, ms | TAKT, ms | `bzip2 -dc`, ms | face à l’original | face à `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× |

L’accélération dépend des données : de 2,96× à 4,32× face à l’original et de 3,43× à 4,87× face à
`bzip2 -dc` sur ces fichiers. Le temps écoulé inclut aussi le démarrage du processus, la lecture de
l’entrée et le travail du noyau, identiques pour tous les programmes ; c’est pourquoi les rapports en
temps sont un peu inférieurs aux rapports en cycles. D’autres données et d’autres CPU donneront
d’autres chiffres. Les détails et tous les échantillons figurent dans `measurements.json`.

## Exécution

```sh
python3 tools/fetch_silesia.py      # télécharge silesia.zip (68 Mo), le vérifie, écrit data/raw et data/bz2
tools/run_bench.sh 7 2              # vérifie chaque octet de sortie, puis 7 tours entrelacés sur le cœur 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # identique à l’octet près
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` ne nécessite que Python 3 et vérifie l’archive (sha256) et chaque fichier
(taille, MD5 publié sur la page du corpus, sha256) ; il indique aussi si vos entrées `.bz2` sont
exactement les octets que nous avons mesurés. `tools/run_bench.sh` compte aussi les cycles lorsque
`perf` est disponible.

Utilisation : `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Codes de sortie : 0 succès ; 1 erreur
d’utilisation, d’E/S ou de CPU ; 2 flux invalide (le message d’erreur du décodeur est écrit sur
stderr) ; 3 erreur interne du décodeur.

Linux x86-64 (glibc). Les deux programmes sont compilés pour x86-64-v3 : AVX2, BMI1, BMI2, FMA
(Intel Haswell et plus récents, AMD Zen et plus récents) ; ils ne fonctionnent pas sur des CPU plus
anciens.

## Équivalence

- Les douze fichiers Silesia : la sortie de `bz2dec-original`, `bz2dec-takt` et `bzip2 -dc` est
  identique au fichier brut octet par octet, fichier par fichier comme en une seule exécution sur
  les douze fichiers.
- 12 900 flux supplémentaires : 1 200 valides (tranches aléatoires des fichiers du corpus, niveaux
  de compression 1–9) et 11 700 corrompus (900 copies corrompues des entrées complètes, le reste des
  tranches corrompues : inversions de bits, troncature, substitution d’octets, plages mises à zéro,
  plages insérées et supprimées). Pour chaque flux, stdout, stderr et le code de sortie des deux
  programmes sont identiques (code de sortie 0 : 1 360 flux, code de sortie 2 : 11 540) ;
  0 divergence. Pour le reproduire :
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (les graines 1 et 2 ont été utilisées,
  voir `measurements.json`).

## Recompiler l’original

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

Lors de notre vérification, cela a reproduit `bin/bz2dec-original` bit à bit (Rust 1.96.0 installé
via rustup, dans un autre répertoire). `bin/bz2dec-takt` est le même `source/src/main.rs` lié au
build TAKT de la crate, qui conserve l’API publique, le type d’erreur et les messages de la crate.

## Contenu

- `bin/` : `bz2dec-original` et `bz2dec-takt` ;
- `source/` : le programme pilote et les fichiers Cargo à partir desquels `bz2dec-original` est
  compilé ;
- `tools/` : `fetch_silesia.py` (corpus et entrées), `run_bench.sh` (vérification et chronométrage),
  `compare_corrupted.py` (flux valides et corrompus) ;
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

Le code source du build TAKT de bzip2-rs n’est pas publié : nous livrons des builds.