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
Hi Vladimir,
2010/6/19 Vladimir Iaroslavski
> 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 "java -client Test" is:
>
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 "java -client Test" is:
a[less], less++; Time: 6998
a[less++]; Time: 8416
It
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
= ae3; ae3 = ae5; ae5 = t; }
> if (ae3 > ae4) { t = ae3; ae3 = ae4; ae4 = t; }
> if (ae4 > ae5) { t = ae4; ae4 = ae5; ae5 = t; }
>
> I also don't mind to change current sorting network to something more
> efficient (i.e. bubble network or so). However its impact on the
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
>
>
; 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
@hotmail.com; j...@google.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[6]: New portion of improvements for Dual-Pivot Quicksort
> Date: Fri, 14 May 2010 23:54:06 +0400
>
> Hello,
>
> I've updated the class, please, review the changes.
low = middle + 1;
> > - } else if (middleValue > 0.0f) {
> > -high = middle - 1;
> > -} else { // middleValue == 0.0f
> > -return middle;
> > +} else { // middleValue >= 0.0f
> > +
} else { // middleValue == 0.0f
> -return middle;
> +} else { // middleValue >= 0.0f
> +high = middle;
> }
> +return low;
> }
> }
>
> Counting negative values appeared more
tmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
> Date: Sun, 9 May 2010 23:51:27 +0400
>
> Josh,
> Dmytro,
>
> I have done more thoroughly testing "great - less >
s in
its worst case - when we have only one negative zero (in the half of array).
And it shows the best result if we have many zeros.
Regards,
Dmytro Sheyko
> From: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mai
ds,
Dmytro Sheyko
> From: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
> Date: Sun, 9 May 2010 23:51:27 +0400
>
> Jo
dualPivotQuicksort(a, great + 1, right, false);
}
}
> From: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
roslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of improvements for Dual-Pivot Quicksort
> Date: Fri, 7 May 2010 00:46:59 +0400
>
> Hello Josh, Dmytro,
>
> I
ort(a, left, less - 1, leftmost);
+dualPivotQuicksort(a, great + 1, right, false);
}
}
> From: iaroslav...@mail.ru
> To: j...@google.com; dmytro_she...@hotmail.com
> CC: core-libs-dev@openjdk.java.net; iaroslav...@mail.ru
> Subject: Re[2]: New portion of im
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
Vladimir,
Fascinating. I don't know why this should be so.
Joch
On Wed, May 5, 2010 at 3:03 PM, Vladimir Iaroslavski wrote:
> 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 v
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:
y comparisons. On the other hand, dual pivot quicksort is also improved:
pivots are chosen from 5 candidates, and hence it must perform less than
2*n*ln(n) key comparisons.
Regards,
Dmytro Sheyko
> Date: Tue, 27 Apr 2010 01:50:08 +0400
> Subject: New portion of improvements for Dual-Pivo
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.
7 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, everyone!
>
> I've investigated the implementation of the Dual-Pivot Quicksort
> which
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
> 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, everyone!
>>
>> I've investigated the implementati
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.ne
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
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
43 matches
Mail list logo
