costin commented on PR #16664: URL: https://github.com/apache/lucene/pull/16664#issuecomment-5687267715
Thanks for the review. This is going to be a long answer as my understanding of the algorithm might be incomplete hence trying to articulate my findings :) To reduce memory, I dropped the reverse maps which connected a merged ordinal back to source graph / source ordinal). Now threads "steal" leftover work as (source graph, source ordinal) and look up the merged ordinal through the forward ordMaps, which the sequential path already had. The concurrent path still uses a completion bitset and a steal cursor. Note that both exist only while the graph is being built. Regarding coverage, thanks for pointing that out; the first revision did not enforce it and the reduced beam ran off whichever neighbour happed to be finished; non zero but also non guaranteed. I've fixed that in this PR and traded some speed in the process: before, reduced beam ran off whichever neighbor happened to be finished, this has now changed so that join-set nodes now always take full beam. A remainder node takes reduced beam only if _at least one_ of its leftover neighbors was already inserted with full beam; otherwise it takes full beam as well. Furthermore, entry points are all completed same-source leftover neighbors plus their current layer-0 neighbors in the output graph, not a single finished neighbor. I also noticed leftover neighbors that were not inserted yet, were getting dropped from the candidate set. Leftover vertices are now pre-added on layer 0 before insert starts. On the cheap path those leftover neighbors are unioned into the candidate set after the reduced search. The pruning occurs as usual however there's more "diversity" to choose from. I experimented with waiting for the join set before cheap inserts, and assigning one worker per leftover graph but neither proved successful. The barrier on the join set did not improve the GIST recall and the one worker per leftover graph ended up slowing the force-merge on GIST, since the merge ends up on a single leaf with hundreds of thousands of vectors (and thus becoming a bottleneck) instead of many tiny graphs, effectively no paralleism. For better benchmarking, I used luceneutil instead of 5×100k random. Cohere-1024 was already close in the first review so I've picked GIST-960 500k as is the dataset that actually showed lost quality in my tests. ### Benchmark GIST-960 500k AMD EPYC 7R32 (c5a.2xlarge), JDK 25, M=16, beam=100, 8 workers. 3 runs (table shows the mean). | path | runs | workers | R@10 | R@100 | multi-seg R@10 | force_merge_s | vs concurrent | | --- | --- | --- | --- | --- | --- | --- | --- | | this encoding | 3 | 8 | 0.834 | 0.818 | 0.920 | 52 | ×0.72 | | concurrent full beam | 3 | 8 | 0.835 | 0.821 | 0.926 | 72 | ×1.00 | | sequential leftover | 1 | 1 | 0.816 | 0.797 | — | 170 | — | The results are quite promising and the speed improvement still shows up. Let me know what you think. P.S. I've added sequential leftover however since the bench occurred on a different machine and different number of segments so it's there for recall not speedup. Thanks! -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
