From: Kornelius Kalnbach <murphy@...>
Date: 2009-02-07T00:56:15+09:00
Subject: [ruby-core:21890] Re: [Feature #1089] Stable sorting for sort and sort_by

Charles Oliver Nutter wrote:
> Your two cases make sense to me, and are similar to reasons I gave
> for us not to abandon a stable sort. I eventually overruled myself,
> however, after more published benchmark results put us slower than
> Ruby 1.8 for array sorts. Perception is important; more important
> than sort stability, I have not decided :)
actually, I'd prefer the feature of "stable sort" over "fast sort". I
use Ruby for convenience, not for speed. still: what is the tradeoff?

> I guess we ended up going with an unstable sort because it did make a
>  difference; I think keeping the sort stable makes it harder to
> combine allgorithms for different classes of list (partially sorted,
> reversed, randomized) which seemed to be key to matching MRI's sort
> performance. I raised a concern about stability, but we figured if
> nobody had seen issues in MRI nobody would care if JRuby's sort
> became unstable.
it's critical how much the difference was...if we get stability for,
say, 15% more sort time, I'd buy it. if even the best alogrithms are 50x
slower, I'd abandon my request. but I don't think this is the case; more
investigation follows.

anything that performs better than this would be appreciated (stable
sort is roughly 50 times slower):

time ruby19 -e 'Array(1..1000000).shuffle.sort'
real	0m0.529s
real	0m0.164s (without sorting)

i = 0; Array(1..1000000).shuffle.sort_by { |o| [o, i += 1] }
real	0m18.742s

Array(1..1000000).shuffle.sort_by.with_index { |o, i| [o, i] }
real	0m18.430s

Array(1..1000000).shuffle.sort_by.with_index { |*a| a }
real	0m18.383s

> Perhaps this is a case where having the fast unstable sort support a 
> slower, possibly ruby-based, stable sort is the way to go. In general
> a ruby-based sort performs pretty well on both JRuby and Ruby 1.9.
> Here's some recent results:
> 
> http://rubyurl.com/3d87
> 
> It certainly wouldn't be as fast as a native sort, but perhaps that's
>  not a big deal?
it is...using their benchmark mergesort:
-rmergesort -e 'mergesort Array(1..1000000).shuffle'
real	0m18.066s

wow, that's faster than the sort_by approach :D my own in-place merge
sort version (based on the one Java uses internally for Object[]) is
even faster:

-rmerge_sort -e 'Array(1..1000000).shuffle.merge_sort!'
real	0m10.401s

so, the best I currently get with pure Ruby is about 30x. I'm sure we
can do better with a Java or C implementation.

let's see timsort now. some Python 2.5 benchmarks:

time python2.5 -c 'from random import shuffle; list = range(1000000);
shuffle(list); sorted(list)'
real	0m2.432s
real	0m1.191s (without sorting)

so I guess timsort takes about 1.3s, which would be about 3.5x slower
than Ruby's sort. this is not very nice; but 1.3s are still much better
than 10s!

so, maybe stable sort should be optional. what options do we have?

- compiler switch, global variable and such; we don't want that

- a new method, like Enumerable#stable_sort. my code example would
  become:

  files.stable_sort_by(&:size).reverse.stable_sort_by(&:type)

- an optional parameter to sort and sort_by:

     enum.sort(stable=false)                   -> array
     enum.sort(stable=false) {| a,b | block }  -> array
     enum.sort_by(stable=false) {| obj | block }  -> array

     array.sort!(stable=false)                   -> array
     array.sort!(stable=false) {| a,b | block }  -> array
     array.sort_by!(stable=false) {| obj | block }  -> array

  I know boolean parameters are not nice, but we already use them in
  Object#methods. my code example would become:

  files.sort_by(true, &:size).reverse.sort_by(true, &:type)

none of these options feels like Ruby to me. I hope somebody has another
idea.

[murphy]