DOCSEARCHbyAlgolia
Submit Docs

turbovec

repository·main·Indexed 12 days ago

https://github.com/ryancodrai/turbovec

A high-performance Rust vector index with Python bindings based on the TurboQuant algorithm. It provides 2-bit and 4-bit compressed vector search optimized for SIMD architectures (ARM/x86), offering higher memory efficiency and speed than FAISS. Features include the TurboQuantIndex for basic search, IdMapIndex for stable IDs and O(1) deletions, and hybrid retrieval with filtered search. Version 0.9.0.

Tokens
83.8K
Snippets
205
Records
403
Agent score
95%

What's inside turbovec

  1. Optimize Arm Neoverse V2 kernels using the `vm8` layout

    main

    The vm8 layout is an in-memory arrangement designed to eliminate ZIP instructions in Arm Neoverse V2 kernels. It changes the vector-major arrangement from 4 vectors x 4 byte-groups per 16-byte register to 2 vectors x 8 byte-groups per 16-byte register.

    This layout ensures that vhi and vlo (the even and odd dimension halves) are already in the correct format for SMMLA B operands, allowing the kernel to run without reordering.

    Performance Characteristics:

    • MT (Multi-threaded): ~1.06x speedup.
    • ST (Single-threaded): Performance parity with the standard 4-group layout (provided register pressure is managed by using smaller blocks to prevent spills).
    • Implementation Note: This is an in-memory-only optimization. turbovec continues to store sequential, arch-neutral bytes on disk; the pack::native_transform function handles the conversion to the vm8 layout at load time.

  2. Implement permute-dot scoring for improved search performance

    main

    A high-performance scoring candidate that replaces per-query Look-Up Tables (LUT) with a query-independent, fixed 16-entry permute. This allows the score to be computed as a plain dot product over permuted bytes, which is significantly more efficient on both x86 and ARM architectures.

    Key Benefits:

    • Reduced LUT Traffic: On x86, LUT traffic falls from 128 bytes to 8 bytes per 64 bytes of query. On ARM, it reduces the number of operations per 32 bytes of codes from 10 to 8.
    • Improved Accuracy: Unlike uniform codebooks which trade recall for speed, the permute-dot approach can actually improve recall (e.g., +0.0130 recall@10) because it allows for a full Lloyd-Max codebook.
    • Hardware Acceleration: On x86, it leverages vpdpbusd for unsigned-by-signed multiplication. On ARM, it uses SDOT for signed-by-signed multiplication.

    Implementation Requirements:

    • Layout: Requires a vector-major layout where four adjacent bytes hold dimension pairs (e.g., dimensions {0,1}, {2,3}, etc.).
    • Query Weights: Requires a reordering of the query weight vector at build time to match the interleaved dimension order.
    • Handling Offsets: On x86, because vpdpbusd is unsigned-by-signed, levels must be stored with a +128 offset. The resulting constant term 128 * sum_d q[d] can be subtracted to recover the identical value to the classic path.
    // Conceptual scoring logic for permute-dot
