Skip to content

improve FSST implementation #287

Closed
Closed

Description

@dfa1

So far we had a very simple FSST implementation. Comparing our implementation against vortex-rust surfaced a lot of missed opportunities for vortex-java.

The idea is to reduce the gap by:

Why? I will be faster to iterate on the design if the drop "vortex" shell and focus on the code algorithm.

Activity

  1. dfa1 commented on Jul 20, 2026

    @dfa1
    OwnerAuthor

    Done — closing this out. Summary of the rewrite:

    Research: studied the paper in full (Boncz/Neumann/Leis, VLDB 2020) plus the actual spiraldb/fsst Rust crate (the reference implementation vortex-jni's own FSST is built on). Confirmed no zero-dependency Java FSST library exists, so per the issue's own decision tree, extracted FSST into its own module.

    New standalone module: vortex-fsst — zero dependency on core/reader/writer, MemorySegment-native (matching this project's FFM-everywhere convention), independently testable/benchmarkable. Public API: Symbol, Compressor/CompressorBuilder, Decompressor.

    Ported faithfully from the paper + the real reference's refinements:

    • Branch-free O(1) matching (was up to 8 sequential hash probes per byte position)
    • Adaptive byte-bounded sampling, per-generation min-count pruning, single-byte gain boost, final cost-based prune during training
    • Unconditional-8-byte-store decode (Algorithm 1)

    Measured result (JavaVsJniFsstBenchmark, unmodified before/after):

    Before After Speedup Gap to vortex-jni
    encode 0.085 ops/s 1.848 ops/s ~21.7x 36x slower → 1.6x slower
    decode 5.243 ops/s 27.137 ops/s ~5.2x 6.5x slower → 1.3x slower

    Along the way: a real data-corruption bug was found and fixed during review (the branch-free matcher could spuriously overrun the true end of short strings) — caught before it ever reached a merged PR, documented as a risk class in ADR 0022.

    Merged as 8 PRs: #290, #291, #292, #293, #294, #295, #296, #297.

    Explicitly out of scope (tracked in TODO.md): AVX512/SIMD kernel, true per-row lazy/random-access decode, OptFSST.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions