High-Performance C++ Vector Index
Vectra is a bare-metal vector search engine engineered from scratch in C++ to demonstrate hardware-sympathetic software design principles. This project explores the fascinating crossover point where algorithmic complexity (O(log N)) meets hardware cache locality benefits (O(N) linear scan).
đź’ˇ The Core Question: When is a "dumb" linear scan faster than a "smart" graph index? Turns out, hardware matters more than you'd think.
🎯 What It Does
Vectra implements two approaches to vector similarity search:
- Brute-force exact search using hand-written AVX2 SIMD intrinsics
- Approximate HNSW (Hierarchical Navigable Small World) graph index
Think of it as building a GPS for high-dimensional data—finding the nearest neighbors among thousands of vectors in milliseconds.
⚡ Technical Deep Dive
| SIMD Acceleration | Custom AVX2 intrinsics (_mm256_fmadd_ps) process 8 floating-point dimensions per CPU cycle → 6x speedup over scalar execution |
| Memory Optimization | Flat, contiguous memory buffers maximize L1/L2 cache hit rates during linear scans |
| HNSW Implementation | Multi-layered skip-list structure built from first principles for sub-linear search complexity on massive datasets |
| Parallelism | OpenMP integration for throughput-oriented batch processing |
đź“Š Performance Benchmarks
Dataset: 10,000 vectors at 1024 dimensions
SCALAR BASELINE
2108ms
SIMD (AVX2)
380ms
⚡ 5.5x faster
SIMD + OpenMP
547ms
Thread overhead at small N
HNSW GRAPH
669ms
Cache misses from pointer chasing
🔍 Key Engineering Insight: For datasets under 100k vectors, cache locality dominates. The AVX2 linear scan outperforms HNSW because it fully saturates memory bandwidth without the random access penalties of graph traversal. This demonstrates that algorithmic complexity isn't everything—hardware characteristics matter immensely.
🌍 Real-World Applications
- Recommendation systems (finding similar products/users)
- Image and document search (semantic similarity)
- ML model serving (nearest neighbor classification)
- Vector databases (alternatives to Pinecone, Weaviate)
📦 Bonus: Header-only library design means zero-dependency integration—just
#include "vectra.hpp" and you're done.
- StackC++20, AVX2 SIMD, OpenMP, HNSW Algorithm
- Sourcehttps://github.com/Shorya-agarwal/Vectra
