From: "MartinBosslet (Martin Bosslet)" Date: 2012-04-07T07:36:13+09:00 Subject: [ruby-core:44169] [ruby-trunk - Feature #6256] Slightly improve ruby_qsort performance Issue #6256 has been updated by MartinBosslet (Martin Bosslet). File rubyqisort.patch added I added a patch, together with benchmarks. Here's the results on my machine without the optimization: $ ruby driver.rb -e ruby -p bm_sort -r 10 ----------------------------------------------------------- benchmark results: name ruby 2.0.0dev (2012-04-05 trunk 35241) [x86_64-linux] sort_int 0.378 sort_int_custom 0.327 sort_int_rev 0.111 sort_int_sorted 0.100 sort_str_rnd 0.107 and here with the patch applied: $ ruby driver.rb -e ruby -p bm_sort -r 10 ----------------------------------------------------------- benchmark results: name ruby 2.0.0dev (2012-04-05 trunk 35241) [x86_64-linux] sort_int 0.367 sort_int_custom 0.332 sort_int_rev 0.229 sort_int_sorted 0.218 sort_str_rnd 0.106 From running them several times, my impression is that it's definetely faster for sorting Fixnums, but there's no real improvement as soon as we compare Strings or use a custom comparison, as I assumed before, the costlier the comparison becomes the less advantage we get, at least that's how it seemed in my tests. Another fact is that we definitely lose in the "already ordered" cases. The existing Quicksort does a linear check for "ordered regions" already, to prevent worst case behavior. I actually had to take those out in order to get the improvement with Insertion Sort. If I put them back in, then the whole advantage is gone, and the "optimized" version runs slightly slower than the old version. Applying just one final Insertion Sort instead of sorting each sub problem below the cut off with it also turned out to be slightly slower unlike in my test extension. I'm confused to see only minimal improvements, when implementing a "textbook" Quicksort with the same optimization, the benefits are much more obvious. I assume there's more optimization in Ruby's current algorithm that would no longer be needed with additional Insertion Sort, maybe you have some ideas? Or maybe there's also room to improve my Insertion Sort? This is as fast as I could get it right now, at least in theory it should be possible to improve it. ---------------------------------------- Feature #6256: Slightly improve ruby_qsort performance https://bugs.ruby-lang.org/issues/6256#change-25691 Author: MartinBosslet (Martin Bosslet) Status: Assigned Priority: Low Assignee: MartinBosslet (Martin Bosslet) Category: core Target version: 2.0.0 Hi all, I think I may have found a way to slightly improve the performance of ruby_qsort. Quicksort running time is slightly decreased if the recursion depth (or in our case, rather iteration depth) is bounded by leaving sub problems larger than or equal to some cutoff bound k untouched and running Insertion Sort on these small sub problems to finalize the sorting. I experimented with this, but to no avail, only marginal improvements if any. Then I remembered that instead of running Insertion Sort on each sub problem, it is equivalent in terms of running time to run one single Insertion Sort on the whole nearly sorted array as a final step. And in practice, this turns out to run faster than without the optimization. In my tests, execution time dropped to about 95% on average with an optimal cutoff (64-bit Fedora 15) [1]. Now this ain't the world - but it is faster, and I could very well imagine that there is still room for improving my code. In my tests, the optimal cutoff seems to be ~13 for Integers and ~8 for Strings and Symbols. I imagine the more costly the comparisons, the lower will be the optimal cutoff. I've tested only on 64 Bit yet, but I will do so for 32 Bit, too. If it turns out that this runs faster regardless of the architecture in use, with an optimal cutoff yet to be determined, do you think this would be a useful addition? I have attached a C extension for testing and discussing, it's mostly a one-to-one copy of the code in util.c. I just added mmassign and insertion_sort plus the few lines that respect the cutoff in rqsort (had to rename it, otherwise it would collide with the real "ruby_qsort"). -Martin [1] https://github.com/emboss/hybridsort/blob/master/hybrid-sort-results -- http://bugs.ruby-lang.org/