1 /* 2 * Copyright (c) 2012, 2019, 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.CountedCompleter; 28 29 /** 30 * Helper utilities for the parallel sort methods in Arrays.parallelSort. 31 * 32 * For each primitive type, plus Object, we define a static class to 33 * contain the Sorter and Merger implementations for that type: 34 * 35 * Sorter classes based mainly on CilkSort 36 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>: 37 * Basic algorithm: 38 * if array size is small, just use a sequential sort (via Arrays.sort) 39 * Otherwise: 40 * 1. Break array in half. 41 * 2. For each half, 42 * a. break the half in half (i.e., quarters), 43 * b. sort the quarters 44 * c. merge them together 45 * 3. merge together the two halves. 46 * 47 * One reason for splitting in quarters is that this guarantees that 48 * the final sort is in the main array, not the workspace array. 49 * (workspace and main swap roles on each subsort step.) Leaf-level 50 * sorts use the associated sequential sort. 51 * 52 * Merger classes perform merging for Sorter. They are structured 53 * such that if the underlying sort is stable (as is true for 54 * TimSort), then so is the full sort. If big enough, they split the 55 * largest of the two partitions in half, find the greatest point in 56 * smaller partition less than the beginning of the second half of 57 * larger via binary search; and then merge in parallel the two 58 * partitions. In part to ensure tasks are triggered in 59 * stability-preserving order, the current CountedCompleter design 60 * requires some little tasks to serve as place holders for triggering 61 * completion tasks. These classes (EmptyCompleter and Relay) don't 62 * need to keep track of the arrays, and are never themselves forked, 63 * so don't hold any task state. 64 * 65 * The base sequential sorts rely on non-public versions of TimSort, 66 * ComparableTimSort sort methods that accept temp workspace array 67 * slices that we will have already allocated, so avoids redundant 68 * allocation. 69 */ 70 /*package*/ class ArraysParallelSortHelpers { 71 72 /* 73 * Style note: The task classes have a lot of parameters, that are 74 * stored as task fields and copied to local variables and used in 75 * compute() methods, We pack these into as few lines as possible, 76 * and hoist consistency checks among them before main loops, to 77 * reduce distraction. 78 */ 79 80 /** 81 * A placeholder task for Sorters, used for the lowest 82 * quartile task, that does not need to maintain array state. 83 */ 84 static final class EmptyCompleter extends CountedCompleter<Void> { 85 @java.io.Serial 86 static final long serialVersionUID = 2446542900576103244L; EmptyCompleter(CountedCompleter<?> p)87 EmptyCompleter(CountedCompleter<?> p) { super(p); } compute()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 @java.io.Serial 96 static final long serialVersionUID = 2446542900576103244L; 97 final CountedCompleter<?> task; Relay(CountedCompleter<?> task)98 Relay(CountedCompleter<?> task) { 99 super(null, 1); 100 this.task = task; 101 } compute()102 public final void compute() { } onCompletion(CountedCompleter<?> t)103 public final void onCompletion(CountedCompleter<?> t) { 104 task.compute(); 105 } 106 } 107 108 /** Object + Comparator support class */ 109 static final class FJObject { 110 static final class Sorter<T> extends CountedCompleter<Void> { 111 @java.io.Serial 112 static final long serialVersionUID = 2446542900576103244L; 113 @SuppressWarnings("serial") // Not statically typed as Serializable 114 final T[] a; 115 @SuppressWarnings("serial") // Not statically typed as Serializable 116 final T[] w; 117 final int base, size, wbase, gran; 118 @SuppressWarnings("serial") // Not statically typed as Serializable 119 Comparator<? super T> comparator; Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, int wbase, int gran, Comparator<? super T> comparator)120 Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, 121 int wbase, int gran, 122 Comparator<? super T> comparator) { 123 super(par); 124 this.a = a; this.w = w; this.base = base; this.size = size; 125 this.wbase = wbase; this.gran = gran; 126 this.comparator = comparator; 127 } compute()128 public final void compute() { 129 CountedCompleter<?> s = this; 130 Comparator<? super T> c = this.comparator; 131 T[] a = this.a, w = this.w; // localize all params 132 int b = this.base, n = this.size, wb = this.wbase, g = this.gran; 133 while (n > g) { 134 int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles 135 Relay fc = new Relay(new Merger<>(s, w, a, wb, h, 136 wb+h, n-h, b, g, c)); 137 Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q, 138 b+u, n-u, wb+h, g, c)); 139 new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork(); 140 new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork(); 141 Relay bc = new Relay(new Merger<>(fc, a, w, b, q, 142 b+q, h-q, wb, g, c)); 143 new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork(); 144 s = new EmptyCompleter(bc); 145 n = q; 146 } 147 TimSort.sort(a, b, b + n, c, w, wb, n); 148 s.tryComplete(); 149 } 150 } 151 152 static final class Merger<T> extends CountedCompleter<Void> { 153 @java.io.Serial 154 static final long serialVersionUID = 2446542900576103244L; 155 // main and workspace arrays 156 @SuppressWarnings("serial") // Not statically typed as Serializable 157 final T[] a; 158 @SuppressWarnings("serial") // Not statically typed as Serializable 159 final T[] w; 160 final int lbase, lsize, rbase, rsize, wbase, gran; 161 @SuppressWarnings("serial") // Not statically typed as Serializable 162 Comparator<? super T> comparator; Merger(CountedCompleter<?> par, T[] a, T[] w, int lbase, int lsize, int rbase, int rsize, int wbase, int gran, Comparator<? super T> comparator)163 Merger(CountedCompleter<?> par, T[] a, T[] w, 164 int lbase, int lsize, int rbase, 165 int rsize, int wbase, int gran, 166 Comparator<? super T> comparator) { 167 super(par); 168 this.a = a; this.w = w; 169 this.lbase = lbase; this.lsize = lsize; 170 this.rbase = rbase; this.rsize = rsize; 171 this.wbase = wbase; this.gran = gran; 172 this.comparator = comparator; 173 } 174 compute()175 public final void compute() { 176 Comparator<? super T> c = this.comparator; 177 T[] a = this.a, w = this.w; // localize all params 178 int lb = this.lbase, ln = this.lsize, rb = this.rbase, 179 rn = this.rsize, k = this.wbase, g = this.gran; 180 if (a == null || w == null || lb < 0 || rb < 0 || k < 0 || 181 c == null) 182 throw new IllegalStateException(); // hoist checks 183 for (int lh, rh;;) { // split larger, find point in smaller 184 if (ln >= rn) { 185 if (ln <= g) 186 break; 187 rh = rn; 188 T split = a[(lh = ln >>> 1) + lb]; 189 for (int lo = 0; lo < rh; ) { 190 int rm = (lo + rh) >>> 1; 191 if (c.compare(split, a[rm + rb]) <= 0) 192 rh = rm; 193 else 194 lo = rm + 1; 195 } 196 } 197 else { 198 if (rn <= g) 199 break; 200 lh = ln; 201 T split = a[(rh = rn >>> 1) + rb]; 202 for (int lo = 0; lo < lh; ) { 203 int lm = (lo + lh) >>> 1; 204 if (c.compare(split, a[lm + lb]) <= 0) 205 lh = lm; 206 else 207 lo = lm + 1; 208 } 209 } 210 Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh, 211 rb + rh, rn - rh, 212 k + lh + rh, g, c); 213 rn = rh; 214 ln = lh; 215 addToPendingCount(1); 216 m.fork(); 217 } 218 219 int lf = lb + ln, rf = rb + rn; // index bounds 220 while (lb < lf && rb < rf) { 221 T t, al, ar; 222 if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { 223 lb++; t = al; 224 } 225 else { 226 rb++; t = ar; 227 } 228 w[k++] = t; 229 } 230 if (rb < rf) 231 System.arraycopy(a, rb, w, k, rf - rb); 232 else if (lb < lf) 233 System.arraycopy(a, lb, w, k, lf - lb); 234 235 tryComplete(); 236 } 237 } 238 } 239 } 240