1 /*
   2  * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package java.util;
  26 
  27 import java.util.concurrent.RecursiveAction;
  28 import java.util.concurrent.CountedCompleter;
  29 
  30 /**
  31  * Helper utilities for the parallel sort methods in Arrays.parallelSort.
  32  *
  33  * For each primitive type, plus Object, we define a static class to
  34  * contain the Sorter and Merger implementations for that type:
  35  *
  36  * Sorter classes based mainly on CilkSort
  37  * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
  38  * Basic algorithm:
  39  * if array size is small, just use a sequential sort (via Arrays.sort)
  40  *         Otherwise:
  41  *         1. Break array in half.
  42  *         2. For each half,
  43  *             a. break the half in half (i.e., quarters),
  44  *             b. sort the quarters
  45  *             c. merge them together
  46  *         3. merge together the two halves.
  47  *
  48  * One reason for splitting in quarters is that this guarantees that
  49  * the final sort is in the main array, not the workspace array
  50  * (workspace and main swap roles on each subsort step). Leaf-level
  51  * sorts use the associated sequential sort.
  52  *
  53  * Merger classes perform merging for Sorter. They are structured
  54  * such that if the underlying sort is stable (as is true for
  55  * TimSort), then so is the full sort. If big enough, they split the
  56  * largest of the two partitions in half, find the greatest point in
  57  * smaller partition less than the beginning of the second half of
  58  * larger via binary search; and then merge in parallel the two
  59  * partitions. In part to ensure tasks are triggered in
  60  * stability-preserving order, the current CountedCompleter design
  61  * requires some little tasks to serve as place holders for triggering
  62  * completion tasks. These classes (EmptyCompleter and Relay) don't
  63  * need to keep track of the arrays, and are never themselves forked,
  64  * so don't hold any task state.
  65  *
  66  * The base sequential sorts rely on non-public versions of TimSort,
  67  * ComparableTimSort sort methods that accept temp workspace array
  68  * slices that we will have already allocated, so avoids redundant
  69  * allocation.
  70  */
  71 /*package*/ class ArraysParallelSortHelpers {
  72 
  73     /*
  74      * Style note: The task classes have a lot of parameters, that are
  75      * stored as task fields and copied to local variables and used in
  76      * compute() methods, We pack these into as few lines as possible,
  77      * and hoist consistency checks among them before main loops, to
  78      * reduce distraction.
  79      */
  80 
  81     /**
  82      * A placeholder task for Sorters, used for the lowest
  83      * quartile task, that does not need to maintain array state.
  84      */
  85     static final class EmptyCompleter extends CountedCompleter<Void> {
  86         static final long serialVersionUID = 2446542900576103244L;
  87         EmptyCompleter(CountedCompleter<?> p) { super(p); }
  88         public final void compute() { }
  89     }
  90 
  91     /**
  92      * A trigger for secondary merge of two merges
  93      */
  94     static final class Relay extends CountedCompleter<Void> {
  95         static final long serialVersionUID = 2446542900576103244L;
  96         final CountedCompleter<?> task;
  97         Relay(CountedCompleter<?> task) {
  98             super(null, 1);
  99             this.task = task;
 100         }
 101         public final void compute() { }
 102         public final void onCompletion(CountedCompleter<?> t) {
 103             task.compute();
 104         }
 105     }
 106 
 107     /** Object + Comparator support class */
 108     static final class FJObject {
 109         static final class Sorter<T> extends CountedCompleter<Void> {
 110             static final long serialVersionUID = 2446542900576103244L;
 111             final T[] a, w;
 112             final int base, size, wbase, gran;
 113             Comparator<? super T> comparator;
 114             Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
 115                    int wbase, int gran,
 116                    Comparator<? super T> comparator) {
 117                 super(par);
 118                 this.a = a; this.w = w; this.base = base; this.size = size;
 119                 this.wbase = wbase; this.gran = gran;
 120                 this.comparator = comparator;
 121             }
 122             public final void compute() {
 123                 CountedCompleter<?> s = this;
 124                 Comparator<? super T> c = this.comparator;
 125                 T[] a = this.a, w = this.w; // localize all params
 126                 int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
 127                 while (n > g) {
 128                     int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
 129                     Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
 130                                                       wb+h, n-h, b, g, c));
 131                     Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
 132                                                       b+u, n-u, wb+h, g, c));
 133                     new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
 134                     new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
 135                     Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
 136                                                       b+q, h-q, wb, g, c));
 137                     new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
 138                     s = new EmptyCompleter(bc);
 139                     n = q;
 140                 }
 141                 TimSort.sort(a, b, b + n, c, w, wb, n);
 142                 s.tryComplete();
 143             }
 144         }
 145 
 146         static final class Merger<T> extends CountedCompleter<Void> {
 147             static final long serialVersionUID = 2446542900576103244L;
 148             final T[] a, w; // main and workspace arrays
 149             final int lbase, lsize, rbase, rsize, wbase, gran;
 150             Comparator<? super T> comparator;
 151             Merger(CountedCompleter<?> par, T[] a, T[] w,
 152                    int lbase, int lsize, int rbase,
 153                    int rsize, int wbase, int gran,
 154                    Comparator<? super T> comparator) {
 155                 super(par);
 156                 this.a = a; this.w = w;
 157                 this.lbase = lbase; this.lsize = lsize;
 158                 this.rbase = rbase; this.rsize = rsize;
 159                 this.wbase = wbase; this.gran = gran;
 160                 this.comparator = comparator;
 161             }
 162 
 163             public final void compute() {
 164                 Comparator<? super T> c = this.comparator;
 165                 T[] a = this.a, w = this.w; // localize all params
 166                 int lb = this.lbase, ln = this.lsize, rb = this.rbase,
 167                     rn = this.rsize, k = this.wbase, g = this.gran;
 168                 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
 169                     c == null)
 170                     throw new IllegalStateException(); // hoist checks
 171                 for (int lh, rh;;) {  // split larger, find point in smaller
 172                     if (ln >= rn) {
 173                         if (ln <= g)
 174                             break;
 175                         rh = rn;
 176                         T split = a[(lh = ln >>> 1) + lb];
 177                         for (int lo = 0; lo < rh; ) {
 178                             int rm = (lo + rh) >>> 1;
 179                             if (c.compare(split, a[rm + rb]) <= 0)
 180                                 rh = rm;
 181                             else
 182                                 lo = rm + 1;
 183                         }
 184                     }
 185                     else {
 186                         if (rn <= g)
 187                             break;
 188                         lh = ln;
 189                         T split = a[(rh = rn >>> 1) + rb];
 190                         for (int lo = 0; lo < lh; ) {
 191                             int lm = (lo + lh) >>> 1;
 192                             if (c.compare(split, a[lm + lb]) <= 0)
 193                                 lh = lm;
 194                             else
 195                                 lo = lm + 1;
 196                         }
 197                     }
 198                     Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh,
 199                                                rb + rh, rn - rh,
 200                                                k + lh + rh, g, c);
 201                     rn = rh;
 202                     ln = lh;
 203                     addToPendingCount(1);
 204                     m.fork();
 205                 }
 206 
 207                 int lf = lb + ln, rf = rb + rn; // index bounds
 208                 while (lb < lf && rb < rf) {
 209                     T t, al, ar;
 210                     if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
 211                         lb++; t = al;
 212                     }
 213                     else {
 214                         rb++; t = ar;
 215                     }
 216                     w[k++] = t;
 217                 }
 218                 if (rb < rf)
 219                     System.arraycopy(a, rb, w, k, rf - rb);
 220                 else if (lb < lf)
 221                     System.arraycopy(a, lb, w, k, lf - lb);
 222 
 223                 tryComplete();
 224             }
 225         }
 226     }
 227 }