How NEON and AVX-512 SIMD Kernels Accelerate Search in Turbovec

Turbovec's SIMD kernels accelerate search by using NEON intrinsics on ARM and AVX-512 instructions on x86 to process 32–64 quantized vectors simultaneously, replacing scalar bit-twiddling with parallel nibble extraction and fused multiply-add operations that yield 10–20× speedups.

Turbovec is a high-performance vector search library that stores data in a 4-bit quantized, blocked layout to maximize throughput on modern CPUs. At query time, the engine must evaluate nibble-wise lookups against pre-computed lookup tables (LUTs) for thousands of vectors—a task that is highly data-parallel but prohibitively slow when implemented scalar. To solve this, turbovec provides handwritten SIMD kernels in turbovec/src/search.rs that exploit ARM NEON and x86 AVX-512 instructions to evaluate multiple vectors per instruction cycle.

Understanding the Quantized Search Bottleneck

The scalar implementation of turbovec's search would iterate over every vector and every byte-group, extract low- and high-nibbles via bit-shifting, perform table lookups for each nibble, convert 8-bit results to 16-bit, then to floating-point, apply per-query scale and bias, and finally normalize per-vector. This sequence involves extensive branching and register pressure.

The SIMD kernels eliminate this bottleneck by loading entire blocks of quantized data into wide vector registers and processing them in parallel. According to the turbovec source code, the NEON kernel handles 32 vectors per block, while the AVX-512 kernel processes 64 vectors per iteration by operating on two blocks simultaneously.

NEON Kernel Implementation on ARM aarch64

The ARM implementation centers on the score_4bit_block_neon function (lines 46–70 in turbovec/src/search.rs). This kernel loads a 32-byte block once and uses NEON intrinsics to perform parallel nibble extraction and accumulation.

The core strategy employs vqtbl1q_u8 to perform 16 simultaneous LUT lookups without branching. The kernel splits nibbles using vandq_u8 (mask) and vshrq_n_u8 (shift), accumulates intermediate sums in uint16x8_t registers to prevent overflow, and flushes to float32x4_t using fused multiply-add (vfmaq_f32) after every 256 byte-groups.

// Conceptual flow of the NEON kernel (simplified)
// Found in turbovec/src/search.rs lines 46-70
use std::arch::aarch64::*;

// Load 32 bytes (representing 32 vectors' nibbles)
let block = vld1q_u8(ptr);
// Extract low and high nibbles in parallel
let low = vandq_u8(block, vdupq_n_u8(0x0F));
let high = vshrq_n_u8(block, 4);
// LUT lookup for 16 values at once
let lut_vals = vqtbl1q_u8(lut_table, low);
// Accumulate in 16-bit to avoid overflow
// ...
// Fused multiply-add to float
let score = vfmaq_f32(acc, scale, converted);

AVX-512 and AVX-2 Kernel Implementation on x86_64

For x86 architectures, turbovec provides two kernels: search_multi_query_avx2 (lines 61–78) for 256-bit registers and search_multi_query_avx512bw (lines 81–99) for 512-bit operations. Both reside in turbovec/src/search.rs.

The AVX-2 kernel processes 32 vectors per block using _mm256_loadu_si256 to load 32-byte blocks. It masks and shifts nibbles with _mm256_and_si256 and _mm256_srli_epi16, then performs table lookups via _mm256_shuffle_epi8. The "SUB-trick"—implemented in the helper avx2_batch_flush_to_fa (lines 700–730)—combines register halves efficiently before converting to f32 with _mm256_cvtepi32_ps and applying _mm256_fmadd_ps for the per-query scale.

The AVX-512 variant doubles throughput by processing two blocks together using 512-bit registers, halving the number of loop iterations required to scan the dataset.

// Runtime dispatch example (conceptual)
// Found in turbovec/src/search.rs
#[cfg(target_arch = "x86_64")]
if is_x86_feature_detected!("avx512bw") {
    return search_multi_query_avx512bw(args);
} else if is_x86_feature_detected!("avx2") {
    return search_multi_query_avx2(args);
}

Critical Optimizations Across Architectures

Both kernels share several optimization strategies that drive the 10–20× speedup over scalar implementations observed in turbovec benchmarks:

• Vectorized Nibble Extraction: Single instructions (vandq_u8/vshrq_n_u8 on NEON; _mm256_and_si256/_mm256_srli_epi16 on AVX) handle 32 nibbles simultaneously, replacing scalar >> and & loops.

• Parallel Table Lookups: NEON's vqtbl1q_u8 and AVX's _mm256_shuffle_epi8 perform 16 or 32 LUT lookups per instruction, eliminating the branch misprediction penalty of scalar table access.

