New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

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