facebook / facebook/zstd

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

Đang mở
#4,723 0 bình luận 0 reaction 0 người được giao Xem trên GitHub
Ngôn ngữ chính
C
Star
27.9k
Fork
2.6k
Merge trung bình
1 ngày 3 giờ
Pull request đã merge (30 ngày)
8

Mô tả

## 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.

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.