RamakrishnaChilaka opened a new pull request, #15140: URL: https://github.com/apache/lucene/pull/15140
### Description This PR updates LongHeap from a fixed 2-ary heap to a 3-ary heap (the code is generic with n-ary Heap). The change improves cache locality and reduces heap operations for larger heaps, which improves overall query performance. ### Benchmarks Luceneutil has been run with TopN as 1000 (see https://github.com/apache/lucene/pull/14709.) ``` TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value BrowseRandomLabelSSDVFacets 1.59 (13.0%) 1.52 (6.1%) -4.4% ( -20% - 16%) 0.167 HighSloppyPhrase 20.10 (9.3%) 19.52 (6.4%) -2.9% ( -17% - 14%) 0.258 BrowseDateSSDVFacets 0.51 (10.2%) 0.50 (10.4%) -2.7% ( -21% - 20%) 0.415 BrowseRandomLabelTaxoFacets 1.35 (15.1%) 1.32 (3.4%) -2.4% ( -18% - 18%) 0.495 BrowseDateTaxoFacets 1.83 (26.1%) 1.79 (9.0%) -2.3% ( -29% - 44%) 0.705 HighTermTitleSort 28.52 (2.9%) 27.98 (3.9%) -1.9% ( -8% - 5%) 0.080 BrowseDayOfYearTaxoFacets 1.88 (23.8%) 1.85 (9.3%) -1.6% ( -27% - 41%) 0.777 HighIntervalsOrdered 5.14 (6.0%) 5.08 (5.8%) -1.2% ( -12% - 11%) 0.502 LowSpanNear 24.52 (6.3%) 24.29 (7.8%) -0.9% ( -14% - 14%) 0.676 AndHighHighDayTaxoFacets 19.61 (4.6%) 19.48 (5.2%) -0.7% ( -10% - 9%) 0.673 BrowseMonthTaxoFacets 1.96 (6.1%) 1.94 (6.3%) -0.6% ( -12% - 12%) 0.748 HighTermTitleBDVSort 6.95 (5.0%) 6.92 (5.8%) -0.5% ( -10% - 10%) 0.785 TermDTSort 51.57 (4.6%) 51.36 (5.1%) -0.4% ( -9% - 9%) 0.787 LowIntervalsOrdered 72.91 (12.9%) 72.63 (15.0%) -0.4% ( -25% - 31%) 0.933 MedIntervalsOrdered 4.67 (5.2%) 4.66 (6.4%) -0.3% ( -11% - 11%) 0.854 AndHighMedDayTaxoFacets 27.57 (3.5%) 27.60 (3.9%) 0.1% ( -7% - 7%) 0.912 MedSloppyPhrase 11.49 (2.9%) 11.54 (2.7%) 0.4% ( -5% - 6%) 0.649 AndHighLow 676.59 (5.6%) 680.20 (4.4%) 0.5% ( -8% - 11%) 0.738 HighTermDayOfYearSort 48.85 (6.8%) 49.18 (6.3%) 0.7% ( -11% - 14%) 0.748 LowPhrase 48.95 (4.5%) 49.52 (4.9%) 1.2% ( -7% - 11%) 0.429 OrHighMedDayTaxoFacets 4.62 (7.1%) 4.68 (5.5%) 1.3% ( -10% - 14%) 0.512 Respell 21.00 (8.2%) 21.28 (6.3%) 1.3% ( -12% - 17%) 0.566 LowSloppyPhrase 18.02 (8.2%) 18.39 (6.0%) 2.0% ( -11% - 17%) 0.373 HighPhrase 26.79 (3.0%) 27.35 (2.5%) 2.1% ( -3% - 7%) 0.015 BrowseDayOfYearSSDVFacets 2.44 (13.5%) 2.49 (10.8%) 2.2% ( -19% - 30%) 0.565 IntNRQ 124.80 (2.6%) 127.62 (2.7%) 2.3% ( -2% - 7%) 0.006 MedSpanNear 71.89 (3.3%) 73.63 (2.9%) 2.4% ( -3% - 8%) 0.014 range 2418.26 (7.8%) 2481.43 (6.2%) 2.6% ( -10% - 18%) 0.242 Fuzzy2 32.82 (6.2%) 33.72 (7.9%) 2.7% ( -10% - 17%) 0.222 PKLookup 124.86 (9.3%) 128.39 (9.8%) 2.8% ( -14% - 24%) 0.350 HighTermMonthSort 109.23 (10.0%) 112.66 (11.5%) 3.1% ( -16% - 27%) 0.355 HighSpanNear 12.77 (10.1%) 13.23 (7.0%) 3.6% ( -12% - 23%) 0.189 MedTermDayTaxoFacets 23.20 (7.2%) 24.08 (3.9%) 3.8% ( -6% - 16%) 0.039 IntSet 319.40 (7.9%) 332.99 (7.0%) 4.3% ( -9% - 20%) 0.070 OrHighNotHigh 63.45 (12.0%) 66.16 (11.1%) 4.3% ( -16% - 31%) 0.242 OrNotHighLow 653.14 (4.5%) 681.44 (5.5%) 4.3% ( -5% - 15%) 0.007 Fuzzy1 33.92 (9.6%) 35.47 (8.8%) 4.6% ( -12% - 25%) 0.116 AndHighHigh 72.73 (11.4%) 76.10 (12.0%) 4.6% ( -16% - 31%) 0.210 Wildcard 162.20 (3.9%) 169.92 (3.7%) 4.8% ( -2% - 12%) 0.000 MedPhrase 105.75 (5.3%) 111.28 (6.2%) 5.2% ( -5% - 17%) 0.004 AndHighMed 300.00 (3.5%) 317.31 (3.5%) 5.8% ( -1% - 13%) 0.000 OrHighHigh 81.99 (10.0%) 86.95 (11.8%) 6.1% ( -14% - 30%) 0.080 OrNotHighHigh 94.63 (8.0%) 100.89 (8.5%) 6.6% ( -9% - 25%) 0.011 OrNotHighMed 156.93 (5.2%) 167.46 (5.7%) 6.7% ( -3% - 18%) 0.000 OrHighNotLow 109.84 (12.4%) 118.15 (13.7%) 7.6% ( -16% - 38%) 0.067 Prefix3 298.72 (4.6%) 321.96 (4.8%) 7.8% ( -1% - 17%) 0.000 BrowseMonthSSDVFacets 2.46 (8.4%) 2.66 (17.5%) 8.0% ( -16% - 37%) 0.066 OrHighMed 135.37 (5.3%) 147.30 (8.0%) 8.8% ( -4% - 23%) 0.000 HighTerm 169.55 (10.9%) 189.84 (15.3%) 12.0% ( -12% - 42%) 0.004 OrHighLow 182.04 (8.5%) 203.99 (10.4%) 12.1% ( -6% - 33%) 0.000 MedTerm 257.50 (9.8%) 297.02 (14.4%) 15.4% ( -8% - 43%) 0.000 OrHighNotMed 215.73 (6.5%) 249.31 (9.1%) 15.6% ( 0% - 33%) 0.000 LowTerm 411.97 (8.6%) 481.02 (13.4%) 16.8% ( -4% - 42%) 0.000 ``` -- 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]
