Skip to main content

Module pdx

ruvector_core

Module pdx 

Source
Expand description

PDX-style vertical (dimension-major) layout for bulk distance computation.

Implements the layout change measured in PDX: A Data Layout for Vector Similarity Search (SIGMOD ’25), which beat hand-written SIMD kernels in SimSIMD and FAISS by ~2.0× on average — using scalar code — purely by reorganizing memory. See ADR-279 §5.1: layout is the lever, not intrinsics.

§Why the row-major batch loop leaves throughput on the table

The conventional layout stores each vector contiguously and computes one distance at a time:

v0: [d0 d1 d2 … dD]   → SIMD across dimensions → horizontal sum → result[0]
v1: [d0 d1 d2 … dD]   → SIMD across dimensions → horizontal sum → result[1]

Two costs are structural, not tuning problems:

  1. A horizontal reduction per vector. Summing a SIMD accumulator into a scalar is a serial dependency chain (_mm512_reduce_add_ps is several dependent shuffles and adds) and it happens once per vector.
  2. A tail per vector. Any dimension count not a multiple of the vector width runs a scalar remainder loop, once per vector.

§The vertical layout

Store a block of LANES vectors dimension-major:

dim 0: [v0 v1 v2 … v15]
dim 1: [v0 v1 v2 … v15]
…

Now one SIMD register holds one dimension of sixteen different vectors. Iterating dimensions accumulates sixteen independent distances in parallel:

  • No horizontal reduction at all — lane i of the accumulator is distance i when the loop ends.
  • No per-vector tail — the only remainder is the final partial block.
  • Sequential access across the whole block.

The accumulator also has no loop-carried dependency between lanes, so the CPU can keep several FMAs in flight.

§Portability

Written against f32 chunks that LLVM autovectorizes, with an explicit AVX-512 path where available. Per ADR-279 this is deliberately not C: the same source compiles for x86-64, aarch64, and wasm32.

Structs§

PdxBlock
A block of up to LANES vectors stored dimension-major.
PdxIndex
A full vector set in PDX layout: a sequence of vertical blocks.

Constants§

LANES
Vectors per block. 16 f32 fills one AVX-512 register; on narrower ISAs the compiler splits it into multiple registers, which still vectorizes cleanly.