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 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 (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:

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:

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):

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

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

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.