[PR] perf(vamana): look up PQ build distances in a per-search table [paimon-vector-index]

["wombatu-kun (via GitHub)" <gi...@apache.org>]

wombatu-kun opened a new pull request, #112:
URL: https://github.com/apache/paimon-vector-index/pull/112

   ## What
   
   The PQ-guided Vamana build (`DiskAnnBuildDistance::ProductQuantized`, the default) scores every candidate of a build search as a sum of m lookups `centroid_distances[sub][candidate_code][query_code]` in an m x 256 x 256 table (8 MiB at m = 32, 60 MiB at m = 240). The query, the node being inserted, is fixed for the whole search, so these lookups walk table columns with a 1 KiB stride, and lookups for different candidate codes never share a cache line.
   
   This PR copies, once per search, the m rows selected by the query's codes into a per-worker m x 256 buffer (32 KiB at m = 32, 240 KiB at m = 240) and scores all candidates from it. The table is symmetric, so every value and the summation order stay the same: graphs and index files are bit-identical, and every index file in the benchmark below has the same SHA-256 before and after the change. The build memory estimate now includes the buffers.
   
   ## Why it is faster
   
   Before the change one search could touch up to m x 16 KiB of the table (512 KiB at m = 32, 3.75 MiB at m = 240), and twelve concurrent searches up to 6 MiB and 45 MiB, competing with the graph, codes and vectors for 256 KiB of L2 per core and a 9 MiB L3. After it a search reads only its m KiB buffer. This is consistent with the gain growing with m in the benchmark below (1.41x at m = 32, 3.00x at m = 240). The cache behaviour is reasoned from the access pattern; I did not collect cache-miss counters.
   
   ## Benchmark
   
   i7-8750H (6 cores / 12 threads, 9 MiB L3), `performance` power profile, 12 threads, `DiskAnnBuildParams::default()` with 8-bit PQ (m = d / 4). "Vamana passes" is the time of both graph passes, "index write" the time of the whole `write_diskann_index_with_stats`. SIFT1M values are the mean of two runs each, interleaved main, PR, PR, main (spread under 1%); GIST1M is one run each.
   
   | Dataset | Stage | main (s) | this PR (s) | Change |
   |---|---|---|---|---|
   | SIFT1M (d = 128, m = 32) | Vamana passes | 210.2 | 148.9 | -29.2% (1.41x) |
   | SIFT1M (d = 128, m = 32) | Index write | 224.0 | 162.6 | -27.4% (1.38x) |
   | GIST1M (d = 960, m = 240) | Vamana passes | 2746.2 | 914.6 | -66.7% (3.00x) |
   | GIST1M (d = 960, m = 240) | Index write | 2839.0 | 1008.4 | -64.5% (2.82x) |
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] perf(vamana): look up PQ build distances in a per-search table [paimon-vector-index]

["JingsongLi (via GitHub) via issues" <is...@paimon.apache.org>]

JingsongLi merged PR #112:
URL: https://github.com/apache/paimon-vector-index/pull/112


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org