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
