DeepSeek总结的PIVCO-Huffman编码性能优化

PIVCO-Huffman

🚧 WIP — 进行中 🚧

PivCo-Huffman 是一个优化 Huffman 编码性能的研究项目。虽然它提供了库和大量代码，但远未达到生产就绪的程度。

论文（HTML、PDF）是权威的详细阐述；本 README 是简短摘要。

TL;DR

在 Apple M4 上的具体数据，pivco_bu 解码 vs huf0_x2：

• proba80 高度倾斜：15.3 GB/s，是 huf0_x2 的 5.9 倍。
• proba50 / proba14：9.2 / 5.2 GB/s，3.6 倍 / 2.1 倍。
• flat_M* 完全平坦：20–24 GB/s，4.1–4.8 倍。
• english / prose_pride / html_wiki / chinese_text 真实文本：4.3–4.8 GB/s，是 huf0_x2 的 2.0–2.5 倍。
• gzip_random / image_jpeg 高熵：4.1–4.9 GB/s，2.7–3.2 倍。

PHA（PH + 每节点 FSE/ANS 编码的分区位图）以部分解码带宽换取倾斜数据上更好的压缩率（M4 数据；huf0 / oo-huff 产生相同的 Huffman 压缩率）：

• proba80：压缩率 8.45 倍 vs huf0 / oo-huff 的 6.40 倍（+32%）；解码 5.9 GB/s，仍是 huf0_x2 的 2.2 倍。
• calgary_pic（真实的 proba80 形态 1bpp 扫描页）：压缩率 6.13 倍 vs 4.79 倍（+28%）；解码 6.4 GB/s，是 huf0_x2 的 2.6 倍。
• 中等熵 / 真实文本分布（english、prose_pride、html_wiki、image_jpeg）：当分区位图不倾斜时，FSE 门控不会触发，因此 PHA 的压缩率在普通 Huffman 的 ±1% 以内。PHA 是压缩率的安全默认选择，PH 是峰值解码带宽的选择。

跨 ISA 峰值倍率随 SIMD 原语宽度扩展：Xeon AVX-512 1.43–13.8 倍 · Apple M4 NEON 1.43–10.7 倍 · Graviton 4 NEON 1.29–8.59 倍 · Zen 3 SSE/AVX2 0.94–22.5 倍（三行深层真实文本在 Zen 3 上落后约 6%）。

编码大小在传统 Huffman 的 1–4% 以内。

每主机表格、方法以及整个基准测试网格的观察结果在 docs/BENCHMARKS.md 中。

什么是 PIVCO-Huffman？

PIVCO-Huffman 将 PIVoted COding（枢轴编码）方法应用于 Huffman。PIVCO 不是通过表查找一次解码一个符号，而是同时处理整个 N 个符号的块，使用两种互补策略中更适合每个 Huffman 子树形态的那一种：

• SIMD 树遍历分区，用于混合深度子树，它根据每个内部节点的位图拆分块的索引集并递归；
• 平坦子树快速路径，用于所有叶子都位于相同相对深度的子树，它用每个元素一个打包的 D 位码和底部一次直接的 code_to_sym[code] 查找来替代一系列逐层位图。

检测和分派在 pivco_huffman_build_table 时发生一次——编码器遍历树并标记每个最大平坦子树（local_min_depth == local_max_depth >= 2），为每个平坦子树预计算 code_to_sym，编码器和解码器都查询这些标志以在每个节点选择正确的路径。

完整的算法描述、动机和分析在论文中。给好奇读者的指引：

• 线格式 — docs/DATA_FORMAT.md 和 src/pivco_huffman_wire.h。
• SIMD 内核走查 — docs/KERNELS.md（NEON partition_8、tree_merge、flat_dN_unpack 及示例）。
• 每个原语的微基准成本 — docs/KEY-PRIMITIVES.md。
• 性能分析笔记（历史） — docs/PROFILING.md。
• 块大小扫描 — docs/BLOCK_SIZE.md。
• 相关工作 + 小波树联系 — docs/RELATED-WORK.md 和 docs/WAVELET_TREES.md。
• 测试数据集 — extras/datasets/（合成 + 真实世界分布）。
• 优化想法日志 — IDEAS.md（已发布 / 已丢弃 / 开放，含周期级分析）。

基线

基准测试网格将 PIVCO-Huffman 解码与我们认为是业界最先进的两种生产级 Huffman 解码器进行比较：

