SIMD Acceleration
Relevant source files
The following files were used as context for generating this wiki page:
SIMD (Single Instruction, Multiple Data) acceleration is a core performance feature of EdgeVec, designed to provide high-throughput vector operations in both native and WebAssembly environments. By leveraging parallel processing at the CPU register level, EdgeVec achieves significant speedups for critical distance metrics such as Dot Product, L2 Distance, and Hamming Distance. In supported environments, this architecture allows the database to process multiple elements simultaneously, reaching throughput levels exceeding 2 Gelem/s (Giga-elements per second).
Sources: README.md:120-130, wasm/examples/simd_benchmark.html:360-365
Architecture Overview
The SIMD architecture in EdgeVec is built around 128-bit registers. For floating-point operations, it utilizes f32x4 lanes, allowing four 32-bit floating-point values to be processed in a single CPU cycle. The implementation uses specific instructions like f32x4.mul, f32x4.add, and horizontal sums to optimize the computation of vector distances.
Sources: wasm/examples/simd_benchmark.html:385-405
Vector Register Mapping
| Register Type | Lane Configuration | Data Type | Simultaneous Elements |
|---|---|---|---|
| SIMD128 | 4 x F32 | Float32 | 4 |
| SIMD128 | 128 x Bit | Binary | 128 |
Sources: wasm/examples/simd_benchmark.html:390-405, examples/browser/binary-test.html:300-310
Processing Flow
The following diagram illustrates how vector data is loaded into SIMD registers and processed through parallel lanes.
The system performs parallel multiplication and addition across lanes before reducing the result to a scalar value through a horizontal sum.
Sources: wasm/examples/simd_benchmark.html:395-410
Implementation Backends
EdgeVec utilizes multiple backends to ensure broad compatibility while maximizing performance on supported hardware.
WebAssembly SIMD128
For browser environments, EdgeVec targets the WASM SIMD128 specification. This backend provides approximately 2x speedup over scalar implementations in modern browsers like Chrome (91+), Firefox (89+), and Safari (16.4+ on macOS).
Sources: README.md:135-145, wasm/examples/simd_benchmark.html:565-570
Native SIMD
In native environments, EdgeVec is designed to utilize advanced instruction sets. The implementation incorporates v128 intrinsics and 4-way unrolling to maximize CPU pipeline utilization. Specific implementations for Hamming distance target 64-byte alignment to ensure compatibility with instructions like AVX-512.
Sources: examples/browser/binary-test.html:410-415, tests/simd_spec.rs:430-440
Scalar Fallback
When SIMD instructions are not available (e.g., iOS Safari or older environments), EdgeVec automatically reverts to a portable scalar implementation. This ensures functional correctness at the cost of roughly 50% performance degradation.
Sources: README.md:148-152, tests/simd_spec.rs:325-330
Hamming Distance Acceleration
Binary Quantization (BQ) relies heavily on the Hamming Distance metric. EdgeVec provides a specialized SIMD implementation for this operation, achieving up to 8.75x speedup compared to standard scalar loops.
The accelerated Hamming implementation processes 128 bits per register, performing XOR and population counts (popcount) in parallel across the vector.
Sources: examples/browser/binary-test.html:315-325, tests/simd_spec.rs:40-60
Performance Benchmarks
Native benchmarks demonstrate the efficiency of SIMD unrolling and lane parallelization across various vector dimensions.
| Dimension | Metric | SIMD Latency | Throughput |
|---|---|---|---|
| 128 | Dot Product | 55 ns | 2.3 Gelem/s |
| 768 | Dot Product | 374 ns | 2.1 Gelem/s |
| 1536 | Dot Product | 761 ns | 2.1 Gelem/s |
| 768 | Hamming | 4.5 ns (pair) | 40 GiB/s |
Sources: README.md:120-135, pkg/README.md:120-135
Correctness and Verification
To ensure the SIMD implementation produces bit-identical results to portable code, EdgeVec employs a strict verification suite including:
- Correctness Tests: 12 tests verifying SIMD matches reference implementations for all-zeros, all-ones, and alternating patterns.
- Property Tests: 10,000 randomized test cases per property to verify symmetry, self-distance (always 0), and triangle inequality.
- Alignment Checks: Ensuring vectors maintain 64-byte alignment required for high-performance CPU instructions.
- Boundary Tests: Verifying correct processing at register boundaries (e.g., 32-byte and 64-byte boundaries for AVX2/AVX-512).
Sources: tests/simd_spec.rs:15-35, 220-250, 430-440
SIMD acceleration is fundamental to EdgeVec's goal of bringing high-performance vector search to resource-constrained environments. By combining automated feature detection with optimized intrinsics, the system delivers sub-millisecond search latencies even on large-scale browser-based datasets.
Sources: README.md:125-130, wasm/examples/simd_benchmark.html:365-375