author | bchristi |
Tue, 12 Nov 2019 13:49:40 -0800 | |
changeset 59042 | 8910b995a2ee |
parent 58520 | e036ee8bae56 |
permissions | -rw-r--r-- |
14925 | 1 |
/* |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
2 |
* Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved. |
14925 | 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 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
27 |
import java.util.concurrent.CountedCompleter; |
14925 | 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: |
|
59042 | 38 |
* if array size is small, just use a sequential sort (via Arrays.sort) |
14925 | 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 |
* |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
47 |
* One reason for splitting in quarters is that this guarantees that |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
48 |
* the final sort is in the main array, not the workspace array. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
49 |
* (workspace and main swap roles on each subsort step.) Leaf-level |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
50 |
* sorts use the associated sequential sort. |
14925 | 51 |
* |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
52 |
* Merger classes perform merging for Sorter. They are structured |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
53 |
* such that if the underlying sort is stable (as is true for |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
54 |
* TimSort), then so is the full sort. If big enough, they split the |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
55 |
* largest of the two partitions in half, find the greatest point in |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
56 |
* smaller partition less than the beginning of the second half of |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
57 |
* larger via binary search; and then merge in parallel the two |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
58 |
* partitions. In part to ensure tasks are triggered in |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
59 |
* stability-preserving order, the current CountedCompleter design |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
60 |
* requires some little tasks to serve as place holders for triggering |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
61 |
* completion tasks. These classes (EmptyCompleter and Relay) don't |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
62 |
* need to keep track of the arrays, and are never themselves forked, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
63 |
* so don't hold any task state. |
14925 | 64 |
* |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
65 |
* The base sequential sorts rely on non-public versions of TimSort, |
59042 | 66 |
* ComparableTimSort sort methods that accept temp workspace array |
67 |
* slices that we will have already allocated, so avoids redundant |
|
68 |
* allocation. |
|
14925 | 69 |
*/ |
70 |
/*package*/ class ArraysParallelSortHelpers { |
|
71 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
72 |
/* |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
73 |
* Style note: The task classes have a lot of parameters, that are |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
74 |
* stored as task fields and copied to local variables and used in |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
75 |
* compute() methods, We pack these into as few lines as possible, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
76 |
* and hoist consistency checks among them before main loops, to |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
77 |
* reduce distraction. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
78 |
*/ |
14925 | 79 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
80 |
/** |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
81 |
* A placeholder task for Sorters, used for the lowest |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
82 |
* quartile task, that does not need to maintain array state. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
83 |
*/ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
84 |
static final class EmptyCompleter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
85 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
86 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
87 |
EmptyCompleter(CountedCompleter<?> p) { super(p); } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
88 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
89 |
} |
14925 | 90 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
91 |
/** |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
92 |
* A trigger for secondary merge of two merges |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
93 |
*/ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
94 |
static final class Relay extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
95 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
96 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
97 |
final CountedCompleter<?> task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
98 |
Relay(CountedCompleter<?> task) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
99 |
super(null, 1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
100 |
this.task = task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
101 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
102 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
103 |
public final void onCompletion(CountedCompleter<?> t) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
104 |
task.compute(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
105 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
106 |
} |
14925 | 107 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
108 |
/** Object + Comparator support class */ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
109 |
static final class FJObject { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
110 |
static final class Sorter<T> extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
111 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
112 |
static final long serialVersionUID = 2446542900576103244L; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
113 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
114 |
final T[] a; |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
115 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
116 |
final T[] w; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
117 |
final int base, size, wbase, gran; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
118 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
119 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
120 |
Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
121 |
int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
122 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
123 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
124 |
this.a = a; this.w = w; this.base = base; this.size = size; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
125 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
126 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
127 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
128 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
129 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
130 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
131 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
132 |
int b = this.base, n = this.size, wb = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
133 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
134 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
135 |
Relay fc = new Relay(new Merger<>(s, w, a, wb, h, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
136 |
wb+h, n-h, b, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
137 |
Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
138 |
b+u, n-u, wb+h, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
139 |
new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork(); |
59042 | 140 |
new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork(); |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
141 |
Relay bc = new Relay(new Merger<>(fc, a, w, b, q, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
142 |
b+q, h-q, wb, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
143 |
new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork(); |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
144 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
145 |
n = q; |
14925 | 146 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
147 |
TimSort.sort(a, b, b + n, c, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
148 |
s.tryComplete(); |
14925 | 149 |
} |
150 |
} |
|
151 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
152 |
static final class Merger<T> extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
153 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
154 |
static final long serialVersionUID = 2446542900576103244L; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
155 |
// main and workspace arrays |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
156 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
157 |
final T[] a; |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
158 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
159 |
final T[] w; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
160 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
161 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
162 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
163 |
Merger(CountedCompleter<?> par, T[] a, T[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
164 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
165 |
int rsize, int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
166 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
167 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
168 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
169 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
170 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
171 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
172 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
173 |
} |
14925 | 174 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
175 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
176 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
177 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
178 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
179 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
180 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0 || |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
181 |
c == null) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
182 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
183 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
184 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
185 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
186 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
187 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
188 |
T split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
189 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
190 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
191 |
if (c.compare(split, a[rm + rb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
192 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
193 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
194 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
195 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
196 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
197 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
198 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
199 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
200 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
201 |
T split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
202 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
203 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
204 |
if (c.compare(split, a[lm + lb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
205 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
206 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
207 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
208 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
209 |
} |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
210 |
Merger<T> m = new Merger<>(this, a, w, lb + lh, ln - lh, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
211 |
rb + rh, rn - rh, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
212 |
k + lh + rh, g, c); |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
213 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
214 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
215 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
216 |
m.fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
217 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
218 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
219 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
220 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
221 |
T t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
222 |
if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
223 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
224 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
225 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
226 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
227 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
228 |
w[k++] = t; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
229 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
230 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
231 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
232 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
233 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
234 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
235 |
tryComplete(); |
14925 | 236 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
237 |
} |
59042 | 238 |
} |
14925 | 239 |
} |