--- jsr166/src/extra166y/PAS.java 2009/01/06 14:30:57 1.1 +++ jsr166/src/extra166y/PAS.java 2010/10/16 16:40:44 1.11 @@ -26,7 +26,7 @@ class PAS { static ForkJoinPool defaultExecutor() { ForkJoinPool p = defaultExecutor; // double-check if (p == null) { - synchronized(poolLock) { + synchronized (poolLock) { p = defaultExecutor; if (p == null) { // use ceil(7/8 * ncpus) @@ -1524,7 +1524,7 @@ class PAS { continue; double x = src[k]; long bits = Double.doubleToLongBits(x); - int hash = hash((int)(bits ^ (bits >>> 32)));; + int hash = hash((int)(bits ^ (bits >>> 32))); long entry = (((long)hash) << 32) + (k + 1); int idx = hash & mask; for (;;) { @@ -1657,7 +1657,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1693,7 +1693,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1730,7 +1730,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1766,7 +1766,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1790,7 +1790,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - dcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1804,7 +1804,7 @@ class PAS { this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1840,7 +1840,7 @@ class PAS { this.a = a; this.w = w; this.origin = origin; this.n = n; this.gran = gran; } - public void compute() { + public void compute() { int l = origin; int g = gran; if (n > g) { @@ -1865,7 +1865,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - lcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1875,11 +1875,13 @@ class PAS { final RecursiveAction right; final RecursiveAction merger; FJSubSorter(RecursiveAction left, RecursiveAction right, - RecursiveAction merger){ + RecursiveAction merger) { this.left = left; this.right = right; this.merger = merger; } public void compute() { - invokeAll(left, right); + right.fork(); + left.invoke(); + right.join(); merger.invoke(); } } @@ -2303,7 +2305,7 @@ class PAS { /** Cutoff for when to use insertion-sort instead of quicksort */ static final int INSERTION_SORT_THRESHOLD = 8; - // Six nearly identical versions of quicksort + // versions of quicksort with comparators static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { for (;;) { @@ -2334,11 +2336,17 @@ class PAS { Object pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && + (c = cmp.compare(pivot, a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { Object t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2346,8 +2354,16 @@ class PAS { else break; } - oquickSort(a, cmp, lo, left); - lo = left + 1; + if (sameLefts && right == hi - 1) + return; + if (left - lo <= hi - right) { + oquickSort(a, cmp, lo, left); + lo = left + 1; + } + else { + oquickSort(a, cmp, right, hi); + hi = left; + } } } @@ -2376,15 +2392,19 @@ class PAS { Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; } } - Comparable pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (pivot.compareTo(a[right]) < 0) --right; - while (left < right && pivot.compareTo(a[left]) >= 0) + int c; + while (left < right && (c = pivot.compareTo(a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { Comparable t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2392,11 +2412,20 @@ class PAS { else break; } - ocquickSort(a, lo, left); - lo = left + 1; + if (sameLefts && right == hi - 1) + return; + if (left - lo <= hi - right) { + ocquickSort(a, lo, left); + lo = left + 1; + } + else { + ocquickSort(a, right, hi); + hi = left; + } } } + static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { for (;;) { if (hi - lo <= INSERTION_SORT_THRESHOLD) { @@ -2426,11 +2455,17 @@ class PAS { double pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && + (c = cmp.compare(pivot, a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { double t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2438,54 +2473,16 @@ class PAS { else break; } - dquickSort(a, cmp, lo, left); - lo = left + 1; - } - } - - static void dcquickSort(double[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - double t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } + if (sameLefts && right == hi - 1) return; + if (left - lo <= hi - right) { + dquickSort(a, cmp, lo, left); + lo = left + 1; } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - double t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - double t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - double u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - double pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; - if (left < right) { - double t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; + else { + dquickSort(a, cmp, right, hi); + hi = left; } - - dcquickSort(a, lo, left); - lo = left + 1; } } @@ -2518,11 +2515,17 @@ class PAS { long pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && + (c = cmp.compare(pivot, a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { long t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2530,54 +2533,16 @@ class PAS { else break; } - lquickSort(a, cmp, lo, left); - lo = left + 1; - } - } - - static void lcquickSort(long[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - long t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } + if (sameLefts && right == hi - 1) return; + if (left - lo <= hi - right) { + lquickSort(a, cmp, lo, left); + lo = left + 1; } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - long t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - long t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - long u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - long pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; - if (left < right) { - long t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; + else { + lquickSort(a, cmp, right, hi); + hi = left; } - - lcquickSort(a, lo, left); - lo = left + 1; } } @@ -2671,7 +2636,7 @@ class PAS { int cb; for (;;) { // Establish action: sum, cumulate, or both int b = phase; - if ((b & FINISHED) != 0) // already done + if ((b & FINISHED) != 0) // already done return false; if ((b & CUMULATE) != 0) cb = FINISHED; @@ -2783,7 +2748,7 @@ class PAS { } /** - * Computational operations for FJSCan + * Computational operations for FJScan */ static abstract class FJScanOp { final int threshold;