Zstandard encoder

What the encoder does where the format leaves a choice. Compressed bytes depend only on the input and the options, so a later port that follows this text and the format (RFC 8878) writes the same bytes. Source: src/OneCompress/Zstd/.

Layers

A match finder turns a window into sequences with real offsets; the block writer decides which of them are written as repeat codes (RFC 8878 section 3.1.1.5), updates the repeat offsets, and chooses the entropy modes. A finder is given the offsets in force at the start of each block so it can look for cheap matches. A block stored raw or as RLE leaves the offsets and the carried tables untouched, as the decoder sees it. A frame writer can take blocks from any source between a header and a checksum.

Levels

Level numbers and meanings follow the zstd command line tool. Level 0 means 3. Levels 1 to 22 and every negative level down to -131072 are implemented; the negative level is the acceleration (the fast strategy's target length). Higher levels throw ArgumentOutOfRangeException. Levels 20 to 22 are the tool's ultra levels: their windows reach 128 MiB (window log 27), so a decoder has to allow that window (ZstdDecompressionOptions.MaxWindowSize defaults to 8 MiB; zstd -d allows 128 MiB without a flag).

Parameters are looked up by the source size class, then shrunk to what the source can use. The size used is the content size plus the dictionary's content size; it is unknown for a streaming encoder that was not told the content size, and then the largest class applies.

Levels 10 to 12 above 256 KiB search one step less deep than the tool. The search log is 4, 5 and 5 where the tool's is 5, 6 and 6 (every other value is the tool's). The row search spends most of its time on candidates that fail the longer-match check, so its time is close to proportional to the candidates visited. On silesia.tar the sizes are +0.55%, +0.32% and +0.32% against the tool at levels 10, 11 and 12, and on enwik8 -0.2% to +0.2%. Level 10 now has 16-entry rows, which take the insert stride (see Match finders). Sizes fall and times rise from level 10 to 12 (11.66, 11.58 and 11.57 MB on the first 32 MiB of silesia.tar).

The strategies above btlazy2 (btopt, btultra, btultra2) take levels 13 to 15 of the 256 KiB and 128 KiB classes, 11 to 15 of the 16 KiB class and levels 16 to 22 of every class; they are the optimal parsers described below.

The values were read off the reference tool's own report (zstd --show-default-cparams) for sources of the class boundary sizes; they are measured behaviour, not copied code. Shrinking: windowLog = min(table, max(10, ceil(log2(size)))) when the size is known, hashLog = min(hashLog, windowLog + 1), chainLog = min(chainLog, windowLog) (windowLog + 1 for the binary-tree strategies, whose table holds two links per position). For negative levels the target length (acceleration) is -level. ZstdCompressionOptions.WindowLog replaces the window log (and tightens the other two logs).

Literals of negative levels are stored raw (the Huffman pass costs more time than it is worth at those speeds). This is part of the level definition, ZstdCompressionParameters.CompressLiterals.

Match finders (greedy, lazy, lazy2, btlazy2)

One finder, ZstdLazyMatchFinder, implements the four strategies. They differ in the search structure (rows of tagged entries or a binary tree) and in how far the parse looks ahead.

