gf2121 commented on PR #12800: URL: https://github.com/apache/lucene/pull/12800#issuecomment-1818846591
Thanks for feedback @jpountz ! > but this seems to come with greater heap requirements as well? Yes, +1 for the concern. The original approach requires at most `ArrayUtil.oversize(n/8, 4)` extra tmp slots while the lsb sorter requires `n`. I also considered the `MSBRadixSorter` (not need tmp slots) but it is 5x slower the LSB sorter. I'll think more about this and try to find out the better trade-off. <details><summary> msb benchmark result </summary> ``` Benchmark (bit) (order) (size) Mode Cnt Score Error Units DocSorterBenchmark.lsbSorter 24 natural 100000 thrpt 5 2.066 ± 0.074 ops/ms DocSorterBenchmark.lsbSorter 24 reverse 100000 thrpt 5 2.086 ± 0.048 ops/ms DocSorterBenchmark.lsbSorter 24 random 100000 thrpt 5 2.073 ± 0.015 ops/ms DocSorterBenchmark.lsbSorter 24 partial 100000 thrpt 5 2.072 ± 0.010 ops/ms DocSorterBenchmark.lsbSorter 24 natural_exception 100000 thrpt 5 2.074 ± 0.037 ops/ms DocSorterBenchmark.lsbSorter 24 reverse_exception 100000 thrpt 5 2.079 ± 0.064 ops/ms DocSorterBenchmark.lsbSorter 31 natural 100000 thrpt 5 1.641 ± 0.030 ops/ms DocSorterBenchmark.lsbSorter 31 reverse 100000 thrpt 5 1.646 ± 0.013 ops/ms DocSorterBenchmark.lsbSorter 31 random 100000 thrpt 5 1.650 ± 0.014 ops/ms DocSorterBenchmark.lsbSorter 31 partial 100000 thrpt 5 1.640 ± 0.027 ops/ms DocSorterBenchmark.lsbSorter 31 natural_exception 100000 thrpt 5 1.641 ± 0.008 ops/ms DocSorterBenchmark.lsbSorter 31 reverse_exception 100000 thrpt 5 1.642 ± 0.019 ops/ms DocSorterBenchmark.msbSorter 24 natural 100000 thrpt 5 0.481 ± 0.007 ops/ms DocSorterBenchmark.msbSorter 24 reverse 100000 thrpt 5 0.422 ± 0.005 ops/ms DocSorterBenchmark.msbSorter 24 random 100000 thrpt 5 0.468 ± 0.003 ops/ms DocSorterBenchmark.msbSorter 24 partial 100000 thrpt 5 0.432 ± 0.003 ops/ms DocSorterBenchmark.msbSorter 24 natural_exception 100000 thrpt 5 0.464 ± 0.010 ops/ms DocSorterBenchmark.msbSorter 24 reverse_exception 100000 thrpt 5 0.422 ± 0.003 ops/ms DocSorterBenchmark.msbSorter 31 natural 100000 thrpt 5 0.565 ± 0.013 ops/ms DocSorterBenchmark.msbSorter 31 reverse 100000 thrpt 5 0.442 ± 0.009 ops/ms DocSorterBenchmark.msbSorter 31 random 100000 thrpt 5 0.447 ± 0.002 ops/ms DocSorterBenchmark.msbSorter 31 partial 100000 thrpt 5 0.428 ± 0.002 ops/ms DocSorterBenchmark.msbSorter 31 natural_exception 100000 thrpt 5 0.518 ± 0.011 ops/ms DocSorterBenchmark.msbSorter 31 reverse_exception 100000 thrpt 5 0.444 ± 0.007 ops/ms DocSorterBenchmark.timSorter 24 natural 100000 thrpt 5 50.030 ± 0.728 ops/ms DocSorterBenchmark.timSorter 24 reverse 100000 thrpt 5 1.005 ± 0.007 ops/ms DocSorterBenchmark.timSorter 24 random 100000 thrpt 5 0.077 ± 0.001 ops/ms DocSorterBenchmark.timSorter 24 partial 100000 thrpt 5 0.238 ± 0.014 ops/ms DocSorterBenchmark.timSorter 24 natural_exception 100000 thrpt 5 2.640 ± 0.077 ops/ms DocSorterBenchmark.timSorter 24 reverse_exception 100000 thrpt 5 0.775 ± 0.007 ops/ms DocSorterBenchmark.timSorter 31 natural 100000 thrpt 5 49.712 ± 2.189 ops/ms DocSorterBenchmark.timSorter 31 reverse 100000 thrpt 5 2.511 ± 0.165 ops/ms DocSorterBenchmark.timSorter 31 random 100000 thrpt 5 0.076 ± 0.001 ops/ms DocSorterBenchmark.timSorter 31 partial 100000 thrpt 5 0.239 ± 0.012 ops/ms DocSorterBenchmark.timSorter 31 natural_exception 100000 thrpt 5 2.494 ± 0.097 ops/ms DocSorterBenchmark.timSorter 31 reverse_exception 100000 thrpt 5 1.180 ± 0.021 ops/ms ``` </details> -- 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-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
