From: "duerst (Martin Dürst)" Date: 2012-04-05T19:04:19+09:00 Subject: [ruby-core:44144] [ruby-trunk - Feature #6256] Slightly improve ruby_qsort performance Issue #6256 has been updated by duerst (Martin D��rst). I haven't looked at the sources, but this exact optimization is very well known in the literature, and I'm showing it to my students in a lecture on algorithms and data structures every year (see e.g. http://www.sw.it.aoyama.ac.jp/2011/DA/programs/6qsort.rb, sorry, comments are in Japanese). I'm quite a bit surprised that this optimization isn't yet made in Ruby. The only potential problem is that the final insertion sort may mask errors in the quicksort, but as Ruby's current quicksort is working well, that should not be a problem. And a cutoff of about 10 is what's generally claimed to be a good value. The speed gains/losses when shifting the cutoff value by just a little bit shouldn't be very big. So I'm definitely encouraging adoption of this improvement. ---------------------------------------- Feature #6256: Slightly improve ruby_qsort performance https://bugs.ruby-lang.org/issues/6256#change-25667 Author: MartinBosslet (Martin Bosslet) Status: Open Priority: Low Assignee: 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/