Re[4]: New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

Josh, Dmytro,

I've updated DualPivotQuicksort class, changes have been done for all types.
Please, review the new version.

Thank you,
Vladimir

Fri, 7 May 2010 16:31:47 +0700 письмо от Dmytro Sheyko <dmytro_sheyko at hotmail.com>:

> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DualPivotQuicksort.java
Type: application/octet-stream
Size: 100790 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100508/45a668cb/DualPivotQuicksort.java>