
MinLZ v1.3 发布,为 Go 和 Rust 新增 SIMD 块压缩
来源标题:MinLZ SIMD block compression (Go, Rust)
MinLZ v1.3 版本发布,同时为 Go(v1.3.0)和 Rust 引入新的 SIMD 块类型,可将 LZ 压缩器的输出存为独立的 Huffman 编码流,让 CPU 用向量指令解码且几乎没有不可预测分支。官方称其压缩比接近 zstd,解压速度接近 LZ4。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
代码 Issues Pull requests Actions 安全与质量 洞察 更多项目 发布版本 v1.3.0 v1.3.0 最新 最新 比较 选择一个标签进行比较 抱歉,出了点问题。 筛选 加载中 抱歉,出了点问题。 哎呀! 加载时出错。请重新加载此页面。 v1.3.0 8fce550 此提交在 GitHub.com 上创建,并使用 GitHub 的验证签名进行了签名。 GPG 密钥 ID:B5690EEEBB952194 已验证 了解 vigilant 模式。 MinLZ v1.3 “SIMD Blocks” 压缩比媲美 zstd,解压速度比肩 LZ4。 MinLZ 新增了一种块类型:SIMD 块,同时面向 Go(v1.3.0)和 Rust 发布。 它们将 LZ 压缩器的输出存储为独立的 Huffman 编码流,其布局使 CPU 能够用向量指令解码, 并且几乎没有不可预测的分支。 结果是压缩比达到 Zstandard 的水平,单核解压速度比 Zstandard 快 2.2-2.5 倍(两者均为 Go 实现), 比经典 MinLZ 块快约 2 倍。 在默认 2 MB 块大小下,MinLZ SIMD “Balanced” 在全部三项指标上均胜过 zstd 的最快级别: 其输出小 2%,单核解压快 2.5 倍(6.4 对 2.6 GB/s), 16 线程压缩快 1.6 倍(单线程快 1.2 倍)。 与 zstd 的默认级别相比,SIMD Balanced 的输出大 3.6%,解压快 2.3 倍。 13 个数据集、总计 58 GB 的几何平均值,Go 实现在 AMD Ryzen 9 9950X 上运行。 SIMD 块是 MinLZ 格式(规范 v1.1)的一部分,并且能在 MinLZ 块支持的所有场景中工作: 流、并发压缩与解压、索引与随机访问,以及搜索。 mz c 默认写入它们。 MinLZ 是 MinIO 开发的一种无损压缩算法, 面向现代数据格式。它旨在以 I/O 速度进行压缩和解压, 同时提供良好的压缩比。 该格式有完整、开放的规范,并且是 AIStor 中使用的主要压缩格式。 SIMD 块的目标是打造一种尽可能与 SIMD 处理良好配合的块格式。 我们保留了现有的标量固定格式块,作为旧 CPU 以及极小块的选项。 新格式的触发点是 pivco-huffman 项目 展示了熵编码和解码都可以用 SIMD 高效完成。 我长期以来一直认为 LZ 可以以一种能用 SIMD 高效解码的方式表达, 但这通常被相对较慢的熵编码所抵消。 目标: 设计一种格式,允许对 LZ 和字面量数据进行熵编码, 且熵编码可以以最小开销完成。 次要目标是尽可能少地牺牲解压速度。 我很希望能有在解压速度上与 LZ4 竞争的东西, 并且很高兴地发现这可以在不大幅牺牲压缩比的情况下实现。 13 个数据集在 AMD Ryzen 9 9950X 上的几何平均值。MinLZ 使用 2 MB 块,zstd 使用 2 MB 窗口; LZ4 和 gzip 使用其固定窗口。所有编解码器均为 Go 实现,参见 Benchmarks。 像 Snappy 或经典 MinLZ 这样的经典 LZ 格式将所有内容交错在单一字节流中: 一个标签、一些字面量字节、一个匹配、另一个标签。解码器读取标签以了解接下来是什么, 因此每个操作都始于一个依赖数据的分支。我们自己为经典 MinLZ 编写的汇编解码器 每个操作大约有 6-10 个条件分支:标签类型、长度字段有多长、 边界检查、复制的尺寸类别,以及复制是否与自身重叠。 在真实数据上,其中许多分支是不可预测的,每次预测失败都会丢弃 CPU 已经开始的工作。LZ4 的解压速度主要来自基本无分支, 但代价是显著的效率损失。 交错的字节流也不适合熵编码。标签、长度、偏移量和字面量字节 并排存在,各自有各自的统计特性,因此没有单一编码能适合所有。 为熵编码构建的格式,如 zstd 和 deflate,压缩效果更好,但它们的解码器在内层循环中为此付出代价: deflate 在复制之间解码每个字面量、长度和距离符号, zstd 在运行每个序列之前立即解码其编码。 这些位读取器是串行的:一个符号从哪里开始取决于它之前符号的长度。 这些格式的解压速度只有 LZ4 的一小部分。 SIMD 块保留 LZ77 解析,但将其每个字段写入各自的缓冲区: 最多 16,384 个操作形成一个块(格式允许 65,535 个),每个块的每个流按原样存储 或进行 Huffman 编码,使用新表或前一个表。 字面量有自己的 Huffman 块。只有当至少节省 64 字节时才写入新表, 因为每个表也会消耗解码时间。 因为每个流持有一种值,每个流都获得适合它的 Huffman 表: token、长度和偏移量类别都有非常不同的统计特性。 而且由于一个块的流在其操作运行之前已经过熵解码,内层循环不做熵解码: 它读取普通字节,加上原始偏移位。 token 中的两个标志意味着没有字面量或没有新偏移量的操作在其他流中不产生任何开销。 拆分流并不是新想法。Oodle 的 Kraken 和 Mermaid 就是这样解码的,LZSSE 展示了 LZ 解码 可以在无分支的情况下运行,而 zstd 将其字面量与序列分开进行 Huffman 编码。 SIMD 块将这些想法结合在一个具有开放规范的格式中,具有 SIMD Huffman 解码 和无分支的内层循环。 首先,它的流用 pivco 进行 Huffman 解码,这是一个基于 pivco-huffman 的 SIMD Huffman 解码器,使用 AVX-512、AVX2 或 NEON 并行解码许多符号。token 和字面量长度告诉解码器每个流持有多少个值, 因此一个块的所有流大小在其操作运行之前一次性检查, 而不是对每个操作进行边界检查。 然后操作运行。每个操作做同样的工作:
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。