• Index: every position with eight bytes after it inside the block is entered, in order, by the search that reaches it (positions skipped over by a match or a step are entered first). The hash is the fast finder's: the low minMatch bytes of an 8-byte read, multiplied by 0x9E3779B185EBCA87, top hashLog bits. Tables hold window positions as uint with 0 for empty; the first byte of a window is never a candidate. A stream that slides its window rebases positions and, for the binary tree (indexed by position modulo its size), turns it around by the slide distance. Blocks continue each other: the last seven positions of a block are entered by the first search of the next one.
• Rows (greedy, lazy, lazy2; chainLog is not used by the frame's own table): the table holds 2^hashLog entries in rows of 2^rowLog entries, rowLog = clamp(searchLog, 4, 6) (16, 32 or 64), 2^(hashLog - rowLog) rows (at least 2). The 64-bit hash picks the row with its top bits and a tag byte with the next 8. Each row is a ring: a new entry (tag and position) goes just below the row's head, which then moves to it, so walking from the head visits entries newest first. A search takes the entries whose tag equals its own, newest first, and stops at the first one that is empty or farther back than the window size; it visits at most min(2^searchLog, 2^rowLog) of them. Only the tags are compared before the match is looked at. A visited candidate is skipped without measuring when its four bytes ending at the current best length differ from the same bytes at the current position (a longer match must agree on them); otherwise the match length is measured and the candidate becomes the best if its gain is higher. With the current best shorter than minMatch - 1 the skip test looks at the single byte at index minMatch - 1 instead (minMatch 3 only).
• Insert stride (rows with rowLog 4, no dictionary, minMatch at least 4, hashLog at least 19): positions skipped over by a match are entered into their rows lazily by the next search (see Index). When more than 16 positions lie between the last one entered and the position being searched, they are entered every 4th position (the first of them, then every fourth), and the last 16 are all entered. A long match usually repeats text whose positions are already in the table, and each entered position is a write to a row far from the cache. Entering every fourth loses almost no match, because the parse extends a match backwards over equal bytes. This is a rule of the output bytes: it applies at levels 5 to 9 for sources over 256 KiB (hashLog 19 to 21) and at levels 6 to 8 for sources of 128 KiB to 256 KiB when their hashLog reaches 19. On silesia.tar it costs 0.04% to 0.17% in size.
• Binary tree (btlazy2): 2^(chainLog-1) nodes, two links each (smaller and larger), one tree per hash value rooted at head[hash]. Entering a position compares it against nodes from the root down, splitting them into those below and those above it (the standard suffix-tree-like insertion of binary-tree match finders); the comparisons give every match met, in increasing length, with at most 2^searchLog nodes visited. Comparison length is capped at 256 (the nice length): a node that matches that far is replaced by the new one, which takes its children. A node entered with fewer than 256 bytes left in its block was ordered by fewer bytes, so the shortcut that starts a comparison at the shorter of the two bounding prefix lengths is not used on it, and the bounds are forgotten after it. The search then extends the best match past the cap.
• Gain: a match of length L at offset d has gain 4 L - floor(log2 d); a repeat-offset match has 4 L - 1. The search keeps the candidate of highest gain (earliest on ties). Repeat offsets are tried before the table: with a literal in front, the three repeat offsets; with none, the second, the third and the first minus one (the cases RFC 8878 section 3.1.1.5 gives codes 1 to 3 to). A repeat match needs 4 equal bytes.
• Parse: greedy takes the best match at the current position, after also trying the first repeat offset one byte further on, which wins if its gain is higher. Lazy (lazy2) takes the best match at ip, then looks at ip + 1 (ip + 2): a later match replaces it when its gain is higher by more than 4 (7 for two positions on), and the check restarts from the new position. A match of 128 bytes or more is not looked past. The match is extended backwards over equal bytes down to the last match end, emitted, and the search resumes at its end. With nothing found the position advances by 1 + (ip - anchor) / 256.
• With a dictionary: the frame's own candidates are visited first; a search that has attempts left continues along the dictionary's hash chains (built once per dictionary and parameter set, for every position with 8 bytes after it, sized by DictionaryHashLog and DictionaryChainLog when set). The dictionary's candidates count only while the bytes produced do not exceed the window size, and the binary-tree strategy searches the dictionary through chains, not a tree. Repeat offsets that reach before the frame's first byte are tried against the dictionary content.

Optimal parsing (btopt, btultra, btultra2)

ZstdOptimalMatchFinder implements the three strategies. They differ only in the parameters of their rows (search depth, target length, minimum match) and in two details: btopt skips searching a position whose successor is already reachable at nearly the same price, and btultra2 parses the first block of a frame twice.

• Tree: the binary tree of btlazy2 (one tree per hash of minMatch bytes, 2^(chainLog-1) nodes, every position entered once, in order), compared up to 1024 bytes (the tree's "long enough"), at most 2^searchLog nodes per search. The matches met on the way down, each longer than the one before, are the candidates; with a dictionary, the dictionary's hash chains add candidates longer than the tree's best. The chain walk has its own budget of 16 times the level's attempts (the frame's tree does not use it up): the dictionary has no tree, and its best match is often far down a chain. The three repeat offsets (with a literal in front; with none, the second, the third and the first minus one, RFC 8878 section 3.1.1.5) are candidates too, from four bytes (three when minMatch is 3). A candidate that reaches the target length ends the stretch at once: the longest candidate is measured to its end and taken.
• Prices: in 1/256 bit. A symbol costs log2(total) - log2(count) (counts below 1 are 1; log2 is the integer table of ZstdCost), plus its extra bits. Four count sets: literals (256), literal length codes (36), match length codes (53) and offset codes (32; the offset value's base-2 logarithm, so the repeat codes 1 to 3 are codes 0 and 1). Counts of the first block start from the block's literal histogram and the predefined distributions (a distribution entry of -1 counts 1); with a dictionary in the Zstandard format they start from the dictionary's tables instead, since the first block can be coded with them: a literal counts 2^(maxBits - codeLength) (1 if it has no code) and a sequence symbol its normalized count (1 for -1 and 0). Prices are rebuilt from the statistics alone at the start of each block, and again every 4096 bytes parsed (half the statistics at the block start plus the counts of this block so far). When a block finishes, its counts are added to half the old statistics. A match of length 3 costs two bits more than its symbols.
• Path search: from the start of a stretch (the first position with a candidate, with the literals since the last match pending) a cell per following position records the cheapest known price of reaching it, whether a literal or a match got there, the match's length, offset, starting cell and literals before it, and the repeat offsets after that path. The price of a cell includes the code of the literal run pending at it, so a literal extends a cell by its own price plus the difference between the run's code prices, and a match adds its offset, length and (for the next run) zero-length literal code prices. Cell by cell: the literal transition is applied (ties go to the literal), the cell's repeat offsets are derived from its path, candidates at the position are found (using that path's repeat offsets) and every length from the candidate's first new length to its length relaxes the cell it reaches. Offsets that equal a repeat offset of the path are priced as repeat codes (the same resolution the block writer uses). The stretch ends when the cell reached is the farthest any match got to; the cheapest path there is written out and the literals at its end stay pending, so a stretch is never forced to end with a match that costs more than literals. A stretch is at most 4096 positions; a candidate that would pass that, or that reaches the target length, is taken as the stretch's last match.
• btultra2: the first block of a frame is parsed once with the starting prices, the counts of that parse become the statistics, the tree is emptied, and the block is parsed again. (Blocks after the first use the statistics of the blocks before them.)
• Window sliding: as for btlazy2: stored positions are rebased, the tree is turned around by the distance moved.

Block splitting

Blocks of the optimal strategies are cut again after parsing. ZstdBlockSplitter groups the block's sequences into chunks of about 4096 input bytes and estimates the cost of coding a run of chunks as one block: the entropy of its literals, literal length codes, match length codes and offset codes (integer, from the counts), plus the extra bits, plus an allowance for the headers and table descriptions of 12 + distinct literals / 2 + 3/4 * (distinct codes of the three sequence alphabets) bytes (a literal alphabet is not counted when raw literals are cheaper). A shortest-path search over the chunk boundaries (at most 32 blocks per 128 KiB) picks the cuts of least total cost. Each part is written as a block of its own with its own tables; repeat offsets run on from part to part exactly as the decoder sees them. Because every part may cost three header bytes more than the single block would have, the bound of GetMaxCompressedLength allows 32 parts per 128 KiB.

Frames

• Content size is written when it is known (one-shot calls, or ContentSize for a stream) unless WriteContentSize is false.
• A frame with a known content size no larger than the window is single-segment: no window descriptor, the content size is the window. Content size field: 1 byte below 256 (single-segment only), 2 bytes (value minus 256) below 65,792, 4 bytes up to 2^32-1, else 8.
• The dictionary ID is written when the dictionary has one and WriteDictionaryId is true, in the fewest of 1, 2, 4 bytes.
• The checksum (Checksum, default false) is the low 32 bits of XXH64 of the content.
• Empty input: header plus one empty raw last block.
• Blocks are cut every 128 KiB of input. A one-shot call and a stream with the same content size make the same bytes however the input is split across calls; Flush ends a block early (and so changes the bytes). A stream without a content size uses the largest class and writes no content size, whether or not its first call happened to carry the whole input.

Blocks

• A block whose bytes are all equal (two or more) is an RLE block. Otherwise the block is compressed, and stored raw when the compressed body would not be smaller than the block.
• Literals section: fewer than 8 literals, or raw literals mode, are stored raw; one distinct byte value is RLE. Otherwise the smallest of raw, a new Huffman tree, and the previous tree (treeless) is written, by exact size. One stream below 256 literals, four streams from 256. A tree description uses 4-bit weights or FSE-compressed weights, whichever is smaller; the compressed form is read back with the decoder's own routine and dropped for the direct form if it does not decode to the same weights. Codes are limited to 11 bits: the Huffman tree is built by a two-queue merge, and too-long codes are shortened by lengthening the least frequent of the longest codes until the Kraft sum fits, then spare code space is given back to the most frequent symbols.
• Skipping work that cannot pay (small blocks): a new Huffman tree is built only when the literals number at least 64 and an estimate of its size (the entropy of the literals, rounded down by the integer logarithm's error, plus 8 + 3/8 bytes per distinct symbol for the description) is below both the raw size and the cost of the previous tree. A new FSE table is tried only when the block has at least 64 sequences and the entropy of its codes plus 16 bits is below the cost of the best of repeat and predefined; with neither available a table is always built. The estimates are integers; they decide bytes, so they are part of the format of our output. At the fast and double-fast strategies, a block whose previous tree can code its literals (the dictionary's, or the last block's) tries a new tree only from 128 literals; below that the saving never repaid the description in the measurements behind this rule.
• Sequences section: for each of literal lengths, offsets and match lengths the cheapest of RLE (one symbol), repeat (the previous table from the frame or the dictionary), predefined and a new FSE table is chosen. Cost is in 1/256 bit, integer: blocks with at most 1,500 sequences price each choice by running the encoder's state machine over the symbols (the table description's bytes included); larger blocks, and every block at the fast and double-fast strategies (levels up to 4 and the negative levels), use the histogram estimate count * (accuracyLog - log2(probability)). log2 is a table built with integer arithmetic. After an RLE or predefined block the repeat mode is not offered (the next block offers a new table or the predefined one at the same cost).
• Normalization: symbols that occur get at least one state; symbols with at most total >> accuracyLog occurrences get the "less than one" probability; the rest are scaled with rounding, then states are removed from or given to the symbols that lose or gain the fewest bits (ties: lower symbol first).
• Accuracy log of a new FSE table, from the number of symbols coded (sampleLog = floor(log2(count - 1))): start from min(maxLog, sampleLog - 2), raise it to at least min(sampleLog + 1, floor(log2(maxSymbol)) + 2), and clamp to 5 up to maxLog. maxLog is 9 for literal and match lengths, 8 for offsets, 6 for Huffman weights. These values were fitted to the reference tool's table sizes by black-box comparison, not derived from a specification.

Match finders (fast, double fast)

• Hash: the low minMatch bytes of an 8-byte little-endian read, shifted up, multiplied by 0x9E3779B185EBCA87, top log bits. The double-fast long table hashes 8 bytes. Tables hold window positions as uint; an empty slot reads as position 0, which is checked like any other candidate. Candidates must be within the window size; the candidate is accepted when its first 4 bytes (double fast long: 8) equal the current bytes.
• Fast: each round hashes two neighbouring positions, ip and ip + 1, writes both into the table, and tests (in this order) the first repeat offset at ip + step, the candidate of ip, the candidate of ip + 1. With no match, ip += step. The step starts at targetLength + 1 (2 when the target length is 0) and grows by one each 128 bytes since the last match. A match is extended backward over equal bytes (not before the last match end) and forward. After a match two positions are indexed (the match start + 2 and the position 2 before its end) and the second repeat offset is tried repeatedly at the end of each match.
• Double fast: one position per round, ip += 1 + (ip - anchor) / 256. Tests the first repeat offset at ip + 1, the long candidate, the short candidate (then also the long candidate at ip + 1, which wins if it matches 8 bytes). Both tables are filled at the same positions after a match.
• With a dictionary: the dictionary content sits logically right before the first byte. A match into it has offset bytes produced + dictionary length - position in dictionary, and is allowed while the bytes produced so far do not exceed the window size (RFC 8878 section 3.1.1.1.2). Repeat offsets that reach before the frame start are tried against the dictionary. A match in the dictionary may run on into the start of the frame. The dictionary's search tables are built once per (minimum match, hash log, chain log, strategy) with an entry for every position (a later position replaces an earlier one with the same hash). With a dictionary and the fast strategy, one position is tried per round (repeat at ip + 1, own table, dictionary table).
• Tables of a small source with a dictionary: the window log, minimum match and strategy come from the size class of source plus dictionary, but the hash and chain tables a frame fills are sized for the source alone (min(table, sourceWindowLog + 1), and sourceWindowLog for the chain), so a 100-byte payload does not clear 100 KiB of table. The dictionary's own search index keeps the sizes its length calls for (DictionaryHashLog, DictionaryChainLog in the parameters).
• Window sliding (streams): the window buffer keeps the last windowSize + 1 bytes; stored positions are rebased by the amount moved and those that fall below become 0. Matches never reach past the window size, so a stream and a one-shot call find the same matches.

Dictionaries

ZstdCompressionDictionary.Parse accepts the Zstandard dictionary format (entropy tables read back into encoder tables, repeat offsets, content) and, for anything else, raw content (8 bytes or more; ID 0 unless given). The Huffman tree, the three FSE tables and the repeat offsets start the frame's carried state, so the first block can use repeat modes and treeless literals.

A dictionary builds search tables over its content for each set of match-finder parameters it is used with (level, size class and window change them). It keeps at most 128 MiB of such tables; the least recently used sets are dropped and rebuilt on demand, which costs time but never changes the output. A long-lived dictionary used at many settings therefore stays bounded in memory.

The fast and double-fast strategies search a dictionary through its index (every content position, the latest of each hash). For content under 16 MiB each index entry holds the position in its low 24 bits and, in its top 8 bits, a tag: the top byte of bytes * 0x9E3779B1 (32-bit, wrapping) for the four bytes at that position. A search compares the tag of the four bytes at the current position before it reads the dictionary content, so a slot that holds other bytes costs no second memory access. A tag is a function of the four bytes a match must share, so it never rejects a match the untagged search would take: the output is the same with or without it. Content of 16 MiB and more has untagged entries.

Windows

WindowLog (10 to 31) replaces the level's window log. The header states it; matches never reach back further than 2^30 bytes, which is the most a window buffer can hold, so 31 is a declaration only (zstd -d --long=31 or --memory is needed to decode it). A log below 17 asked for explicitly is written as 17 in the header, because a block (128 KiB) may not exceed the window (RFC 8878 section 3.1.1.2.3); matching keeps to the smaller window. A frame whose content size is known and fits the window is single-segment and needs no window descriptor.

What a decoder accepts: this library's ZstdDecompressionOptions.MaxWindowSize defaults to 8 MiB and is raised by the caller (it plays the part of zstd -d --long=N and --memory); it holds up to two windows, so it refuses windows of 2^30 and above. The zstd command line decodes up to 2^27 by default.

Memory

What an encoder holds depends on the parameters and on whether it is told the size.

• Known size (one call, or ContentSize): the window and tables are sized to the source as the parameter table above says, and allocated whole when the frame starts.
• Unknown size (a stream without ContentSize): the parameters are those of the largest size class, as zstd itself uses for a pipe, so the output is the same as before. What the encoder allocates is not: the window buffer and the binary-tree link table of btopt, btultra and btultra2 start small (1 MiB; 65,536 positions) and are enlarged as data arrives, to four times their size, or to the whole once a quarter of it is needed. A node of the link table lives at the slot of its position modulo the full table size; below the current size that slot is the position itself, so enlarging moves nothing and cannot change a match. Where the window slides depends on the full capacity, never on how much is allocated. The hash tables are indexed by hash and are allocated whole (up to 128 MiB at level 22), as are the chain tables of the other strategies (up to 16 MiB at level 12).
• SizeHint: for a stream whose length is only roughly known. The window and tables are chosen as for a source of that size and allocated whole; the header states no content size, and its window log is at least 17 (a block may not exceed the window, RFC 8878 section 3.1.1.2.3) while matching keeps to the smaller window. Input beyond the hint is still compressed correctly, with that smaller window. ContentSize, when given, wins.
• Dictionary search index: the index a dictionary builds for a parameter set holds one entry per content position, so its tables are capped by the content, not by the source: the chain index at ceil(log2(content length)) (at least 10), which keeps every position and so cannot change a match, and the hash tables at four bits more (sixteen slots per position). A 4 KiB dictionary at level 22 used to build 256 MiB of index for a large source and now builds under 1 MiB.
• Sliding the tree-link table is done in place (reverse the two parts, then the whole) rather than through a copy of the table.

Peak memory (measured when these allocation changes were made), one process per row, managed bytes allocated and peak working set in MiB, before and after, for generated text (GC.GetTotalAllocatedBytes and Process.PeakWorkingSet64; levels 1 and 3 did not change). Each cell is the no-dictionary row / the row with a 4 KiB dictionary.

The compressed bytes of all 90 rows are unchanged.

Long-distance matching

LongDistanceMatching is zstd --long: with it on and no WindowLog, the window is 2^27 (smaller when the content size is known to be smaller: the log of the size, at least 10). A second matcher finds long repeats anywhere in the window; the level's own match finder parses the rest, whatever its strategy. The matcher is ZstdLongDistanceMatcher and the glue is ZstdLongSequencer, both public.

• Anchoring. A gear hash runs over every byte: h = (h << 1) + G[byte], with 256 constants from the SplitMix64 sequence seeded with 0x2545F4914F6CDD1D (each step adds 0x9E3779B97F4A7C15, then z = (z ^ z >> 30) * 0xBF58476D1CE4E5B9, `z = (z ^ z >> 27) * 0x94D049BB133111EB,G = z ^ z >> 31). The hash after bytejcovers bytesj-63toj; positioni = j - 63` is a checkpoint when the top HashRateLog bits of the hash are zero (content-defined sampling, so both copies of a repeat are anchored at the same place).
• Table. 2^HashLog entries of 8 bytes in buckets of 2^BucketSizeLog: check << 32 | (position + 1), newest first, the oldest falls out. With mixed = (h ^ h >> 29) * 0xBF58476D1CE4E5B9, the bucket is the top HashLog - BucketSizeLog bits of mixed and the check is its low 32 bits. Defaults: HashLog = clamp(min(windowLog, sizeLog) - 7, 6, 24), BucketSizeLog = 2, HashRateLog = clamp(min(windowLog, sizeLog) - HashLog, 1, 24), MinMatch = 64 (16 to 4096), where sizeLog is the log of the content size when it is known.
• Search. At a checkpoint at or after the end of the previous long match and the block start, each bucket entry with the same check and a distance of at most the window is verified byte by byte, extended forward to the block end and backward to the previous match end or block start; the longest wins, the newest on a tie, and it is taken when at least MinMatch long. Then the checkpoint is stored. Positions scanned inside a match are stored but not searched from. The dictionary content is not indexed.
• Blocks. Long matches are found per 128 KiB block (matches stay inside a block). In a block, each long match becomes a sequence; the match finder parses the stretches between them, told the repeat offsets that follow from what came before, and the last 256 bytes of a long match are added to its tables so that what follows can refer back into it. Hash tables hold position and check only, never pointers, so the matches do not depend on the platform.
• Sliding the stream's window buffer drops entries older than the window and changes nothing else: a stream and a one-shot call make the same matches.

Jobs and threads

JobSize (bytes, 0 = off) cuts the input into jobs; Workers (0 = one per processor, default 1) is how many are compressed at once. The bytes depend on the job size, the overlap and the other options, never on Workers, the processor count, the platform or the order in which jobs finish; a browser runs the jobs one after another. With JobSize 0 there is one job and Workers is ignored.

• Job size. AutoJobSize (-1) is max(1 MiB, 4 * min(windowSize, 4 MiB)). Any size is rounded up to a multiple of 128 KiB (so the jobs add no blocks of their own and GetMaxCompressedLength holds) and capped at 1 GiB. Job k covers input bytes k * size to (k + 1) * size. An input no longer than one job is compressed exactly as without jobs.
• Overlap. The bytes before a job are history for matching. OverlapSize (default min(windowSize / 8, 1 MiB), at most the window) of them are added to the match finder's tables when the job starts (ZstdMatchFinder.Prime: every position of the overlap, hashed as during parsing); with long-distance matching the whole window before the job can be matched into, found by the one long-distance matcher, which sees the whole input in order whichever thread runs which job (jobs take their turn at it in job order, then compress in parallel).
• Job frames. The header and checksum are written once. The jobs' blocks follow one another; every job writes its own blocks from fresh tables: its first block uses no table of the previous job and no repeat offset code until it has coded three offsets of its own (the decoder's offsets come from the end of the previous job; ZstdBlockWriter.ForgetRepeatOffsets makes the writer assume three offsets above any real one). Only the job that starts the frame uses the dictionary. The last block of the last job is the frame's last block.
• Streaming. ZstdEncoder.Compress buffers the window (or overlap) behind the next batch of Workers jobs and compresses a batch when more input than a batch has arrived, or at the end; the bytes do not depend on how the input is split across calls. Memory is the window plus Workers * JobSize plus the batch's output. Flush compresses what is buffered as a short job and ends it (and so changes the bytes). Each new job loads its overlap into the match finder again, so flushing after every few bytes costs time that grows with the square of the stream length (about 3.7 s for 80 KB written one byte per flush). Writers that flush often should leave jobs off.

Measuring

• Ratio: compressed bytes of the whole file in one frame, no checksum, against zstd -N --no-check (negative levels --fast=N), on the same machine.
• Speed: zstd -b<level> in-memory modes against tools/zstd-encode-bench (big): both warm, memory to memory, single thread, best of several seconds. Decompression compares our decoder on our frame with the tool decoding its own frame.
• Peak memory: /usr/bin/time -v on both sides.
• Game snapshot data: tools/zstd-encode-bench/game.sh trains with zstd --train on seed 1 and compresses seed 2 one frame per payload.

Results (zstd 1.5.7, one thread, memory to memory)

The tables in this section and the next are dated measurements; each says which build or levels it covers. They are not kept current level by level. The size bar (+1%) is met except where a table says otherwise; the known misses are enwik8 level 22 (+1.16%) and the long-distance and dictionary rows noted below.

Method as above (tools/zstd-encode-bench/run.sh, game.sh --timing); time ratio is our time divided by the tool's, so the bar is 1.15. Sizes are identical on both machines (the output does not depend on the processor). x64: Ryzen 9 7950X3D, 32 cores, .NET 10.0.402, load 10 to 12 from other work on the machine; arm64: Apple M2, 8 cores, load 2 to 4.

These are the first full measurement of levels -5 to 4. Sizes were within the 1% bar at those levels; compression speed was not (1.26 to 1.74 times the tool's time). Levels 1 to 9 have since been retuned (faster search loops, a sparser insert at levels 5 to 9), so the time ratios and the split below are superseded; the current rows are in the README, and sizes are unchanged at levels -5 to 4. Where the time went at level 1 on silesia.tar (per 212 MB pass, x64): match finding about 290 ms, literals about 90 ms, sequence coding about 115 ms; the sequence coding took twice that before its loop was split out and its state kept in registers. Dynamic profile guidance in the JIT matters: without it the search loop is 30% slower.

Game payloads with trained dictionaries (seed 2, one frame per payload, our size and payloads per second against the tool's; geometric means over three games, levels 1 to 3): frames (tens of bytes) are 1.0 to 1.4 times the tool's rate on x64 and 1.0 to 1.2 on arm64 with sizes 0.2 to 1.1% smaller; snapshots and saves (hundreds of bytes to 6 KB) run at 0.32 to 0.42 times the tool's rate with sizes 2 to 10% smaller.

The unchecked accessors (Raw) are worth 5 to 7% of the encoder's speed: the same code built in the Checked configuration (every accessor bounds-checked) runs at 564/598 (level -5), 400/430 (level 1) and 259/273 MB/s (level 3), match finding 10% slower and block writing level.

Block writer speed work (arm64, zstd 1.5.7; measured before the levels 1 to 9 retuning)

The block writer prices the three sequence tables side by side (their state machines are independent, so the walks overlap), keeps the table it priced instead of building it again, and keeps the Huffman bit container in registers; the fast and double-fast strategies choose table modes from the histogram estimate at every block size (above). Output is unchanged except for one small block in the matrix (same size). Apple M2, time ratio as above (reference speed divided by ours, bar 1.15), load 3 to 6 from other work on the machine; the whole-file rows move by less than their run-to-run spread, because the match finders dominate there:

Small payloads with a 16 or 112 KiB trained dictionary (payloads per second divided by the tool's, geometric mean of three games and two dictionary sizes; above 1 is faster than the tool; bar 0.87):

At a few hundred bytes to a few kilobytes a block costs about a hundred matches and three table decisions, and the time is spread over the match loop (about 45 ns a match), the literal section and the sequence section; no single step is more than a third.

Results: long-distance matching and jobs (zstd 1.5.7; measured before the levels 1 to 4 retuning)

Method as above, run.sh --ref-opts ... --ours-opts ... (zstd -b<L> -e<L> -T<n> [--long=27] against ZstdEncodeBench big ... --workers n --job auto [--long 27], best of 3 s). time ratio is our time over the tool's. x64: Ryzen 9 7950X3D, 32 cores, load 2 to 7 from other work; arm64: Apple M2, 8 cores, load 3 to 6. Sizes are the same on both machines. Jobs cost 0.03% in size (silesia.tar level 1: 73,520,243 bytes as one job, 73,540,841 with jobs).

The long-distance matcher alone scans 2.1 GB/s of silesia.tar (x64). On an input with far repeats (1.2 GB, three 32 MB pieces recurring at about 96 MB with one byte in 64 KiB changed) the output is 47% smaller than the tool's at levels 1 and 3, at 1.18 and 0.90 times its time. With jobs and no long matching the ratio of times is 1.25 to 1.5 (the single-thread gap) at 4 to 16 jobs, and size is +0.34% (level 1) and +0.82% (level 3) on silesia.tar.

Levels 16 to 22 (optimal parsing)

Sizes against zstd --ultra -N (1.5.7) on the full files, our size divided by the tool's minus one; the tool decodes every frame we write. Level 21 is not measured on the big files. Times are from the Apple M2 (8 cores, load 2.4 to 4.2 from other work), run.sh --seconds 1; the x64 timing rows wait for a quiet window.

Compression time is over the 1.15 bar everywhere but enwik8 22 (where the size is also over the 1% bar), so levels 16 to 22 stay preview. Outliers by file (first 4 MB of Silesia files, levels 16 and 19): mr +1.1% and +1.3%, x-ray 0.0% and +1.7%, nci +0.9% and +0.4%; the others are within 0.4% (osdb is 1.3% smaller). x-ray at levels 18 and up is 1.7% larger than at level 17 for us but 1.2% smaller for the tool: skipping the search at a position where a literal is almost as cheap (what level 17 does) brings it to +0.4% and costs 0.3% on text, so the other levels do not do it. Inputs of 16 KB or less at levels 13 to 15 can be up to 1.8% larger than the tool's.

Small game payloads with a trained dictionary at levels 16 and 19 (seed 2, one frame per payload, dictionaries of 16 and 112 KiB trained on seed 1; size against the tool's at the same level; worst cell, then the range over all 24 cells): before the dictionary-aware starting prices and the dictionary's own chain-walk budget, L16 up to +8.7% and L19 up to +5.8%; after, L16 -1.5% to +1.2% (worst: lanterns saves, 16 KiB dictionary) and L19 -4.8% to +0.4%. Levels 13 and 15 on the same payloads are -2.2% to +0.4%.