京公网安备11010502063487号LZ4 和 Snappy 为什么那么快、又为什么压缩比低?这篇自己写解析器拆开它们的真实输出:格式里没有什么,字面量和序列的编码各占多少,窗口多大,小输入的开销多少。
b'abracadabra abracadabra abracadabra':原 35 字节 → block 20 字节 70 61 62 72 61 63 61 64 07 00 1e 20 0c 00 50 64 61 62 72 61;序列 [(7, 4, 7), (1, 18, 12), (5, None, None)](字面量长度, 匹配长度, 偏移);解回一致
b'{"id":1,"id":2,"id":3,"id":4}':原 29 字节 → block 25 字节 81 7b 22 69 64 22 3a 31 2c 07 00 12 32 07 00 90 33 2c 22 69 64 22 3a 34 7d;序列 [(8, 5, 7), (1, 6, 7), (9, None, None)](字面量长度, 匹配长度, 偏移);解回一致
products 1 MiB:block 338418 字节(压缩比 3.10×),60988 个序列;字面量共 142240 字节(占输入 13.6%),匹配共 906336 字节;平均每序列字面量 2.3 字节、匹配 14.9 字节;解回一致
匹配长度:最短 5、最长 79(LZ4 最小匹配 4 字节);偏移:最小 1、最大 65535(偏移占 2 字节,最大 65535)
block 里 token 与偏移等"元数据"的字节数:60988 个 token + 60987 × 2 字节偏移 + 扩展长度字节 = 196178 字节;其余 142240 字节是原样存放的字面量每个序列是 token(高 4 位字面量长度、低 4 位匹配长度减 4)、字面量、2 字节偏移。长度超过 15 时用扩展字节。全是字节对齐的操作,没有位流,没有 Huffman,解码就是复制。
b'abracadabra abracadabra abracadabra':原 35 字节 → 18 字节 23 18 61 62 72 61 63 61 64 01 07 00 20 01 05 4a 0c 00;头里的原始长度 35;元素 [('L', 7, 0), ('C1', 4, 7), ('L', 1, 0), ('C1', 4, 5), ('C2', 19, 12)];解回一致
b'{"id":1,"id":2,"id":3,"id":4}':原 29 字节 → 29 字节 1d 1c 7b 22 69 64 22 3a 31 2c 05 07 3c 32 2c 22 69 64 22 3a 33 2c 22 69 64 22 3a 34 7d;头里的原始长度 29;元素 [('L', 8, 0), ('C1', 5, 7), ('L', 16, 0)];解回一致
products 1 MiB:365498 字节(压缩比 2.87×),113510 个元素:{'L': 31585, 'C1': 14937, 'C2': 66988};字面量共 103018 字节(9.8%);复制的平均长度 11.5、最长 64(单个复制元素最长 64 字节);偏移最大 65043开头是原始长度,然后是字面量或复制元素,每个元素的 tag 低 2 位决定类型,单个复制元素最长 64 字节。也是字节对齐,没有熵编码。
LZ4 默认 :block 338418 字节,字面量 142240 字节;对字面量做 Huffman 估计 90050 字节,可省 52190 字节(15.4% 的 block);对照 zstd-3 198156 字节 LZ4 HC 级别 9 :block 244274 字节,字面量 43706 字节;对字面量做 Huffman 估计 27705 字节,可省 16001 字节(6.6% 的 block);对照 zstd-3 198156 字节 LZ4 HC 级别 12 :block 241190 字节,字面量 32973 字节;对字面量做 Huffman 估计 20969 字节,可省 12004 字节(5.0% 的 block);对照 zstd-3 198156 字节
两者的解码只有“读标签、复制字节”,没有构建码表、没有位操作:LZ4 解压约 4150 MiB/s(第 14 篇)。代价是压缩比:products 上 Snappy 2.87×、LZ4 3.10×,而 zstd-3 是 5.29×。
数据 snappy lz4 lz4 HC-9 zlib-6 zstd-3 zstd-19 products JSON Lines 2.87× 3.10× 4.29× 4.82× 5.29× 6.34× 类 HTML 页面 2.82× 2.93× 3.98× 4.54× 5.00× 5.62× timeseries JSON Lines 4.60× 4.23× 5.68× 8.75× 7.77× 15.75× 随机字节 1.00× 1.00× 1.00× 1.00× 1.00× 1.00×
LZ4 的 338418 字节里,字面量 142240 字节(Huffman 可省约 15%),元数据 196178 字节(58%)。zstd-3 比 LZ4 默认小 41%,既因为字面量有熵编码,也因为序列(字面量长度、匹配长度、偏移)本身也被熵编码。
pages 8 MiB:LZ4 最大偏移 65532(上限 65535);Snappy 最大偏移 65416,复制类型 {'C1': 60353, 'C2': 527033}
products 全部:LZ4 最大偏移 65535(上限 65535);Snappy 最大偏移 65487,复制类型 {'C1': 103255, 'C2': 459185}2 字节偏移意味着最多往回看 64 KiB,更远的重复找不到;实测 LZ4 和 Snappy 的最大偏移都没有超过 65535。
输入 lz4.block lz4.frame snappy raw zlib gzip zstd-3 空 1 11 1 8 20 9 1 字节 2 24 3 9 21 10 10 字节 11 33 12 18 30 19 100 字节 JSON 97 120 98 94 106 97 1000 字节 JSON 655 695 694 485 497 491
1000 字节的 JSON,snappy 压成 694 字节,zlib 485,zstd-3 491;lz4 frame 比 block 多 10–23 字节的帧头。很小的输入要攒批或者用字典(见第 17 篇)。