从零实现高性能压缩库：LZ77匹配引擎与SIMD优化实战

曾经我以为压缩库就是调个参数的事，直到线上服务的 CPU 给压缩打满，我才决定老老实实动手，把一个高性能压缩库实现从头写了一遍。这篇帖子就是记录那几周里做的算法选型、工程取舍和踩坑过程。如果你也遇到过通用压缩库性能不够、压缩率调不上去、或者想理解 zstd / LZ4 这类库背后到底在忙什么，这篇文章应该能帮上忙。

这不是一篇泛泛的综述，而是我实际从空文件写到能跑压测的完整复盘，包含可参考的 C 代码片段、性能测试方法和一堆文档里不会写的细节。

1. 一场真实的压缩性能瓶颈：我为什么决定自己写压缩库

1.1 那个 CPU 被打满的下午

故事背景是这样一个系统：大量日志和结构化数据实时写入存储层，每条记录在落盘前都要压缩。最初用的通用压缩库默认配置，压测时发现压缩这一个环节就吃掉了将近 30% 的 CPU 时间。数据量一上去，服务整体吞吐就上不去了。当时团队里有人提议换更强的算法，但结果是压缩率上去了，CPU 开销更高；换更快的算法，CPU 下来了，磁盘空间却涨得飞快。这就像买东西只看价格不看质量，两头都不讨好。

我后来仔细看了性能剖析数据，发现真正的问题不是压缩算法选错了，而是通用库必须兼容各种输入、各种配置，内部做了太多通用性牺牲。它要考虑老 CPU、小内存、流式输入、文本二进制混合……这些兼容性全都要花 CPU 和内存。而我们场景里的数据模式其实非常固定，完全可以通过更针对性的实现拿到好几个百分点的性能提升。就在那一刻我决定：与其继续在通用库的参数空间里打转，不如直接写一个贴合自己场景的高性能压缩库实现。

1.2 压缩库设计里的"黄金三角"：速度、压缩率、内存

动手之前，我先梳理了一下压缩库设计时绕不开的三角约束：压缩速度、压缩率和内存占用。这三者永远在互相拉扯，你想压缩率高，就得更仔细地找重复、建更复杂的统计模型，计算量必然上去；你想速度快，就得牺牲搜索深度、用更简单的编码，压缩率自然下滑。

对于我现在的场景，我明确排序：解压速度第一，压缩率第二，内存占用第三。为什么解压速度优先？因为数据是写多读少，但读的时候要大批量回溯历史，解压慢会直接拖垮查询链路。这个排序直接决定了后面所有选型。因此我建议你在开始之前也先把这个三角排序想清楚，不然中途容易反复改架构。

2. 算法选型的第一步：LZ77、Huffman 与 ANS 怎么选

2.1 一切从 LZ77 滑动窗口开始

几乎所有现代压缩库的地基都是 LZ77，zlib、gzip、zstd、LZ4 全是它的变体。LZ77 的基本思想很简单：维护一个已经处理过的历史窗口，尝试从窗口里找到当前数据的最长匹配，如果能找到足够长的重复片段，就输出一个“距离 + 长度”的引用；找不到就直接输出原始字节。

这个消息的表述可以类比成：你在校对一本翻印稿，看见一句“从前有座山，山里有座庙”，发现前面三页刚出现过一模一样的句子，就没必要再抄一遍，写个“翻到第三页、重复 12 个字”就行了。这就是匹配器在做的事。理解这一点以后，再去看任意一款压缩库的核心代码，你就不会迷路，因为它们的骨架基本都是 LZ77 匹配引擎加后续编码。

2.2 LZ77 之上为什么要再接一层熵编码

如果只做 LZ77，输出流里会有大量距离、长度和字面量，这些数值的出现频率差异很大。比如距离值通常集中在很小的范围内，长度值也有偏向性。这时候用统计编码再压一遍，能把高频值用更短的 bit 表示，低频值用更长的 bit。常用的有 Huffman 和 ANS（非对称数字系统）。Huffman 是 deflate 的老搭档，实现简单、解压快；ANS 是 zstd 里 FSE 的基础，压缩率更高但编解码状态机更复杂。

2.3 我的选择：LZ77 匹配引擎 + 轻量熵编码起步

我并不建议第一次写压缩库就直接上 ANS。ANS 的状态转移逻辑很容易写错，而且一旦写错，压缩出来的数据解不开，排查成本非常高。我当时采用的分阶段策略是：

1. 先把 LZ77 匹配引擎写出来，输出“字面量 + 距离 + 长度”的中间格式，这个阶段先不做熵编码，保证链路能跑通。
2. 用 Huffman 对中间格式做一次熵编码，先获得一个能压缩的版本。
3. 等整个框架稳定之后，再把 Huffman 替换成 ANS，按需优化压缩率。

