# TAKT 쇼케이스: bzip2 압축 해제 (Silesia 코퍼스)

하나의 프로그램을 두 가지로 빌드했습니다. `bz2dec`는 `bzip2 -dc`처럼 `.bz2` 파일을 표준 출력으로 압축 해제합니다.
`bz2dec-original`은 crates.io에 공개된 그대로의 [bzip2-rs](https://crates.io/crates/bzip2-rs) 0.1.2 크레이트(순수 Rust
bzip2 디코더)를 사용하고, `bz2dec-takt`는 TAKT 최적화를 거친 같은 크레이트를 사용합니다. 드라이버는 같은 소스
파일이고 빌드 레시피도 같으며, 두 프로그램의 출력은 바이트 단위로 동일합니다. 이 패키지에는 실행 가능한 두
프로그램, 원본 빌드의 소스, 코퍼스를 내려받는 스크립트, 측정과 검증을 재현하는 스크립트가 들어 있습니다.

## 벤치마크 내용

[Silesia 코퍼스](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia)의 파일 12개(텍스트, 실행 파일,
데이터베이스, 이미지, XML; 211,938,580바이트)를 각각 Python의 `bz2.compress(data, 9)`(libbz2 1.0.8, 파일당
스트림 1개, 합계 54,506,769바이트)로 압축한 뒤, 하나의 프로세스에서 압축 해제합니다:

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

비교를 위해 시스템의 `bzip2 -dc`(C 참조 구현)로 같은 작업을 실행합니다.

## 측정 (TAKT 측정 장비)

AMD Threadripper PRO 5975WX (Zen 3), Linux, 전용 코어 1개(SMT 형제 스레드는 유휴 상태, 해당 CCX는 측정
전용으로 예약). `perf stat`으로 디코딩 프로세스의 사용자 모드 사이클과 명령어 수, 실제 경과 시간을 측정합니다.
교차 실행 9라운드(라운드마다 프로그램 실행 순서를 순환), 중앙값입니다. 이 패키지의 파일을 그대로 측정했습니다.
세 프로그램 모두 glibc에 동적 링크된 실행 파일이며, 두 `bz2dec` 빌드는 같은 레시피를 사용합니다: Rust 1.96.0,
LTO, codegen-units 1, `target-cpu=x86-64-v3`, panic abort, 심볼 제거(stripped).

전체 세트, 프로그램당 프로세스 1개:

| 프로그램 | 디코더 | 사이클(백만) | 명령어(백만) | 시간(ms) | MB/s | 가속 |
|---|---|---:|---:|---:|---:|---:|
| `bz2dec-original` | crates.io의 bzip2-rs 0.1.2 | 17,867.0 | 22,191.1 | 4,129 | 51.3 | 1.00× |
| `bzip2 -dc` | C bzip2 / libbz2 1.0.8 (Ubuntu 24.04 패키지) | 21,148.9 | 25,378.5 | 4,884 | 43.4 | 0.84× |
| `bz2dec-takt` | TAKT 최적화를 거친 같은 크레이트 | 5,104.7 | 10,028.5 | 1,204 | 176.0 | 3.50× |

`bz2dec-takt`는 C `bzip2 -dc` 대비 사이클 기준 4.14배, 시간 기준 4.06배 빠릅니다.
`bz2dec-original` 대비 시간 기준으로는 3.43배입니다. 가속은 사이클 중앙값의 비율이며, MB/s는 실제 경과 시간
1초당 압축 해제된 메가바이트(10⁶바이트)입니다.

파일마다 별도 프로세스로 실행(같은 라운드, 시간은 ms, 가속은 사이클 기준):

| 파일 | 압축 전(MB) | 원본(ms) | TAKT(ms) | `bzip2 -dc`(ms) | 원본 대비 | `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× |

가속은 데이터에 따라 다릅니다. 이 파일들에서는 원본 대비 2.96–4.32배, `bzip2 -dc` 대비 3.43–4.87배입니다.
실제 경과 시간에는 프로세스 시작, 입력 읽기, 커널 작업도 포함되며 이 부분은 모든 프로그램에서 같습니다. 그래서
시간 기준 비율이 사이클 기준 비율보다 약간 낮습니다. 다른 데이터와 다른 CPU에서는 수치가 달라집니다. 자세한
내용과 모든 샘플은 `measurements.json`에 있습니다.

## 실행

```sh
python3 tools/fetch_silesia.py      # silesia.zip(68 MB)을 내려받아 검증하고 data/raw, data/bz2를 생성
tools/run_bench.sh 7 2              # 모든 출력 바이트를 검사한 뒤 코어 2에서 교차 실행 7라운드
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # 바이트 단위로 동일
sha256sum -c SHA256SUMS
```

`tools/fetch_silesia.py`는 Python 3만 있으면 되며, 아카이브(sha256)와 모든 파일(크기, 코퍼스 페이지에 공개된
MD5, sha256)을 검사합니다. 또한 사용자의 `.bz2` 입력이 저희가 측정한 것과 정확히 같은 바이트인지도 알려 줍니다.
`tools/run_bench.sh`는 `perf`를 사용할 수 있으면 사이클도 측정합니다.

사용법: `bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT`. 종료 코드: 0 성공, 1 사용법·I/O·CPU 오류, 2 잘못된
스트림(디코더의 오류 메시지가 stderr에 출력됨), 3 디코더 내부 오류.

Linux x86-64 (glibc). 두 프로그램 모두 x86-64-v3용으로 빌드했습니다: AVX2, BMI1, BMI2, FMA(Intel Haswell
이후, AMD Zen 이후). 이전 CPU에서는 실행되지 않습니다.

## 동등성

- Silesia 파일 12개: `bz2dec-original`, `bz2dec-takt`, `bzip2 -dc`의 출력은 파일별로 실행할 때나 12개 파일을
  한 번에 실행할 때나 원본 파일과 바이트 단위로 동일합니다.
- 추가 스트림 12,900개: 유효한 스트림 1,200개(코퍼스 파일의 무작위 구간, 압축 레벨 1–9)와 손상된 스트림
  11,700개(전체 입력의 손상된 사본 900개, 나머지는 손상된 구간: 비트 반전, 잘림, 바이트 치환, 구간 0으로
  채우기, 구간 삽입 및 삭제). 모든 스트림에서 두 프로그램의 stdout, stderr, 종료 코드가 동일하며(종료 코드 0:
  1,360개, 종료 코드 2: 11,540개), 불일치는 0건입니다. 다음 명령으로 재현할 수 있습니다:
  `python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1`(시드 1과 2를
  사용했으며, `measurements.json` 참조).

## 원본 빌드

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

저희 검증에서는 이 방법으로 `bin/bz2dec-original`을 비트 단위로 동일하게 다시 빌드했습니다(rustup의 Rust
1.96.0, 다른 디렉터리에서). `bin/bz2dec-takt`는 같은 `source/src/main.rs`를 TAKT 빌드 크레이트와 링크한 것으로,
크레이트의 공개 API, 오류 타입, 메시지를 그대로 유지합니다.

## 구성

- `bin/`: `bz2dec-original`과 `bz2dec-takt`
- `source/`: `bz2dec-original`을 빌드하는 드라이버와 Cargo 파일
- `tools/`: `fetch_silesia.py`(코퍼스와 입력), `run_bench.sh`(검증과 시간 측정),
  `compare_corrupted.py`(유효한 스트림과 손상된 스트림)
- `measurements.json`, `SHA256SUMS`, `LICENSE`

bzip2-rs의 TAKT 빌드 소스는 공개하지 않습니다. 저희는 빌드를 제공합니다.