Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests This change will not lead to more crashes. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests Will the VM still exit if -XX:+ExitOnOutOfMemoryError/-XX:+CrashOnOutOfMemoryError/-XX:OnOutOfMemoryError/... was specified? I.e. can this change lead to more (avoidable) crashes? - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests Well explained, vladimir. I propose to adopt max_heap / 128 min to stay less than 1% footprint. Then factors are 7 for ints, 8 for long, min. For 1gb heap, it gives 8mb, so 2m ints or 1m long. Laurent - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests Hi Piotr, I agree that catching out-of-memory-error is very rarely in prod. I can say that LSD Radix sort works 3-5 times faster than Quicksort (array of int 2M elements), merging sort works 10-30 (!) times faster than Quicksort (structured array of int 2M elements), therefore it is worth to use algorithms with additional buffers. If we allocate buffer like 'new int[size]' and there is no free memory, sorting fails with OOME. If we catch memory error, we switch to in-place algorithms and sorting will be completed successfully. I checked such use case, it works fine. It doesn't matter if we run several threads or not. Some threads may use additional buffers, some threads - not, but finally all threads will be completed without errors. The known problem with OOME is handling inside catch block. If we try to create new object, try to log message with details, we can face with new OOME. In DualPivotQuicksort we return null only, no any actions, no new objects etc. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote:
>> 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
>
> iaroslavski has updated the pull request incrementally with one additional
> commit since the last revision:
>
> JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
>
> * Improved mixed insertion sort
> * Optimized insertion sort
> * Improved merging sort
> * Optimized soring tests
hi Vladimir,
the main reason i raise the issue with catching out-of-memory-error is that
it's done very rarely in production code and also it's rather unpredictable
when multiple things are going on (e.g. one thread can allocate a lot of
memory, but other threads receive `oome`).
i've searched through /src/ in openjdk/jdk repository for `oome` (i.e. this
one) and found that most times the `oome` is caught is in `java.desktop` module
(probably this means the `oome` was related to native memory or other resources
external to jvm), so i've narrowed search to `java.base`:
https://github.com/search?q=outofmemoryerror+repo%3Aopenjdk%2Fjdk+path%3A%2Fsrc%2Fjava.base%2F+language%3AJava=Code=advsearch=Java
and found just 2 cases of catching `oome` without always rethrowing it:
-
https://github.com/openjdk/jdk/blob/d8b0b32f9f4049aa678809aa068978e3a4e29457/src/java.base/share/classes/sun/nio/ch/FileChannelImpl.java#L1304
(but this rethrows if it internally fails with `oome` for a second time)
-
https://github.com/openjdk/jdk/blob/739769c8fc4b496f08a92225a12d07414537b6c0/src/java.base/share/classes/java/util/concurrent/SubmissionPublisher.java#L1171
overall, it seems that swallowing `oome` (i.e. in this case: catching and not
rethrowing) is definitely not a readily used approach.
> We need additional buffer for int, long, float and double types only.
>
> We will have 2 constants which limit the number of int/float and
long/double elements in array, like this:
> (...)
> See, that the max number of elements for long/double is in 2 times less than
> for int/float,
because long/double occupies 2 times more bytes.
sounds good
> Why do we need to use Math.min(…, Integer.MAX_VALUE)? (...) So, limit by 2 Gb
> max is required.
yep, understood
> What do you think, what value of shift is the best, 6, 7, 8, 9, 10, 11, 12
> etc.?
> Runtime.getRuntime().maxMemory() >> 10??
>
> Do you have actual scenarios? Actual requirements? Your feedback are welcome!
keeping the extra buffer size below 1% of max memory should be safe enough.
currently the code is:
private static final int MAX_BUFFER_LENGTH =
(int) Math.min(Runtime.getRuntime().maxMemory() >> 6, 256L << 20);
// ...
private static Object tryAllocate(Object a, int length) {
if (length > MAX_BUFFER_LENGTH) {
return null;
}
try {
if (a instanceof int[]) {
return new int[length];
}
if (a instanceof long[]) {
return new long[length];
}
...
which means that in the worst case `sizeof(long) * (max memory >> 6) == 12.5%
of heap size limit` would be used which is a lot when someone runs java code in
memory constrained environment and that is rather common nowadays
(microservices, containers, etc).
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Sun, 15 May 2022 14:17:41 GMT, Piotr Tarsa wrote:
>> iaroslavski has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
>>
>> * Improved mixed insertion sort
>> * Optimized insertion sort
>> * Improved merging sort
>> * Optimized soring tests
>
> i think it would make much more sense to have the extra buffer size limit in
> bytes, not in elements. for single-threaded sorting the limit should be low,
> e.g. 1/64 of the heap, not 1/8 (in case of sorting e.g. longs as each long is
> 8 byte long). multi-threaded sorting could be more aggressive when it comes
> to resource usage as it's less likely to be used in resource constrained
> environment.
@tarsa Hi Piotr,
Thank you for your interest to sorting and your point to allocation of buffers
in sorting.
Let’s I share my thoughts.
The number of elements of any array is not more than ~2 billion
(max positive int value) and therefore the size (in bytes) of
int array is not more than ~2 GB * 4 = ~8 GB.
We need additional buffer for int, long, float and double types only.
We will have 2 constants which limit the number of int/float and
long/double elements in array, like this:
private static final int MAX_BUFFER_LENGTH_1 = // for int/float
(int) Math.min(Runtime.getRuntime().maxMemory() >> 10,
Integer.MAX_VALUE);
private static final int MAX_BUFFER_LENGTH_2 = // for
long/double
(int) Math.min(Runtime.getRuntime().maxMemory() >> 11,
Integer.MAX_VALUE);
See, that the max number of elements for long/double is in 2 times less than
for int/float,
because long/double occupies 2 times more bytes.
I take factors 10 and 11 as example, it may be other values, but the first is
less than the second by 1.
Why do we need to use Math.min(…, Integer.MAX_VALUE)? We must do it in this
case:
if Runtime.getRuntime().maxMemory() >> 11 is larger than max int (for example,
we have power server),
casting to int will produce negative value. So, limit by 2 Gb max is required.
And the method tryAllocate will look like this:
private static Object tryAllocate(Object a, int length) {
try {
if (a instanceof int[]) {
return length > MAX_BUFFER_LENGTH_1 ? null : new int[length];
}
if (a instanceof long[]) {
return length > MAX_BUFFER_LENGTH_2 ? null : new long[length];
}
if (a instanceof float[]) {
return length > MAX_BUFFER_LENGTH_1 ? null : new float[length];
}
if (a instanceof double[]) {
return length > MAX_BUFFER_LENGTH_2 ? null : new double[length];
}
throw new IllegalArgumentException("Unknown array: " +
a.getClass().getName());
} catch (OutOfMemoryError e) {
return null;
}
}
What do you think, what value of shift is the best, 6, 7, 8, 9, 10, 11, 12 etc.?
Runtime.getRuntime().maxMemory() >> 10??
Do you have actual scenarios? Actual requirements? Your feedback are welcome!
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests i think it would make much more sense to have the extra buffer size limit in bytes, not in elements. for single-threaded sorting the limit should be low, e.g. 1/64 of the heap, not 1/8 (in case of sorting e.g. longs as each long is 8 byte long). multi-threaded sorting could be more aggressive when it comes to resource usage as it's less likely to be used in resource constrained environment. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests I checked the latest code: line 128: Max length of additional buffer, limited by max_heap / 64 or 256mb elements (2gb max). private static final int MAX_BUFFER_LENGTH = (int) Math.min(Runtime.getRuntime().maxMemory() >> 6, 256L << 20); So the current upper limit concerns the max length = max_heap_bytes / 64 (max heap/8) or 2gb (if heap is huge). - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Fri, 13 May 2022 17:48:50 GMT, Piotr Tarsa wrote: > 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. DPQS uses several sorting algorithms, merge sort & new radix sort need an extra buffer in contrary to isort, mixed isort, single and dual pivot quick sort. In this PR an upper limit on the heap usage is in use min(max heap / 16, 128mb) to reduce the memory footprint. Anyway catching OOME now permits DPQS to use in-place but slower algorithms if the extra buffer can not be allocated. Possibly the upper limit could be made configurable using system properties if it is really critical. To sum up, low allocations are now under control in this PR. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests 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. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests 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. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Improved mixed insertion sort > * Optimized insertion sort > * Improved merging sort > * Optimized soring tests waiting testing result from Laurent - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v12]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) * Improved mixed insertion sort * Optimized insertion sort * Improved merging sort * Optimized soring tests - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/95f15386..8a373741 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=11 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=10-11 Stats: 2935 lines in 3 files changed: 1092 ins; 1401 del; 442 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Wed, 12 Jan 2022 14:22:03 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Updated javadoc > * Improved mixed insertion > * Optimized sort networking > * Improved pivot partitioning New update is coming - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
On Wed, 12 Jan 2022 14:22:03 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Updated javadoc > * Improved mixed insertion > * Optimized sort networking > * Improved pivot partitioning Please review optimized sorting code. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v11]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) * Updated javadoc * Improved mixed insertion * Optimized sort networking * Improved pivot partitioning - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/41b92f67..95f15386 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=10 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=09-10 Stats: 798 lines in 1 file changed: 230 ins; 226 del; 342 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v10]
On Mon, 29 Nov 2021 21:16:32 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Updated javadoc > * Optimized insertion sort threshold > * Refactored parallel sorting section > * Improved step for pivot candidates > * Changed condition for Radix sort Please review this PR, it is ready for months, or give comments, please ! - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v10]
On Mon, 29 Nov 2021 21:16:32 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > * Updated javadoc > * Optimized insertion sort threshold > * Refactored parallel sorting section > * Improved step for pivot candidates > * Changed condition for Radix sort 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 拾 - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v10]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) * Updated javadoc * Optimized insertion sort threshold * Refactored parallel sorting section * Improved step for pivot candidates * Changed condition for Radix sort - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/4baa9a39..41b92f67 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=09 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=08-09 Stats: 128 lines in 2 files changed: 14 ins; 48 del; 66 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
On Mon, 15 Nov 2021 16:20:07 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Updated comments for partitioning As jdk18 Ramp Down 0 is approaching and jdk19 is being opened soon, maybe this PR review should be planned for jdk19 build 1 ? - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
On Mon, 15 Nov 2021 16:20:07 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Updated comments for partitioning 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. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
On Mon, 15 Nov 2021 16:20:07 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Updated comments for partitioning Please core-libs reviewers could you have a look before jdk18 rdp0 or not ? - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
On Mon, 15 Nov 2021 16:20:07 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Updated comments for partitioning As I am not an official openjdk reviewer, I can not approve, but I do support - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
On Mon, 15 Nov 2021 16:20:07 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Updated comments for partitioning 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? - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v9]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Updated comments for partitioning - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/e1b01cfb..4baa9a39 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=08 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=07-08 Stats: 54 lines in 1 file changed: 0 ins; 0 del; 54 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v8]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) - Set limit for buffer length - Radix sort is invoked on fully random data - Use 3 steps in Radix sort isntead of 4 for int/float - Set better options for parallel sorting - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/ee7f6e82..e1b01cfb Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=07 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=06-07 Stats: 182 lines in 2 files changed: 46 ins; 59 del; 77 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v7]
> 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 iaroslavski has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains ten commits: - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Merge with external changes - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Added more comments - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Better naming of methods - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Simplified mixed insertion sort - Merge remote-tracking branch 'upstream/master' into JDK-8266431-Dual-Pivot-Quicksort-improvements-Radix-sort - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Update target version - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Testing: - remove @since and @date, otherwise jtreg tag parser fails - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Sorting: - move radix sort out from quicksort partitioning - rename radixSort to tryRadixSort - minor javadoc and comment changes Testing: - rename radixSort to tryRadixSort in helper - 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 - Changes: https://git.openjdk.java.net/jdk/pull/3938/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=3938=06 Stats: 1288 lines in 3 files changed: 855 ins; 102 del; 331 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Added more comments It is possible to use an upper limit on the array size to disable radix sort and reduce memory footprint and gc overhead... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Added more comments 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... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski wrote: >> 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 > > iaroslavski has updated the pull request incrementally with one additional > commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) > > Added more comments 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. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Added more comments - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/90c08aed..9989de5b Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=05 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=04-05 Stats: 615 lines in 1 file changed: 295 ins; 173 del; 147 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v5]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Better naming of methods - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/adcc6942..90c08aed Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=04 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=03-04 Stats: 147 lines in 1 file changed: 0 ins; 0 del; 147 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v4]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Simplified mixed insertion sort - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/6003fb69..adcc6942 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=03 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=02-03 Stats: 204 lines in 1 file changed: 52 ins; 96 del; 56 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v3]
> 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 iaroslavski has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains five additional commits since the last revision: - Merge remote-tracking branch 'upstream/master' into JDK-8266431-Dual-Pivot-Quicksort-improvements-Radix-sort - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Update target version - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Testing: - remove @since and @date, otherwise jtreg tag parser fails - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Sorting: - move radix sort out from quicksort partitioning - rename radixSort to tryRadixSort - minor javadoc and comment changes Testing: - rename radixSort to tryRadixSort in helper - 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 - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/189f547a..6003fb69 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=01-02 Stats: 781419 lines in 7625 files changed: 627030 ins; 118369 del; 36020 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v2]
> 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 iaroslavski has updated the pull request incrementally with one additional commit since the last revision: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Update target version - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/2d972887..189f547a Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=01 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=00-01 Stats: 3 lines in 2 files changed: 0 ins; 0 del; 3 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 14 Sep 2021 10:57:17 GMT, Alan Bateman wrote: >>> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I >>> believe this work derives from an unsigned radix sort I implemented on >>> 10/04/2021 >>> [richardstartin/radix-sort-benchmark@ab4da23#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226](https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226) >>> which has numerous structural similarities to this work: >>> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated >>> with me about doing so. On 25/04/2021 there was a new implementation of >>> `DualPivotQuicksort` with a signed radix sort but the same structural >>> similarities, and with the same method and variable names in places >>> [bourgesl/radix-sort-benchmark@90ff7e4#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609](https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609) >> >> @iaroslavski The attribution is not clear here. Can you provide a summary as >> to who is contributing to this patch? I can't tell if all involved have >> signed the OCA or not. I'm sure there will be questions about space/time >> trade-offs with radix sort but I think it's important to first establish the >> origins of this patch first. > >> @AlanBateman Vertical pipeline of PR hides comments in the middle and you >> have to click on "Show more..." to see all comments. There are no claims >> related to the origin of my patch, it doesn't violate any rights. > > There is a comment from richardstartin suggesting that something was derived > from code in his repo. Is this a benchmark that is not part of this PR? Only > asking because I can't find him on OCA signatories. You can use the Skara > /contributor command to list the contributors. @AlanBateman my claim was that the implementation was derived from my implementation, and demonstrated a sequence of name changes after @bourgesl forked my repository containing a structurally similar radix sort implementation and benchmarks, in order to provide circumstantial evidence for my claim. Via email @iaroslavski told me that this was not the case, which I decided to accept at face value. So please judge this PR on its merits, and disregard the claims made in these comments. I have not signed an OCA but do not want to block this PR if the space time tradeoff is deemed acceptable. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 14 Sep 2021 10:57:17 GMT, Alan Bateman wrote: >>> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I >>> believe this work derives from an unsigned radix sort I implemented on >>> 10/04/2021 >>> [richardstartin/radix-sort-benchmark@ab4da23#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226](https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226) >>> which has numerous structural similarities to this work: >>> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated >>> with me about doing so. On 25/04/2021 there was a new implementation of >>> `DualPivotQuicksort` with a signed radix sort but the same structural >>> similarities, and with the same method and variable names in places >>> [bourgesl/radix-sort-benchmark@90ff7e4#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609](https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609) >> >> @iaroslavski The attribution is not clear here. Can you provide a summary as >> to who is contributing to this patch? I can't tell if all involved have >> signed the OCA or not. I'm sure there will be questions about space/time >> trade-offs with radix sort but I think it's important to first establish the >> origins of this patch first. > >> @AlanBateman Vertical pipeline of PR hides comments in the middle and you >> have to click on "Show more..." to see all comments. There are no claims >> related to the origin of my patch, it doesn't violate any rights. > > There is a comment from richardstartin suggesting that something was derived > from code in his repo. Is this a benchmark that is not part of this PR? Only > asking because I can't find him on OCA signatories. You can use the Skara > /contributor command to list the contributors. Mentioned benchmarking is not a part of this PR. Our benchmarking was done by Laurent. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 14 Sep 2021 09:23:23 GMT, Alan Bateman wrote: >> @richardstartin And one more addon: my first version of Radix sort, see my >> github https://github.com/iaroslavski/sorting/tree/master/radixsort uses >> another name, like skipBytes, then renamed to passLevel. >> So, the common part is "skip". And this method has different number of >> parameters. I don't see any collision with your code. > >> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I >> believe this work derives from an unsigned radix sort I implemented on >> 10/04/2021 >> [richardstartin/radix-sort-benchmark@ab4da23#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226](https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226) >> which has numerous structural similarities to this work: >> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with >> me about doing so. On 25/04/2021 there was a new implementation of >> `DualPivotQuicksort` with a signed radix sort but the same structural >> similarities, and with the same method and variable names in places >> [bourgesl/radix-sort-benchmark@90ff7e4#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609](https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609) > > @iaroslavski The attribution is not clear here. Can you provide a summary as > to who is contributing to this patch? I can't tell if all involved have > signed the OCA or not. I'm sure there will be questions about space/time > trade-offs with radix sort but I think it's important to first establish the > origins of this patch first. > @AlanBateman Vertical pipeline of PR hides comments in the middle and you > have to click on "Show more..." to see all comments. There are no claims > related to the origin of my patch, it doesn't violate any rights. There is a comment from richardstartin suggesting that something was derived from code in his repo. Is this a benchmark that is not part of this PR? Only asking because I can't find him on OCA signatories. You can use the Skara /contributor command to list the contributors. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 14 Sep 2021 09:23:23 GMT, Alan Bateman wrote: >> @richardstartin And one more addon: my first version of Radix sort, see my >> github https://github.com/iaroslavski/sorting/tree/master/radixsort uses >> another name, like skipBytes, then renamed to passLevel. >> So, the common part is "skip". And this method has different number of >> parameters. I don't see any collision with your code. > >> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I >> believe this work derives from an unsigned radix sort I implemented on >> 10/04/2021 >> [richardstartin/radix-sort-benchmark@ab4da23#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226](https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226) >> which has numerous structural similarities to this work: >> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with >> me about doing so. On 25/04/2021 there was a new implementation of >> `DualPivotQuicksort` with a signed radix sort but the same structural >> similarities, and with the same method and variable names in places >> [bourgesl/radix-sort-benchmark@90ff7e4#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609](https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609) > > @iaroslavski The attribution is not clear here. Can you provide a summary as > to who is contributing to this patch? I can't tell if all involved have > signed the OCA or not. I'm sure there will be questions about space/time > trade-offs with radix sort but I think it's important to first establish the > origins of this patch first. @AlanBateman There was discussion with Richard Startin, where Laurent and I explained the origin of my patch. There was misunderstanding based on git changes only. Finally Richard wrote comment in PR on May 13, 2021, I duplicate it here: "In private correspondence with Vladimir, it was explained that where Vladimir's code and Laurent's code are identical, including typos (Vladimir's code, Laurent's code) it is because Vladimir sent the code to Laurent, not the other way around, therefore Vladimir's code does not derive from Laurent's, and it does not derive from mine. I can only trust that this is the case, so please disregard my claim that this is derivative work when reviewing this PR." @AlanBateman Vertical pipeline of PR hides comments in the middle and you have to click on "Show more..." to see all comments. There are no claims related to the origin of my patch, it doesn't violate any rights. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 11:31:49 GMT, iaroslavski wrote: >> Perhaps we can resolve this issue in private - my email address is on my >> profile (or in the commits in `radix-sort-benchmark`)? > > @richardstartin And one more addon: my first version of Radix sort, see my > github https://github.com/iaroslavski/sorting/tree/master/radixsort uses > another name, like skipBytes, then renamed to passLevel. > So, the common part is "skip". And this method has different number of > parameters. I don't see any collision with your code. > Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I > believe this work derives from an unsigned radix sort I implemented on > 10/04/2021 > [richardstartin/radix-sort-benchmark@ab4da23#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226](https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226) > which has numerous structural similarities to this work: > Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with > me about doing so. On 25/04/2021 there was a new implementation of > `DualPivotQuicksort` with a signed radix sort but the same structural > similarities, and with the same method and variable names in places > [bourgesl/radix-sort-benchmark@90ff7e4#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609](https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609) @iaroslavski The attribution is not clear here. Can you provide a summary as to who is contributing to this patch? I can't tell if all involved have signed the OCA or not. I'm sure there will be questions about space/time trade-offs with radix sort but I think it's important to first establish the origins of this patch first. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 17:50:11 GMT, Piotr Tarsa wrote: >> I made a JMH test on jdk16 to test count4 (xor) performance: >> https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor >> >> >> Benchmark (size) Mode Cnt Score Error Units >> ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 >> ns/op >> ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 >> ns/op >> ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op >> ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op >> >> Masked xor does not get optimized by c2 too. >> >> Using Unsafe is better, see: >> https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java >> >> If you want, I could make another radixsort() using on or off heap count >> buffers and Unsafe, as I did in Marlin to avoid bound checks... > > I think an uncontroversial and efficient solution would be to replace > > count4[(a[i] >>> 24) ^ 0x80]--; > > with > > count4[(a[i] >>> 24) & 0xFF]--; > > and after finishing counting, first half of `count4` should be swapped with > second half of `count4`. FYI I made another radixsortNew() using Unsafe to access to all count arrays: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/dbfbd731ffd798defc75528cc1db04063bdb4619/src/edu/sorting/DualPivotQuicksort202105.java#L795 But it is only 2% faster in radix-sort-benchmark (1M arrays): https://github.com/bourgesl/radix-sort-benchmark/blob/main/results/2021-ref/cmp-16-1M-full.log It looks not worth the extra complexity for few percents, I think. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 20 May 2021 08:03:03 GMT, Nils Eliasson wrote: >> I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: >> using Unsafe is only 2% faster, not worth the extra complexity for few >> percent. > > A small update of the XorINodes type calculation makes the bound check go > away. Testing now. That bounds check shouldn't be there, it's an obvious case and will be fixed: https://github.com/openjdk/jdk/pull/4136 - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 18 May 2021 19:58:35 GMT, iaroslavski wrote: >> https://bugs.openjdk.java.net/browse/JDK-8267332 > > I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: > using Unsafe is only 2% faster, not worth the extra complexity for few > percent. A small update of the XorINodes type calculation makes the bound check go away. Testing now. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 18 May 2021 18:06:21 GMT, Nils Eliasson wrote: >> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: >> >>> 670: count2[(a[i] >>> 8) & 0xFF]--; >>> 671: count3[(a[i] >>> 16) & 0xFF]--; >>> 672: count4[(a[i] >>> 24) ^ 0x80]--; >> >> It seems that C2 can't eliminate the bounds check here because of the `xor`, >> even though this can't possibly exceed 256. The three masked accesses above >> are all eliminated. Maybe someone could look in to improving that. > > https://bugs.openjdk.java.net/browse/JDK-8267332 I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: using Unsafe is only 2% faster, not worth the extra complexity for few percent. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > 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 src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: > 670: count2[(a[i] >>> 8) & 0xFF]--; > 671: count3[(a[i] >>> 16) & 0xFF]--; > 672: count4[(a[i] >>> 24) ^ 0x80]--; It seems that C2 can't eliminate the bounds check here because of the `xor`, even though this can't possibly exceed 256. The three masked accesses above are all eliminated. Maybe someone could look in to improving that. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 20 May 2021 21:21:26 GMT, Nils Eliasson wrote: >> A small update of the XorINodes type calculation makes the bound check go >> away. Testing now. > > That bounds check shouldn't be there, it's an obvious case and will be fixed: > https://github.com/openjdk/jdk/pull/4136 Thanks for fixing hotspot C2 (xor) so quickly ! - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 11 May 2021 14:37:21 GMT, Jörn Horstmann
wrote:
>> 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
>
> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 669:
>
>> 667:
>> 668: for (int i = low; i < high; ++i) {
>> 669: count1[ a[i] & 0xFF]--;
>
> Not a reviewer, but having recently implemented a radixsort myself I'm
> wondering what is the logic or benefit of decrementing and counting backwards
> here?
>
> One thing I did differently, and I'm not fully sure is an optimization, is
> remembering the last bucket for each of the 4 counts. Checking whether the
> data is already sorted by that digit can then be done by checking
> `count[last_bucket] == size`, which avoids the first loop in `passLevel`.
> Again, not sure whether it is actually faster, maybe the two separate simple
> loops like here are better.
@jhorstmann In counting backwards we perform comparing with 0 in a loop,
Comparing with 0 may be faster than comparing with other value. In general,
backward or forward moving is your favor.
Keeping last_bucket and use check count[last_bucket] == size sounds good, but
we need to run benchmarking and compare. I think we will not see big difference
because the size of count array is too small, 256 only, whereas we scan whole
array with size at least 6K. The corner case when we can see max effect of
using last_bucket is array with all equal elements (4 count arrays will have
only one non-zero element). but such array will be caught by tryMerge method.
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 13:18:27 GMT, Laurent Bourgès wrote: >> I don't know Laurent, I find the handling of signed order over-complicated. >> Subtracting `Integer.MIN_VALUE` is really cheap... > > I made a JMH test on jdk16 to test count4 (xor) performance: > https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor > > > Benchmark (size) Mode Cnt Score Error Units > ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 ns/op > ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 ns/op > ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op > ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op > > Masked xor does not get optimized by c2 too. > > Using Unsafe is better, see: > https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java > > If you want, I could make another radixsort() using on or off heap count > buffers and Unsafe, as I did in Marlin to avoid bound checks... I think an uncontroversial and efficient solution would be to replace count4[(a[i] >>> 24) ^ 0x80]--; with count4[(a[i] >>> 24) & 0xFF]--; and after finishing counting, first half of `count4` should be swapped with second half of `count4`. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 20:47:48 GMT, Richard Startin wrote: >> 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 > > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: > >> 670: count2[(a[i] >>> 8) & 0xFF]--; >> 671: count3[(a[i] >>> 16) & 0xFF]--; >> 672: count4[(a[i] >>> 24) ^ 0x80]--; > > It seems that C2 can't eliminate the bounds check here because of the `xor`, > even though this can't possibly exceed 256. The three masked accesses above > are all eliminated. Maybe someone could look in to improving that. https://bugs.openjdk.java.net/browse/JDK-8267332 - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski
wrote:
> 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
src/java.base/share/classes/java/util/DualPivotQuicksort.java line 669:
> 667:
> 668: for (int i = low; i < high; ++i) {
> 669: count1[ a[i] & 0xFF]--;
Not a reviewer, but having recently implemented a radixsort myself I'm
wondering what is the logic or benefit of decrementing and counting backwards
here?
One thing I did differently, and I'm not fully sure is an optimization, is
remembering the last bucket for each of the 4 counts. Checking whether the data
is already sorted by that digit can then be done by checking
`count[last_bucket] == size`, which avoids the first loop in `passLevel`.
Again, not sure whether it is actually faster, maybe the two separate simple
loops like here are better.
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 07:41:19 GMT, Richard Startin wrote: >> Great analysis on C2, richard. >> >> maybe (x ^ 0x80) &0xFF would help C2 to eliminate bound checks... > > I don't know Laurent, I find the handling of signed order over-complicated. > Subtracting `Integer.MIN_VALUE` is really cheap... I made a JMH test on jdk16 to test count4 (xor) performance: https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor Benchmark (size) Mode Cnt Score Error Units ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 ns/op ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 ns/op ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op Masked xor does not get optimized by c2 too. Using Unsafe is better, see: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java If you want, I could make another radixsort() using on or off heap count buffers and Unsafe, as I did in Marlin to avoid bound checks... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 09:53:37 GMT, Richard Startin
wrote:
>> Laurent, the date in this class is not the date of our last commit,
>> this date is the date when I have final idea regarding to Radix sort,
>> therefore, I prefer to keep 2020.06.14
>
> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I
> believe this work derives from an unsigned radix sort I implemented on
> 10/04/2021
> https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
> which has numerous structural similarities to this work:
> * Producing all four histograms in one pass
> * Skipping passes based on detecting the total in the histogram
> * Bailing out of the skip detection if a nonzero value not equal to the total
> is encountered
> * Manually unrolling the LSD radix sort loop in order to avoid array copies
>
> My implementation from 10th April is below for reference:
>
> public static void unrollOnePassHistogramsSkipLevels(int[] data) {
> int[] histogram1 = new int[257];
> int[] histogram2 = new int[257];
> int[] histogram3 = new int[257];
> int[] histogram4 = new int[257];
>
> for (int value : data) {
> ++histogram1[(value & 0xFF) + 1];
> ++histogram2[((value >>> 8) & 0xFF) + 1];
> ++histogram3[((value >>> 16) & 0xFF) + 1];
> ++histogram4[(value >>> 24) + 1];
> }
> boolean skipLevel1 = canSkipLevel(histogram1, data.length);
> boolean skipLevel2 = canSkipLevel(histogram2, data.length);
> boolean skipLevel3 = canSkipLevel(histogram3, data.length);
> boolean skipLevel4 = canSkipLevel(histogram4, data.length);
>
> if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
> return;
> }
> int[] copy = new int[data.length];
>
> int[] source = data;
> int[] dest = copy;
>
> if (!skipLevel1) {
> for (int i = 1; i < histogram1.length; ++i) {
> histogram1[i] += histogram1[i - 1];
> }
> for (int value : source) {
> dest[histogram1[value & 0xFF]++] = value;
> }
> if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel2) {
> for (int i = 1; i < histogram2.length; ++i) {
> histogram2[i] += histogram2[i - 1];
> }
> for (int value : source) {
> dest[histogram2[(value >>> 8) & 0xFF]++] = value;
> }
> if (!skipLevel3 || !skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel3) {
> for (int i = 1; i < histogram3.length; ++i) {
> histogram3[i] += histogram3[i - 1];
> }
> for (int value : data) {
> dest[histogram3[(value >>> 16) & 0xFF]++] = value;
> }
> if (!skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel4) {
> for (int i = 1; i < histogram4.length; ++i) {
> histogram4[i] += histogram4[i - 1];
> }
> for (int value : source) {
> dest[histogram4[value >>> 24]++] = value;
> }
> }
> if (dest != data) {
> System.arraycopy(dest, 0, data, 0, data.length);
> }
> }
>
> private static boolean canSkipLevel(int[] histogram, int dataSize) {
> for (int count : histogram) {
> if (count == dataSize) {
> return true;
> } else if (count > 0) {
> return false;
> }
> }
> return true;
> }
>
>
> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with
> me about doing so. On 25/04/2021 there was a new implementation of
> `DualPivotQuicksort` with a signed radix sort but the same structural
> similarities, and with the same method and variable names in places
> https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
>
>
> // TODO add javadoc
> private static void radixSort(Sorter sorter, int[] a, int low, int high) {
> int[] b;
> // LBO: prealloc (high - low) +1 element:
> if (sorter == null || (b = sorter.b) == null || b.length < (high -
> low)) {
> // System.out.println("alloc b: " + (high - low));
> b = new int[high - low];
> }
>
> int[] count1, count2, count3, count4;
> if (sorter != null) {
> sorter.resetRadixBuffers();
> count1 = sorter.count1;
> count2 = sorter.count2;
> count3 = sorter.count3;
> count4 = sorter.count4;
> } else {
> // System.out.println("alloc radix buffers(4x256)");
> count1 = new int[256];
> count2 = new int[256];
> count3 = new int[256];
>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 10:22:57 GMT, Laurent Bourgès wrote:
>> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I
>> believe this work derives from an unsigned radix sort I implemented on
>> 10/04/2021
>> https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
>> which has numerous structural similarities to this work:
>> * Producing all four histograms in one pass
>> * Skipping passes based on detecting the total in the histogram
>> * Bailing out of the skip detection if a nonzero value not equal to the
>> total is encountered
>> * Manually unrolling the LSD radix sort loop in order to avoid array copies
>>
>> My implementation from 10th April is below for reference:
>>
>> public static void unrollOnePassHistogramsSkipLevels(int[] data) {
>> int[] histogram1 = new int[257];
>> int[] histogram2 = new int[257];
>> int[] histogram3 = new int[257];
>> int[] histogram4 = new int[257];
>>
>> for (int value : data) {
>> ++histogram1[(value & 0xFF) + 1];
>> ++histogram2[((value >>> 8) & 0xFF) + 1];
>> ++histogram3[((value >>> 16) & 0xFF) + 1];
>> ++histogram4[(value >>> 24) + 1];
>> }
>> boolean skipLevel1 = canSkipLevel(histogram1, data.length);
>> boolean skipLevel2 = canSkipLevel(histogram2, data.length);
>> boolean skipLevel3 = canSkipLevel(histogram3, data.length);
>> boolean skipLevel4 = canSkipLevel(histogram4, data.length);
>>
>> if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
>> return;
>> }
>> int[] copy = new int[data.length];
>>
>> int[] source = data;
>> int[] dest = copy;
>>
>> if (!skipLevel1) {
>> for (int i = 1; i < histogram1.length; ++i) {
>> histogram1[i] += histogram1[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram1[value & 0xFF]++] = value;
>> }
>> if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel2) {
>> for (int i = 1; i < histogram2.length; ++i) {
>> histogram2[i] += histogram2[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram2[(value >>> 8) & 0xFF]++] = value;
>> }
>> if (!skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel3) {
>> for (int i = 1; i < histogram3.length; ++i) {
>> histogram3[i] += histogram3[i - 1];
>> }
>> for (int value : data) {
>> dest[histogram3[(value >>> 16) & 0xFF]++] = value;
>> }
>> if (!skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel4) {
>> for (int i = 1; i < histogram4.length; ++i) {
>> histogram4[i] += histogram4[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram4[value >>> 24]++] = value;
>> }
>> }
>> if (dest != data) {
>> System.arraycopy(dest, 0, data, 0, data.length);
>> }
>> }
>>
>> private static boolean canSkipLevel(int[] histogram, int dataSize) {
>> for (int count : histogram) {
>> if (count == dataSize) {
>> return true;
>> } else if (count > 0) {
>> return false;
>> }
>> }
>> return true;
>> }
>>
>>
>> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with
>> me about doing so. On 25/04/2021 there was a new implementation of
>> `DualPivotQuicksort` with a signed radix sort but the same structural
>> similarities, and with the same method and variable names in places
>> https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
>>
>>
>> // TODO add javadoc
>> private static void radixSort(Sorter sorter, int[] a, int low, int high)
>> {
>> int[] b;
>> // LBO: prealloc (high - low) +1 element:
>> if (sorter == null || (b = sorter.b) == null || b.length < (high -
>> low)) {
>> // System.out.println("alloc b: " + (high - low));
>> b = new int[high - low];
>> }
>>
>> int[] count1, count2, count3, count4;
>> if (sorter != null) {
>> sorter.resetRadixBuffers();
>> count1 = sorter.count1;
>> count2 = sorter.count2;
>> count3 = sorter.count3;
>> count4 = sorter.count4;
>> } else {
>> // System.out.println("alloc radix buffers(4x256)");
>> count1 = new int[256];
>> count2 = new int[256];
>> count3 = new int[256];
>> count4 = new int[256];
>> }
>>
>>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 21:44:38 GMT, Richard Startin wrote: >> For what it's worth, I benchmarked this implementation radix sort ([adapted >> here to fit in to my >> harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) >> against a [signed >> variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) >> of what I have claimed this work was derived from and the proposed >> implementation does not perform favourably on uniformly random data: >> >> >> >> Benchmark (bits) (padding) >> (scenario) (seed) (size) Mode Cnt Score Error Units >> RadixSortBenchmark.jdk17 7 >> UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op >> RadixSortBenchmark.jdk23 7 >> UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op >> RadixSortBenchmark.jdk30 7 >> UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 >> UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 >> UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 >> UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op >> >> >> >> I believe the root cause is a defect in the mechanism employed to skip >> passes as can be seen by the increased number of instructions and cycles >> here. In the proposed implementation, instructions is roughly constant as a >> function of bits. In the case where all passes must be performed (bits = >> 30), IPC is superior in `unrollOnePassHistogramsSkipLevelsSigned`. >> >> >> Benchmark >> (bits) (padding) (scenario) (seed) (size) Mode Cnt Score >> Error Units >> RadixSortBenchmark.jdk:cycles >> 17 7 UNIFORM 0 100 avgt 34976971.877 >>#/op >> RadixSortBenchmark.jdk:instructions >> 17 7 UNIFORM 0 100 avgt 70121142.003 >>#/op >> RadixSortBenchmark.jdk:cycles >> 23 7 UNIFORM 0 100 avgt 32369970.385 >>#/op >> RadixSortBenchmark.jdk:instructions >> 23 7 UNIFORM 0 100 avgt 70201664.963 >>#/op >> RadixSortBenchmark.jdk:cycles >> 30 7 UNIFORM 0 100 avgt 30789736.602 >>#/op >> RadixSortBenchmark.jdk:instructions >> 30 7 UNIFORM 0 100 avgt 70180942.122 >>#/op >> RadixSortBenchmark.jdk:IPC >> 30 7 UNIFORM 0 100 avgt 2.279 >> insns/clk >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 17 7 UNIFORM 0 100 avgt 26983994.479 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 17 7 UNIFORM 0 100 avgt 62065304.827 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 23 7 UNIFORM 0 100 avgt 26161703.124 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 23 7 UNIFORM 0 100 avgt 63102683.167 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 30 7 UNIFORM 0 100 avgt 29780103.795 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 30 7 UNIFORM 0 100 avgt 74437097.025 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:IPC >> 30 7 UNIFORM 0 100 avgt 2.500 >> insns/clk >> >> >> >> The biggest difference in executed code appears to be that bounds checks are >> not eliminated in the first counting pass in the proposed implementation: >> >> >> [Hottest Region >>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 07:14:27 GMT, Laurent Bourgès wrote: >> So the issue of not skipping passes was my fault in the translation process, >> so not something to worry about, though after [fixing >> that](https://github.com/richardstartin/radix-sort-benchmark/commit/ccbee984c6a0e0f50c30de59e1a5e9fbcad89510) >> the original implementation still has the edge because of the bounds checks >> on the `xor` not getting eliminated. >> >> >> Benchmark (bits) (padding) >> (scenario) (seed) (size) Mode Cnt ScoreError Units >> RadixSortBenchmark.jdk17 7 >> UNIFORM 0 100 avgt5 10432.408 ± 87.024 us/op >> RadixSortBenchmark.jdk23 7 >> UNIFORM 0 100 avgt5 9465.990 ± 40.598 us/op >> RadixSortBenchmark.jdk30 7 >> UNIFORM 0 100 avgt5 11189.146 ± 50.972 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 >> UNIFORM 0 100 avgt5 9546.963 ± 41.698 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 >> UNIFORM 0 100 avgt5 9412.114 ± 43.081 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 >> UNIFORM 0 100 avgt5 10823.618 ± 64.311 us/op > > Great analysis on C2, richard. > > maybe (x ^ 0x80) &0xFF would help C2 to eliminate bound checks... I don't know Laurent, I find the handling of signed order over-complicated. Subtracting `Integer.MIN_VALUE` is really cheap... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 14:44:28 GMT, Richard Startin wrote: >> @iaroslavski I would prefer to discuss this in private than here, but my >> argument is that the name `skipByte` came from Laurent's code, and that >> Laurent's code was clearly derived from my own within a fork of my >> repository. I linked the commits where you changed `skipByte` to `passLevel` >> and Laurent changed my name `canSkipLevel` to `skipByte`. >> >> For me, this raises questions about the independence of your work from >> Laurent's, and Laurent's work is clearly derived from my own (and I don't >> think anyone is disputing the latter). I would be happy to sort this out in >> private. > > In private correspondence with Vladimir, it was explained that where > Vladimir's code and Laurent's code are identical, including typos > ([Vladimir's > code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), > [Laurent's > code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) > it is because Vladimir sent the code to Laurent, not the other way around, > therefore Vladimir's code does not derive from Laurent's, and it does not > derive from mine. I can only trust that this is the case, so please disregard > my claim that this is derivative work when reviewing this PR. For what it's worth, I benchmarked this implementation radix sort ([adapted here to fit in to my harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) against a [signed variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) of what I have claimed this work was derived from and the proposed implementation does not perform favourably on uniformly random data: Benchmark (bits) (padding) (scenario) (seed) (size) Mode Cnt Score Error Units RadixSortBenchmark.jdk17 7 UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op RadixSortBenchmark.jdk23 7 UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op RadixSortBenchmark.jdk30 7 UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op I believe the root cause is a defect in the mechanism employed to skip passes as can be seen by the increased number of instructions and cycles here. In the proposed implementation, instructions is roughly constant as a function of bits. In the case where all passes must be performed (bits = 30), IPC is superior in `unrollOnePassHistogramsSkipLevelsSigned`. Benchmark (bits) (padding) (scenario) (seed) (size) Mode Cnt Score Error Units RadixSortBenchmark.jdk:cycles 17 7 UNIFORM 0 100 avgt 34976971.877 #/op RadixSortBenchmark.jdk:instructions 17 7 UNIFORM 0 100 avgt 70121142.003 #/op RadixSortBenchmark.jdk:cycles 23 7 UNIFORM 0 100 avgt 32369970.385 #/op RadixSortBenchmark.jdk:instructions 23 7 UNIFORM 0 100 avgt 70201664.963 #/op RadixSortBenchmark.jdk:cycles 30 7 UNIFORM 0 100 avgt 30789736.602 #/op RadixSortBenchmark.jdk:instructions 30 7 UNIFORM 0 100 avgt 70180942.122 #/op RadixSortBenchmark.jdk:IPC 30 7 UNIFORM 0 100 avgt 2.279 insns/clk RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles 17 7 UNIFORM 0 100 avgt 26983994.479 #/op
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 20:23:16 GMT, Richard Startin wrote: >> In private correspondence with Vladimir, it was explained that where >> Vladimir's code and Laurent's code are identical, including typos >> ([Vladimir's >> code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), >> [Laurent's >> code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) >> it is because Vladimir sent the code to Laurent, not the other way around, >> therefore Vladimir's code does not derive from Laurent's, and it does not >> derive from mine. I can only trust that this is the case, so please >> disregard my claim that this is derivative work when reviewing this PR. > > For what it's worth, I benchmarked this implementation radix sort ([adapted > here to fit in to my > harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) > against a [signed > variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) > of what I have claimed this work was derived from and the proposed > implementation does not perform favourably on uniformly random data: > > > > Benchmark (bits) (padding) > (scenario) (seed) (size) Mode Cnt Score Error Units > RadixSortBenchmark.jdk17 7 > UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op > RadixSortBenchmark.jdk23 7 > UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op > RadixSortBenchmark.jdk30 7 > UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 > UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 > UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 > UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op > > > > I believe the root cause is a defect in the mechanism employed to skip passes > as can be seen by the increased number of instructions and cycles here. In > the proposed implementation, instructions is roughly constant as a function > of bits. In the case where all passes must be performed (bits = 30), IPC is > superior in `unrollOnePassHistogramsSkipLevelsSigned`. > > > Benchmark > (bits) (padding) (scenario) (seed) (size) Mode Cnt Score > Error Units > RadixSortBenchmark.jdk:cycles > 17 7 UNIFORM 0 100 avgt 34976971.877 > #/op > RadixSortBenchmark.jdk:instructions > 17 7 UNIFORM 0 100 avgt 70121142.003 > #/op > RadixSortBenchmark.jdk:cycles > 23 7 UNIFORM 0 100 avgt 32369970.385 > #/op > RadixSortBenchmark.jdk:instructions > 23 7 UNIFORM 0 100 avgt 70201664.963 > #/op > RadixSortBenchmark.jdk:cycles > 30 7 UNIFORM 0 100 avgt 30789736.602 > #/op > RadixSortBenchmark.jdk:instructions > 30 7 UNIFORM 0 100 avgt 70180942.122 > #/op > RadixSortBenchmark.jdk:IPC > 30 7 UNIFORM 0 100 avgt 2.279 > insns/clk > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles > 17 7 UNIFORM 0 100 avgt 26983994.479 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions > 17 7 UNIFORM 0 100 avgt 62065304.827 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles > 23 7 UNIFORM 0 100 avgt 26161703.124 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions > 23 7 UNIFORM 0 100 avgt 63102683.167
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 11:31:49 GMT, iaroslavski wrote: >> Perhaps we can resolve this issue in private - my email address is on my >> profile (or in the commits in `radix-sort-benchmark`)? > > @richardstartin And one more addon: my first version of Radix sort, see my > github https://github.com/iaroslavski/sorting/tree/master/radixsort uses > another name, like skipBytes, then renamed to passLevel. > So, the common part is "skip". And this method has different number of > parameters. I don't see any collision with your code. @iaroslavski I would prefer to discuss this in private than here, but my argument is that the name `skipByte` came from Laurent's code, and that Laurent's code was clearly derived from my own within a fork of my repository. I linked the commits where you changed `skipByte` to `passLevel` and Laurent changed my name `canSkipLevel` to `skipByte`. For me, this raises questions about the independence of your work from Laurent's, and Laurent's work is clearly derived from my own (and I don't think anyone is disputing the latter). I would be happy to sort this out in private. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 11:47:58 GMT, Richard Startin wrote: >> @richardstartin And one more addon: my first version of Radix sort, see my >> github https://github.com/iaroslavski/sorting/tree/master/radixsort uses >> another name, like skipBytes, then renamed to passLevel. >> So, the common part is "skip". And this method has different number of >> parameters. I don't see any collision with your code. > > @iaroslavski I would prefer to discuss this in private than here, but my > argument is that the name `skipByte` came from Laurent's code, and that > Laurent's code was clearly derived from my own within a fork of my > repository. I linked the commits where you changed `skipByte` to `passLevel` > and Laurent changed my name `canSkipLevel` to `skipByte`. > > For me, this raises questions about the independence of your work from > Laurent's, and Laurent's work is clearly derived from my own (and I don't > think anyone is disputing the latter). I would be happy to sort this out in > private. In private correspondence with Vladimir, it was explained that where Vladimir's code and Laurent's code are identical, including typos ([Vladimir's code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), [Laurent's code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) it is because Vladimir sent the code to Laurent, not the other way around, therefore Vladimir's code does not derive from Laurent's, and it does not derive from mine. I can only trust that this is the case, so please disregard my claim that this is derivative work when reviewing this PR. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 10:53:48 GMT, Richard Startin wrote: >> You misunderstood my approach: >> - vladimir & tagir discussed radix sorts since previous work on DPQS in 2019 >> - I enjoyed reading your blog post testing the performance of your radix >> sort vs Arrays.sort() >> - I tested and forked your radix-sort-benchmark to reproduce your >> experiments on openjdk16 (dpqs 19.11) >> - Vladimir proposed his own radixsort() >> - I did port DPQS impls in my fork of your benchmark to make a global >> comparison: dpqs 11, 19, 21 vs yours + arrays.sort(): it helped comparing >> implementations and decide when radix sort wins depending on dataset >> presortness >> - I tried many variants on my github repositories, but Vladimir never merged >> any of my change as he is not a regular github user (clone, fork, merge). >> >> Our goal is not to underestimate your work (sort + benchmark) but Vladimir >> wrote his own code, me many experiments (tests, benchmarks) to obtain this >> original patch, written by Vladimir, with his radix sort implementation >> working on any int/long/float/double arrays, following the GPLv2 license. >> >> You gave me motivation to make Arrays.sort() faster and we worked hard to >> write, test and benchmark this patch to be ready for OpenJDK 17 > > Perhaps we can resolve this issue in private - my email address is on my > profile (or in the commits in `radix-sort-benchmark`)? @richardstartin The ideas to take 4 histograms at once or use check to skip digits are very simple and come not only from you, for example, see article from 2001, http://stereopsis.com/radix.html When Laurent and I discussed our Radix sort, your code was demonstrated. I wrote my implementation and at the first version I took the similar names (even not perfect for my cases) and later I renamed them to better values. You can see that from functional point of view your code and my code are different, they process skipped digits in different manner, No your code was copied. Date 2020.06.14 means the start of my activities on Radix sort, not final version. Let me know, if you have any questions @richardstartin And one more addon: my first version of Radix sort, see my github https://github.com/iaroslavski/sorting/tree/master/radixsort uses another name, like skipBytes, then renamed to passLevel. So, the common part is "skip". And this method has different number of parameters. I don't see any collision with your code. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 12:20:09 GMT, iaroslavski
wrote:
>> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47:
>>
>>> 45: * @author Doug Lea
>>> 46: *
>>> 47: * @version 2020.06.14
>>
>> Vladimir, I would update to 2021.05.06 (+your hash)
>
> Laurent, the date in this class is not the date of our last commit,
> this date is the date when I have final idea regarding to Radix sort,
> therefore, I prefer to keep 2020.06.14
Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I believe
this work derives from an unsigned radix sort I implemented on 10/04/2021
https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
which has numerous structural similarities to this work:
* Producing all four histograms in one pass
* Skipping passes based on detecting the total in the histogram
* Bailing out of the skip detection if a nonzero value not equal to the total
is encountered
* Manually unrolling the LSD radix sort loop in order to avoid array copies
My implementation from 10th April is below for reference:
public static void unrollOnePassHistogramsSkipLevels(int[] data) {
int[] histogram1 = new int[257];
int[] histogram2 = new int[257];
int[] histogram3 = new int[257];
int[] histogram4 = new int[257];
for (int value : data) {
++histogram1[(value & 0xFF) + 1];
++histogram2[((value >>> 8) & 0xFF) + 1];
++histogram3[((value >>> 16) & 0xFF) + 1];
++histogram4[(value >>> 24) + 1];
}
boolean skipLevel1 = canSkipLevel(histogram1, data.length);
boolean skipLevel2 = canSkipLevel(histogram2, data.length);
boolean skipLevel3 = canSkipLevel(histogram3, data.length);
boolean skipLevel4 = canSkipLevel(histogram4, data.length);
if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
return;
}
int[] copy = new int[data.length];
int[] source = data;
int[] dest = copy;
if (!skipLevel1) {
for (int i = 1; i < histogram1.length; ++i) {
histogram1[i] += histogram1[i - 1];
}
for (int value : source) {
dest[histogram1[value & 0xFF]++] = value;
}
if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel2) {
for (int i = 1; i < histogram2.length; ++i) {
histogram2[i] += histogram2[i - 1];
}
for (int value : source) {
dest[histogram2[(value >>> 8) & 0xFF]++] = value;
}
if (!skipLevel3 || !skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel3) {
for (int i = 1; i < histogram3.length; ++i) {
histogram3[i] += histogram3[i - 1];
}
for (int value : data) {
dest[histogram3[(value >>> 16) & 0xFF]++] = value;
}
if (!skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel4) {
for (int i = 1; i < histogram4.length; ++i) {
histogram4[i] += histogram4[i - 1];
}
for (int value : source) {
dest[histogram4[value >>> 24]++] = value;
}
}
if (dest != data) {
System.arraycopy(dest, 0, data, 0, data.length);
}
}
private static boolean canSkipLevel(int[] histogram, int dataSize) {
for (int count : histogram) {
if (count == dataSize) {
return true;
} else if (count > 0) {
return false;
}
}
return true;
}
Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with me
about doing so. On 25/04/2021 there was a new implementation of
`DualPivotQuicksort` with a signed radix sort but the same structural
similarities, and with the same method and variable names in places
https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
// TODO add javadoc
private static void radixSort(Sorter sorter, int[] a, int low, int high) {
int[] b;
// LBO: prealloc (high - low) +1 element:
if (sorter == null || (b = sorter.b) == null || b.length < (high -
low)) {
// System.out.println("alloc b: " + (high - low));
b = new int[high - low];
}
int[] count1, count2, count3, count4;
if (sorter != null) {
sorter.resetRadixBuffers();
count1 = sorter.count1;
count2 = sorter.count2;
count3 = sorter.count3;
count4 = sorter.count4;
} else {
// System.out.println("alloc radix buffers(4x256)");
count1 = new int[256];
count2 = new int[256];
count3 = new int[256];
count4 = new int[256];
}
for (int i = low; i <
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 12:20:09 GMT, iaroslavski wrote: >> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: >> >>> 45: * @author Doug Lea >>> 46: * >>> 47: * @version 2020.06.14 >> >> Vladimir, I would update to 2021.05.06 (+your hash) > > Laurent, the date in this class is not the date of our last commit, > this date is the date when I have final idea regarding to Radix sort, > therefore, I prefer to keep 2020.06.14 as you want, but you should maybe indicate which version corresponds to your master code too. It would help tracking changes between forks (iarosalvskiy/sorting master) - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > 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 Still waiting OCA approval 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 . Still waiting OCA approval - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 11:36:09 GMT, Laurent Bourgès wrote: >> 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 > > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: > >> 45: * @author Doug Lea >> 46: * >> 47: * @version 2020.06.14 > > Vladimir, I would update to 2021.05.06 (+your hash) Laurent, the date in this class is not the date of our last commit, this date is the date when I have final idea regarding to Radix sort, therefore, I prefer to keep 2020.06.14 > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 288: > >> 286: /* >> 287: * Invoke radix sort on large array. >> 288: */ > > I prefer testing (sorter == null) first as it is always true for sequential > sort and avoid testing bits > ... in this case It makes sense, I will update. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > 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 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 Still waiting for individual OCA approval src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: > 45: * @author Doug Lea > 46: * > 47: * @version 2020.06.14 Vladimir, I would update to 2021.05.06 (+your hash) src/java.base/share/classes/java/util/DualPivotQuicksort.java line 288: > 286: /* > 287: * Invoke radix sort on large array. > 288: */ I prefer testing (sorter == null) first as it is always true for sequential sort and avoid testing bits > ... in this case - PR: https://git.openjdk.java.net/jdk/pull/3938