这个路线最核心的好处是每一步都有可验证的中间产物，出问题容易定位。我自己见过好几个朋友一上来就照着 zstd 抄 ANS，结果前两周全部耗在熵编码上，匹配引擎反而没写明白。记住：匹配引擎才是 LZ 类压缩库性能的主战场，熵编码是锦上添花。

3. 核心实现：哈希表、滑动窗口与匹配链的工程取舍

3.1 为什么匹配引擎决定整体性能下限

压缩库的整体性能基本上在上限上由匹配引擎决定。CPU 每秒能扫描多少数据、能找到多好的匹配，直接决定压缩吞吐和压缩率。而匹配器的本质是：快速回答“当前字节串之前在窗口里出现过吗？最长出现在哪？”这个问题。快速是关键，因为你每处理一个字节都要问一遍，窗口大小可能是 64KB、256KB 甚至更高，全扫一遍不现实，必须用索引结构把查找变成近似 O(1)。

3.2 哈希表设计：4 字节滑窗与桶大小

标准做法是对输入做哈希。常见策略是每次取当前四个字节（4-byte stride）计算哈希，用哈希值做下标查哈希表。为什么取四个字节？三个字节区分度不够高，冲突会很严重；五个字节以上计算量和内存都涨，收益不大。四个字节在性价比上正好。

我实现时用的是直接索引匹配，哈希函数选择了一个简单的乘法哈希，代码是这样：

