Skip to content

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

Closed as not planned

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

  1. ajianaz commented on Sep 13, 2026

    @ajianaz
    ContributorAuthor

    Closing as not-planned based on the measured evidence from #52 (landed in #53):

    • vecq's measured sweet spot is the local/on-device profile, up to roughly 10K vectors. At 10K the single-threaded scan is already interactive: 5-bit default 16.5 ms/q (recall@10 0.932), 4-bit+residual 9.0 ms/q at recall@10 0.951.
    • At 100K a parallel scan would improve latency but not the recall ceiling. The 10th-vs-11th neighbor margin collapses with N (2.0e-3 at 2K vs 3.6e-4 at 100K), so ~1e-3 quantization noise reorders identity-level rankings regardless of scan speed — 6-bit (0.856) and residual (0.836) do not restore the edge either.
    • The levers that matter at server N are width/residual for accuracy and working_dim truncation for scan speed (42 ms/q); a threads-scaling table would not change this positioning, so the work is declined for now rather than kept open.

    If a workload with a pinned server-latency requirement shows up, this can be reopened — the original design notes (rayon chunked scan, per-vector kernels untouched, fixed-order merge, threads > 1 bitwise parity test in the *_matches_scalar_bitwise family) remain the starting point.

  2. added a commit that references this issue on Sep 14, 2026
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