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 i
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 i
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 m
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 i
sting:
> - 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 improvem
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 i
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 i
sting:
> - 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 improveme
sting:
> - 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 improveme
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 i
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 i
sting:
> - 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 improvem
sting:
> - 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 imp
sting:
> - 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: D
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 i
sting:
> - 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 im
sting:
> - 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 impro
sting:
> - 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 improvem
sting:
> - 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 br
sting:
> - 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 impro
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
>>> [richardstart
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.
>
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]--;
>>
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
d 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/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
> elem
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
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
Hello,
Here is improvement for sorting primitives:
http://cr.openjdk.java.net/~alanb/7013585/webrev
Highly structured (nearly sorted) data like
1,2,3,..,k,1,2,3,..,k,... or
1,2,3,...,n/2,n/2,...,3,2,1 etc.
is sorted very effectively by merge sort.
The main idea of this optimization is to check
Hello Dmytro,
Thank you for investigation, the results are interesting.
I prepared simpler test [1], which has no recursion, it just
sorts 5 candidates and compare all elements with first (or second)
candidate. I run on array of 200 elements and result is:
e1/e2 267/460 on random data
Hello,
I have performance question in sorting.
In an implementation of Dual-Pivot Quicksort 5 elements
a[e1], a[e2], a[e3], a[e4], a[e5]
where e1 = len/6, e2 = len/3, e3 = len/2, e4 = len*2/3, e5 = len*5/6,
are sorted and then elements a[e2], a[e4] are taken as pivots.
but if I take a[e1] and
Hello,
Please, review the Sorting test class. I added tests
for null arrays (NPE must be thrown) and added description
of test to error message.
Thanks,
Vladimir
/*
* Copyright 2009 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
Iaroslavski iaroslav...@mail.ru
mailto:iaroslav...@mail.ru
Hello Osvaldo,
I've prepared simple test which scans an array and does assignments
for each element,
see attached Test class:
a[k] = a[less];
a[less++] = 0; // or a[less] = 0; less++;
The result of running
)
Thanks,
Vladimir
Fri, 18 Jun 2010 13:03:50 -0300 письмо от Osvaldo Doederlein
opin...@gmail.com:
Hi,
2010/6/18 Vladimir Iaroslavski iaroslav...@mail.ru
Hello,
Here is next piece of improvements, see attached class.
It is surprise but code
a[less++] = ak;
works slower (client VM
of improvements for Dual-Pivot
Quicksort
To: dmytro_she...@hotmail.com
CC: core-libs-dev@openjdk.java.net
resend the class with correct constructor
Vladimir Iaroslavski wrote:
Dmytro,
Thank you for comments, I
To: dmytro_she...@hotmail.com
CC: core-libs-dev@openjdk.java.net
resend the class with correct constructor
Vladimir Iaroslavski wrote:
Dmytro,
Thank you for comments, I updated double method, did
little bit
javadoc changes
To: dmytro_she...@hotmail.com
CC: core-libs-dev@openjdk.java.net
resend the class with correct constructor
Vladimir Iaroslavski wrote:
Dmytro,
Thank you for comments, I updated double method, did little bit
javadoc changes and replaced in char/short
14:41:32 +0400
From: iaroslav...@mail.ru
Subject: Re: New portion of improvements for Dual-Pivot Quicksort
To: dmytro_she...@hotmail.com
CC: core-libs-dev@openjdk.java.net
resend the class with correct constructor
Vladimir Iaroslavski wrote:
Dmytro,
Thank you for comments, I
Hello,
Thank you for review, I'll check and run tests again with you changes.
Thank you,
Vladimir
Dmytro Sheyko wrote:
Hello,
More ideas.
1. We can use
Double.doubleToRawLongBits instead of Double.doubleToLongBits and
Float.floatToRawIntBits instead of Float.floatToIntBits.
No need to
Sounds good!
Will consider too...
Mon, 17 May 2010 22:24:11 +0700 письмо от Dmytro Sheyko
dmytro_she...@hotmail.com:
Hi,
Regarding counting sort. We can check whether we should switch to counting
sort only once in the beginning.
Date: Mon, 17 May 2010 17:30:37 +0400
From:
Dmytro,
I've tested your suggested variants, and found that case C
(very interesting approach to find first position of zero
by counting negative elements) works slower than original
or two other cases.
Implementations F and S are very close to each other
and little bit faster than original. I
Hello Dmytro,
Could you please send new version of DPQ
with your changes?
Thanks,
Vladimir
Dmytro Sheyko wrote:
Vladimir,
Your changes are good for me.
Additionally I have some comments/proposals regarding dealing with
negative zeros.
1. Scanning for the first zero we can avoid range
Hello Dmytro,
Thank you for reviewing float/double section!
I'll look at your code and run tests tomorrow
and let you know results.
Best regards,
Vladimir
Dmytro Sheyko wrote:
Vladimir,
Your changes are good for me.
Additionally I have some comments/proposals regarding dealing with
Hello Dmytro,
I tried this case too, and the results are the same.
But to be sure, I will check your version again.
Thank you,
Vladimir
Dmytro Sheyko wrote:
Hi,
Wouldn't it better to use boolean flag instead of int index?
--
Dmytro Sheyko
PS
--- DualPivotQuicksortWithoutSentinel.java
Hello Dmytro,
I got your idea, and now I'm trying to combine insertion sort
with your suggestion (don't set a sentinel), to be under
restriction that we cannot change anything outside of the
range and to sort correctly if initially part of array only
is to be sorted (not whole array), see:
[ ?
Josh,
Thank you very much for review.
I'll prepare updated version and send it with my comments soon.
Vladimir
Joshua Bloch wrote:
Vladimir,
Hi. I'm thrilled that you were able to eke so much more perforance out
of this already optimized code. I read your changes on my flight to
Hi Dmytro,
Thank you very much for suggestions! I checked it and here
is my results:
If we consider case when the whole array is sorted,
we can omit setting sentinel and restoring original value:
// int before = a[left - 1]; a[left - 1] = Integer.MIN_VALUE;
for (int j, i = left + 1; i =
Josh,
Quick note on changing
int pivot1 = a[e2[;
int pivot2 = a[e4];
by
int pivot1 = ae2;
int pivot2 = ae4;
It is extremely surprised, but version with local variables eats
5% (!) of time for client and 2% for server mode (in compare
with one-pivot implementation from JDK 6), see:
Hello Dmytro,
Please, see file test/java/util/Arrays/Sorting.java in the
JDK repository, It contains unit tests.
Thank you,
Vladimir
2010/4/30 Dmytro Sheyko dmytro_she...@hotmail.com:
Hello Vladimir,
Could you remind me where can I find sources for the test suite?
Thanks,
Dmytro
Date:
Hello, everyone!
I've investigated the implementation of the Dual-Pivot Quicksort
which is used for sorting primitives and here is my result:
http://cr.openjdk.java.net/~alanb/6947216/webrev.00
New implementation of Dual-Pivot Quicksort is faster
than previous one of 12% for client VM and few
Hello,
The optimization of -0.0 and NaN handling in Dual-Pivot Quicksort
was done for sorting float and double values. The sorting of
floating-point values is done in three phases:
1. Move out NaN to the end of array, count -0.0 and convert it to 0.0
2. Sort everything except NaNs
If count
Date: Tue, 6 Oct 2009 23:11:25 + (UTC)
From: quitos marqu...@marquits.com
Subject: Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot
Quicksort
To: core-libs-dev@openjdk.java.net
I suppose if the array is small enough, it is better to use simple Quicksort.
And the larger
sure, will do it
Rémi Forax wrote:
just my two cents :
In the loop tagged sorting and equals element,
a[k] can be stored in a local variable to avoid to recompute it several
time.
The algorithm use two constants: 37 and 13,
I think they should be declared as private static final.
Rémi
Le
53 matches
Mail list logo
