Context
While investigating why vortex-java's FSST encode still trails vortex-jni after all
15 fixes from #393 landed, I compared our training hot loop against the actual Rust
reference (spiraldb/fsst, the crate vortex-data/vortex's FSSTScheme depends on via
fsst_train_compressor).
Sample sizing is identical between the two implementations —
spiraldb/fsst/src/builder.rs: FSST_SAMPLETARGET = 1 << 14 (16384) and
FSST_SAMPLELINE = 512 match our Sample.TARGET_SAMPLE_BYTES (16 KB) and
Sample.MAX_CHUNK_BYTES (512) exactly, so sample-size tuning isn't the gap. The
"measure on a sample, then re-encode on full data" pattern is also shared architecture,
not Java-specific (see #394's update) — vortex-jni pays that cost too and still wins,
so it isn't the gap either.
What's actually different
TrainingGeneration.Counts (fsst/src/main/java/io/github/dfa1/vortex/fsst/TrainingGeneration.java)
still tallies candidates with two HashMaps — Map<Single, long[]> and
Map<Pair, long[]> — even after #393's #4/#5/#6 fixes (which improved allocation
patterns and load count, but kept the hash-map shape). Every bumpSingle/bumpPair
call pays a hash computation, bucket lookup, and record.equals() on the Single/Pair
key.
The Rust reference's Counter (spiraldb/fsst/src/builder.rs:104-220) counts with flat
arrays indexed directly by code, no hashing at all:
const COUNTS1_SIZE: usize = (FSST_CODE_MASK + 1) as usize; // 512
const COUNTS2_SIZE: usize = COUNTS1_SIZE * COUNTS1_SIZE; // 262144
struct Counter {
counts1: Vec<usize>, // flat, indexed directly by code
counts2: Vec<usize>, // flat, indexed by code1*512 + code2
code1_index: CodesBitmap, // 64-byte bitmap tracking which slots are populated
pair_index: Vec<CodesBitmap>, // one bitmap per code1, tracking which code2s follow it
}
record_count1/record_count2 are #[inline] array writes gated by a bitmap check —
no allocation, no hashing, cache-friendly contiguous memory, the whole Counter reused
(.clear()) across generations and across training runs
(CompressorBuilder::new() is called once; compare to our Counts being a fresh
instance every compressCount call).
This is exactly the "bigger redesign" alternative #393's finding #4 flagged and we
deliberately deferred:
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.
Confirmed: Matcher.longestMatch already returns a packed code << 8 | length value,
and Matcher.codeOf(int) already exists — TrainingGeneration.matchLengthAt (now
matchLengthOf) calls Matcher.lengthOf(packedMatch) but discards the code half
entirely, then re-derives a different identity (packed bytes + length) to key the
counters.
Suggested design
Replace Counts's two HashMaps with:
long[] counts1 sized 256 (escape bytes) + 255 (trained codes), or equivalent,
indexed by the code Matcher.codeOf(packedMatch) returns (using a reserved escape
range for the 256 possible literal bytes that never matched a trained symbol, matching
Rust's FSST_CODE_MASK scheme).
long[] counts2 sized codeSpace * codeSpace, indexed by code1 * codeSpace + code2.
- A "which slots are populated" bitmap (or just a
boolean[]/small BitSet) instead of
a HashMap's implicit key presence, so forEachSingle/forEachPair can iterate only
populated entries without scanning the whole array.
This needs compressCount to capture the code from each match (not just its length and
packed bytes) and thread it through bumpSingle/bumpPair, and makeTable to look up a
candidate's actual bytes from the current compressor's symbol table by code (for
already-matched symbols) rather than re-deriving them from a packed-bytes-plus-length
key — a bigger shape change than #393's incremental fixes, since the counted "identity"
moves from (packed, length) to (code), which only exists relative to some trained
table (the escaping byte's own "code" for singles at generation 0, before any symbol is
trained, still needs its own definition — Rust reserves FSST_CODE_MASK for this).
Scope
This is bigger than a "cleanup batch" item — it changes Counts's fundamental
representation and how TrainingGeneration derives candidate bytes, not just its
allocation pattern. Filed separately from #393 (which is closed/done) and from #394
(the double-training architecture issue, now clarified as shared with vortex-jni).
Context
While investigating why
vortex-java's FSST encode still trailsvortex-jniafter all15 fixes from #393 landed, I compared our training hot loop against the actual Rust
reference (
spiraldb/fsst, the cratevortex-data/vortex'sFSSTSchemedepends on viafsst_train_compressor).Sample sizing is identical between the two implementations —
spiraldb/fsst/src/builder.rs:FSST_SAMPLETARGET = 1 << 14(16384) andFSST_SAMPLELINE = 512match ourSample.TARGET_SAMPLE_BYTES(16 KB) andSample.MAX_CHUNK_BYTES(512) exactly, so sample-size tuning isn't the gap. The"measure on a sample, then re-encode on full data" pattern is also shared architecture,
not Java-specific (see #394's update) —
vortex-jnipays that cost too and still wins,so it isn't the gap either.
What's actually different
TrainingGeneration.Counts(fsst/src/main/java/io/github/dfa1/vortex/fsst/TrainingGeneration.java)still tallies candidates with two
HashMaps —Map<Single, long[]>andMap<Pair, long[]>— even after #393's #4/#5/#6 fixes (which improved allocationpatterns and load count, but kept the hash-map shape). Every
bumpSingle/bumpPaircall pays a hash computation, bucket lookup, and
record.equals()on theSingle/Pairkey.
The Rust reference's
Counter(spiraldb/fsst/src/builder.rs:104-220) counts with flatarrays indexed directly by code, no hashing at all:
record_count1/record_count2are#[inline]array writes gated by a bitmap check —no allocation, no hashing, cache-friendly contiguous memory, the whole
Counterreused(
.clear()) across generations and across training runs(
CompressorBuilder::new()is called once; compare to ourCountsbeing a freshinstance every
compressCountcall).This is exactly the "bigger redesign" alternative #393's finding #4 flagged and we
deliberately deferred:
Confirmed:
Matcher.longestMatchalready returns a packedcode << 8 | lengthvalue,and
Matcher.codeOf(int)already exists —TrainingGeneration.matchLengthAt(nowmatchLengthOf) callsMatcher.lengthOf(packedMatch)but discards the code halfentirely, then re-derives a different identity (packed bytes + length) to key the
counters.
Suggested design
Replace
Counts's twoHashMaps with:long[] counts1sized256 (escape bytes) + 255 (trained codes), or equivalent,indexed by the code
Matcher.codeOf(packedMatch)returns (using a reserved escaperange for the 256 possible literal bytes that never matched a trained symbol, matching
Rust's
FSST_CODE_MASKscheme).long[] counts2sizedcodeSpace * codeSpace, indexed bycode1 * codeSpace + code2.boolean[]/smallBitSet) instead ofa
HashMap's implicit key presence, soforEachSingle/forEachPaircan iterate onlypopulated entries without scanning the whole array.
This needs
compressCountto capture the code from each match (not just its length andpacked bytes) and thread it through
bumpSingle/bumpPair, andmakeTableto look up acandidate's actual bytes from the current compressor's symbol table by code (for
already-matched symbols) rather than re-deriving them from a packed-bytes-plus-length
key — a bigger shape change than #393's incremental fixes, since the counted "identity"
moves from (packed, length) to (code), which only exists relative to some trained
table (the escaping byte's own "code" for singles at generation 0, before any symbol is
trained, still needs its own definition — Rust reserves
FSST_CODE_MASKfor this).Scope
This is bigger than a "cleanup batch" item — it changes
Counts's fundamentalrepresentation and how
TrainingGenerationderives candidate bytes, not just itsallocation pattern. Filed separately from #393 (which is closed/done) and from #394
(the double-training architecture issue, now clarified as shared with
vortex-jni).