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

Aperta
  • Qualcosa non va?
#483 4 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
8/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
java
Ambito
data, performance

Direzione di ricerca

Start with DeltaEncodingDecoder#undeltaChunk and the new SimdOperations#undeltaChunk on perf/simd-kernels, then the FusedFilterAggregate and FusedFilterSum classes for the filter-plus-aggregate loop. Run the JMH baselines and check C2 vectorization with perfasm or JFR. Done means the acceptance checklist is met, with ADR 0005 updated with the numbers, whether or not a Vector API kernel is adopted.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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: https://github.com/dfa1/vortex-java/issues/484#issuecomment-6081505161):

  • 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
Lingua principale
Java
Stelle
3
Fork
2
Merge medio
9h 47m
PR unite (30g)
128

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di dfa1/vortex-java

Tutte le issue di dfa1/vortex-java

Issue simili

Altre issue su Java

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.