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 improve
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 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 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
>>> [richard
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 j
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
> element
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 j
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
-
re no unexplained differences between
> the implementation but am curious if it would be possible that differences
> could arise or exist.
>
> Mike
>
> On Jan 20 2011, at 10:09 , Vladimir Iaroslavski wrote:
>
> > Here is improvement for sorting primitives:
> > http://cr.openjdk.java.net/~alanb/7013585/webrev
> > ...
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!
I've updated Dual-Pivot Quicksort, Sorting and Arrays classes,
please review.
http://cr.openjdk.java.net/~alanb/6976036/webrev
In compare with previous version (JDK 7 vs. JDK 6) the ratio is:
52.14% for client and 41.62% for server VM (was 57.22% and 46.18%).
Summary of changes:
1. Ran
Hello!
I updated Dual-Pivot Quicksort and Sorting classes.
http://cr.openjdk.java.net/~alanb/6976036/webrev
In compare with previous version the ratio (JDK 7 / JDK 6)
now is (client / server): 54.35% / 42.79% (was 57.22% / 46.18%).
Summary of changes:
Sorting class: new type of test (check su
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
e1/e2
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
Osvaldo Doederlein wrote:
Hi Vladimir,
2010/6/19 Vladimir Iaroslavski <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; //
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.
*
HotSpot(TM) Client VM (build 17.0-b09, mixed mode, sharing)
Thanks,
Vladimir
Fri, 18 Jun 2010 13:03:50 -0300 письмо от Osvaldo Doederlein
:
> Hi,
>
> 2010/6/18 Vladimir Iaroslavski
> Hello,
>
> Here is next piece of improvements, see attached class.
> It is surprise but c
dmytro_she...@hotmail.com
> > > > > > > > > > CC: core-libs-dev@openjdk.java.net
> > > > > > > > > >
> > > > > > > > > > Hello,
> > > > > > > > > >
> > > >
; > > > > > > current version: 57.22% 46.18%
> > > > > > >
> > > > > > > So, we win 2-3% !
> > > > > > >
> > > > > > > Thank you,
> > > > > > > Vladimir
> >
ecause Hotspot anyway emits
> > range
> > > > > > checks at its discretion and therefore processZeros generally
> > does not
> > > > > > work as fast as I expected.
> > > > > > So complications I made are not
> where k == p).
> > > >
> > > > /*
> > > > * Skip the last negative value (if any) or all leading negative
> > > > zeros
> > > > */
> > > > while (left <= right && Double.doubleToRaw
gt; > > where k == p).
> > > >
> > > > /*
> > > > * Skip the last negative value (if any) or all leading negative
> > > > zeros
> > > > */
> > > > while (left <= right && Double.doubleToRawLongBits(a[left]
Sheyko
> Date: Wed, 19 May 2010 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
Sounds good!
Will consider too...
Mon, 17 May 2010 22:24:11 +0700 письмо от Dmytro Sheyko
:
> 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: iaroslav...@mail.ru
> > Sub
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 handle
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
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
negative
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 chec
m preparing new version, and will send it soon.
Thank you,
Vladimir
Vladimir Iaroslavski wrote:
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
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.javaFr
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,
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:
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,
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
Pittsburgh.
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 :
> Hello Vladimir,
>
> Could you remind me where can I find sources for the test suite?
>
> Thanks,
> Dmytro
>
>> Date: Tue, 27 Apr 2010 0
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 pe
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 of
Date: Tue, 6 Oct 2009 23:11:25 + (UTC)
From: quitos
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 the array, the more se
Hi,
I've tried to use local variable int ak = a[k] in the loop
and not found saving of time. There are 3 occurrences of a[k]
in each loop, but only two can be changed because third
comes after line: swap(a, k, great--);
As summary: I'm changing only hardcoded constant by
private static final var
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
L
Hi Ulf,
Sure, I have tried it, see:
Original Message
Subject: Re: Dual-Pivot Quicksort Analysis
Date: Wed, 09 Sep 2009 18:45:46 +0400
From: Vladimir Yaroslavskiy
Organization: Sun Microsystems, Inc.
To: Jon Bentley
CC: Joshua Bloch
Hello,
I've converted the pseudocode into
61 matches
Mail list logo