• Reduced Memory Traffic: The kernels read one block of codes and one LUT per query batch, then reuse those registers for all vectors in the block, minimizing cache thrashing.

• Batch-wise Flushing: After FLUSH_EVERY byte-groups (typically 256), 16-bit accumulators are converted to floating-point via fused multiply-add operations. This prevents 16-bit overflow while keeping costly FP conversions to a minimum.

• Early-exit Masking: Before scoring a block, functions like block_has_allowed (AVX) or block_pair_has_allowed (AVX-512) check a user-supplied bitmap. If the entire block is masked out, the kernel skips the SIMD inner loop entirely.

• Bit-identical Computation: The flush sequence mirrors the FAISS-style "perm0-interleaved" layout, ensuring that ARM and x86 produce identical similarity scores for the same LUTs—a critical property for reproducible benchmarking.

Practical Usage Example

The high-level search API automatically dispatches to the appropriate kernel based on runtime CPU feature detection. The same code runs unchanged on ARM or x86:

use turbovec::search::{search, SearchParams};
use turbovec::codebook::Codebook;
use turbovec::io::load_vectors;

// Load pre-quantised data (4-bit blocked format)
let codebook = Codebook::load("data/codebook.bin")?;
let db_vectors = load_vectors("data/blocked_vectors.bin")?;
let query = load_vectors("data/query.bin")?;

let params = SearchParams {
    k: 10,
    mask: None,
    nq: 1, // single query
    ..Default::default()
};

// Automatically selects score_4bit_block_neon on aarch64
// or AVX-2/AVX-512 on x86_64
let (scores, ids) = search(&codebook, &db_vectors, &query, &params)?;

For batch processing, the multi-query kernels can evaluate four queries simultaneously, maximizing register utilization:

use turbovec::benchmarks::suite::recall_d3072_4bit;

// Exercises search_multi_query_avx2 or search_multi_query_avx512bw
recall_d3072_4bit::run()?;

Summary

• NEON kernel (score_4bit_block_neon in turbovec/src/search.rs lines 46–70) processes 32 ARM vectors per block using vqtbl1q_u8 for parallel LUT lookups and vfmaq_f32 for fused accumulation.

• AVX-512 kernel (search_multi_query_avx512bw in turbovec/src/search.rs lines 81–99) processes 64 x86 vectors per iteration using 512-bit registers, while the AVX-2 fallback handles 32 vectors with _mm256_shuffle_epi8.

• Shared optimizations include vectorized nibble extraction, reduced memory traffic through register reuse, batch-wise flushing every 256 byte-groups, and early-exit bitmap checks.

• Performance gains of 10–20× are achieved by replacing scalar bit-twiddling with SIMD instructions that process 16–32 nibbles per cycle, backed by the helper avx2_batch_flush_to_fa (lines 700–730) for efficient float conversion.

Frequently Asked Questions

What is the difference between the AVX-2 and AVX-512 kernels in turbovec?

The AVX-2 kernel (search_multi_query_avx2) utilizes 256-bit registers to process 32 vectors per block, while the AVX-512 kernel (search_multi_query_avx512bw) uses 512-bit registers to process 64 vectors per iteration—effectively handling two blocks simultaneously. This halves the loop iteration count on compatible hardware, though both kernels share the same nibble extraction logic and memory access patterns.

How does turbovec ensure bit-identical results across ARM and x86?

Turbovec implements a "perm0-interleaved" layout inspired by FAISS that standardizes the order of accumulation and conversion operations. Both the NEON kernel (vfmaq_f32) and AVX kernels (_mm256_fmadd_ps) apply the same sequence of scale, bias, and normalization operations, ensuring that 4-bit quantized vectors produce identical similarity scores regardless of architecture.

What is the "block" size in turbovec's SIMD kernels?

The block size refers to the number of vectors processed in a single SIMD register load. For NEON and AVX-2, this is 32 vectors (represented as 32 bytes of 4-bit quantized data). For AVX-512, the kernel processes 64 vectors per iteration by loading two 32-byte blocks into a 512-bit register. This blocked layout minimizes cache misses by keeping vector data contiguous in memory.

When does turbovec fall back to scalar implementation?

Turbovec performs runtime feature detection using is_x86_feature_detected! on x86 or std::arch checks on ARM. If the CPU lacks AVX-2 or NEON support, the library falls back to a scalar implementation that iterates through nibbles individually. However, the scalar path is rarely used on modern hardware, as the kernels target baseline requirements of aarch64 for ARM and SSE4.1/AVX for x86_64.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}