gsmiller commented on issue #15934: URL: https://github.com/apache/lucene/issues/15934#issuecomment-4184893809
I made the binary search approach [a bit smarter](https://github.com/apache/lucene/pull/15933/changes/73eee9fb6c1438d377ced417294db354e8b81ba2) and reran benchmarks. Providing new results and an AI-generated summary: ``` Benchmark (numDocIds) (numLeaves) Mode Cnt Score Error Units PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100 5 thrpt 15 1444.092 ± 79.023 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100 10 thrpt 15 1209.812 ± 145.064 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100 20 thrpt 15 1141.308 ± 78.308 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100 50 thrpt 15 885.316 ± 63.670 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100 200 thrpt 15 549.317 ± 31.922 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 1000 5 thrpt 15 101.334 ± 6.847 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 1000 10 thrpt 15 101.028 ± 2.527 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 1000 20 thrpt 15 99.230 ± 7.228 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 1000 50 thrpt 15 97.103 ± 7.316 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 1000 200 thrpt 15 79.708 ± 2.740 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 10000 5 thrpt 15 5.995 ± 0.387 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 10000 10 thrpt 15 6.134 ± 0.801 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 10000 20 thrpt 15 6.402 ± 0.561 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 10000 50 thrpt 15 5.425 ± 0.267 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 10000 200 thrpt 15 5.632 ± 0.548 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100000 5 thrpt 15 0.262 ± 0.005 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100000 10 thrpt 15 0.247 ± 0.008 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100000 20 thrpt 15 0.262 ± 0.008 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100000 50 thrpt 15 0.261 ± 0.005 ops/ms PartitionByLeafBenchmark.arraysSortBinarySearchPartition 100000 200 thrpt 15 0.257 ± 0.008 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100 5 thrpt 15 1194.994 ± 78.870 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100 10 thrpt 15 1068.638 ± 52.030 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100 20 thrpt 15 805.194 ± 42.816 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100 50 thrpt 15 1198.694 ± 104.503 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100 200 thrpt 15 741.903 ± 40.591 ops/ms PartitionByLeafBenchmark.arraysSortOnly 1000 5 thrpt 15 80.241 ± 3.126 ops/ms PartitionByLeafBenchmark.arraysSortOnly 1000 10 thrpt 15 83.524 ± 5.633 ops/ms PartitionByLeafBenchmark.arraysSortOnly 1000 20 thrpt 15 101.379 ± 1.832 ops/ms PartitionByLeafBenchmark.arraysSortOnly 1000 50 thrpt 15 98.004 ± 4.570 ops/ms PartitionByLeafBenchmark.arraysSortOnly 1000 200 thrpt 15 91.082 ± 3.440 ops/ms PartitionByLeafBenchmark.arraysSortOnly 10000 5 thrpt 15 5.556 ± 0.474 ops/ms PartitionByLeafBenchmark.arraysSortOnly 10000 10 thrpt 15 5.763 ± 0.511 ops/ms PartitionByLeafBenchmark.arraysSortOnly 10000 20 thrpt 15 5.240 ± 0.415 ops/ms PartitionByLeafBenchmark.arraysSortOnly 10000 50 thrpt 15 5.410 ± 0.390 ops/ms PartitionByLeafBenchmark.arraysSortOnly 10000 200 thrpt 15 5.632 ± 0.530 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100000 5 thrpt 15 0.252 ± 0.005 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100000 10 thrpt 15 0.261 ± 0.004 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100000 20 thrpt 15 0.258 ± 0.002 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100000 50 thrpt 15 0.255 ± 0.006 ops/ms PartitionByLeafBenchmark.arraysSortOnly 100000 200 thrpt 15 0.257 ± 0.010 ops/ms ``` Both approaches use Arrays.sort for sorting. The difference is only in the partition step: - **Linear**: scan sorted doc IDs, advance leaf pointer on boundary crossings - **BinarySearch**: iterate leaf boundaries, binary search for each in sorted doc IDs (with O(1) empty-leaf skip and early termination) | numDocIds | numLeaves | Linear (ops/ms) | BinarySearch (ops/ms) | Difference | |-----------|-----------|------------------|-----------------------|------------| | 100 | 5 | 1,195 | 1,444 | BS +21% ✅ | | 100 | 10 | 1,069 | 1,210 | BS +13% ✅ | | 100 | 20 | 805 | 1,141 | BS +42% ✅ | | 100 | 50 | 1,199 | 885 | Linear +35% ❌ | | 100 | 200 | 742 | 549 | Linear +35% ❌ | | 1,000 | 5 | 80 | 101 | BS +26% ✅ | | 1,000 | 10 | 84 | 101 | BS +21% ✅ | | 1,000 | 20 | 101 | 99 | ~tie | | 1,000 | 50 | 98 | 97 | ~tie | | 1,000 | 200 | 91 | 80 | Linear +14% ❌ | | 10,000 | 5 | 5.6 | 6.0 | ~tie | | 10,000 | 10 | 5.8 | 6.1 | ~tie | | 10,000 | 20 | 5.2 | 6.4 | ~tie | | 10,000 | 50 | 5.4 | 5.4 | ~tie | | 10,000 | 200 | 5.6 | 5.6 | ~tie | | 100,000 | 5 | 0.252 | 0.262 | ~tie | | 100,000 | 10 | 0.261 | 0.247 | ~tie | | 100,000 | 20 | 0.258 | 0.262 | ~tie | | 100,000 | 50 | 0.255 | 0.261 | ~tie | | 100,000 | 200 | 0.257 | 0.257 | ~tie | Key observations: - At 10K+ doc IDs, the sort dominates — partition strategy makes no measurable difference. - At small doc counts with few leaves (the common search case: top-50/100, 5-20 segments), binary search is 13-42% faster. - At small doc counts with many leaves (50+), linear scan wins because binary search still iterates leaf boundaries even with the empty-leaf optimization. - In absolute terms, all differences are sub-microsecond. -- 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]