static inline uint32_t hash4(const uint8_t *p) { uint32_t v = (uint32_t)p[0] | ((uint32_t)p[1] << 8) | ((uint32_t)p[2] << 16) | ((uint32_t)p[3] << 24); v *= 0x9E3779B1u; // 黄金比例哈希常数 return v >> (32 - HASH_BITS); }

HASH_BITS决定了哈希表大小，我选了 16，即 65536 个桶。每个桶里存的是“最近一个进入窗口且哈希值为 h 的位置”。这个数字不是随便定的，它和窗口大小有直接关系：窗口 64KB，每个位置都会在某个桶里占一个坑，桶太少则会频繁碰撞。

3.3 用链表还是用数组：内存布局的取舍

教科书会告诉你哈希表后面挂链表，每个桶里一串位置。但真正写高性能实现时，我不会用指针链表。内存分配散落各处，每一次链指针跳转都可能触发缓存未命中，对性能是致命的。我给每个哈希桶只保存一个“头的索引”，然后在窗口上维护一个数组prev[]，记录“从我这个位置往前数，上一个哈希值相同的位置”。这本质上是在数组上模拟链表，代码长这样：

// head: 哈希桶，存最近位置索引 // prev: 记录同一哈希链的前驱 uint32_t head[1 << HASH_BITS]; uint32_t prev[WINDOW_SIZE]; void insert(uint32_t pos, const uint8_t *p) { uint32_t h = hash4(p); prev[pos & WINDOW_MASK] = head[h]; head[h] = pos; }

这样整个索引结构就是三个连续数组，内存紧凑，访问一个位置时，大概率周围的prev也刚好在缓存里，性能好很多。

3.4 一次完整的匹配查找流程

有了索引，查找匹配的过程就清晰了：对当前四个字节算哈希，取到桶里的链头，然后沿着prev往前回溯若干个候选位置，逐一对候选位置做实际字节比对，找到最长的那一段。完整代码见下：

static int find_match(const uint8_t *src, const uint8_t *win_start, uint32_t cur_pos, uint32_t max_len, int depth, uint32_t *best_dist) { uint32_t h = hash4(src); uint32_t cand = head[h]; int best_len = 0; *best_dist = 0; while (cand != INVALID_POS && depth-- > 0) { uint32_t dist = cur_pos - cand; if (dist == 0 || dist > WINDOW_SIZE) break; const uint8_t *p = src; const uint8_t *q = win_start + cand; while (p < src + max_len && *p == *q) { p++; q++; } int len = (int)(p - src); if (len > best_len) { best_len = len; *best_dist = dist; if (len >= MAX_LEN_LIMIT) break; } cand = prev[cand & WINDOW_MASK]; } return best_len; }

这里面有几个细节值得展开。第一，max_len不能太大，因为输出编码里的长度字段是有限制的，超过了就得断开重来。第二，depth是搜索深度，控制最少回溯多少候选，depth 越小速度越快、压缩率越差，zlib 里对应的是最大匹配链长度。第三，prev的下标必须用窗口掩码规约，否则索引会一直涨导致数组越界。

这类代码的关键考量是：候选不一定要最多，而是要足够好。我的经验是把 depth 控制在 32~64 之间，够用又不慢，具体值按你的数据集微调。

4. SIMD 与缓存之道：高性能压缩库的底层加速手段

4.1 缓存友好：块大小与内存连续的底层逻辑

写完上面的匹配器，压缩已经能跑了，但性能距离理想状态差得远。我开始用工具看热点，最后发现大部分时间不在哈希计算，而在寻找匹配时的逐字节比较。逐字节比较的问题在于，每比较一个字节都要加载一次内存，等到发现匹配长度很长时，CPU 已经浪费了大量周期。

优化的第一步是简化候选位置的管理，第二步就是用 SIMD 一次比较更多字节。先说块大小。我把输入切成 64KB 一个块，每个块有一个独立的哈希表和窗口，让所有热数据尽量压在 L2 缓存里。64KB 不是拍脑袋定的，我的测试平台 L2 是 512KB，窗口 + 哈希表 + 中间缓冲加起来刚好能放进缓存，再大就会出现缓存颠簸，吞吐反而掉。

4.2 用 SIMD 把 16 字节的比对变成一条指令

逐字节循环里最核心的代码是*p == *q然后p++, q++，编译器一般会尝试自动向量化，但那种向量化效果不稳定。我改成显式 SIMD 后，单次可以并排比较 16 或 32 字节。以 SSE2 为例：

#include <immintrin.h> static inline int match_len_simd(const uint8_t *a, const uint8_t *b, int limit) { int len = 0; while (len + 16 <= limit) { __m128i va = _mm_loadu_si128((const __m128i *)(a + len)); __m128i vb = _mm_loadu_si128((const __m128i *)(b + len)); __m128i eq = _mm_cmpeq_epi8(va, vb); int mask = _mm_movemask_epi8(eq); if (mask != 0xFFFF) { int bits = (int)__builtin_ctz(~mask); // 第一个不同的位置 return len + bits; } len += 16; } while (len < limit && a[len] == b[len]) len++; return len; }

原理并不复杂：_mm_cmpeq_epi8把对应位置的字节比较结果放进一个 16 字节的向量里，每个字节要么是0xFF（相等）要么是0x00（不等），_mm_movemask_epi8把每个字节的最高位抽出来组成一个 16 位整数，这样一次就能判断 16 个字节是否全部相等，以及第一个不相等的位置在哪里。实测效果非常明显，匹配长度在 16 字节以下时，SIMD 版本和逐字节版本差不多；一旦匹配超过 32 字节，SIMD 版本能快接近一个数量级。

4.3 内存对齐、编译选项与指令集分派

写这类代码时，我习惯做三件事：

1. 对热循环里的关键数组做对齐：给哈希表和窗口数组加alignas(64)，避免跨缓存行访问带来的额外负载。
2. 编译期开启目标指令集：-O3 -march=native或者针对目标服务器明确启用-msse4.2、-mavx2，不要用默认的-O2，这个差别在压缩这种计算密集型代码里经常能达到两位数百分比。
3. 在运行时检测指令集做分派：如果程序要部署在多代 CPU 上，不能直接用-march=native编译出来的版本，否则老 CPU 会崩溃。我认为更好的做法是用__builtin_cpu_supports("avx2")之类接口做运行时判断，提供 SSE2 / AVX2 / 纯标量三个实现。

内存对齐还有一个容易忽略的点：SIMD 加载最好不要真的对齐到 16 字节边界，因为数据流的位置是任意的。所以我上面用的是_mm_loadu_si128（非对齐加载），它在绝大多数现代 CPU 上性能已经接近对齐加载，不值得为了对齐去复制数据。

5. 基准测试与瓶颈定位：数据会告诉你优化方向

5.1 建立一套可信的测试基准

优化如果没有可信的基准，基本等于盲人摸象。我最开始犯的错就是只用一个大文件测试，结果优化方向全被偏差带着跑了。后来我用了一组固定的混合数据集：

每组数据我都固定大小（比如 256MB），冷启动跑三次，取中位数。为什么取中位数而不是平均值？因为平均值容易被偶发抖动拉高，中位数更稳定。压缩库这种紧贴硬件的性能，很小的系统扰动都会带来百分之几的噪声，只跑一次的结果根本不可信。

5.2 三个关键指标与测试方法

我用的指标是压缩吞吐、解压吞吐、压缩率。压缩吞吐指每秒处理多少 MB 输入，解压吞吐指每秒解出多少 MB 原始数据。压缩率则是输出大小除以输入大小。这三者在测试时不能混在一起看，尤其是压缩吞吐，要包含哈希计算和匹配查找的全部时间，不能只测压缩核心函数。

测试解压吞吐时有个细节：解压往往比压缩简单，但它的瓶颈可能是分支预测失败和内存随机读。我在测试时特意用了压缩率差异很大的多组数据，观察解压速度是否稳定。如果数据一换，解压速度剧烈波动，说明实现里存在大量依赖数据的条件分支，这是需要重点优化的问题。

5.3 一次 perf 采样找到的隐形瓶颈

我自己的实现优化到一定程度后，吞吐一直卡在某个数值上不去。用perf record抓热点，发现热点既不在哈希表，也不在最内层的字节比较，而在我没注意到的函数。具体是怎么发现的？perf结果里五个热点函数中有一个是哈希计算函数本身，占用比例高得出奇。问题在于我每次查找都重复做了一次哈希，而插入时已经算过一次了，完全可以复用。把哈希计算改成“当前块的哈希值缓存”，每次滑动窗口只需要增量更新，热点立刻降下来。

那次改动给我一个很深的印象：性能瓶颈往往藏在“你没有意识到的重复劳动”里。因此我用两个建议概括这部分经验：一是周期性用perf看热点，不要靠猜；二是把所有“每次循环都重复计算的值”列出来，逐个问是否真的需要重复算。

6. 踩坑记录：哈希退化、边界处理与内存分配器的隐形代价

6.1 哈希桶退化：当输入全是相同字符时

第一个真正让我崩溃的问题，是处理特殊输入时性能突然暴跌。用连续相同的字节（比如 1MB 的全0）做测试，压缩吞吐掉到正常水平的十分之一。原因很清楚：所有位置算出来的哈希值都相同，所有位置都挤在同一个哈希桶里，prev链变成一条超长的顺序链表，查找匹配时深度失控。

解决方案不是在哈希函数上做文章，而是在匹配查找循环里加上主动退出条件：如果当前候选和当前位置的距离已经超过窗口限制，或者已经找到了长度足够长的匹配，就立刻停止继续回溯。此外我还加了一个“最小匹配长度”阈值，长度小于阈值就拒绝输出引用，避免为 3 个字节的重复付出大量哈希查找成本。经过处理后，这种极端输入的性能平稳了很多。

6.2 最后一公里的边界：压缩块末尾的数据怎么处理

LZ77 匹配到压缩块末尾时，很容易遇到“当前字节还能匹配上，但剩下的数据不够编码一个长度字段”的情况。我最初的处理是偷懒直接拷贝剩余数据，结果压缩率在短块场景下比预期差不少。后来改成：在临近块末尾时，如果匹配长度不足以完全覆盖剩余数据，就拆成“部分匹配 + 部分字面量”，并对长度字段做范围判断。

这里尤其注意编码和解码的边界必须完全一致，否则解压端会收到一个越界的长度引用，直接产生毁坏性错误。我在调试时专门写了一个模糊测试生成器，不断生成随机长度、随机内容的短块做压缩解压回环测试，才把这些边角问题一个不落地揪出来。

6.3 内存分配器的隐形代价：一次分配还是多次分配

我最早版本的实现里，每压缩一块就分配一次哈希表和临时缓冲，结果perf显示malloc相关开销占了总时间的一大部分。小块内存反复申请释放，不仅慢，还会造成内存碎片。后来改成初始化压缩器时一次性申请所有需要的缓冲空间，整个压缩过程不再发生任何动态内存分配，效果立竿见影，耗时下降了约 15%。

对压缩库这种频率很高的场景，我认为一条设计原则是：运行时分配器尽量只在初始化或者批量边界出现，热路径里严禁出现malloc/free。这也是很多工业级压缩库采用的模式，比如 zstd 提供ZSTD_compressCCtx就是为了复用上下文而不重新分配。

6.4 并行压缩的边界条件与收益曲线

最后提一下并行。多线程压缩看似简单，每个线程压缩一个块然后拼接结果即可，但直接拼接是不行的，因为压缩块与块之间可能存在引用关系，如果你不共享窗口，随便拼接会导致解压方无法定位。工业实现里要么维护独立的块上下文，要么在块的头部保存每次压缩的元信息，解压时按元信息解每个块。

我在实测中发现，并行收益并不是线性增长的。核数从 1 加到 8 时收益明显，但超过 8 之后受内存带宽限制，吞吐基本不再提升。所以我最后的建议是：不要盲目把线程数拉满，先测出你机器上的收益拐点，再用那个数做上限。

最后分享一点个人体会

经过这次从零实现，我最大的感受是：高性能压缩库的“高性能”往往不是某一个惊天动地的技巧，而是每个环节都不拖后腿。匹配引擎的索引结构要紧凑，字节比对要 SIMD，内存分配要提前规划，哈希退化要主动防御，边界条件要反复测试。任何一个环节掉了链子，整体性能都会被打回原形。

如果看完这篇你也想自己动手，我会建议你从 LZ77 加 Huffman 的组合开始，先跑通完整链路，再去碰 ANS 和并行。碰到性能瓶颈时，先测再做判断，千万别靠感觉调参。毕竟，压缩这种贴近硬件的活儿，数据会告诉你答案，只是你得先去听。