PIVCO-Huffman WIP — 进行中 PivCo-Huffman 是一个优化 Huffman 编码性能的研究项目。虽然它提供了库和大量代码但远未达到生产就绪的程度。论文HTML、PDF是权威的详细阐述本 README 是简短摘要。TL;DR在 Apple M4 上的具体数据pivco_bu解码 vshuf0_x2proba80高度倾斜15.3 GB/s是huf0_x2的 5.9 倍。proba50/proba149.2 / 5.2 GB/s3.6 倍 / 2.1 倍。flat_M*完全平坦20–24 GB/s4.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/s2.7–3.2 倍。PHAPH 每节点 FSE/ANS 编码的分区位图以部分解码带宽换取倾斜数据上更好的压缩率M4 数据huf0/oo-huff产生相同的 Huffman 压缩率proba80压缩率 8.45 倍 vshuf0/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-HuffmanPIVCO-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.mdNEONpartition_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/FiniteStateEntropyzstd 中的 Huffman 解码器。4 流交错11 位主表X1或 115 位双查找X2。原版自动分派是默认的头条基线。oo-huff— Oodle 的newlz_arrays_huffRAD 发布的 OodleUE 源码6 流手工调优 ASM。被认为是 Huffman 解码的绝对 SotA。当 Oodle SDK 符号链接在ext/oodle时链接到bench/bench_fair.c。较旧的遗留基线树内trad_1s/trad_4s4 流参考解码器已从头条表格中退役。ph是与人们实际发布的两种编解码器进行对比定位的。构建与测试# 前置条件仅首次gitsubmodule update--initext/fse# FSE 熵编码器PHA 必需# 构建cmake-Bbuild-DCMAKE_BUILD_TYPERelease cmake--buildbuild# 测试./build/pivco_huffman_tests# 基准测试参数 每次运行的重复次数默认 100./build/pivco_huffman_bench20# 快速./build/pivco_huffman_bench100# 彻底在你自己的数据上试用PIVCO-Huffman 可作为库使用——你不必采用我们的文件格式来测量它。三种方式从最简单开始CLI—pivcohuf压缩文件并打印大小 / 压缩率 / 时间 / 带宽./build/pivcohuf c yourfile# PH - yourfile.ph./build/pivcohuf c-ayourfile# PHA ANS 编码位图倾斜数据上压缩率更好./build/pivcohuf d yourfile.ph# 解压自动检测 PH vs PHA示例—examples/try.cCMake 目标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无需了解线格式#includepivcohuf_file.hsize_tcappivcohuf_compress_bound(in_len);uint8_t*outmalloc(cap);size_tout_lencap;pivcohuf_compress_ex(in,in_len,out,out_len,/*use_ans*/1);// PHA; 0 PHsize_tusz;pivcohuf_peek_uncompressed_size(out,out_len,usz);uint8_t*decmalloc(usz);size_tdlenusz;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-Bbuild-DCMAKE_BUILD_TYPERelease\-DCMAKE_C_FLAGS-DPIVCO_BLOCK_SIZE16384与 zstd / FSE 一起链接—libpivco_huffman.a内置了 FiniteStateEntropyFSE_*/HUF_*/HIST_*/g_debuglevel因此将其链接到任何也内置 FSE 的东西zstd、lz4 的熵层……旁边会遇到重复符号错误。对于这种情况构建会生成一个可直接替换的可重定位对象build/libpivco_huffman_local.o其中这些符号被本地化而 pivco 的公共pivco_*/pivcohuf_*API 保持全局——链接它而不是.a冲突就消失了cmake--buildbuild--targetpivco_huffman_local# 默认也会构建cc your_app.c build/libpivco_huffman_local.o-Iinclude-oyour_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 和链式规则熵总计的假设分析以及拖动最大码长滑块。直接在浏览器中打开该文件——无需构建服务器。