• huf0 — cyan4973/FiniteStateEntropy，zstd 中的 Huffman 解码器。4 流交错，11 位主表（X1）或 11+5 位双查找（X2）。原版自动分派是默认的头条基线。
• oo-huff — Oodle 的 newlz_arrays_huff（RAD 发布的 OodleUE 源码），6 流手工调优 ASM。被认为是 Huffman 解码的绝对 SotA。当 Oodle SDK 符号链接在 ext/oodle 时链接到 bench/bench_fair.c。

较旧的遗留基线（树内 trad_1s / trad_4s 4 流参考解码器）已从头条表格中退役。ph 是与人们实际发布的两种编解码器进行对比定位的。

构建与测试

# 前置条件（仅首次）
git submodule update –init ext/fse # FSE 熵编码器（PHA 必需）

# 构建
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake –build build

# 测试
./build/pivco_huffman_tests

# 基准测试（参数 = 每次运行的重复次数，默认 100）
./build/pivco_huffman_bench 20 # 快速
./build/pivco_huffman_bench 100 # 彻底

在你自己的数据上试用

PIVCO-Huffman 可作为库使用——你不必采用我们的文件格式来测量它。三种方式，从最简单开始：

CLI — pivcohuf 压缩文件并打印大小 / 压缩率 / 时间 / 带宽：

./build/pivcohuf c yourfile # PH -> yourfile.ph
./build/pivcohuf c -a yourfile # PHA （ANS 编码位图；倾斜数据上压缩率更好）
./build/pivcohuf d yourfile.ph # 解压（自动检测 PH vs PHA）

示例 — examples/try.c（CMake 目标 pivco_try）用 PH 和 PHA 压缩一个文件并报告压缩率 + 编码/解码吞吐量：

./build/pivco_try yourfile
# yourfile (2000000 bytes) [ratio = in/out, higher = better]
# ph 6.28x (2000000 -> 318379) enc 704 MB/s dec 5405 MB/s roundtrip ok
# pha 8.44x (2000000 -> 236833) enc 495 MB/s dec 3578 MB/s roundtrip ok

库 — 链接 libpivco_huffman.a 并调用 include/pivcohuf_file.h 中的缓冲区 API（无需了解线格式）：

#include "pivcohuf_file.h"
size_t cap = pivcohuf_compress_bound(in_len);
uint8_t *out = malloc(cap); size_t out_len = cap;
pivcohuf_compress_ex(in, in_len, out, &out_len, /*use_ans=*/1); // PHA; 0 = PH

size_t usz; pivcohuf_peek_uncompressed_size(out, out_len, &usz);
uint8_t *dec = malloc(usz); size_t dlen = usz;
pivcohuf_decompress(out, out_len, dec, &dlen); // 自动检测 PH/PHA

要将编解码器嵌入你自己的容器/帧格式，请使用 include/pivco_huffman.h 中的块原语（先 pivco_huffman_build_table，然后对 PIVCO_BLOCK_SIZE 符号块调用 pivco_huffman_encode / pivco_huffman_decode；为 PHA 调用 pivco_huffman_set_fse_enabled(1)）。

编译时自定义块大小：

cmake -B build -DCMAKE_BUILD_TYPE=Release \\
-DCMAKE_C_FLAGS="-DPIVCO_BLOCK_SIZE=16384"

与 zstd / FSE 一起链接 — libpivco_huffman.a 内置了 FiniteStateEntropy（FSE_*/HUF_*/HIST_*/g_debuglevel），因此将其链接到任何也内置 FSE 的东西（zstd、lz4 的熵层……）旁边会遇到重复符号错误。对于这种情况，构建会生成一个可直接替换的可重定位对象 build/libpivco_huffman_local.o，其中这些符号被本地化，而 pivco 的公共 pivco_*/pivcohuf_* API 保持全局——链接它而不是 .a，冲突就消失了：

cmake –build build –target pivco_huffman_local # 默认也会构建
cc your_app.c build/libpivco_huffman_local.o -Iinclude -o your_app

例如 extras/phaz 就是这样链接的。

交互式树可视化

figures/tree_viz.html 是一个自包含的 HTML/JS 探索器，用于查看 Huffman 树并叠加平坦子树快速路径。它从 figures/tree_viz_data.js 加载 29 个基准分布（由 ./build/pivco_dump_distributions > figures/tree_viz_data.js 重新生成），接受文件/文本上传，并允许你切换平坦子树检测、点击平坦根来（取消）扁平化以进行 ops/leaf 和链式规则熵总计的假设分析，以及拖动最大码长滑块。直接在浏览器中打开该文件——无需构建服务器。