# Vitrine TAKT: descompressão bzip2 (corpus Silesia)

Um programa em dois builds: `bz2dec` descomprime arquivos `.bz2` para a saída padrão, como `bzip2 -dc`.
`bz2dec-original` usa o crate [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 (um decodificador
bzip2 em Rust puro) tal como publicado no crates.io; `bz2dec-takt` usa o mesmo crate após a
otimização da TAKT. O driver é o mesmo arquivo-fonte, a receita de build é a mesma e a saída dos
dois programas é idêntica byte a byte. Aqui você encontra os dois programas prontos, o código-fonte
do build original, um script que baixa o corpus e os scripts que repetem a medição e as verificações.

## O que o benchmark faz

Os doze arquivos do [corpus Silesia](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)
(texto, executáveis, bancos de dados, imagens, XML; 211.938.580 bytes), cada um comprimido com
`bz2.compress(data, 9)` do Python (libbz2 1.0.8, um fluxo por arquivo, 54.506.769 bytes no total),
são descomprimidos em um único 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
```

O `bzip2 -dc` do sistema (a implementação de referência em C) executa a mesma tarefa para comparação.

## Medição (bancada TAKT)

AMD Threadripper PRO 5975WX (Zen 3), Linux, um núcleo dedicado (seu par SMT ocioso e seu CCX
reservado para a medição). O `perf stat` conta os ciclos e as instruções em modo usuário do processo
de decodificação e o tempo decorrido; 9 rodadas intercaladas (a ordem dos programas muda de uma
rodada para outra), mediana. Foram medidos exatamente estes arquivos. Os três programas são
executáveis glibc com linkagem dinâmica; os dois builds de `bz2dec` usam a mesma receita: Rust 1.96.0,
LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, sem símbolos (strip).

O conjunto inteiro, um processo por programa:

| Programa | Decodificador | Ciclos, mi | Instruções, mi | Tempo, ms | MB/s | Aceleração |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | bzip2-rs 0.1.2 do crates.io | 17.867,0 | 22.191,1 | 4.129 | 51,3 | 1,00× |
| `bzip2 -dc` | bzip2 / libbz2 1.0.8 em C (pacote do Ubuntu 24.04) | 21.148,9 | 25.378,5 | 4.884 | 43,4 | 0,84× |
| `bz2dec-takt` | o mesmo crate após a otimização da TAKT | 5.104,7 | 10.028,5 | 1.204 | 176,0 | 3,50× |

`bz2dec-takt` em relação ao `bzip2 -dc` em C: 4,14× em ciclos, 4,06× em tempo.
Em relação ao `bz2dec-original` em tempo: 3,43×. A aceleração é a razão entre as medianas de ciclos;
MB/s são megabytes descomprimidos (10⁶ bytes) por segundo de tempo decorrido.

Cada arquivo em seu próprio processo (mesmas rodadas; tempo em ms, aceleração em ciclos):

| Arquivo | Descomprimido, MB | Original, ms | TAKT, ms | `bzip2 -dc`, ms | vs. original | vs. `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× |

A aceleração depende dos dados: de 2,96× a 4,32× em relação ao original e de 3,43× a 4,87× em
relação ao `bzip2 -dc` nestes arquivos. O tempo decorrido também inclui o início do processo, a
leitura da entrada e o trabalho do kernel, que são iguais para todos os programas; por isso as
razões em tempo são um pouco menores que as razões em ciclos. Outros dados e outras CPUs darão
outros números. Os detalhes e todas as amostras estão em `measurements.json`.

## Execução

```sh
python3 tools/fetch_silesia.py      # baixa silesia.zip (68 MB), verifica e grava data/raw e data/bz2
tools/run_bench.sh 7 2              # confere cada byte da saída e depois faz 7 rodadas intercaladas no núcleo 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # idêntico byte a byte
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py` precisa apenas do Python 3 e verifica o arquivo zip (sha256) e cada arquivo
(tamanho, o MD5 publicado na página do corpus, sha256); ele também informa se as suas entradas `.bz2`
são exatamente os bytes que medimos. `tools/run_bench.sh` também conta ciclos quando o `perf` está
disponível.

Uso: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. Códigos de saída: 0, sucesso; 1, erro de uso, de E/S
ou de CPU; 2, fluxo inválido (a mensagem de erro do decodificador é impressa no stderr); 3, erro
interno do decodificador.

Linux x86-64 (glibc). Os dois programas são compilados para x86-64-v3: AVX2, BMI1, BMI2, FMA (Intel
Haswell e mais recentes, AMD Zen e mais recentes); eles não rodam em CPUs mais antigas.

## Equivalência

- Os doze arquivos do Silesia: a saída de `bz2dec-original`, `bz2dec-takt` e `bzip2 -dc` é igual ao
  arquivo descomprimido byte a byte, arquivo por arquivo e em uma única execução com os doze arquivos.
- Mais 12.900 fluxos: 1.200 válidos (trechos aleatórios dos arquivos do corpus, níveis de compressão
  1–9) e 11.700 corrompidos (900 cópias corrompidas das entradas completas; o restante, trechos
  corrompidos: bits invertidos, truncamento, substituição de bytes, intervalos zerados, intervalos
  inseridos e removidos). Para cada fluxo, o stdout, o stderr e o código de saída dos dois programas
  são idênticos (código de saída 0: 1.360 fluxos; código de saída 2: 11.540); 0 divergências. Repita com
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1` (foram usadas
  as sementes 1 e 2, veja `measurements.json`).

## Build do 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
```

Na nossa verificação, isso reproduziu `bin/bz2dec-original` bit a bit (Rust 1.96.0 via rustup, em
outro diretório). `bin/bz2dec-takt` é o mesmo `source/src/main.rs` linkado com o build TAKT do crate,
que mantém a API pública, o tipo de erro e as mensagens do crate.

## Conteúdo

- `bin/`: `bz2dec-original` e `bz2dec-takt`;
- `source/`: o driver e os arquivos do Cargo a partir dos quais `bz2dec-original` é compilado;
- `tools/`: `fetch_silesia.py` (corpus e entradas), `run_bench.sh` (verificação e cronometragem),
  `compare_corrupted.py` (fluxos válidos e corrompidos);
- `measurements.json`, `SHA256SUMS`, `LICENSE`.

O código-fonte do build TAKT do bzip2-rs não é publicado: entregamos builds.