Skip to content

perf(reader): SIMD kernels mirroring Rust: C2-shaped scalar loops, opt-in Vector API for filter compress/bitmap/small-table take #483

Open

Description

@dfa1

Summary

ADR 0005 defers the Vector API, partly because a hard --add-modules jdk.incubator.vector would tax every consumer. This issue covers the read side: which loops get an optional Vector API kernel, and which stay scalar loops shaped for C2. The write side is #484.

Selection rule (prime directive: parity with Rust). The Rust reference uses SIMD at two levels (survey: #484 (comment)):

  • Level 1, scalar loops shaped for the auto-vectorizer. All encode/decode work: the fastlanes crate (bit-pack, delta, FoR, RLE), casts, ALP. No intrinsics.
  • Level 2, hand-written SIMD with one-time CPU dispatch (vortex-buffer/src/dispatch.rs CpuKernel, fearless_simd). Used only for selection and bitmap work: filter compress, take, bitmap pack/popcount/select, UTF-8.

A Java kernel gets a Vector API implementation only if (a) the corresponding Rust operation is level 2, or (b) C2 provably fails to vectorize a level-1 loop that LLVM does. Everything else stays scalar and C2-shaped. ADR 0005's bar still applies on top: ≥ 10% over the best scalar loop on two architectures, and hot in a real profile.

Level 2: Vector API candidates (Rust uses hand-written SIMD)

Ranked by fit to the Java API:

# Operation Rust Java Vector API Java call site
R1 Filter compress: mask-select fixed-width values arrays/filter/execute/simd_compress/ (AVX-512 maskz_compress, AVX2 permutevar8x32, NEON vqtbl1q_u8 + LUT, portable swizzle_dyn for 1/2-byte); rung 3 of the filter/execute/buffer.rs ladder XxxVector.compress(VectorMask) (JDK 19+, intrinsified on AVX-512/SVE; NEON lowering unverified) + VectorMask.fromLong none today: row filtering is fused or per-row, scans prune by zone only (see comment)
R2 bool → bitmap pack (collect_bool) vortex-buffer/src/bit/pack.rs (AVX-512BW vptestmb, pmovmskb, NEON ushl + addp) compare(...) → VectorMask.toLong() predicate result → validity/selection bitmap
R3 Small-table take: u8 codes, ≤ 16 one-byte values fixed_width/take/small_table/{neon,avx2}.rs (vqtbl1q_u8, vmaxq_u8 bound check) ByteVector.selectFrom / rearrange DictEncodingDecoder with small u8 dictionaries; its code bound check (vmaxq_u8) shipped as maxUnsigned (fbecfb45)
R4 Bitmap popcount / nth-set-bit select bit/count_ones.rs, bit/select.rs, vortex-mask/src/intersect_by_rank.rs (SIMD popcount, BMI2 pdep/tzcnt) Long.bitCount is already a C2 intrinsic: measure only mask true-count, row-range selection
R5 Take / gather fixed_width/take/avx2/ (AVX2 gather, 4/8-byte only) fromArray(..., indexMap, ...) exists only for heap arrays, not MemorySegment. Weak fit, not proposed n/a
R6 UTF-8 validation simdutf8 The JDK String decode is already intrinsified (countPositives). No action n/a

Each candidate needs JMH A/B (-f 3, ClassName.methodName) at selectivities 1%/50%/99% where relevant, plus a JFR profile of a real filtered scan (e.g. JavaVsJniFilterBenchmark, CalciteBoundaryAggregateBenchmark) showing the loop is hot.

Not proposed

  • Dictionary gather (except the R3 small-table case), LazyAlp*/FoR/ZigZag: level 1 in Rust, and C2 already handles the clean ones.
  • Any DecodeContext/ReadOptions flag (Strategy B).

Design constraints

  • Bit-identical to the scalar path. Differential test in SimdOperationsTest (hardwood pattern): seeded random plus edge cases (empty, tail, Long.MIN_VALUE, unsigned, NaN/-0.0).
  • Opt-in only, scalar default. A link failure falls back silently (DEBUG log).
  • Security contract unchanged: bounds are checked before the kernel, and a kernel throws only VortexException.
  • ADR 0005 (status and evidence), docs/reference.md, and CHANGELOG are updated in the same commit.

Acceptance

  • Packaging (hardwood-style, opt-in): SimdOperations seam with AutoVectorizedSimdOperations (default) and VectorApiSimdOperations, chosen once per JVM by SimdOperationsSupport
  • Level 1: scalar, C2-shaped loops (no Vector API): AutoVectorizedSimdOperations is the Rust-parity default for all eleven ptypes
  • Delta undelta: JMH baseline vs pre-interchange, C2 vectorization confirmed (perfasm/JFR), result recorded
  • Fused filter-aggregate: plain-Java branch-free compare loop tried first (Rust analogue: compare_fused.rs; keep double SUM sequential), result recorded
  • R1–R3: JMH baselines on M5 + one x86 machine before any kernel
  • Vector kernel only if rule (a)/(b) holds and it is ≥ 10% over the best scalar loop on both machines
  • Differential test against the scalar path
  • ADR 0005 updated with the numbers either way

Activity

  1. changed the title [-]perf(reader): optional Vector API kernels for fused filter-aggregate and Delta decode (hardwood-style, opt-in)[/-] [+]perf(reader): SIMD kernels mirroring Rust: C2-shaped scalar loops, opt-in Vector API for filter compress/bitmap/small-table take[/+] on Oct 9, 2026
  2. dfa1 commented on Oct 9, 2026

    @dfa1
    OwnerAuthor

    Read-side survey + first rule-(b) evidence (2026-10-09)

    Dict code bound check: shipped scalar, Vector API measured

    DictEncodingDecoder#validateCodesInRange (every dict decode scans every code for max < poolLength) is our equivalent of Rust's vmaxq_u8 bound check in take/small_table/neon.rs. Committed as SimdOperations#maxUnsigned (fbecfb45). MaxUnsignedBenchmark, M5 / NEON (MaxVectorSize=16), 1M codes, µs/op:

    ptype old (serial long max) scalar kernel (shipped) Vector API UMAX Vector API signed MAX with sign bit flipped
    U8 322 139 217 30
    U16 376 135 435 60
    U32 436 120 871 120

    (-f 3 for the first two columns, -f 2 for the Vector API.)

    Findings:

    • C2 doesn't vectorize a widening U8/U16 max reduction (byte/short → int), in either the int or the long domain. The scalar kernel gets 2.3× from four independent accumulators (instruction-level parallelism, not SIMD).
    • VectorOperators.UMAX isn't intrinsified on aarch64 in JDK 25. It runs a Java fallback that's slower than scalar, with cost proportional to element width. XOR the sign bit, then MAX, maps to NEON smax instead. Every Vector API kernel needs a JMH row per operator, not just per kernel.
    • U8 at 30 µs is memory-bound: 1 MB per 30 µs, the same speed as reading the bytes 8 at a time as longs. That's 4.6× over the scalar kernel. U16 is 2.2× better. U32 gains nothing, because C2 already vectorizes the int loop.
    • So U8/U16 meet rule (b) and the ≥10% bar on one architecture. Still missing for ADR 0005: an x86 run, and a profile showing this loop is hot in a real workload.

    The experiment needs --add-modules jdk.incubator.vector at compile time and -jvmArgsAppend --add-modules=jdk.incubator.vector at run time. It's not committed; the core seam doesn't load the incubator module yet.

    Read-side loop inventory (what else maps to Rust's level 2)

    Java loop Rust analogue Status / next step
    BitpackedEncodingDecoder unpackLoop{8,16,32,64} fastlanes unpack (level 1) Already lane-inner. Confirm vectorization with perfasm, no kernel
    DictFilter code scans (seg.get(i) == only, match[code]) + per-row fold.accept collect_bool byte → bitmap (pack.rs, vptestmb / pmovmskb / NEON ushl + addp) R2 candidate. ByteVector.eq(only).toLong() → iterate set bits. Same C2 widening problem expected. Use signed ops only
    FusedFilterSum / FusedFilterAggregate (selectedLong + getBoolean per row) compare_fused.rs (compare during unpack, then one transpose_bits) Level 1 first: branch-free compare-to-word, then fold over set bits
    DictEncodingDecoder#rowValidity (per-row getBoolean + setBit, only when the pool has nulls) bitmap AND over words Plain Java: word-wise when codes validity is absent. Low priority (rare path)
    BoolEncodingDecoder#realign (byte-at-a-time shift) BitBuffer works on u64 words Plain Java: long-at-a-time funnel shift. Low priority (only when offset ≠ 0)
    Filter compress (R1) simd_compress/ No Java call site. Row-level filtering is fused into aggregates or tested per row (Compute#matches); scans prune by zone only. Revisit if a selection-vector API appears
    Lazy{For,ZigZag,Alp}*Array#materialize level 1 Monomorphic per-class loops. Verify with perfasm before touching
  3. dfa1 commented on Oct 9, 2026

    @dfa1
    OwnerAuthor

    Progress and plan (branch perf/simd-kernels, not pushed)

    Done: Delta undelta (candidate 2) — plain Java, no Vector API needed

    undeltaChunk now lives in core.simd.SimdOperations (VectorSupport.operations() is the single seam; scalar implementation only). DeltaEncodingDecoder delegates to it. Loops are swapped to rows-outer / lanes-inner, and only the result is masked (the low bits of a sum depend only on the operands' low bits). SimdKernelBenchmark.undelta, 256 chunks, -f 3, Apple M5:

    typeBits before after
    8 136 µs 69 µs
    16 132 µs 73 µs
    32 143 µs 80 µs
    64 150 µs 93 µs

    So the loop-interchange experiment this issue asked for ran first, and it already gives 1.6–2×. A Vector API version of undelta now has to beat these numbers, not the old ones. Commit b18ad842. Reader/writer Delta tests and the Rust interop ITs pass. scatterChunk (permutation scatter) is unchanged and still bounds the end-to-end gain.

    Next: fused filter + aggregate (candidate 1), scalar first

    FusedFilterAggregate#foldLongDomain / FusedFilterSum run a per-row loop: one LongPredicate call per leaf, an early continue, a validity check, then sum += and min/max with a found branch. C2 cannot vectorize that.

    Plan, same shape as the other kernels:

    1. Scalar kernel in SimdOperations for the primitive case (long/double column vs constant, after PrimitiveFilter.lowerLong): compare a block against the constant and fold only the matching rows, with no predicate object per row. Add SimdKernelBenchmark rows at 1% / 50% / 99% selectivity for the baseline.
    2. Differential test against the current loop (signed and unsigned, nulls, empty, tail).
    3. Only then a Vector API version (compare to mask, trueCount, masked reduceLanes), kept only if it beats the scalar kernel by >= 10% on two architectures.

    Parity risk unchanged: double SUM in lane order rounds differently from a sequential loop, so it stays sequential (or must match Rust's accumulation order). Integer paths are exact.

    Not planned: the reader's bit-unpack loops. BitpackedEncodingDecoder already has per-width unpackLoop16/32/64 written for C2 (ADR 0005); revisit only if a profile shows them hot.

  4. dfa1 commented on Oct 9, 2026

    @dfa1
    OwnerAuthor

    Design and rationale: ADR-0005 (previously tracked in TODO.md, now retired in favor of GitHub Issues).

  5. dfa1 commented on Oct 24, 2026

    @dfa1
    OwnerAuthor

    Tried and reverted (2026-10-24): generated FastLanes unpack kernels in Rust's unpack! shape, one per (type width, bit width): per lane each packed word loaded once, every row's shift a constant.

    • Single-column microbenchmark (one width, whole-column decode, JDK 25, M5): u8 +45%, u16 +46%, u32 +19-25%, u64 -39% (64 stores and up to 63 live words per lane spill).
    • RealFileScanBenchmark on the seven real files, against main: every file regressed. With u8/u16/u32 kernels: tpch orders -53%, appian-order -37%, store_sales -35%, bi-corporations -28%, imdb-job-title -26%. With u8/u16 only: appian-order -27%, orders -5%.
    • Profile on orders: the kernels were C2-compiled, but the FFM per-access checks (MemorySessionImpl.checkValidStateRaw, checkBounds) were hot leaves. In a straight-line body of 50+ segment accesses they are not hoisted, while the existing row-outer loops (one lane loop per row) get them hoisted.

    Related, measured the same day: on JDK 25, C2 does not vectorize a loop that loads one native segment and stores another (two-segment out[i] = in[i] & mask is 3.7x slower than over heap arrays); JDK 26 does. So on the JDK 25 baseline, explicit SIMD (the opt-in Vector API path) is the remaining lever for unpacking.

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