facebook / facebook/zstd

zdict legacy trainer: the merge fixpoint deletes an unrelated segment when the rank sort invalidates its slot index

Open
#4,723 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
27.9k
Forks
2.6k
Avg merge
1d 3h
Merged PRs (30d)
8

Description

## Summary

`ZDICT_insertDictItem` builds the legacy trainer's segment table by fixpoint.
Each `dictItem` is an interval `[pos, pos + length)` in the sample buffer;
`ZDICT_tryMerge` fuses the candidate with one overlapping entry, and the loop
re-runs because fusing two intervals can produce one that reaches a third.
Across that loop the absorbed entry is identified by its array slot,
`mergeId` (`lib/dictBuilder/zdict.c:431-443`):

```c
U32 mergeId = ZDICT_tryMerge(table, elt, 0, buffer);
if (mergeId) {
U32 newMerge = 1;
while (newMerge) {
newMerge = ZDICT_tryMerge(table, table[mergeId], mergeId, buffer);
if (newMerge) ZDICT_removeDictItem(table, mergeId);
mergeId = newMerge;
}
return;
}
```

`ZDICT_tryMerge` ends each successful merge with a rank-improving insertion
sort (`zdict.c:377-380` and `zdict.c:396-400`):

```c
elt = table[u];
/* sort : improve rank */
while ((u>1) && (table[u-1].savings < elt.savings))
table[u] = table[u-1], u--;
table[u] = elt;
return u;
```

Merging raises `savings`, so the absorbing entry moves toward the front of the
savings-ranked table and every entry between its old and new slot shifts one
slot back. `mergeId` is passed as `eltNbToSkip`, so it is by construction an
index into the region the sort disturbs. When it is displaced, the following
`ZDICT_removeDictItem(table, mergeId)` deletes an unrelated live segment while
the absorbed entry survives as a duplicate.

There is a second, independent invalidation in the same loop.
`ZDICT_removeDictItem` shifts every entry above `mergeId` one slot forward
(`zdict.c:425-426`), including the entry `newMerge` denotes, and `newMerge` is
carried into the next round unchanged (`zdict.c:440`).

## Reproduction

Four inserts into a freshly initialised table, items given as
`(pos, length, savings)`:

```
(1000, 10, 200) isolated: 700 bytes from the nearest other interval
( 340, 20, 100)
( 300, 20, 90)
( 320, 30, 60) bridges [300,320) and [340,360)
```

The fourth item tail-overlaps `(340, 20)`, which then front-overlaps
`(300, 20)`. The second merge lifts the absorbing entry from slot 3 to slot 1,
shifting slots 1 and 2 back; the caller still holds slot 2.

| tree | surviving entries |
|---|---|
| `dev` at 82d322c49 | `(pos=300 len=60 savings=229)` |
| with slot index carried by pointer | `(pos=300 len=60 savings=238)`, `(pos=1000 len=10 savings=200)` |

The segment at position 1000 takes part in no merge and is deleted.

## Frequency

An executable port of `zdict.c:137-545`, driven over this repository's own
`lib/` directory as the training corpus, counts every `ZDICT_removeDictItem`
call whose victim differs from the entry the caller selected, comparing
`(pos, length)` before and after:

| training corpus | dictionary segments | wrongful deletions |
|---|---|---|
| 48 KB | 263 | 6 |
| 96 KB | 622 | 15 |
| 192 KB | 1371 | 30 |

Roughly one live segment destroyed per 6 KB of training corpus, growing
linearly. Building real dictionaries through `ZDICT_trainFromBuffer_legacy` from `lib/`
and `programs/` (2,359,503 B across 57 files, dictionary capacity 112,640 B,
`selectivityLevel` 9) and counting 32-byte windows of dictionary content that
occur more than once gives 2,554 before the change and 2,525 after. Both
dictionaries fill the capacity exactly.

## Reachability

`ZDICT_trainFromBuffer` routes to `ZDICT_optimizeTrainFromBuffer_fastCover`
(`zdict.c:1111-1127`) and is unaffected. The code above is reached only by
`ZDICT_trainFromBuffer_legacy` (`lib/zdict.h:443`) and by the CLI's
`--train-legacy` (`programs/dibio.c:396`).

`tests/fuzzer.c` exercises `ZDICT_trainFromBuffer` (`fuzzer.c:3050`, `:3058`,
`:3648`, `:4474`) and `ZDICT_trainFromBuffer_cover` (`fuzzer.c:3790`), but never
`ZDICT_trainFromBuffer_legacy`. `tests/playTests.sh` invokes `--train-legacy`
only in two negative cases asserting failure on insufficient and on pure-noise
input (`playTests.sh:1165`, `:1167`). The legacy trainer has no positive
assertion on its output in the test suite.

## Limits

The merge machinery and the segment table are file-static and unreachable from
any public or static-API entry point, so the reproduction above requires
including `zdict.c` directly. Compression ratio is not the argument here: on
held-out samples the effect is within noise in both directions, measured at
-75 bytes at level 3 and +40 bytes at level 9 over 1,340,695 B of held-out
input. All measurements come from gcc 15.2.0 on Ubuntu 26.04 LTS under WSL2 on
a single machine, and no 32-bit target was exercised.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.