FSST review: missing bulk decode path, per-row allocations, training-count length collision

[dfa1]

Review of the fsst module plus its reader/writer adapters, looking for wasteful allocations
and non-optimal algorithms. Findings below, ordered by impact. One is a correctness bug in
training (#5); the rest are performance/cleanup.

Suggested order of attack: 2 and 1 (read throughput), then 5 (bug), then 4 + 6
(training cost), then 12. The rest is a cleanup batch.

---

Reader hot path — LazyFsstVarBinArray.getBytes

1. Two heap allocations + a full copy per row, one of them 8x over-sized

reader/src/main/java/io/github/dfa1/vortex/reader/array/LazyFsstVarBinArray.java:87-108

byte[] scratch = new byte[(int) maxLen + 7];   // maxLen = 8 * compressedBytes
... decompress(..., MemorySegment.ofArray(scratch), 0)   // + a segment wrapper
return Arrays.copyOf(scratch, (int) decodedLen);          // + the real array

maxLen is the FSST paper's worst-case bound, not the actual size — and the actual size is
already known: uncompressedLength(i) is read a few lines later at :103. So every row costs an
oversized array, a MemorySegment wrapper, an exact-size array, and a full byte copy, where one
exact-size array would do.

The fix needs a small addition to Decompressor: a
decompress(MemorySegment compressed, long start, long end, byte[] out, int outPos) overload that
keeps the unconditional-8-byte-store trick while outIndex + 8 <= out.length and falls back to a
byte loop for the final <= 7 bytes. Then getBytes reads the claimed length first, validates it
against maxLen (the check getByteLength already does at :121), allocates new byte[claimedLen],
and returns it directly — 1 allocation, no copy, no slack. The decodedLen != claimedLen check
still works.

2. There is no bulk decode path at all

reader/src/main/java/io/github/dfa1/vortex/reader/array/VarBinArray.java:101-113

VarBinArray.toOffsetMode walks getByteLength then getBytes per row and wraps each result in
MemorySegment.ofArray — so materializing an FSST column is ~3 allocations/row plus two copies.

Because row code ranges are contiguous and monotonic in the code stream, the entire column can be
decompressed in a single decompress(compressedBytes, 0, totalCodes, outBytes, 0) call straight
into the arena segment, with offsets derived by prefix-summing the lengths child. That is the
batched shape that got FSST to vortex-jni parity in #300; the ADR 0026 lazy refactor kept per-row
random access (correctly) but appears to have dropped the bulk case.

Add an override or an instanceof LazyFsstVarBinArray fast path in toOffsetMode. This is the
single largest win — DictEncodingDecoder:390 and DictLayoutDecoder:154 hit it directly.

3. Redundant offset reads

toOffsetMode's two passes mean codeRange(i) runs twice per row
(LazyFsstVarBinArray.java:79 and :119) and uncompressedLength(i) twice, each going through
SegmentBroadcast.elementOffset and a readAt ptype switch — 6 switch dispatches per row on values
that are read-only for the life of the array.

---

Training — TrainingGeneration

4. Counts allocates ~4 objects per input position

fsst/src/main/java/io/github/dfa1/vortex/fsst/TrainingGeneration.java:221-254

singles.merge(packed, new long[]{1, length}, (existing, added) -> { existing[0]++; return existing; });
pairs.merge(new Pair(first, second), 1L, Long::sum);

Map.merge evaluates its value argument eagerly, so new long[]{1, length} and new Pair(...)
allocate on every occurrence, not just the first — plus Long boxing of both the key and the
summed count. Across five generations replaying ~2.7x the 16 KB sample that is on the order of 1e5
throwaway objects per train(), i.e. per encoded chunk.

The reference design (and the paper's) is flat arrays indexed by code, not by packed bytes:
count1[512] and count2[512][512], with codes 0..255 and escaped literals at 256 + byte.
matchLengthAt already has the code in hand at :95 and throws it away. That removes both hash maps
entirely.

Minimal alternative if the redesign is too big for one pass:
computeIfAbsent(packed, k -> new long[]{0, length})[0]++ allocates only on a miss.

5. BUG — singles is keyed by packed bytes only, which conflates different lengths

A length-1 symbol and a length-2 symbol collide whenever the shorter is a prefix of the longer and
the extra bytes are NUL: {0x41} and {0x41, 0x00} both mask to 0x41 under lengthMask.
bumpSingle's merge function discards the incoming length and keeps the first-seen one, so:

• the two are counted as one candidate with the wrong length, and
• counts.lengthOf(first) at :124 returns the wrong shift for concatenate, producing pair
  candidates whose bytes do not correspond to any real substring.

Output stays correct (compressor and decompressor agree on whatever table is trained), but the table
is silently degraded on any NUL-containing data — i.e. DType.Binary columns.

Fix: key by (packed, length), or adopt the code-indexed arrays from #4, which do not have the
problem. Needs a regression test with NUL bytes in a Binary column.

6. compressCount loads the input word twice per position, both times byte-by-byte

TrainingGeneration.java:74-75

matchLengthAt calls Compressor.loadWord, then the caller calls it again with a different end.
loadWord (Compressor.java:261-268) is an 8-iteration load-and-shift loop — and note that
compress() has a LONG_LE_BYTES VarHandle fast path (Compressor.java:159) that the training path
never uses.

Since loadWord(bytes, pos, pos + matchLength) == loadWord(bytes, pos, end) & lengthMask(matchLength)
whenever matchLength <= end - pos (which the guard at :97 enforces), one load suffices:

long word = pos <= end - 8 ? (long) LONG_LE_BYTES.get(bytes, pos) : loadWord(bytes, pos, end);
int matchLength = matchLengthOf(current, word, pos, end);
long packed = word & lengthMask(matchLength);

Roughly 16 scalar loads + shifts down to 1 per position, in the dominant loop of training.

7. The Matcher is rebuilt from scratch six times per train()

CompressorBuilder.java:60,70 -> Compressor.of -> Matcher.of. Each rebuild allocates a fresh
int[65536] (256 KB) plus Arrays.fill, and a long[4096]. ~1.5 MB of churn and ~400 K redundant
fills per encoded chunk. The tables could be allocated once and re-seeded per generation.

8. selectTop applies the final cost prune after top-K selection

TrainingGeneration.java:156-170. Candidates that fail realGain > length + 1 are dropped from the
surviving 255 and leave the slots empty, even when there were qualifying candidates just below the
cut. The prune belongs before the heap, so the 255 slots always get filled with symbols that earn
them.

---

Sample

9. Sample.draw boxes every chunk boundary

fsst/src/main/java/io/github/dfa1/vortex/fsst/Sample.java:85,159 — two List<Integer> converted
back to int[]. Chunks can be as short as one byte, so this is up to 16 K boxed Integers x2 for a
16 KB sample. Both are computable into pre-sized int[].

10. chunkEnds is redundant

Chunks are written back-to-back (Sample.java:102-105), so chunkEnds[i] == chunkStarts[i+1] always
and the last end is bytes.length. One int[chunkCount + 1] replaces both arrays.

11. The comment at Sample.java:90-91 describes a guard that does not exist

It claims the number of empty-row skips is bounded; the loop (:92-106) is an unbounded rejection
sampler. It terminates with probability 1, but on a mostly-empty corpus (1 M rows, 0.01 % non-empty)
the expected draw count is quadratic in the sparsity. Either pre-filter the non-empty row indices
once — cheap, rows.length work, and it makes drawing O(chunks) — or fix the comment.

---

Writer adapter

12. FsstEncodingEncoder allocates a heap scratch of 2 * totalInput then copies it into the arena

writer/src/main/java/io/github/dfa1/vortex/writer/encode/FsstEncodingEncoder.java:167,177-178

For a large string chunk that is double peak memory plus a full copy, and it is exactly the pattern
CLAUDE.md's allocation rule forbids. Compressor already has a MemorySegment compress overload —
compress straight into arena.allocate(2 * totalInput) and both the heap array and the copy
disappear.

13. remapCodesToWire is a second full pass over the code stream

FsstEncodingEncoder.java:238. Avoidable by having the compressor's tables carry wire codes directly,
though it needs a small API addition (Compressor.of(symbols, codeMapping)). Lower priority — it is
one linear pass over already-compressed data — but it is pure overhead on every encode.

14. codesSortedByLength boxes <= 255 codes and sorts with a deref-heavy comparator

fsst/src/main/java/io/github/dfa1/vortex/fsst/Compressor.java:98-118 — builds a List<Integer> and
compares with two list-gets and two record derefs per comparison. Symbol lengths are 1-8, so a
9-bucket counting sort is O(n), allocation-free, stable by construction, and shorter than the current
code.

15. VarBinBytes.toByteArrays allocates two byte[][] outer arrays

writer/src/main/java/io/github/dfa1/vortex/writer/encode/VarBinBytes.java:44-51 — toRawByteArrays
builds one, then the null-substitution pass builds another. One pass would do. Shared by four
encoders, not just FSST.

---

Dead API

• Decompressor.decompress(byte[], int, int, byte[], long) — public, zero production callers, tests
  only. It also narrows outPos to int unchecked at Decompressor.java:55. If it stays, the
  byte-copy inner loop at :63-65 is the variable-length branch the hot-loop rule warns about; the
  segment overload's 8-byte-store trick applies equally to byte[] via a VarHandle. Note Welcome to vortex-java Discussions! #1 wants a
  byte[]-output overload anyway — worth reconciling the two.
• ShortCodeTable.codeFor / lengthFor — test-only.
• Matcher.maxSymbolLength() — no callers anywhere (FsstEncodingEncoderTest:254 defines its own
  private method of the same name).