--- jsr166/src/test/loops/BoxedLongSort.java 2011/10/10 16:59:04 1.6 +++ jsr166/src/test/loops/BoxedLongSort.java 2012/04/09 13:18:06 1.7 @@ -11,7 +11,7 @@ class BoxedLongSort { static final long NPS = (1000L * 1000 * 1000); static int THRESHOLD; - static final boolean warmup = true; + // static final int THRESHOLD = 64; public static void main(String[] args) throws Exception { int procs = 0; @@ -30,53 +30,71 @@ class BoxedLongSort { System.out.println("Usage: java BoxedLongSort threads n reps"); return; } - ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() : - new ForkJoinPool(procs); + if (procs == 0) + procs = Runtime.getRuntime().availableProcessors(); + THRESHOLD = ((n + 7) >>> 3) / procs; + // THRESHOLD = ((n + 15) >>> 4) / procs; + // THRESHOLD = ((n + 31) >>> 5) / procs; + if (THRESHOLD < 64) + THRESHOLD = 64; + + System.out.println("Threshold = " + THRESHOLD); + + Long[] numbers = new Long[n]; + for (int i = 0; i < n; ++i) + numbers[i] = Long.valueOf(i); Long[] a = new Long[n]; - seqRandomFill(a, 0, n); - - if (warmup) { - System.out.printf("Sorting %d longs, %d replications\n", n, 1); - Collections.shuffle(Arrays.asList(a)); - long last = System.nanoTime(); - java.util.Arrays.sort(a); - double elapsed = (double)(System.nanoTime() - last) / NPS; - System.out.printf("Arrays.sort time: %7.3f\n", elapsed); - checkSorted(a); - } - - // for now hardwire 8 * #CPUs leaf tasks - THRESHOLD = 1 + ((n + 7) >>> 3) / pool.getParallelism(); - // THRESHOLD = 1 + ((n + 15) >>> 4) / pool.getParallelism(); - // THRESHOLD = 1 + ((n + 31) >>> 5) / pool.getParallelism(); + ForkJoinPool pool = new ForkJoinPool(procs); + seqTest(a, numbers, pool, 1); + System.out.println(pool); + parTest(a, numbers, pool, reps); + System.out.println(pool); + seqTest(a, numbers, pool, 2); + System.out.println(pool); + pool.shutdown(); + } + static void seqTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) { + int n = numbers.length; System.out.printf("Sorting %d longs, %d replications\n", n, reps); + long start = System.nanoTime(); for (int i = 0; i < reps; ++i) { - Collections.shuffle(Arrays.asList(a)); - // pool.invoke(new RandomFiller(a, 0, n)); + pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); + // pool.invoke(new TaskChecker()); long last = System.nanoTime(); - pool.invoke(new Sorter(a, new Long[n], 0, n)); - double elapsed = (double)(System.nanoTime() - last) / NPS; - System.out.printf("Parallel sort time: %7.3f\n", elapsed); + // quickSort(a, 0, n-1); + java.util.Arrays.sort(a); + long now = System.nanoTime(); + double total = (double)(now - start) / NPS; + double elapsed = (double)(now - last) / NPS; + System.out.printf("Arrays.sort time: %7.3f total %9.3f\n", + elapsed, total); if (i == 0) checkSorted(a); } - System.out.println(pool); + } - System.out.printf("Sorting %d longs, %d replications\n", n, sreps); - for (int i = 0; i < sreps; ++i) { - Collections.shuffle(Arrays.asList(a)); - // pool.invoke(new RandomFiller(a, 0, n)); + static void parTest(Long[] a, Long[] numbers, ForkJoinPool pool, int reps) { + int n = numbers.length; + Long[] w = new Long[n]; + System.out.printf("Sorting %d longs, %d replications\n", n, reps); + long start = System.nanoTime(); + for (int i = 0; i < reps; ++i) { + // Arrays.fill(w, 0, n, null); + pool.invoke(new RandomRepacker(numbers, a, 0, n, n)); + // pool.invoke(new TaskChecker()); long last = System.nanoTime(); - java.util.Arrays.sort(a); - double elapsed = (double)(System.nanoTime() - last) / NPS; - System.out.printf("Arrays.sort time: %7.3f\n", elapsed); + pool.invoke(new Sorter(a, w, 0, n)); + long now = System.nanoTime(); + // pool.invoke(new TaskChecker()); + double total = (double)(now - start) / NPS; + double elapsed = (double)(now - last) / NPS; + System.out.printf("Parallel sort time: %7.3f total %9.3f\n", + elapsed, total); if (i == 0) checkSorted(a); } - System.out.println(pool); - pool.shutdown(); } static final class Sorter extends RecursiveAction { @@ -90,8 +108,10 @@ class BoxedLongSort { public void compute() { int l = origin; - if (n <= THRESHOLD) - Arrays.sort(a, l, l+n); + if (n <= THRESHOLD) { + // Arrays.sort(a, l, l+n); + quickSort(a, l, l+n-1); + } else { // divide in quarters to ensure sorted array in a not w int h = n >>> 1; int q = n >>> 2; @@ -149,28 +169,53 @@ class BoxedLongSort { */ public final void compute() { Merger rights = null; - int nleft = ln; - int nright = rn; - while (nleft > THRESHOLD) { // && nright > (THRESHOLD >>> 3)) { - int lh = nleft >>> 1; - int splitIndex = lo + lh; - Long split = a[splitIndex]; + Long[] a = this.a; + Long[] w = this.w; + int ln = this.ln; + int rn = this.rn; + int l = this.lo; + int r = this.ro; + int k = this.wo; + while (ln > THRESHOLD && rn > 4) { + int lh = ln >>> 1; + int lm = l + lh; + Long split = a[lm]; + long ls = split.longValue(); int rl = 0; - int rh = nright; + int rh = rn; while (rl < rh) { - int mid = (rl + rh) >>> 1; - if (split <= a[ro + mid]) - rh = mid; + int rm = (rl + rh) >>> 1; + if (ls <= a[r + rm].longValue()) + rh = rm; else - rl = mid + 1; + rl = rm + 1; } - (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh, - nright-rh, wo+lh+rh, rights)).fork(); - nleft = lh; - nright = rh; + (rights = new Merger(a, w, lm, ln-lh, r+rh, rn-rh, k+lh+rh, rights)).fork(); + rn = rh; + ln = lh; } - merge(nleft, nright); + int lFence = l + ln; + int rFence = r + rn; + for (Long t;;) { + if (l < lFence) { + Long al = a[l], ar; + if (r >= rFence || + al.longValue() <= (ar = a[r]).longValue()) { + ++l; t = al; + } + else { + ++r; t = ar; + } + } + else if (r < rFence) + t = a[r++]; + else + break; + w[k++] = t; + } + + // merge(nleft, nright); if (rights != null) collectRights(rights); @@ -246,4 +291,86 @@ class BoxedLongSort { } + static final class RandomRepacker extends RecursiveAction { + final Long[] src; + final Long[] dst; + final int lo, hi, size; + RandomRepacker(Long[] src, Long[] dst, + int lo, int hi, int size) { + this.src = src; this.dst = dst; + this.lo = lo; this.hi = hi; this.size = size; + } + + public final void compute() { + Long[] s = src; + Long[] d = dst; + int l = lo, h = hi, n = size; + if (h - l > THRESHOLD) { + int m = (l + h) >>> 1; + invokeAll(new RandomRepacker(s, d, l, m, n), + new RandomRepacker(s, d, m, h, n)); + } + else { + ThreadLocalRandom rng = ThreadLocalRandom.current(); + for (int i = l; i < h; ++i) + d[i] = s[rng.nextInt(n)]; + } + } + } + + static final int INSERTION_SORT_THRESHOLD = 8; + + static void quickSort(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]; + long tv = t.longValue(); + int j = i - 1; + while (j >= lo && tv < a[j].longValue()) { + a[j+1] = a[j]; + --j; + } + a[j+1] = t; + } + return; + } + + int mid = (lo + hi) >>> 1; + if (a[lo].longValue() > a[mid].longValue()) { + Long t = a[lo]; a[lo] = a[mid]; a[mid] = t; + } + if (a[mid].longValue() > a[hi].longValue()) { + Long t = a[mid]; a[mid] = a[hi]; a[hi] = t; + if (a[lo].longValue() > a[mid].longValue()) { + Long u = a[lo]; a[lo] = a[mid]; a[mid] = u; + } + } + + long pivot = a[mid].longValue(); + int left = lo+1; + int right = hi-1; + for (;;) { + while (pivot < a[right].longValue()) + --right; + while (left < right && pivot >= a[left].longValue()) + ++left; + if (left < right) { + Long t = a[left]; a[left] = a[right]; a[right] = t; + --right; + } + else break; + } + + if (left - lo <= hi - right) { + quickSort(a, lo, left); + lo = left + 1; + } + else { + quickSort(a, right, hi); + hi = left; + } + } + } + }