SIMD Acceleration in Feather DB: SSE/AVX L2 Distance at CPU Speed

Why distance computation is the bottleneck

Approximate nearest neighbor search with HNSW is, at its core, a graph traversal. Starting from a set of entry points, the algorithm follows edges to candidate nodes, evaluates a distance metric against the query vector, and maintains a priority queue of the best k candidates. The traversal logic itself is graph-topology-bound — you cannot skip candidate evaluations without hurting recall. But the distance metric is a different story: it's a tight, stateless inner loop that runs thousands of times per query.

At 768 dimensions (Feather DB's native format for Gemini and OpenAI embeddings), a single L2 distance computation requires 768 subtractions, 768 multiply-accumulates, and a square root. In scalar code on a modern CPU, one such pair takes roughly 200–400ns. With HNSW at M=16 and ef=200 over a 500K-vector store, each search evaluates several thousand candidate pairs. That scalar cost accumulates into the millisecond range fast.

This is the bottleneck that SIMD targets.

What SIMD actually means

SIMD stands for Single Instruction Multiple Data. Instead of applying an arithmetic operation to one float at a time, SIMD instructions operate on a register that holds multiple floats packed side by side. The CPU executes a single instruction, but all lanes compute in parallel.

On x86, there are three generations of SIMD width you care about for vector math:

• SSE (128-bit): Four float32 values per register, four values per instruction. SSE4.2 is available on virtually every x86 CPU manufactured after 2008.
• AVX2 (256-bit): Eight float32 values per register, eight values per instruction. Available on most Intel Haswell (2013) and AMD Ryzen (2017) and later processors — which covers the overwhelming majority of cloud VMs today.
• AVX-512 (512-bit): Sixteen float32 values per register, sixteen values per instruction. Available on Intel Skylake-X, Ice Lake, and AMD EPYC 7003+ series. Common on cloud compute-optimized instances.

For a 768-dim L2 computation in AVX2: instead of 768 scalar multiply-accumulate operations, you need 96 AVX2 FMA (fused multiply-add) operations plus a horizontal reduction. At typical AVX2 throughput, this cuts per-pair L2 time from ~300ns down to ~50–70ns. That's a 4–6× improvement on the raw compute step. The improvement on end-to-end search latency is lower — typically 1.4–1.8× — because HNSW also pays graph traversal and memory access costs that SIMD doesn't touch.

Runtime dispatch: one binary, every CPU

The naive way to ship SIMD code is to compile with -mavx2 and call it a day. The problem: that binary will crash with an illegal instruction on any CPU that doesn't support AVX2. You'd either ship a lowest-common-denominator scalar binary or maintain multiple CPU-specific builds.

Feather DB uses runtime dispatch instead. At process startup, Feather reads the CPUID instruction to detect which SIMD instruction sets are available on the running hardware, then selects the best L2 kernel for the session. The decision tree:

• AVX-512 available → 512-bit L2 kernel (16 floats/op)
• AVX2 available, no AVX-512 → 256-bit L2 kernel (8 floats/op)
• SSE4.2 available, no AVX → 128-bit L2 kernel (4 floats/op)
• No x86 SIMD detected (old hardware, edge cases) → scalar fallback

All four kernels ship in the same feather-db wheel. The dispatch happens once at startup and is zero-overhead for the actual hot path — the selected function pointer is written to a global at initialization and called directly from the HNSW inner loop from that point on.

This means upgrading to a better instance type — say, from an SSE-only VM to an AVX2-capable one — gives you the performance benefit automatically with no code change on your end.

ARM64: the NEON path

Feather DB ships hand-written x86 SIMD kernels for SSE, AVX2, and AVX-512. On ARM64 (Apple Silicon, AWS Graviton, GCP Axion), the approach is different.

ARM has its own SIMD instruction set called NEON (128-bit, 4 × float32 per instruction — analogous to SSE). Rather than maintaining a parallel set of hand-written NEON kernels, Feather's C++17 core is compiled with -O3 -ffast-math on ARM64. Modern compilers — both Clang and GCC — do a reliable job auto-vectorizing tight inner loops like L2 distance using NEON when compiled with these flags. The scalar source is written in a style that guides auto-vectorization: sequential memory access, no loop-carried dependencies, explicit accumulator patterns.

The NEON path is not as precisely tuned as the hand-written AVX2 kernel, but ARM64 out-of-order execution and large register files mean the practical gap is smaller than the architectural width difference suggests. Feather's benchmarks on M-series Apple Silicon are competitive with AVX2 x86 numbers.

ARM64 users don't need to do anything differently — pip install feather-db on Graviton or Apple Silicon pulls the ARM64 wheel and the NEON path activates automatically.

The HNSW inner loop in detail

HNSW search at ef=200 over 500K vectors looks roughly like this at each step of graph traversal:

1. Pop the best candidate from the priority queue (min-heap, O(log ef))
2. Lock the candidate node's neighbor list
3. For each of M=16 neighbors: call the L2 kernel on (query_vec, neighbor_vec)
4. If distance < worst distance in the result set: push to both the candidate queue and result set
5. Repeat until the candidate queue is exhausted or ef distance budget is met

Step 3 is where SIMD lives. At M=16 neighbors per node and ~1,000–2,000 node evaluations for a 500K-vector search at ef=200, the L2 kernel executes somewhere between 16,000 and 32,000 times per query. Shaving 250ns off each call — scalar 300ns vs AVX2 50ns — saves 4–8ms in pure compute. Most of the remaining latency is memory latency (candidate vectors may not be in cache), queue operations, and thread scheduling overhead.

Benchmark numbers

On a 500K-vector store (HNSW M=16, ef=200), measured on x86 hardware with AVX2:

A note on the p99 < p50 number: this is not a typo. The benchmark dataset has variable cluster density. p50 samples a query that lands in a dense region — the search traverses deeper before finding nearest neighbors. p99 happens to hit a sparse region where neighbors are found shallower in the graph. This is a known property of HNSW on non-uniform datasets, not a measurement artifact.

How v0.16.0 changes the SIMD story

Before v0.16.0, every cold start of Feather DB rebuilt the HNSW graph from scratch: it read vectors from disk and re-ran the M-nearest-neighbor link construction for each vector. That construction is also distance-computation-heavy — SIMD was helping there too, but cold-start time was still significant for large stores.

v0.16.0 introduced persisted HNSW graphs. The graph topology (which nodes link to which, at which layer) is serialized to the .feather file alongside the vectors. On startup, Feather deserializes the graph structure directly — no distance computation needed for reconstruction. This means:

• Cold-start reconstruction is now a memory deserialization, not a distance-computation workload.
• SIMD's role is concentrated entirely on the search hot path — which is exactly where it belongs.
• The cold-start time for a 100K-vector store drops from ~940ms (rebuild) to <200ms (deserialization).

SIMD is no longer splitting its benefit between cold load and search. It is 100% search-path optimization now.

Parallel cold-start with FEATHER_LOAD_THREADS

Even with persisted graphs, production deployments that manage many tenant stores still face startup latency at scale. If you're loading 50 tenant stores at service boot, sequential loading adds up.

Feather DB exposes FEATHER_LOAD_THREADS as an environment variable to control how many stores load in parallel:

FEATHER_LOAD_THREADS=8 python main.py

This controls the thread count for parallel HNSW deserialization at startup. Eight threads loading eight stores simultaneously reduces wall-clock startup time proportionally, bounded by disk I/O bandwidth and per-store deserialization overhead. For rolling deployments and serverless environments where restart frequency is high, this is the lever that keeps startup latency from becoming a production constraint.

You can also use it programmatically via the Python API if you prefer to manage the parallelism in application code:

import feather_db as fdb
from concurrent.futures import ThreadPoolExecutor

def load_store(path: str) -> fdb.DB:
    return fdb.DB.open(path, dim=768)

store_paths = [f"/data/{tid}.feather" for tid in active_tenants]
with ThreadPoolExecutor(max_workers=8) as pool:
    dbs = list(pool.map(load_store, store_paths))

SIMD and int8 quantization together

Feather DB v0.15.0 added in-RAM int8 quantization: vectors are stored as signed 8-bit integers with a per-vector scale factor, reducing memory footprint by 1.7× compared to float32 storage. This interacts with SIMD in an interesting way.

The current SIMD kernels operate on float32. When a search is executed against an int8-quantized store, vectors are dequantized to float32 before the L2 kernel runs. The SIMD speedup applies fully to the dequantized computation. But int8 storage has an independent cache-locality benefit: more vectors fit in L1/L2 cache because they're 4× smaller per element. Cache-resident distance computation is faster than cache-miss distance computation regardless of SIMD width — SIMD arithmetic throughput can be saturated only when the operands are available.

The combined effect: int8 quantization reduces the RAM footprint by 1.7×, improves cache hit rates for hot vectors in the HNSW graph, and the SIMD kernel still runs at full throughput on the dequantized float32 values. These are complementary, not competing, optimizations.

Future work on the roadmap: native int8 SIMD kernels that compute L2 directly in 8-bit arithmetic using _mm256_maddubs_epi16 and related instructions. This would compound the two benefits more tightly — fewer bytes fetched from memory, and more elements processed per instruction cycle.

Adaptive index capacity: 7.7× less RAM

SIMD and int8 quantization address compute throughput and vector storage. A third lever addresses HNSW graph structure overhead: adaptive index capacity.

Standard HNSW pre-allocates memory for a fixed maximum number of nodes at construction time. If you build a graph with capacity=1,000,000 but only store 50,000 vectors, you've pre-allocated 20× the memory you actually need. Feather DB's adaptive capacity resizes the underlying graph structures as vectors are added, using a doubling strategy similar to dynamic arrays. This eliminates the pre-allocation waste.

In practice, for stores that don't know their final size at construction time — which is most agent memory workloads — adaptive capacity reduces HNSW graph RAM usage by 7.7× compared to max-capacity pre-allocation. Combined with int8 quantization (1.7×), total memory consumption for a 500K-vector store is substantially lower than a naive HNSW implementation would predict.

Why the C++17 core matters against Python-based alternatives

Several vector databases in the Python ecosystem implement their search logic in Python, using NumPy or PyTorch for vectorized distance computation. These approaches have a fundamental ceiling: the Python GIL (Global Interpreter Lock).

When a Python-based search path calls NumPy for batch distance computation, NumPy releases the GIL and runs in C. But the HNSW traversal logic — the loop that decides which candidates to evaluate next — runs under the GIL in Python. At ef=200 with 2,000 candidate evaluations, that's 2,000 Python function calls and priority queue operations per search, all serialized by the GIL. Concurrent search requests on a multi-core machine end up queuing behind each other at the Python layer.

Feather DB's HNSW implementation is C++17 throughout: graph traversal, priority queue, SIMD distance computation, and result ranking all happen in native code without a Python interpreter in the loop. Python is on the call boundary only — db.search(query_vec, k=10) dips into C++, does the full search in native code, and returns a Python list of results. This means concurrent search calls on a multi-core machine actually run on separate cores without GIL contention.

The result is that Feather DB's latency numbers — 0.19ms p50, 97.2% recall@10 at 500K vectors — are reproducible under concurrent load in a way that pure-Python traversal implementations are not.

What this adds up to

The performance architecture of Feather DB's search path is a stack of complementary decisions:

• SIMD L2 kernels: Runtime-dispatched SSE/AVX/AVX-512 on x86, compiler-auto-vectorized NEON on ARM64. Cuts per-pair L2 compute by 4–6×.
• int8 quantization (v0.15.0): 1.7× memory reduction + cache locality improvement for hot graph nodes.
• Adaptive index capacity: 7.7× less RAM for HNSW graph structure overhead in grow-as-you-go workloads.
• Persisted HNSW graph (v0.16.0): Cold-start time drops from ~940ms to <200ms at 100K vectors; SIMD is now 100% search-path-concentrated.
• Parallel load (FEATHER_LOAD_THREADS): Linear cold-start scaling across tenant stores for high-restart environments.
• C++17 core: No GIL on the search path; concurrent queries scale across cores.

Together, these produce 0.19ms p50 retrieval at 500K vectors on a standard x86 machine — no GPU, no dedicated infrastructure, no server process. That's the number that makes in-process vector search a realistic choice for AI agents that need sub-millisecond memory recall without adding a managed service to the stack.

To get it: pip install --upgrade feather-db. The SIMD path activates automatically based on your CPU. No configuration needed.

GitHub: github.com/feather-store/feather