I actually looked into this in some detail and the reason for the difference in
C1 is two fold. First the state of the JVM at array load is slightly different
for a[i++] vs. a[i], i++. In the first case the top state has a copy of the
original i but the local for i has i+1. In the second ther
The ironic thing is that these operators were originally introduced in the C
language, at least according to well-known folklore, as an optimization -
taking advantage of inc/dec instructions from the PDP arch, in the old times
when (I suppose) compilers wouldn't do even basic strength-reduction
op
I asked someone to take a look at this and it seems that the problem is
that a[less++] requires introduction of a temporary to store the
pre-incremented index value which in turn increases register pressure
and can lead to a register spill. This seems to not only be architecture
dependent but e
both computers with Intel processor:
Pentium, Intel, 4 CPU, 3.2 GHz, 2 Gb RAM
Pentium, Intel, 4 CPU, 2.8 GHz, 2 Gb RAM
Osvaldo Pinali Doederlein wrote:
Hi Vladimir,
Hello,
I tried with the latest JDK, build 98 and see different behaviour
on two computers: 7570 / 8318 and 8560 / 8590, but so
Hi Vladimir,
Hello,
I tried with the latest JDK, build 98 and see different behaviour
on two computers: 7570 / 8318 and 8560 / 8590, but sorting method
works slower with a[less++] instruction on both computers:
Is the first computer (with larger performance diff) an AMD by any
chance? It's
00
> 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
>
> Hello,
>
> Good catch! I agree with k!=p condition, but have doubt about using
> Float.isNaN
Jun 2010 15:40:19 +0400
> From: iaroslav...@mail.ru
> Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> To: dmytro_she...@hotmail.com
> CC: joshua.bl...@google.com; core-libs-dev@openjdk.java.net
>
> Hi Dmytro,
>
> Very interesting investigation, thank you
120=40%)(48/120=40%)(36/120=30%)(24/120=20%)[376/1080=34%]
Regards,
Dmytro Sheyko
> Date: Wed, 26 May 2010 16:12:17 +0400
> From: iaroslav...@mail.ru
> Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> To: dmytro_she...@hotmail.com; joshua.bl...@google.com
> C
;
> Dmytro Sheyko wrote:
> > That's great! Thank you.
> >
> > > Date: Fri, 21 May 2010 18:38:51 +0400
> > > From: iaroslav...@mail.ru
> > > Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> > > To: dmytro_she.
Le 20/05/2010 13:25, Dmytro Sheyko a écrit :
Hi Remi,
I believe that it is up to javac to generate compact and
interpretation-efficient bytecode.
No, javac is dumb, at least, when it translates instructions. And JITs
love that.
But anyway the first case seems to as acceptable as the second
jdk6: 9132
>
> Dmytro Sheyko wrote:
> > That's great! Thank you.
> >
> > > Date: Fri, 21 May 2010 18:38:51 +0400
> > > From: iaroslav...@mail.ru
> > > Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> > > To: dmytro_she.
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
0 12:09:57 +0200
From: fo...@univ-mlv.fr
To: core-libs-dev@openjdk.java.net
Subject: Re: New portion of improvements for Dual-Pivot Quicksort
Le 19/05/2010 11:02, Dmytro Sheyko a écrit :
Vladimir,
I can see that you changed sortNegZeroAndNaN(float[]...) but probably
forgot
Le 19/05/2010 11:02, Dmytro Sheyko a écrit :
Vladimir,
I can see that you changed sortNegZeroAndNaN(float[]...) but probably
forgot to change sortNegZeroAndNaN(double[]...).
You really puzzled me with failed testcase and note that sorting
algorithm (without special attention to zeros) genera
}
I prefer the second one.
Thanks a lot,
Dmytro Sheyko
> Date: Tue, 18 May 2010 18:57:50 +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
>
>
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
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
Hi Dmytro,
Your suggested variant is better than variant with fromIndex.
It works little bit faster than my original one: ~0.7% for
client and the same for server VM (my variant with boolean
flag uses opposite value, and it works slower than yours).
Now the ratio of times is:
new / jdk7: 0.88 f
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
mail.ru
> Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> To: dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net
>
> Hi Dmytro,
>
> Thank you very much for suggestions! I checked it and here
> is my results:
>
> If we consider
ed, 5 May 2010 21:23:37 +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
>
> Hi Dmytro,
>
> Thank you very much for suggestions! I checked it and here
>
,
Dmytro Sheyko
> Date: Fri, 30 Apr 2010 17:11:10 +0400
> Subject: Re: New portion of improvements for Dual-Pivot Quicksort
> From: vladimir.iaroslav...@googlemail.com
> To: dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net
>
> Hello Dmytro,
>
> Please, see
Vladimir,
On Wed, May 5, 2010 at 12:57 AM, Joshua Bloch wrote:
>
> The sentinel technique that you use in lines 118 - 136 is questionable: you
> are modifying a portion of the array outside the specified range of the
> call, which arguably violates the contract of the call, and could be
> observ
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.
Hi Vladimir,
The trick with sentinel is quite cute. Going farther, I think it is not always
necessary to replace left outer element with the least possible value
(and restore it later after sorting) because after partitioning every element
in adjoining array part can play the role of sentinel.
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.
Here's the code review:
I think the comment on lines 102-105 was too useful to delete:
102... This
103 * method differs
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 Vladimir,
Could you remind me where can I find sources for the test suite?
Thanks,
Dmytro
> Date: Tue, 27 Apr 2010 01:50:08 +0400
> Subject: New portion of improvements for Dual-Pivot Quicksort
> From: vladimir.iaroslav...@googlemail.com
> To: core-libs-dev@openjdk.java.net
>
> Hello, ev
One quick comment: you can consider moving trivial array check so it will be
executed only if insertion sort threshold check passes:
if (length < INSERTION_SORT_THRESHOLD) {
if (length < 2) {
return;
}
On Mon, Apr 26, 2010 at 2:50 PM, Vladimir Iaroslavski <
vladimir.iaroslav...@g
Vladimir,
Cool! I will look at the changes tomorrow (Wednesday). Have you told Jon
Bentely?
Josh
On Mon, Apr 26, 2010 at 2:50 PM, Vladimir Iaroslavski <
vladimir.iaroslav...@googlemail.com> wrote:
> Hello, everyone!
>
> I've investigated the implementation of the Dual-Pivot Quicksort
> wh
32 matches
Mail list logo
