jdk
jdk copied to clipboard
openjdk
JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
Sorting:
- adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K)
- fix tryMergeRuns() to better handle case when the last run is a single element
- minor javadoc and comment changes
Testing:
- add new data inputs in tests for sorting
- add min/max/infinity values to float/double testing
- add tests for radix sort
Progress
- [ ] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
- [x] Change must not contain extraneous whitespace
- [x] Commit message must refer to an issue
Error
⚠️ OCA signatory status must be verified
Issue
- JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
Reviewing
Using git
Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk pull/3938/head:pull/3938
$ git checkout pull/3938
Update a local copy of the PR:
$ git checkout pull/3938
$ git pull https://git.openjdk.org/jdk pull/3938/head
Using Skara CLI tools
Checkout this PR locally:
$ git pr checkout 3938
View PR using the GUI difftool:
$ git pr show -t 3938
Using diff file
Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/3938.diff
Congratulation, what an amazing job !
DPQS is now 50% faster in average but 2.5 times faster (rms) my favorite !!
Finally OOME is now handled to let sort work under low-mem conditions !
I will work on more benchmarks for long/float/double types.
Laurent
Hi @iaroslavski, welcome to this OpenJDK project and thanks for contributing!
We do not recognize you as Contributor and need to ensure you have signed the Oracle Contributor Agreement (OCA). If you have not signed the OCA, please follow the instructions. Please fill in your GitHub username in the "Username" field of the application. Once you have signed the OCA, please let us know by writing /signed in a comment in this pull request.
If you already are an OpenJDK Author, Committer or Reviewer, please click here to open a new issue so that we can record that fact. Please use "Add GitHub user iaroslavski" as summary for the issue.
If you are contributing this work on behalf of your employer and your employer has signed the OCA, please let us know by writing /covered in a comment in this pull request.
![bridgekeeper[bot] avatar](https://avatars.githubusercontent.com/u/41768318?v=4 "Published by a pub.dev verified publisher"){kind=small}
@iaroslavski The following label will be automatically applied to this pull request:
core-libs
When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing list. If you would like to change these labels, use the /label pull request command.
Thank you! Please allow for up to two weeks to process your OCA, although it is usually done within one to two business days. Also, please note that pull requests that are pending an OCA check will not usually be evaluated, so your patience is appreciated!
@iaroslavski This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!
Yes, I ping again, will see what happens
Суббота, 24 июля 2021, 14:47 +03:00 от Laurent Bourgès @.***>: Still waiting for individual OCA approval — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub , or unsubscribe .
@iaroslavski This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!
Webrevs
- 18: Full - Incremental (4f6ece03)
- 17: Full - Incremental (203610a5)
- 16: Full - Incremental (4772617d)
- 15: Full - Incremental (fcda2aa8)
- 14: Full - Incremental (618bdb5f)
- 13: Full - Incremental (1cb6fd7a)
- 12: Full - Incremental (6acc0bdb)
- 11: Full - Incremental (8a373741)
- 10: Full - Incremental (95f15386)
- 09: Full - Incremental (41b92f67)
- 08: Full - Incremental (4baa9a39)
- 07: Full - Incremental (e1b01cfb)
- 06: Full (ee7f6e82)
- 05: Full - Incremental (9989de5b)
- 04: Full - Incremental (90c08aed)
- 03: Full - Incremental (adcc6942)
- 02: Full - Incremental (6003fb69)
- 01: Full - Incremental (189f547a)
- 00: Full (2d972887)
LSD (Least Significant Digit) Radix sort is introduced to improve sorting. Thшs algorithm requires additional buffer, but has O(n) complexity. At the same time Quicksort performs at O(n*ln(n)). Radix sort shows extremely better performance on large random data, whereas Quicksort or merging sort win on other inputs.
We reuse additional buffer, if it is created during merge sort (in case of parallel sorting on computer with many processors). The same approach is used during allocation of buffer in merging sort. So, additional buffer is not created twice.
We also check if we have enough memory for the buffer. Otherwise, sorting is continued with in-place algorithms only.
Summary: introduced Radix sort requires the same amount memory as merge or merging sorts, reuses it if necessary, but works much faster than Quicksort.
I want to give my point of view on the new memory requirements:
- as radix sort is used for length > 4k, more often a temporary buffer will be needed (size = array length), so more often young gen GC passes will happen and maybe full gc if this buffer is really big (half heap?)
- if OOME is encountered when the buffer is allocated, then dpqs is used (in-place no-alloc) so new sorting is more robust than dpqs in jdk17
Sorting tests could be made with verbose gc to ascertain the increased gc work, latency...
It is possible to use an upper limit on the array size to disable radix sort and reduce memory footprint and gc overhead...
Hi reviewers!
@jhorstmann @tarsa @bourgesl @richardstartin @AlanBateman @neliasso
I applied and tested all ideas/comments from Laurent and Alan, the sorting sources (3 classes) are in final state. Could you please review and approve the PR, if you don't have comments?
As I am not an official openjdk reviewer, I can not approve, but I do support
Please core-libs reviewers could you have a look before jdk18 rdp0 or not ?
Hi all,
Not only Dual-Pivot Quicksort has been optimized, but I also improved test classes. I measured coverage of these tests. It was shown that all methods, all branches are invoked. So, we have full test coverage.
As jdk18 Ramp Down 0 is approaching and jdk19 is being opened soon, maybe this PR review should be planned for jdk19 build 1 ?
Vladimir, I updated the benchmarking code and here are the complete test results: system vs dpqs 21.5 vs 21.11: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/results/2021/2021-12-final/DPQS-sort-1k-1M-stats.out
Full results: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/results/2021/2021-12-final/sort-1k-1M-stats.out
All good, on 1k, 10k, 100k, 1m integer arrays. Congratulations 🥳
@iaroslavski This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!
@iaroslavski This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!
@iaroslavski This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!
I am improving test code (jmh + robust estimators) to have more robust results on small arrays (20 - 1000). I do hope having new results within 1 or 2 weeks.
allocating extra buffers and catching OOME when sorting primitives is rather unsatisfactory. you're not giving a reliable option for sorting under low memory conditions. IMO at least the single-threaded primitives (ints, longs, floats, etc all non-objects) sorting should be frugal when it comes to memory usage.
just my 2 cents.