// score = sum_d q[d] * C[code[d]]
// where C is the permuted byte value

  3. Understand x86 thread scaling and core counts

    main

    When benchmarking on x86 (specifically c3-standard-8 instances), be aware of the physical core vs. thread distinction. A c3-standard-8 instance has 4 physical cores with 2 threads per core (SMT).

    Scaling behavior for the kernel on this hardware typically follows this pattern:

    • 1 -> 2 threads: ~1.94x speedup
    • 2 -> 4 threads: ~1.93x speedup
    • 4 -> 8 threads: ~1.04x speedup (no gain from SMT)

    Performance gains from increasing threads beyond the physical core count (4) are negligible for port-bound scans. Do not mistake lack of SMT scaling for a software bug; it is a hardware characteristic.

  4. Understand AMX performance limitations and tile renaming

    main

    While AMX TDPBSSD instructions offer a significantly higher theoretical issue rate compared to AVX-512 vpdpbusd (up to ~6.36x), real-world kernel performance often only reaches parity.

    This limitation is due to the lack of register renaming for tiles in current hardware. Because tileloadd tmm6 cannot begin until the previous tdpbssd using tmm6 has finished, the hardware cannot overlap tile loads with computation.

    In high-dimensional dot products (e.g., 768 dimensions), the operands change too frequently to remain resident in tiles, forcing constant reloads that negate the throughput gains of the AMX unit.

  5. Understand the difference between LUT cap and codebook

    main

    It is important to distinguish between the query-side lookup table (LUT) cap and the database codebook (referenced in P15):

    1. LUT Cap: Quantizes the query-side lookup table. It is computed per query using build_query_neon_lut_from_slice and is not baked into the stored vectors.
    2. Codebook: Refers to the stored vector representations in the database.

    Because the LUT is computed per query, its performance characteristics and quantization effects are distinct from the static codebook.

  6. Understand Async behavior and cancellation

    main

    Async methods (aadd_texts, asimilarity_search, etc.) run index operations in a worker thread via asyncio.to_thread to keep the event loop responsive.

    Cancellation Warning: Cancellation is only partial. If a task is cancelled (e.g., via task.cancel() or a timeout), the Python coroutine returns control promptly, but the underlying worker thread will continue to run the operation to completion.

    Because a cancelled write is an "outcome unknown" state (it may have fully committed or never started), you should make retries idempotent by passing explicit ids.

  7. Benchmark performance considerations for small N

    main

    When evaluating kernel improvements or instruction-count optimizations, the index size N significantly impacts the results due to memory overhead:

    • Small N (e.g., 32,768): The memory term is negligible (~2.1% of cost). At this scale, the measured performance is almost entirely driven by instruction count (98% of the cost). This is the ideal scale for judging instruction-count optimizations.
    • Large N (e.g., 200,000+): The memory term becomes significant (e.g., 12.5% at 200k, saturating around 20% at 400k+). At this scale, instruction-count wins are diluted by memory latency, and improvements should be re-evaluated at 800k to ensure they are true kernel improvements rather than benchmark artifacts.

  8. Understand the relationship between tile size and scan performance

    main

    In turbovec, tile sizes (controlled by constants like MIN_TILE_BLOCKS_NEON and MIN_TILE_BLOCKS_X86) determine the granularity of work assigned to threads.

    As the underlying scan kernels become faster (e.g., through optimizations like SMMLA or prefetching), the relative cost of per-range top-k duplication remains constant. Consequently, larger (coarser) tile sizes become more efficient because they allow workers to stay on longer contiguous runs, amortizing the duplication cost more effectively. This is why both ARM and x86 architectures have moved toward larger tile floors in recent optimizations.

  9. Thread safety and concurrency in TurboQuantVectorStore

    main

    The store is designed for concurrent multi-threaded environments with the following concurrency model:

    Reads

    • Concurrent and Scalable: query and get_nodes do not take a lock. The underlying index releases the GIL during scoring, allowing multiple threads to perform queries in parallel.
    • Consistency: A read overlapping a write will see either the pre-write or post-write state, never a partially written (torn) state.

    Writes

    • Serialized: Operations like add, delete, delete_nodes, clear, and persist are serialized using a per-store lock.
    • Async Support: async_add and other a* variants delegate to the same locked bodies. Concurrent adds use unique handles to ensure no batch is lost to collisions.
    • Persistence: persist is serialized with writes, ensuring it always snapshots a consistent state of the store.

    Limitations

    • No Cross-call Atomicity: A sequence like get_nodes followed by delete_nodes is not atomic; other writers can intervene between calls.
    • No Multi-process Access: The store does not support access from multiple processes.

  10. Thread safety in the Agno store

    main

    The Agno store is designed for concurrent multi-threaded use with the following concurrency model:

    Reads (Concurrent & Scalable)

    Methods that perform reads do not use a lock and can run in parallel. The underlying index releases the GIL during scoring, allowing independent searches from multiple threads to overlap and scale.

    • search
    • Existence checks
    • get_count

    Writes (Serialized)

    Write operations are serialized using a per-store lock. The async_* variants of these methods delegate to the same locked logic.

    • insert
    • upsert
    • delete_by_* family
    • update_metadata
    • drop
    • save

    Important Concurrency Guarantees and Constraints

    • Consistency: A read overlapping a write will see either the pre-write or post-write state, never a partially updated (torn) state. However, under heavy churn, a search might transiently return fewer than the requested limit results if hits are deleted mid-search.
    • Atomicity: There is no cross-call atomicity. A sequence like id_exists followed by delete_by_id is not atomic and can be interleaved by other writers. Batch writes are not atomic relative to readers.
    • External Components: The embedder and reranker are invoked outside the store's lock and must be thread-safe.
    • File Persistence: Multiple stores writing to the same file path is safe. save calls are atomic; the last writer wins, and no caller will see a torn file.
    • Multi-process: Multi-process access is not supported.

  11. Understand why nq=1 (single-query) bypasses tiling constants

    main

    The tiling constants (MIN_TILE_BLOCKS, TILES_PER_THREAD, or k_cap) do not affect single-query (nq=1) performance. Single-query dispatches use a different splitter logic called block_range_stride:

    block_range_stride(n_blocks, n_threads) = (6250 / 8).max(64).next_multiple_of(2) = 782

    This logic assigns exactly one range per worker based on the number of blocks and threads, making it independent of the batched tile path parameters. Consequently, tuning tiling constants for batched queries will not improve nq=1 latency.

  12. Performance measurement rule: Re-derive scores in a single session

    main
    To avoid measurement bias caused by fluctuating machine states (e.g., bimodal frequency states or stale artifacts), never inherit performance scores from previous runs. Always re-derive the 8-cell performance score by building both the main and head branches from source and measuring them in a single, alternating A/B session on the same machine. This ensures that any shift in baseline affects both arms of a pair equally.