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

Offen
  • Stimmt etwas nicht?
#483 4 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
8/100
Issue-Typ
Feature
Klarheit
Größtenteils klar
Aktivitätsstatus
Aktiv
Tech-Stack
java
Bereich
data, performance

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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
Vorherrschende Sprache
Java
Sterne
3
Forks
2
Ø Merge
9 Std. 47 Min.
Gemergte PRs (30 T.)
128

Entwicklungsumgebung

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus dfa1/vortex-java

Alle Issues in dfa1/vortex-java

Ähnliche Issues

Weitere Issues zu Java

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.