ctDeflate writes exactly the same .gz files as gzip from libdeflate 1.26,
byte for byte, and compresses a single file on all cores – up to 4.9 times as fast on
an 8-core CPU. libdeflate’s compressor is sequential by design: where a block ends
and how a position is encoded depend on everything before it. These eight pictures show
how, step by step, a single compressor became a task graph on ThinkMeta ConcurrentTasks that keeps every
core busy – and why each step was needed.
Picture 1 of 8
The reference: gzip from libdeflate
gzip from libdeflate maps the file into its address space (the operating system loads the parts it touches), compresses it in one call and builds the whole output in memory before writing it – all on one thread, one after another. Every stage depends
on what came before: where a block ends, how a position is encoded, at which
bit the next block starts. One core works, the others wait.
These bits are the yardstick: every following picture has
to write exactly the same .gz file, byte for byte – with any number
of threads and any chunk size.
Sequential three times over
Where a block ends depends on the symbol statistics since the block began.
The minimum match length (3 to 9) is chosen from the first 4 KiB
of each block and, at the lazy levels, recalculated as the parse goes
on. The same position is encoded differently depending on where its
block began.
Every block starts at the bit where the one before ended, and whether
a block is stored uncompressed depends on that bit offset.
The reference
gzip.exe from the official Windows build of libdeflate 1.26. On
enwik9, 1 GB of Wikipedia text, it manages 217, 106 and
61 MB/s at levels 1, 6 and 9, measured over the whole program
run.
Throughput · enwik9, level 9, whole program run
61 MB/s
Picture 2 of 8
The port: one compressor task between asynchronous reading and writing
libdeflate’s compressor is rebuilt in C++, from the matchfinder to
the bitstream, and runs as one task on the compute scheduler. Read and
Write become tasks of their own with overlapped I/O on an I/O scheduler.
Bounded windows lie between them: the compressor lets Read run at most
8 MiB ahead of the current block and releases the input behind its
32 KiB search window; Write writes every finished MiB and releases it.
The port is cut so that the match search can start at any position, as long
as it is given the complete state – every later picture needs that.
Reading and writing now run while the compressor works, not
before and after it. On enwik9 the port needs 17 MB instead of the
1,329 MB of gzip – memory no longer depends on the file size.
Over the whole program run it is as fast as the same port with the whole
file in memory, or up to 7 % faster, and bit-identical at every level.
Bit-identical first
Nothing was allowed to run in parallel before the port wrote the
same bytes as libdeflate: levels 0 to 9 over 23 real files of up
to 163 MB.
Every percent counts
Single-core speed is the base of every later factor. Measured in
memory on one thread, CRC-32 with carry-less multiplication,
prefetching in the matchfinders and aggressive inlining took the
port from 79–91 % to 90–107 % of libdeflate,
median about 95 %. The rest is the compiler: built with the
same compiler, libdeflate is not faster than the port.
Memory of the port
Peak memory: enwik9 (1 GB) at levels 1 / 6
17 / 17 MB instead of 1,354 / 1,329 MB with gzip; the
database file (163 MB) at level 6 21 instead of 191 MB.
Tried and dropped: one I/O thread
A write that extends the file runs synchronously in NTFS. With a
single I/O thread it held that thread and so blocked reading as
well; at level 1 up to 47 MB of finished output waited to be
written. With two I/O threads, Read and Write no longer block each
other.
Still in use today
This graph is still in the code: ctDeflate --sequential
runs it – the reference path every later picture is measured
against.
Peak memory · enwik9, level 6, gzip → port
1,329 → 17 MB
Picture 3 of 8
Search speculatively, resolve exactly
The input is cut into chunks of 1 MiB. For every chunk the match search runs in parallel, as if a block began at its start. A serial resolver then replays
libdeflate’s block logic in order: where a chunk’s search meets the true result, it takes it over; where none fits, it searches that stretch again exactly on its own (dashed).
The expensive work, the match search, depends almost only on the data and
now runs on every core. The state that makes libdeflate sequential is small
and can be replayed. On a binary database: 3.6 times as fast as libdeflate
at level 6, 8.2 times at level 9.
Taking over or re-parsing
Each chunk rebuilds the matchfinder from the 32 KiB before it.
Where its search reaches the same position with the same minimum match length as the true one, the two run identically from there
on, and the resolver takes the chunk’s work over. Only where no search fits does it search again – just that stretch.
Uncompressed blocks
Whether a block is stored uncompressed depends on the bit offset it
starts at. Such a block is marked and decided only when the blocks are assembled, with the real offset.
Four test files
Speed-up over libdeflate at levels 1 / 6 / 9, 16 threads, whole file in memory:
text log, 26 MB: 2.4× / 1.5× / 3.1×
source code, 12 MB: 2.0× / 0.9× / 1.7×
binary database, 163 MB: 2.3× / 3.6× / 8.2×
precompiled header, 77 MB: 2.2× / 2.6× / 6.8×
The weak spots: where the minimum match length differs from the
chunk’s guess, the resolver has to repair serially – on the
text log at level 6, 19 % of the file. And coding and assembly still run only after the resolver.
Throughput · database file, level 6, in memory
802 MB/s · 3.6× libdeflate
Picture 4 of 8
Several tracks in one search
The graph stays the same, but the match search is rebuilt from the inside: a chunk searches several tracks together – one per possible minimum match
length and a history track with its own block logic. The first search of
every step is the same for all tracks; they split only where the decision
for a match differs and merge again at a common starting point.
Repairs are serial – each one is time in which only one core works.
With several tracks the resolver nearly always finds one that fits: on the
text log, repairs drop from 4.9 MB to 21 KB. Source code at level
6 goes from 411 to 700 MB/s.
Exactly the same search
However the tracks split and merge, every search sees exactly the
matchfinder state libdeflate would see at that point. That is what
keeps every track bit-identical to the real search.
The price
With a single track the new search was about 20 % slower than
the old one, so the database file lost ground at first (level 6:
802 → 616 MB/s). Profile-guided work afterwards brought it
to 1,479 / 750 / 346 MB/s at levels 1 / 6 / 9.
Throughput · text log, level 6, in memory
420 → 630 MB/s
Picture 5 of 8
Coding and assembly run alongside
Match search and Huffman coding run in the same worker tasks, one per thread. A worker
first encodes the next block the resolver has released; otherwise it searches the next chunk. Whoever finishes encoding a block appends every block that
is ready in order – assembly needs no task of its own.
Before, encoding only started after the resolver: a second serial stretch
at the end that decided the run time at level 1. Now almost nothing is left
after the resolver – less than a millisecond on the database file.
Level 1 gets 13 to 24 % faster; at levels 6 and 9 the resolver and the match search set the limit.
Why coding comes first
Coding before searching keeps resolved blocks waiting only briefly, and assembly runs right where a block has just been finished.
No handover gets lost
Only one worker assembles at a time. When it is done, it checks once
more whether the next block has become ready in the meantime –
so no block waits for an assembly that never comes.
Throughput · database file, level 1, in memory
1,479 → 1,828 MB/s
Picture 6 of 8
A bounded window: memory no longer depends on the file size
Without a limit the searches run arbitrarily far ahead, and input and
search results grow with the file. Now chunks are searched at most a few
places ahead of the chunk the resolver is waiting for (by default the
number of threads plus 4), and Read only reads what that window can use.
Assembly releases input and search results behind the bitstream; Write
releases the output it has written. The block ring holds 4096 slots.
New are the bounded window and the releasing – reading and writing
alongside the compression have been there since the port. Memory now
depends on the chunks in flight, not on the file size.
A 5.2 GB file
Level 6 with 144 MB of memory in 7.3 s, against 28.8 s
for gzip (4.0×) – with the same output.
The input lands at its file position in a reserved address range;
memory is committed only for what the search window needs, so the
compression code stays unchanged. The output is written in 1 MiB
segments and released right after.
First whole-program measurement
Over the four test files (278 MB in all), measured over the whole
program run: 3.19× / 3.05× / 6.02× as fast as gzip at levels 1 / 6 /
9.
Peak memory · database file, level 6, 16 threads
246 → 84 MB
Picture 7 of 8
The resolver reports back
The tracks cost more than their extra searches explain, and on uniform data
they are almost never needed. Only the resolver knows whether they are
– so that knowledge flows back (dashed): after 8 chunks in a row
without a miss, new chunks search only the history track, with a faster search made for a single track. At the next miss the full choice is back.
The small search window makes sure the feedback arrives in time: only a few chunks are already searched when it changes. Repairs stay the same, and so do
the bits.
What a track costs
Database file, level 6, one thread: 89 MB/s with one track,
63 MB/s with three. The minimum match lengths of the last
blocks also feed into which tracks a chunk follows.
Tried and dropped
A large search window of 64 chunks was 6 % faster on the database
file (733 instead of 690 MB/s), but needed more than twice the
memory (197 instead of 84 MB) and delayed the feedback. The
default stays small. Choosing the tracks only from the values of the
last blocks caused many repairs on databases.
Throughput · database file, level 6, file to file
651 → 852 → 930 MB/s
Picture 8 of 8
The graph today
With 16 threads, 16 workers do the match search and Huffman coding on the
compute scheduler; Read and Write run on the I/O scheduler, as in the port.
The resolver stays on the calling task, which has a thread of its own beside
the workers. Assembly runs in the worker that finishes the next block.
Since the last rework Write is a task of its own beside the assembly
instead of writing from inside it – as fast as before or slightly
faster.
On enwik9, 1 GB of Wikipedia text, ctDeflate was 4.3 times as fast as
gzip at level 1 (217 → 928 MB/s), 3.7 times at level 6 (106
→ 392 MB/s) and 4.9 times at level 9 – measured before the
rework over the whole program run including reading and writing, every file
bit-identical.
Why fibers make the difference
The resolver waits in the middle of its loop for the next chunk search and, when the ring is full, for a free slot. A search waits for its input; Read and Write wait for overlapped I/O, Write also for finished output. On ThinkMeta ConcurrentTasks
such a wait suspends only the task; its thread meanwhile searches or codes, and every node stays a simple loop in order.
The rework measured
Whole program run, median of alternating pairs, against the state
before: 0.97–1.06 with 16 threads, 1.00–1.07 with 2
threads. Peak memory on enwik9 with 16 threads stays at
135–142 MB at level 6 and 129–136 MB at level 9;
at level 1 it rises from 98–109 to 135–165 MB. There
the output comes at more than 300 MB/s: before, writing inside the
assembly slowed down the whole pipeline; now Write runs alongside,
and up to 16 MiB of finished output may wait to be written.
Tried and dropped: the resolver as a scheduler task
As a task on the compute scheduler the resolver was as fast with 16
threads and up to 9 % slower with 2. On the calling task it has
a thread of its own and never waits for a free worker thread.
Many smaller files
On the Silesia corpus (12 files, 212 MB) ctDeflate was 2.4 /
2.2 / 3.6 times as fast as gzip at levels 1 / 6 / 9. Small files
have fewer chunks than the CPU has threads, and program start and
I/O weigh more. Measured before the rework.
Other CPUs
Published measurements, before the rework, levels 1 / 6 / 9:
