Skip to content

perf: parallel scan path (deterministic merge, threads-scaling benchmark) #51

Description

@ajianaz

What

Add an optional parallel scan path to VecqIndex / VecqView search: partition the vector list into contiguous chunks, score each chunk in parallel (the existing per-vector kernels stay untouched), and merge the partial top-k results in a fixed, deterministic order.

Why

At server-scale N the single-threaded linear scan is the only remaining architectural gap: measured 3.21 ms/query at 2K vectors (5-bit default) extrapolates linearly to roughly ~160 ms/query at 100K vectors — that figure is an extrapolation, not a measurement, which is exactly why the companion benchmark issue exists. Multi-tenant deployments such as uteke-cloud query per-workspace subsets (small N), but global-scale workloads need a parallel path for vecq to stay usable as a server engine. Combined with cascade search (#22) and Matryoshka working_dim truncation (#24), threading is the lever that could plausibly land 100K-vector search in the ~5–15 ms/query range — server-grade, while keeping the 4.8× storage advantage and zero-dependency profile.

Testing

  • Bit-identity must hold at any thread count: chunk scores use the existing kernels unchanged; the merge uses a fixed association order (same discipline as the NEON/scalar/AVX2 parity tests). Add a threads > 1 parity test to the *_matches_scalar_bitwise family.
  • Standard merge gate: full test suite + re-run real / vs_usearch / widths; recall tables must stay bit-identical to the BENCHMARK.md baseline at threads = 1.
  • Publish a threads-scaling table (1/2/4/8 cores, aarch64 + x86_64) in BENCHMARK.md; update BENCHMARK.md in the same commit as the perf change.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions