# Vetrina TAKT: decompressione bzip2 (corpus Silesia)

Un solo programma in due build: `bz2dec` decomprime file `.bz2` sullo standard output, come `bzip2 -dc`.
`bz2dec-original` usa il crate [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 (un decoder bzip2
in puro Rust) così come è pubblicato su crates.io; `bz2dec-takt` usa lo stesso crate dopo
l’ottimizzazione TAKT. Il driver è lo stesso file sorgente, la ricetta di build è la stessa e
l’output dei due programmi è identico al byte. Qui si trovano i due programmi pronti, il sorgente
della build originale, uno script che scarica il corpus e gli script che ripetono la misura e le
verifiche.

## Che cosa fa il benchmark

I dodici file del [corpus Silesia](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(testo, eseguibili, database, immagini, XML; 211.938.580 byte), ciascuno compresso con
`bz2.compress(data, 9)` di Python (libbz2 1.0.8, uno stream per file, 54.506.769 byte in totale),
vengono decompressi in un unico processo:

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

Per confronto, lo stesso lavoro viene eseguito dal `bzip2 -dc` di sistema (l’implementazione C di
riferimento).

## Misura (banco TAKT)

AMD Threadripper PRO 5975WX (Zen 3), Linux, un core dedicato (il suo gemello SMT inattivo, il suo
CCX riservato alla misura). `perf stat` conta i cicli e le istruzioni in modalità utente del
processo di decodifica e il suo tempo reale; 9 round alternati (l’ordine dei programmi ruota da un
round all’altro), mediana. Sono stati misurati esattamente questi file. Tutti e tre i programmi
sono eseguibili glibc a collegamento dinamico; entrambe le build di `bz2dec` usano la stessa
ricetta: Rust 1.96.0, LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, simboli rimossi.

L’intero set, un processo per programma:

| Programma | Decoder | Cicli, mln | Istruzioni, mln | Tempo, ms | MB/s | Accelerazione |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 da crates.io | 17.867,0 | 22.191,1 | 4.129 | 51,3 | 1,00× |
| `bzip2 -dc` | bzip2 / libbz2 1.0.8 in C (pacchetto Ubuntu 24.04) | 21.148,9 | 25.378,5 | 4.884 | 43,4 | 0,84× |
| `bz2dec-takt` | lo stesso crate dopo l’ottimizzazione TAKT | 5.104,7 | 10.028,5 | 1.204 | 176,0 | 3,50× |

`bz2dec-takt` rispetto al `bzip2 -dc` in C: 4,14× in cicli, 4,06× in tempo.
Rispetto a `bz2dec-original` in tempo: 3,43×. L’accelerazione è il rapporto tra le mediane dei
cicli; MB/s indica i megabyte decompressi (10⁶ byte) per secondo di tempo reale.

Ogni file in un processo separato (stessi round; tempo in ms, accelerazione in cicli):

| File | Non compresso, MB | Originale, ms | TAKT, ms | `bzip2 -dc`, ms | rispetto all’originale | rispetto a `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× |

L’accelerazione dipende dai dati: su questi file va da 2,96× a 4,32× rispetto all’originale e da
3,43× a 4,87× rispetto a `bzip2 -dc`. Il tempo reale comprende anche l’avvio del processo, la
lettura dell’input e il lavoro del kernel, che sono uguali per ogni programma; per questo i
rapporti in tempo sono un po’ più bassi dei rapporti in cicli. Altri dati e altre CPU daranno altri
numeri. I dettagli e tutti i campioni sono in `measurements.json`.

## Esecuzione

```sh
python3 tools/fetch_silesia.py      # scarica silesia.zip (68 MB), lo verifica, scrive data/raw e data/bz2
tools/run_bench.sh 7 2              # verifica ogni byte in uscita, poi 7 round alternati sul core 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # identico al byte
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` richiede solo Python 3 e verifica l’archivio (sha256) e ogni file
(dimensione, l’MD5 pubblicato sulla pagina del corpus, sha256); indica anche se i suoi input `.bz2`
sono esattamente i byte che abbiamo misurato. `tools/run_bench.sh` conta anche i cicli quando
`perf` è disponibile.

Uso: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Codici di uscita: 0 successo; 1 errore di utilizzo,
di I/O o della CPU; 2 stream non valido (il messaggio di errore del decoder viene stampato su
stderr); 3 errore interno del decoder.

Linux x86-64 (glibc). Entrambi i programmi sono compilati per x86-64-v3: AVX2, BMI1, BMI2, FMA
(Intel Haswell e successivi, AMD Zen e successivi); non funzionano su CPU più vecchie.

## Equivalenza

- I dodici file Silesia: l’output di `bz2dec-original`, `bz2dec-takt` e `bzip2 -dc` coincide con il
  file non compresso byte per byte, file per file e in un’unica esecuzione sui dodici file.
- Altri 12.900 stream: 1.200 validi (porzioni casuali dei file del corpus, livelli di compressione
  1–9) e 11.700 corrotti (900 copie corrotte degli input completi, il resto porzioni corrotte:
  inversione di bit, troncamento, sostituzione di byte, intervalli azzerati, intervalli inseriti ed
  eliminati). Per ogni stream stdout, stderr e codice di uscita dei due programmi sono identici
  (codice di uscita 0: 1.360 stream, codice di uscita 2: 11.540); 0 discrepanze. Per ripetere la
  verifica: `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (sono stati usati
  i seed 1 e 2, si veda `measurements.json`).

## Build dell’originale

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

Nella nostra verifica questa procedura ha ricostruito `bin/bz2dec-original` bit per bit (Rust 1.96.0
da rustup, in un’altra directory). `bin/bz2dec-takt` è lo stesso `source/src/main.rs` collegato alla
build TAKT del crate, che mantiene l’API pubblica, il tipo di errore e i messaggi del crate.

## Contenuto

- `bin/`: `bz2dec-original` e `bz2dec-takt`;
- `source/`: il driver e i file Cargo da cui si compila `bz2dec-original`;
- `tools/`: `fetch_silesia.py` (corpus e input), `run_bench.sh` (verifica e misura dei tempi),
  `compare_corrupted.py` (stream validi e corrotti);
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

Il sorgente della build TAKT di bzip2-rs non è pubblicato: consegniamo build.