# Demostración de TAKT: descompresión bzip2 (corpus Silesia)

Un programa en dos compilaciones: `bz2dec` descomprime archivos `.bz2` a la salida estándar, como
`bzip2 -dc`. `bz2dec-original` usa el crate [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 (un
decodificador bzip2 escrito íntegramente en Rust) tal como está publicado en crates.io;
`bz2dec-takt` usa el mismo crate tras la optimización de TAKT. El programa de control es el mismo
archivo fuente, la receta de compilación es la misma y la salida de ambos programas es idéntica
byte a byte. Aquí encontrará los dos programas listos, el código fuente de la compilación original,
un script que descarga el corpus y los scripts que repiten la medición y las verificaciones.

## Qué hace el benchmark

Los doce archivos del [corpus Silesia](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(texto, ejecutables, bases de datos, imágenes, XML; 211.938.580 bytes), cada uno comprimido con
`bz2.compress(data, 9)` de Python (libbz2 1.0.8, un flujo por archivo, 54.506.769 bytes en total),
se descomprimen en un solo proceso:

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

Como comparación, el `bzip2 -dc` del sistema (la implementación de referencia en C) ejecuta la misma
tarea.

## Medición (banco de TAKT)

AMD Threadripper PRO 5975WX (Zen 3), Linux, un núcleo dedicado (su hilo SMT gemelo inactivo y su
CCX reservado para la medición). `perf stat` cuenta los ciclos y las instrucciones en modo usuario
del proceso de decodificación, así como su tiempo de reloj; 9 rondas intercaladas (el orden de los
programas rota de una ronda a otra), mediana. Se midieron exactamente estos archivos. Los tres
programas son ejecutables glibc con enlace dinámico; las dos compilaciones de `bz2dec` usan la misma
receta: Rust 1.96.0, LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, sin símbolos.

El conjunto completo, un proceso por programa:

| Programa | Decodificador | Ciclos, M | Instrucciones, M | Tiempo, ms | MB/s | Aceleración |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 de crates.io | 17.867,0 | 22.191,1 | 4.129 | 51,3 | 1,00× |
| `bzip2 -dc` | bzip2 en C / libbz2 1.0.8 (paquete de Ubuntu 24.04) | 21.148,9 | 25.378,5 | 4.884 | 43,4 | 0,84× |
| `bz2dec-takt` | el mismo crate tras la optimización de TAKT | 5.104,7 | 10.028,5 | 1.204 | 176,0 | 3,50× |

`bz2dec-takt` frente al `bzip2 -dc` en C: 4,14× en ciclos, 4,06× en tiempo.
Frente a `bz2dec-original` en tiempo: 3,43×. La aceleración es el cociente de las medianas de
ciclos; MB/s son megabytes descomprimidos (10⁶ bytes) por segundo de tiempo de reloj.

Cada archivo en su propio proceso (las mismas rondas; tiempo en ms, aceleración en ciclos):

| Archivo | Sin comprimir, MB | Original, ms | TAKT, ms | `bzip2 -dc`, ms | frente al original | frente a `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× |

La aceleración depende de los datos: de 2,96× a 4,32× frente al original y de 3,43× a 4,87× frente
a `bzip2 -dc` en estos archivos. El tiempo de reloj incluye también el arranque del proceso, la
lectura de la entrada y el trabajo del kernel, que son iguales para todos los programas; por eso los
cocientes en tiempo son algo menores que los cocientes en ciclos. Otros datos y otras CPU darán
otras cifras. Los detalles y todas las muestras están en `measurements.json`.

## Ejecución

```sh
python3 tools/fetch_silesia.py      # descarga silesia.zip (68 MB), lo verifica y escribe data/raw y data/bz2
tools/run_bench.sh 7 2              # verifica cada byte de salida y luego hace 7 rondas intercaladas en el núcleo 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # idénticos byte a byte
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` solo necesita Python 3 y verifica el archivo comprimido (sha256) y cada
archivo del corpus (tamaño, el MD5 publicado en la página del corpus, sha256); también le indica si
sus entradas `.bz2` son exactamente los bytes que medimos. `tools/run_bench.sh` también cuenta ciclos
cuando `perf` está disponible.

Uso: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Códigos de salida: 0, éxito; 1, error de uso, de E/S
o de CPU; 2, flujo no válido (el mensaje de error del decodificador se imprime en stderr); 3, error
interno del decodificador.

Linux x86-64 (glibc). Ambos programas están compilados para x86-64-v3: AVX2, BMI1, BMI2, FMA (Intel
Haswell y posteriores, AMD Zen y posteriores); no funcionan en CPU más antiguas.

## Equivalencia

- Los doce archivos de Silesia: la salida de `bz2dec-original`, `bz2dec-takt` y `bzip2 -dc` es igual
  al archivo sin comprimir byte a byte, archivo por archivo y en una sola ejecución con los doce.
- 12.900 flujos adicionales: 1.200 válidos (fragmentos aleatorios de los archivos del corpus, niveles
  de compresión 1–9) y 11.700 corruptos (900 copias corruptas de las entradas completas; el resto,
  fragmentos corruptos: inversión de bits, truncamiento, sustitución de bytes, rangos puestos a cero,
  rangos insertados y eliminados). Para cada flujo, la stdout, la stderr y el código de salida de los
  dos programas son idénticos (código de salida 0: 1.360 flujos; código de salida 2: 11.540);
  0 discrepancias. Puede repetirlo con
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (se usaron las semillas 1 y 2;
  consulte `measurements.json`).

## Compilar el 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
```

En nuestra verificación, esto reconstruyó `bin/bz2dec-original` bit a bit (Rust 1.96.0 de rustup, en
otro directorio). `bin/bz2dec-takt` es el mismo `source/src/main.rs` enlazado con la compilación de
TAKT del crate, que conserva la API pública del crate, su tipo de error y sus mensajes.

## Contenido

- `bin/`: `bz2dec-original` y `bz2dec-takt`;
- `source/`: el programa de control y los archivos de Cargo a partir de los cuales se compila
  `bz2dec-original`;
- `tools/`: `fetch_silesia.py` (corpus y entradas), `run_bench.sh` (verificación y cronometraje),
  `compare_corrupted.py` (flujos válidos y corruptos);
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

No se publica el código fuente de la compilación de TAKT de bzip2-rs: entregamos compilaciones.