author | mchung |
Fri, 22 May 2015 16:43:39 -0700 | |
changeset 30789 | 9eca83469588 |
parent 25859 | 3317bb8137f4 |
permissions | -rw-r--r-- |
14925 | 1 |
/* |
23010
6dadb192ad81
8029235: Update copyright year to match last edit in jdk8 jdk repository for 2013
lana
parents:
22078
diff
changeset
|
2 |
* Copyright (c) 2012, 2013, 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 |
||
27 |
import java.util.concurrent.RecursiveAction; |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
28 |
import java.util.concurrent.CountedCompleter; |
14925 | 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 quicksort (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 |
* |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
48 |
* One reason for splitting in quarters is that this guarantees that |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
49 |
* 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
|
50 |
* (workspace and main swap roles on each subsort step.) Leaf-level |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
51 |
* sorts use the associated sequential sort. |
14925 | 52 |
* |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
53 |
* Merger classes perform merging for Sorter. They are structured |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
54 |
* 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
|
55 |
* 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
|
56 |
* 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
|
57 |
* smaller partition less than the beginning of the second half of |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
58 |
* larger via binary search; and then merge in parallel the two |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
59 |
* partitions. In part to ensure tasks are triggered in |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
60 |
* stability-preserving order, the current CountedCompleter design |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
61 |
* requires some little tasks to serve as place holders for triggering |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
62 |
* completion tasks. These classes (EmptyCompleter and Relay) don't |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
63 |
* 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
|
64 |
* so don't hold any task state. |
14925 | 65 |
* |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
66 |
* The primitive class versions (FJByte... FJDouble) are |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
67 |
* identical to each other except for type declarations. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
68 |
* |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
69 |
* The base sequential sorts rely on non-public versions of TimSort, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
70 |
* ComparableTimSort, and DualPivotQuicksort sort methods that accept |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
71 |
* temp workspace array slices that we will have already allocated, so |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
72 |
* avoids redundant allocation. (Except for DualPivotQuicksort byte[] |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
73 |
* sort, that does not ever use a workspace array.) |
14925 | 74 |
*/ |
75 |
/*package*/ class ArraysParallelSortHelpers { |
|
76 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
77 |
/* |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
78 |
* 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
|
79 |
* 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
|
80 |
* compute() methods, We pack these into as few lines as possible, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
81 |
* and hoist consistency checks among them before main loops, to |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
82 |
* reduce distraction. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
83 |
*/ |
14925 | 84 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
85 |
/** |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
86 |
* A placeholder task for Sorters, used for the lowest |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
87 |
* quartile task, that does not need to maintain array state. |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
88 |
*/ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
89 |
static final class EmptyCompleter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
90 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
91 |
EmptyCompleter(CountedCompleter<?> p) { super(p); } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
92 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
93 |
} |
14925 | 94 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
95 |
/** |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
96 |
* A trigger for secondary merge of two merges |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
97 |
*/ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
98 |
static final class Relay extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
99 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
100 |
final CountedCompleter<?> task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
101 |
Relay(CountedCompleter<?> task) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
102 |
super(null, 1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
103 |
this.task = task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
104 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
105 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
106 |
public final void onCompletion(CountedCompleter<?> t) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
107 |
task.compute(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
108 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
109 |
} |
14925 | 110 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
111 |
/** Object + Comparator support class */ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
112 |
static final class FJObject { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
113 |
static final class Sorter<T> extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
114 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
115 |
final T[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
116 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
117 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
118 |
Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
119 |
int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
120 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
121 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
122 |
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
|
123 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
124 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
125 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
126 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
127 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
128 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
129 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
130 |
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
|
131 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
132 |
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
|
133 |
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
|
134 |
wb+h, n-h, b, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
135 |
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
|
136 |
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
|
137 |
new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork(); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
138 |
new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();; |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
139 |
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
|
140 |
b+q, h-q, wb, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
141 |
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
|
142 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
143 |
n = q; |
14925 | 144 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
145 |
TimSort.sort(a, b, b + n, c, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
146 |
s.tryComplete(); |
14925 | 147 |
} |
148 |
} |
|
149 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
150 |
static final class Merger<T> extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
151 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
152 |
final T[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
153 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
154 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
155 |
Merger(CountedCompleter<?> par, T[] a, T[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
156 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
157 |
int rsize, int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
158 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
159 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
160 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
161 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
162 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
163 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
164 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
165 |
} |
14925 | 166 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
167 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
168 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
169 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
170 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
171 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
172 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0 || |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
173 |
c == null) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
174 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
175 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
176 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
177 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
178 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
179 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
180 |
T split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
181 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
182 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
183 |
if (c.compare(split, a[rm + rb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
184 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
185 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
186 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
187 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
188 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
189 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
190 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
191 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
192 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
193 |
T split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
194 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
195 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
196 |
if (c.compare(split, a[lm + lb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
197 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
198 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
199 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
200 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
201 |
} |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
202 |
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
|
203 |
rb + rh, rn - rh, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
204 |
k + lh + rh, g, c); |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
205 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
206 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
207 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
208 |
m.fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
209 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
210 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
211 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
212 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
213 |
T t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
214 |
if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
215 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
216 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
217 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
218 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
219 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
220 |
w[k++] = t; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
221 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
222 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
223 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
224 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
225 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
226 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
227 |
tryComplete(); |
14925 | 228 |
} |
229 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
230 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
231 |
} // FJObject |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
232 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
233 |
/** byte support class */ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
234 |
static final class FJByte { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
235 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
236 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
237 |
final byte[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
238 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
239 |
Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
240 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
241 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
242 |
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
|
243 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
244 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
245 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
246 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
247 |
byte[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
248 |
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
|
249 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
250 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
251 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
252 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
253 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
254 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
255 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
256 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
257 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
258 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
259 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
260 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
261 |
n = q; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
262 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
263 |
DualPivotQuicksort.sort(a, b, b + n - 1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
264 |
s.tryComplete(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
265 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
266 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
267 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
268 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
269 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
270 |
final byte[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
271 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
272 |
Merger(CountedCompleter<?> par, byte[] a, byte[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
273 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
274 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
275 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
276 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
277 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
278 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
279 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
280 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
281 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
282 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
283 |
byte[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
284 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
285 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
286 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
287 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
288 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
289 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
290 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
291 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
292 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
293 |
byte split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
294 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
295 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
296 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
297 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
298 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
299 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
300 |
} |
14925 | 301 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
302 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
303 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
304 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
305 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
306 |
byte split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
307 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
308 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
309 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
310 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
311 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
312 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
313 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
314 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
315 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
316 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
317 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
318 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
319 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
320 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
321 |
m.fork(); |
14925 | 322 |
} |
323 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
324 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
325 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
326 |
byte t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
327 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
328 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
329 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
330 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
331 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
332 |
} |
14925 | 333 |
w[k++] = t; |
334 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
335 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
336 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
337 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
338 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
339 |
tryComplete(); |
14925 | 340 |
} |
341 |
} |
|
342 |
} // FJByte |
|
343 |
||
344 |
/** char support class */ |
|
345 |
static final class FJChar { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
346 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
347 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
348 |
final char[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
349 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
350 |
Sorter(CountedCompleter<?> par, char[] a, char[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
351 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
352 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
353 |
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
|
354 |
this.wbase = wbase; this.gran = gran; |
14925 | 355 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
356 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
357 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
358 |
char[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
359 |
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
|
360 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
361 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
362 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
363 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
364 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
365 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
366 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
367 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
368 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
369 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
370 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
371 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
372 |
n = q; |
14925 | 373 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
374 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
375 |
s.tryComplete(); |
14925 | 376 |
} |
377 |
} |
|
378 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
379 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
380 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
381 |
final char[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
382 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
383 |
Merger(CountedCompleter<?> par, char[] a, char[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
384 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
385 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
386 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
387 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
388 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
389 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
390 |
this.wbase = wbase; this.gran = gran; |
14925 | 391 |
} |
392 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
393 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
394 |
char[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
395 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
396 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
397 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
398 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
399 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
400 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
401 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
402 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
403 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
404 |
char split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
405 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
406 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
407 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
408 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
409 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
410 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
411 |
} |
14925 | 412 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
413 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
414 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
415 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
416 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
417 |
char split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
418 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
419 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
420 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
421 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
422 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
423 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
424 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
425 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
426 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
427 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
428 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
429 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
430 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
431 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
432 |
m.fork(); |
14925 | 433 |
} |
434 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
435 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
436 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
437 |
char t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
438 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
439 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
440 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
441 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
442 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
443 |
} |
14925 | 444 |
w[k++] = t; |
445 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
446 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
447 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
448 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
449 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
450 |
tryComplete(); |
14925 | 451 |
} |
452 |
} |
|
453 |
} // FJChar |
|
454 |
||
455 |
/** short support class */ |
|
456 |
static final class FJShort { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
457 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
458 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
459 |
final short[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
460 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
461 |
Sorter(CountedCompleter<?> par, short[] a, short[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
462 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
463 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
464 |
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
|
465 |
this.wbase = wbase; this.gran = gran; |
14925 | 466 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
467 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
468 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
469 |
short[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
470 |
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
|
471 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
472 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
473 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
474 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
475 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
476 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
477 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
478 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
479 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
480 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
481 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
482 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
483 |
n = q; |
14925 | 484 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
485 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
486 |
s.tryComplete(); |
14925 | 487 |
} |
488 |
} |
|
489 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
490 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
491 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
492 |
final short[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
493 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
494 |
Merger(CountedCompleter<?> par, short[] a, short[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
495 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
496 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
497 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
498 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
499 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
500 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
501 |
this.wbase = wbase; this.gran = gran; |
14925 | 502 |
} |
503 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
504 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
505 |
short[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
506 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
507 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
508 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
509 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
510 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
511 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
512 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
513 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
514 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
515 |
short split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
516 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
517 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
518 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
519 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
520 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
521 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
522 |
} |
14925 | 523 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
524 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
525 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
526 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
527 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
528 |
short split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
529 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
530 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
531 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
532 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
533 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
534 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
535 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
536 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
537 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
538 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
539 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
540 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
541 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
542 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
543 |
m.fork(); |
14925 | 544 |
} |
545 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
546 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
547 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
548 |
short t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
549 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
550 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
551 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
552 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
553 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
554 |
} |
14925 | 555 |
w[k++] = t; |
556 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
557 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
558 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
559 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
560 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
561 |
tryComplete(); |
14925 | 562 |
} |
563 |
} |
|
564 |
} // FJShort |
|
565 |
||
566 |
/** int support class */ |
|
567 |
static final class FJInt { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
568 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
569 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
570 |
final int[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
571 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
572 |
Sorter(CountedCompleter<?> par, int[] a, int[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
573 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
574 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
575 |
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
|
576 |
this.wbase = wbase; this.gran = gran; |
14925 | 577 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
578 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
579 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
580 |
int[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
581 |
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
|
582 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
583 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
584 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
585 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
586 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
587 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
588 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
589 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
590 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
591 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
592 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
593 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
594 |
n = q; |
14925 | 595 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
596 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
597 |
s.tryComplete(); |
14925 | 598 |
} |
599 |
} |
|
600 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
601 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
602 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
603 |
final int[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
604 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
605 |
Merger(CountedCompleter<?> par, int[] a, int[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
606 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
607 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
608 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
609 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
610 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
611 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
612 |
this.wbase = wbase; this.gran = gran; |
14925 | 613 |
} |
614 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
615 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
616 |
int[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
617 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
618 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
619 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
620 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
621 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
622 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
623 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
624 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
625 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
626 |
int split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
627 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
628 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
629 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
630 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
631 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
632 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
633 |
} |
14925 | 634 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
635 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
636 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
637 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
638 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
639 |
int split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
640 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
641 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
642 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
643 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
644 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
645 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
646 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
647 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
648 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
649 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
650 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
651 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
652 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
653 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
654 |
m.fork(); |
14925 | 655 |
} |
656 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
657 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
658 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
659 |
int t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
660 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
661 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
662 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
663 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
664 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
665 |
} |
14925 | 666 |
w[k++] = t; |
667 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
668 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
669 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
670 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
671 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
672 |
tryComplete(); |
14925 | 673 |
} |
674 |
} |
|
675 |
} // FJInt |
|
676 |
||
677 |
/** long support class */ |
|
678 |
static final class FJLong { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
679 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
680 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
681 |
final long[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
682 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
683 |
Sorter(CountedCompleter<?> par, long[] a, long[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
684 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
685 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
686 |
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
|
687 |
this.wbase = wbase; this.gran = gran; |
14925 | 688 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
689 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
690 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
691 |
long[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
692 |
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
|
693 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
694 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
695 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
696 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
697 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
698 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
699 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
700 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
701 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
702 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
703 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
704 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
705 |
n = q; |
14925 | 706 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
707 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
708 |
s.tryComplete(); |
14925 | 709 |
} |
710 |
} |
|
711 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
712 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
713 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
714 |
final long[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
715 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
716 |
Merger(CountedCompleter<?> par, long[] a, long[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
717 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
718 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
719 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
720 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
721 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
722 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
723 |
this.wbase = wbase; this.gran = gran; |
14925 | 724 |
} |
725 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
726 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
727 |
long[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
728 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
729 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
730 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
731 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
732 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
733 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
734 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
735 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
736 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
737 |
long split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
738 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
739 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
740 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
741 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
742 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
743 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
744 |
} |
14925 | 745 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
746 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
747 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
748 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
749 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
750 |
long split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
751 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
752 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
753 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
754 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
755 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
756 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
757 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
758 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
759 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
760 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
761 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
762 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
763 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
764 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
765 |
m.fork(); |
14925 | 766 |
} |
767 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
768 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
769 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
770 |
long t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
771 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
772 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
773 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
774 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
775 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
776 |
} |
14925 | 777 |
w[k++] = t; |
778 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
779 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
780 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
781 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
782 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
783 |
tryComplete(); |
14925 | 784 |
} |
785 |
} |
|
786 |
} // FJLong |
|
787 |
||
788 |
/** float support class */ |
|
789 |
static final class FJFloat { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
790 |
static final class Sorter extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
791 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
792 |
final float[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
793 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
794 |
Sorter(CountedCompleter<?> par, float[] a, float[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
795 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
796 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
797 |
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
|
798 |
this.wbase = wbase; this.gran = gran; |
14925 | 799 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
800 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
801 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
802 |
float[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
803 |
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
|
804 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
805 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
806 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
807 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
808 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
809 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
810 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
811 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
812 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
813 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
814 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
815 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
816 |
n = q; |
14925 | 817 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
818 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
819 |
s.tryComplete(); |
14925 | 820 |
} |
821 |
} |
|
822 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
823 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
824 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
825 |
final float[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
826 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
827 |
Merger(CountedCompleter<?> par, float[] a, float[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
828 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
829 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
830 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
831 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
832 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
833 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
834 |
this.wbase = wbase; this.gran = gran; |
14925 | 835 |
} |
836 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
837 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
838 |
float[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
839 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
840 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
841 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
842 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
843 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
844 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
845 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
846 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
847 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
848 |
float split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
849 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
850 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
851 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
852 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
853 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
854 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
855 |
} |
14925 | 856 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
857 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
858 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
859 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
860 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
861 |
float split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
862 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
863 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
864 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
865 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
866 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
867 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
868 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
869 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
870 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
871 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
872 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
873 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
874 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
875 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
876 |
m.fork(); |
14925 | 877 |
} |
878 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
879 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
880 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
881 |
float t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
882 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
883 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
884 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
885 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
886 |
rb++; t = ar; |
14925 | 887 |
} |
888 |
w[k++] = t; |
|
889 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
890 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
891 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
892 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
893 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
894 |
tryComplete(); |
14925 | 895 |
} |
896 |
} |
|
897 |
} // FJFloat |
|
898 |
||
899 |
/** double support class */ |
|
900 |
static final class FJDouble { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
901 |
static final class Sorter extends CountedCompleter<Void> { |
14925 | 902 |
static final long serialVersionUID = 2446542900576103244L; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
903 |
final double[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
904 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
905 |
Sorter(CountedCompleter<?> par, double[] a, double[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
906 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
907 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
908 |
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
|
909 |
this.wbase = wbase; this.gran = gran; |
14925 | 910 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
911 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
912 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
913 |
double[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
914 |
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
|
915 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
916 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
917 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
918 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
919 |
Relay rc = new Relay(new Merger(fc, a, w, b+h, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
920 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
921 |
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
922 |
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
923 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
924 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
925 |
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
926 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
927 |
n = q; |
14925 | 928 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
929 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
930 |
s.tryComplete(); |
14925 | 931 |
} |
932 |
} |
|
933 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
934 |
static final class Merger extends CountedCompleter<Void> { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
935 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
936 |
final double[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
937 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
938 |
Merger(CountedCompleter<?> par, double[] a, double[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
939 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
940 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
941 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
942 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
943 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
944 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
945 |
this.wbase = wbase; this.gran = gran; |
14925 | 946 |
} |
947 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
948 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
949 |
double[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
950 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
951 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
952 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
953 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
954 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
955 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
956 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
957 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
958 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
959 |
double split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
960 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
961 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
962 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
963 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
964 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
965 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
966 |
} |
14925 | 967 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
968 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
969 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
970 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
971 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
972 |
double split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
973 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
974 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
975 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
976 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
977 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
978 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
979 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
980 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
981 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
982 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
983 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
984 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
985 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
986 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
987 |
m.fork(); |
14925 | 988 |
} |
989 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
990 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
991 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
992 |
double t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
993 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
994 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
995 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
996 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
997 |
rb++; t = ar; |
14925 | 998 |
} |
999 |
w[k++] = t; |
|
1000 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1001 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1002 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1003 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1004 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1005 |
tryComplete(); |
14925 | 1006 |
} |
1007 |
} |
|
1008 |
} // FJDouble |
|
1009 |
||
1010 |
} |