-
-
Notifications
You must be signed in to change notification settings - Fork 925
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Arrays.sort #3919
Comments
Ah, I see according to this
looks like, openjdk-mirror/jdk7u-jdk@cdf72de Is there an easy way to benchmark the current Qsort.java with the current |
@sri Yes, we introduced our own sort both for performance and to match MRI behaviorally. It would definitely be worth examining whether the rewritten JDK-provided Arrays.sort is now as fast or faster, since we always like deleting code. Are you interested in working on a test patch and benchmarking it? |
@headius Yes, I am totally interested. The deleting part seems easy enough: delete Qsort.java and replace calls to it with Arrays.sort. I can get started on that. Is there a benchmarking data that I can use to benchmark the sorts? Or am I coming up with my own? |
@headius Here is my first attempt at a sort benchmark: https://github.com/sri/jruby-sort-benchmark. They are pretty comparable. The major difference in the total timing is Java's native sort is that it doesn't do much work when the array is sorted or mostly sorted. I recall that was TimSort's benefits. Btw, these benchmarks were run inside of a Ubuntu VM on my Macbook laptop. Here is another run on my machine:
Looking at the overall timing, Arrays.sort seems a bit faster, but not sure I understand this part on with Arrays.sort does pretty badly on the random_ints part:
Any suggestions on what I should do next? Thanks! |
najs work ... you should also include Java version as the numbers might be different on Java 7 vs. 8 |
@sri I think too you may want to add some <16 element data in here as well. Our impl did insertion sort for smaller lists. I expect this new improved code in Java will be as good as us. I think this impl of Sort happened way back in the 1.4 days when it was trivial to micro opt anything to perform better than what they shipped. |
@enebo OK added that (sri/jruby-sort-benchmark@031e618#diff-40e9e3b314e488cae33dd0064545543eR19) and updated the Readme with the latest report: https://github.com/sri/jruby-sort-benchmark/blob/master/README.md. Seems comparable. I varies a little bit each time I run it. I wonder if there is a better way to capture the results. |
Probably would get better results if you ran the whole benchmark in a loop, so the JVM can settle in and JIT/GC things properly. Thanks for looking into this! If the numbers look mostly the same after all our benchmarking, I have no problem making this move. No code is good code :-) |
@headius I've update the Readme (https://github.com/sri/jruby-sort-benchmark/blob/master/README.md) as you suggested (https://github.com/sri/jruby-sort-benchmark/blob/master/sort_benchmark.rb#L31). It seems to be all over the place. Maybe I should run the benkmarks on the same data? I can try that next. Currently, it generates random data for Also, you mentioned about matching MRI behavior -- how can I test that out? |
OK I modified the script to load the same data for both the sorts (see the Readme).
This is from the 5th run: 5th run of Qsort
5th run of Arrays.sort
It'll be great if someone else can run and confirm the results! |
Oh, btw, I had to add this option to the JVM to get it to run without memory errors: |
Java's Arrays.sort more robust and is faster is certain cases. See jruby#3919 and https://github.com/sri/jruby-sort-benchmark.
Fixed by PR. closing. |
Hi, I am getting 'Comparison method violates its general contract!' error while sorting below array: but if remove an nil from the above error then its working fine. Please help in this issue. |
@annuyadav This is expected behavior in Ruby in general, so it has nothing to do with this issue. You need to clean up your data before calling |
@annuyadav - That's correct you need to clean the data for sorting or make comparator method to handle it gracefully to return correct order for nil values. I.e. 0, 1 or -1 |
Is there a reason that JRuby's RubyArray uses it own hand-rolled sort (in Qsort.java) instead of using Java's builtin
Arrays.sort
?I'm looking at these files:
The reason I'm asking: I encountered a bug in a piece of code. A class was overriding the <=> method, but due to a typo, it was doing this comparision:
def <=>(other); self.a <=> other.b; end
instead of
def <=>(other); self.a <=> other.a; end
.Obviously, that is a bug in the application. I didn't notice the bug because
a == b
most of the time. However, recently, there were cases wherea != b
and that's when the bug manifisted. And JRuby's sort got stuck in an infinite loop.When I converted JRuby to use
Arrays.sort
instead ofQsort
and tried it with the bad data, it threw an exception: "Comparison method violates its general contract!".Also, there are other benefits of using
Arrays.sort
:https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TimSort.java#L29
Is there interest in converting RubyArray to use
Arrays.sort
?Thanks!
-Sriram
The text was updated successfully, but these errors were encountered: