New portion of improvements for Dual-Pivot Quicksort
Vladimir Iaroslavski
iaroslavski at mail.ru
Fri May 7 12:27:55 UTC 2010
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 for client, 1.01 for server
new / jdk6: 0.61 for client, 0.49 for server
And what about long method declaration:
private static void dualPivotQuicksort(int[] a, int left, int right, boolean leftmost)
I think that we can use name "sort" for it, and the line will be shorter.
I'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 flag instead of int index?
>>
>> --
>> Dmytro Sheyko
>>
>> PS
>> --- DualPivotQuicksortWithoutSentinel.java Fri May 07 10:40:14 2010
>> +++ DualPivotQuicksortWithoutSentinelA.java Fri May 07 11:54:51 2010
>> @@ -39,7 +39,7 @@
>> * @version 2010.04.30 m765.827.12i:5\7
>> * @since 1.7
>> */
>> -final class DualPivotQuicksortWithoutSentinel {
>> +final class DualPivotQuicksortWithoutSentinelA {
>>
>> /**
>> * Prevents instantiation.
>> @@ -78,7 +78,7 @@
>> * @param a the array to be sorted
>> */
>> public static void sort(int[] a) {
>> - dualPivotQuicksort(a, 0, a.length - 1, 0);
>> + dualPivotQuicksort(a, 0, a.length - 1, true);
>> }
>>
>> /**
>> @@ -96,7 +96,7 @@
>> */
>> public static void sort(int[] a, int fromIndex, int toIndex) {
>> rangeCheck(a.length, fromIndex, toIndex);
>> - dualPivotQuicksort(a, fromIndex, toIndex - 1, fromIndex);
>> + dualPivotQuicksort(a, fromIndex, toIndex - 1, true);
>> }
>>
>> /**
>> @@ -108,12 +108,12 @@
>> * @param right the index of the last element, inclusive, to be
>> sorted
>> * @param fromIndex the first index of the original range to be
>> sorted
>> */
>> - private static void dualPivotQuicksort(int[] a, int left, int
>> right, int fromIndex) {
>> + private static void dualPivotQuicksort(int[] a, int left, int
>> right, boolean leftmost) {
>> int length = right - left + 1;
>>
>> // Use insertion sort on tiny arrays
>> if (length < INSERTION_SORT_THRESHOLD) {
>> - if (left > fromIndex) {
>> + if (!leftmost) {
>> /*
>> * TODO
>> */
>> @@ -129,11 +129,11 @@
>> * For case, when left == fromIndex, traditional
>> (without
>> * sentinel) insertion sort, optimized for server VM,
>> is used.
>> */
>> - for (int i = fromIndex, j = i; i < right; j = ++i) {
>> + for (int i = left, j = i; i < right; j = ++i) {
>> int ai = a[i + 1];
>> while (ai < a[j]) {
>> a[j + 1] = a[j];
>> - if (j-- == fromIndex) {
>> + if (j-- == left) {
>> break;
>> }
>> }
>> @@ -237,8 +237,8 @@
>> a[right] = a[great + 1]; a[great + 1] = pivot2;
>>
>> // Sort left and right parts recursively, excluding known
>> pivots
>> - dualPivotQuicksort(a, left, less - 2, fromIndex);
>> - dualPivotQuicksort(a, great + 2, right, fromIndex);
>> + dualPivotQuicksort(a, left, less - 2, leftmost);
>> + dualPivotQuicksort(a, great + 2, right, false);
>>
>> /*
>> * If center part is too large (comprises > 5/7 of the
>> array),
>> @@ -295,7 +295,7 @@
>> }
>>
>> // Sort center part recursively
>> - dualPivotQuicksort(a, less, great, fromIndex);
>> + dualPivotQuicksort(a, less, great, false);
>>
>> } else { // Pivots are equal
>> /*
>> @@ -350,8 +350,8 @@
>> }
>>
>> // Sort left and right parts recursively
>> - dualPivotQuicksort(a, left, less - 1, fromIndex);
>> - dualPivotQuicksort(a, great + 1, right, fromIndex);
>> + dualPivotQuicksort(a, left, less - 1, leftmost);
>> + dualPivotQuicksort(a, great + 1, right, false);
>> }
>> }
>>
>> > From: iaroslavski at mail.ru
>> > To: jjb at google.com; dmytro_sheyko at hotmail.com
>> > CC: core-libs-dev at openjdk.java.net; iaroslavski at 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've modified the DQP and now it doesn't touch elements outside of
>> > the range and doesn't set a sentinel at all. Elements from the left
>> > part are used as a sentinel (as it was suggested by Dmytro) and index
>> > fromIndex is used as left boundary (suggestion from Josh). The index
>> > fromIndex is the initial left boundary and passed down through the
>> > recursions. No any tricks with changing outside of the range and
>> > negative infinity.
>> >
>> > The fragment of code is (full version see in attachment):
>> >
>> > * ...
>> > * @param fromIndex the first index of the original range to be sorted
>> > */
>> > private static void dualPivotQuicksort(int[] a, int left, int
>> right, int fromIndex) {
>> > int length = right - left + 1;
>> >
>> > // Use insertion sort on tiny arrays
>> > if (length < INSERTION_SORT_THRESHOLD) {
>> > if (left > fromIndex) {
>> > /*
>> > * TODO
>> > */
>> > for (int j, i = left + 1; i <= right; i++) {
>> > int ai = a[i];
>> > for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
>> > a[j + 1] = a[j];
>> > }
>> > a[j + 1] = ai;
>> > }
>> > } else {
>> > /*
>> > * For case, when left == fromIndex, traditional (without
>> > * sentinel) insertion sort, optimized for server VM, is used.
>> > */
>> > for (int i = fromIndex, j = i; i < right; j = ++i) {
>> > int ai = a[i + 1];
>> > while (ai < a[j]) {
>> > a[j + 1] = a[j];
>> > if (j-- == fromIndex) {
>> > break;
>> > }
>> > }
>> > a[j + 1] = ai;
>> > }
>> > }
>> > return;
>> > }
>> > ...
>> >
>> > This variant is little bit faster (~0.5%) on client VM and slower
>> (~2%)
>> > on server VM than original variant. I think that it is not too bad.
>> > What do you think?
>> >
>> > And one question: the method declaration
>> >
>> > private static void dualPivotQuicksort(int[] a, int left, int
>> right, int fromIndex) {
>> >
>> > now is too long, how should I format it? What is the guideline?
>> >
>> > Thank you,
>> > Vladimir
>> >
>> > Wed, 5 May 2010 18:21:18 -0400 письмо от Joshua Bloch
>> <jjb at google.com>:
>> >
>> > > Vladimir,
>> > >
>> > > On Wed, May 5, 2010 at 12:57 AM, Joshua Bloch <jjb at google.com>
>> 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 observed in a multithreaded program. It's not
>> beyond the realm of reason that it could break existing clients. I
>> will discuss it with Doug Lea and let you know what he says.
>> > >
>> > > I talked to Doug, and he agrees that it's not acceptable to
>> modify any location outside the array range that the caller has asked
>> you to sort. This doesn't entirely kill the optimization; it's still
>> OK to use on subranges that don't include the first element of the
>> range that you were asked to sort. In other words, this test
>> > >
>> > > 120 if (left > 0) {
>> > >
>> > > Should be replaced by:
>> > >
>> > > 120 if (left > fromIndex + 1) {
>> > >
>> > > and you have to pass original fromIndex down to the recursive
>> calls (in fact, you could pass fromIndex +1 to avoid the cost of the
>> addition in each test). It's not clear whether the cost of passing
>> this index down through the recursive calls will eliminate the gains
>> of the optimization, but it's worth performing the experiment.
>> > >
>> > > Sorry,
>> > > Josh
More information about the core-libs-dev
mailing list