
ZLIB-TURBO: Zlib, faster, and byte for byte the same
zlib, faster, and byte for byte the same.
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
zlib, faster, and byte for byte the same.
zlib-turbo is zlib 1.3.2 with faster decompression and compression. It has the same API, the same ABI and the same headers (zlib.h is unchanged), and it produces the same compressed bytes as zlib for every input at every setting zlib has. It decompresses every stream, valid or damaged, with the same output and the same errors. You can put it in place of zlib in a program, a package or a whole system, and nothing else changes except the speed.
zlib-turbo also adds three optional features: multithreaded compression, with output still identical to zlib's; prepared dictionaries, which make compressing many small messages with a dictionary up to four times as fast (see below); and levels 10 to 12, which compress smaller than level 9 with an optimal parse (their output is valid deflate data but not zlib's, since no zlib level has it). Programs that do not use them see plain zlib. A build option adds SIMD checksums for x86 processors with AVX2, off by default.
zlib-turbo is more than known speedups applied to zlib. It contributes:
Speed without changing a byte, as a guarantee. Every change at levels 0 to 9 alters how zlib does its work, never what it decides: the same matches in the same order, the same blocks, the same bits, the same return codes. The guarantee is checked against unmodified zlib 1.3.2 rather than against expected outputs: three corpora, nearly 35,000 damaged streams, about 80 million differential fuzzing runs, six processor architectures and MSVC (see How it was tested). Faster zlib-compatible libraries give it up; zlib-turbo shows how much speed there is without giving it up: 66% to 86% in decompression and 4% to 39% in compression on one core, and up to 12 times as fast with threads.
Multithreaded compression whose output is zlib's. At levels 4 to 9 zlib's hash chains depend only on the input, so the matches its lazy parse will ask for can be found ahead of it. Each worker thread replays zlib's parse over its chunk of input, starting a little before it, so that it searches exactly the positions zlib will search, with the chain length zlib will use. The calling thread keeps every decision of zlib's parse and takes 99.99% of its searches from the workers, and finished blocks are written on workers only where zlib would write them too, so even the return codes and pending output match. With 16 threads, level 6 runs 6.8 times as fast as zlib 1.3.2 and level 9 up to 12 times, for the same bytes. We know of no other parallel deflate compressor whose output equals single-threaded zlib's: pigz, the usual parallel gzip, compresses separate pieces, so its bytes differ.
Levels 10 to 12: smaller than libdeflate's best, in zlib's own API. An optimal-parsing compressor written for zlib-turbo: a binary-tree match finder kept from segment to segment, a parse iterated over exact bit costs, block boundaries by dynamic programming, and the shortest coding of each block's trees. Level 12 is 0.15% to 0.33% smaller than libdeflate's level 12 on Silesia, enwik8 and Canterbury + Calgary, 4.0% to 5.7% smaller than zlib's level 9, and within 0.2% of Zopfli at 6 to 11 times its speed. Any program that can ask zlib for a level can ask for these.
Prepared dictionaries. zlib indexes a dictionary again for every stream. deflatePrepareDictionary() indexes it once, and deflateUseDictionary() copies the index into each stream, giving exactly the state, and so the output, that deflateSetDictionary() gives. Small messages compress up to 4.1 times as fast.
A faster decoder and faster checksums. A 64-bit fast loop with branch-free refills, larger first-level tables and wide match copies decompresses 66% to 86% faster, with zlib's results for every valid and damaged stream; it is offered back to zlib as pull request #793. A portable SWAR Adler-32, three multiplications per eight bytes, makes the zlib format's checksum 43% faster. An optional build adds SIMD checksums for x86, with the same results bit for bit: CRC-32 by carry-less multiplication, 5.5 times as fast, and Adler-32 with AVX2, 7.4 times. With them, gzip streams decompress 93% faster than with zlib 1.3.2.
Every number measured and reproducible. Each change's gain is measured on its own, the ideas that did not pay are listed with their measurements in turbo/TECHNIQUES.md, and the scripts in turbo/ repeat every comparison against any zlib source tree.
Faster zlib-compatible libraries exist; zlib-ng is the best known, and on one core it is faster than zlib-turbo. But they compress differently: the output is valid, yet not the bytes zlib would write. That breaks anything that hashes or compares compressed data:
zlib-turbo keeps those guarantees: every change speeds up how zlib does its work, never what it decides. The same matches are found in the same order, the same blocks are emitted, and the same bits are written.
Silesia, Canterbury + Calgary and enwik8 (the first 10^8 bytes of enwik9), each file whole; one core of an AMD EPYC 9334 (Zen 4, 2.7 GHz), GCC 14.2 -O2, best of two runs. MB/s of uncompressed data.
Compression (compressed bytes identical to zlib's in every case)
Decompression of zlib streams made by zlib at each level, in one inflate() call / in 16 KiB input and 64 KiB output pieces
Other compilers, Silesia level 6, compression / decompression in one call: GCC 11 +11% / +77%, clang 18 +12% / +62%. On 32-bit x86, where 64-bit arithmetic is emulated, +5% / +8%.
For context, zlib-ng 2.3.3 (compat mode, same machine and compiler) decompresses 15% to 20% faster than zlib-turbo, which reaches 82% to 86% of its speed without any SIMD code (the default build). zlib-ng compresses two to three times as fast, with different output; at level 1 its files are 18% to 22% larger than zlib's. All runs: turbo/results/speed_epyc9334.txt.
zlib-turbo is also in TurboBench, which measures it with zlib, zlib-ng, libdeflate and many other codecs on several platforms: see its benchmarks.
How each change works, why the output stays the same, what each one gains, and what was tried and dropped: turbo/TECHNIQUES.md.
Everything is portable C89 by default: no SIMD code, no assembly and no run-time CPU detection, so the same source builds wherever zlib builds, and compilers that target newer CPUs simply generate better code from it. The one exception is opt-in: SIMD checksums for x86, chosen at build time, below. Threads are POSIX threads, or Windows' own.
deflateSetThreads() puts worker threads on a stream. At levels 4 to 9 they search for matches ahead of the parse and write the finished blocks, and the compressed output is still zlib's, byte for byte, for any number of threads, any sizes of input and output per call, flushes, deflateParams() and dictionaries:
#include "zturbo.h"
deflateInit(&strm, 6); deflateSetThreads(&strm, 16); /* 0 or 1: back to one thread / / deflate() as usual */
Silesia / enwik8, MB/s 1 thread 4 threads 8 threads 16 threads 24 threads
Level 4 85.8 / 70.7 214 / 205 223 / 212 232 / 219 211 / 211
Level 6 35.8 / 27.1 126 / 103 202 / 190 218 / 210 198 / 206
Level 9 14.1 / 20.7 51 / 78 92 / 155 148 / 223 160 / 211
Each file compressed whole in one deflate() call, worker threads on one socket of a 2 × 32-core AMD EPYC 9334, GCC 14 -O2, best of two runs. zlib 1.3.2 itself does 31.9 / 24.4 MB/s at level 6 and 13.1 / 18.9 at level 9. With 16 threads that is 6.8 and 8.6 times zlib at level 6, and 11 to 12 times at level 9. The calling thread still chooses every match, in zlib's order, so the speed levels off near 220 MB/s; at level 9 on Silesia the workers are the limit. Levels 1 to 3, Z_HUFFMAN_ONLY and Z_RLE stay on one thread: their matches depend on the matches before them, so they cannot be found ahead with the same result.
Two rules come with the threads, both in zturbo.h. When deflate() returns with input left, the next call must be given the same bytes (they may be at another address), since the workers read ahead. The workers write a block only when the output space left for that call can take all of it, so give deflate() 256 KiB of output space or more per call for the speeds above. Each worker takes about 4 MB. All runs: turbo/results/threads_epyc9334.txt.
deflateSetDictionary() indexes its dictionary again for every stream, up to 32K hash insertions before the first byte of input. When many short messages are compressed with the same dictionary (HTTP or RPC payloads, log records, database rows), that indexing is most of the work. A prepared dictionary is indexed once and then shared, read-only, by any number of streams and threads:
#include "zturbo.h"
z_dict dict; deflatePrepareDictionary(&first, dictionary, dictionary_length, &dict); / on a just-initialized stream / ... deflateReset(&strm); deflateUseDictionary(&strm, dict); / same effect and output as deflateSetDictionary() */ ... deflateFreeDictionary(dict);
deflateUseDictionary() gives a stream exactly the state deflateSetDictionary() would: the same return value, total_in and Adler-32, and the same compressed output, byte for byte. On a stream it cannot copy into (other windowBits or memLevel, or not just initialized or reset), it calls deflateSetDictionary().
Time per message, each compressed as its own zlib stream with a 32 KiB dictionary; messages from enwik8, one core of an AMD EPYC 9334, GCC 14. JSON records from a DCLM-baseline shard give the same picture. All runs: turbo/results/dictionary_epyc9334.txt.
These functions are declared in zturbo.h, not zlib.h, and exported under their own version tag (ZLIB_TURBO_1.0), so programs built for zlib see no difference. zlibTurboVersion() tells a program that it is running with zlib-turbo; zlibVersion() still returns the zlib version it is based on.
Levels 10, 11 and 12 compress smaller than level 9, and smaller than libdeflate's level 12, at a few MB/s. They are a compressor of their own, so their output is not zlib's (no zlib level has it), but it is ordinary deflate data that every inflater decompresses, and it is the same for the same input, flushes and parameters, however the input is fed. Ask for them as for any level:
deflateInit2(&strm, 12, Z_DEFLATED, 15, 8, Z_DEFAULT_STRATEGY); /* or compress2(dest, &len, src, n, 12) */
Raw deflate bytes, MB/s Silesia enwik8 Canterbury + Calgary
zlib level 9 67,643,201 · 14.2 36,475,786 · 20.7 1,783,551 · 8.4
libdeflate 1.26 level 9 66,715,085 · 35.8 36,244,245 · 39.2 1,739,956 · 27.4
libdeflate 1.26 level 12 64,681,628 · 6.5 35,103,237 · 8.5 1,688,340 · 6.3
Zopfli 1.0.3 (15 iterations) 64,713,006 · 0.29 34,966,060 · 0.65 1,680,016 · 0.32
zlib-turbo level 10 64,681,882 · 5.5 35,016,775 · 5.6 1,687,697 · 5.5
zlib-turbo level 11 64,613,145 · 4.4 35,012,093 · 5.1 1,684,734 · 4.4
zlib-turbo level 12 64,584,749 · 3.2 35,007,174 · 3.9 1,682,786 · 3.1
Each file compressed whole on one core of an AMD EPYC 9334, GCC 14 -O2, best time of two runs. Level 12 is 0.15% to 0.33% smaller than libdeflate's level 12, at half its speed, and 4.0% to 5.7% smaller than level 9. Against Zopfli it is 0.2% smaller on Silesia and 0.1% to 0.2% larger on the others, at 6 to 11 times its speed. Level 10 is as small as libdeflate's level 12 on Silesia. All runs, per file: turbo/results/levels10-12_epyc9334.txt.
How they work: the input is parsed 256 KiB at a time, with the 32 KiB before it. A binary tree of the window's strings gives every match at every position; a parse that finds the cheapest path for given bit costs runs several times, first with the costs of a lazy parse's statistics, then with each block's own Huffman codes; block boundaries come from dynamic programming over an entropy estimate, and each block is written dynamic, fixed or stored, whichever is smallest. Details: turbo/TECHNIQUES.md.
They take about 24 MB per stream and keep up to 256 KiB of input before they compress it (a flush compresses what is there). A stream can change among levels 10 to 12 at any time, but between them and levels 0 to 9 onl
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。