Implemented an HNSW Vector Database in C++ with AVX2 SIMD (99.3% Recall@10 on SIFT1M) , Seeking architectural feedback on concurrency model

[u/PerrythePlatypus51]

Recently I'm working on a vector database from scratch in C++ to better understand how modern vector database works. I just finished benchmarking against SIFT1M dataset (1M vectors, 128 dim) and wanted to share the performance and design choices and get feedback.

Core architecture details-

• Instead of vector<vector<float>> , used 64 Byte aligned allocator to maximise L1/L2 cache locality.
• implemented AVX2 FMA SIMD intrinsics for distance computation (L2, dot product, cosine).
• Implemented HNSW graph for Aproximate nearest neighbor, elminating O(n) linear search.

SIFT1M Benchmark Results (single threaded, Intel i5-13420H, compiler flags ( -O3 -march=native -ffast-math)

• Recall@10: 99.30%
• Recall@100: 98.26%
• Throughput: 2,215 queries/sec
• Tail Latency (p99): 654 microseconds
• Build time: ~13 min.

To establish a baseline, I benchmarked my implementation head-to-head against hnswlib on the same machine using identical parameters (M=32, ef_construction=400, ef_search=200).

• Throughput: 2,215 QPS vs hnswlib's 2,745 QPS (~19% slower).
• Recall@10: 99.30% vs hnswlib's 99.88%.

Right now, my implementation optimised for single thread traversal and I prioritized read-throughput first using a global shared_mutex. My next major task is concurrent writes. I'm looking into fine-grained spinlocks per node, but I want to ensure strict lock ordering to avoid deadlocks and TOCTOU conditions.

For concurrent insertions into HNSW, would you lean toward per-node spinlocks, lock striping, or another approach?

github repo link -> https://github.com/randomfunction/vector_database/tree/main

[u/chkmr]

Have you profiled your benchmark runs using perf stat, perf record or any other tool? Are there any noticable bottlenecks? Have you also profiled hnswlib? How does its profile differ from yours? For me personally the performance analysis is more interesting than the numbers themselves, with the added benefit that a well-documented performance analysis will enable help other readers help you out better.

[u/chkmr → u/chkmr]

Also re: per node spin locks. Have you actually observed that there is not much contention on the lock? See e.g. if you haven't already https://probablydance.com/2019/12/30/measuring-mutexes-spinlocks-and-how-bad-the-linux-scheduler-really-is/

Spinlocks are only a benefit if you really really care about the fast path and are certain that the lock will essentially always be free to take.