author | darcy |
Wed, 09 Oct 2019 10:17:50 -0700 | |
changeset 58520 | e036ee8bae56 |
parent 57956 | e0b8b019d2f5 |
child 58679 | 9c3209ff7550 |
child 59042 | 8910b995a2ee |
permissions | -rw-r--r-- |
14925 | 1 |
/* |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
2 |
* Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved. |
14925 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
7 |
* published by the Free Software Foundation. Oracle designates this |
|
8 |
* particular file as subject to the "Classpath" exception as provided |
|
9 |
* by Oracle in the LICENSE file that accompanied this code. |
|
10 |
* |
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
24 |
*/ |
|
25 |
package java.util; |
|
26 |
||
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> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
90 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
91 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
92 |
EmptyCompleter(CountedCompleter<?> p) { super(p); } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
93 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
94 |
} |
14925 | 95 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
96 |
/** |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
97 |
* A trigger for secondary merge of two merges |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
98 |
*/ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
99 |
static final class Relay extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
100 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
101 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
102 |
final CountedCompleter<?> task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
103 |
Relay(CountedCompleter<?> task) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
104 |
super(null, 1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
105 |
this.task = task; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
106 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
107 |
public final void compute() { } |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
108 |
public final void onCompletion(CountedCompleter<?> t) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
109 |
task.compute(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
110 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
111 |
} |
14925 | 112 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
113 |
/** Object + Comparator support class */ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
114 |
static final class FJObject { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
115 |
static final class Sorter<T> extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
116 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
117 |
static final long serialVersionUID = 2446542900576103244L; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
118 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
119 |
final T[] a; |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
120 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
121 |
final T[] w; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
122 |
final int base, size, wbase, gran; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
123 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
124 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
125 |
Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
126 |
int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
127 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
128 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
129 |
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
|
130 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
131 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
132 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
133 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
134 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
135 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
136 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
137 |
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
|
138 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
139 |
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
|
140 |
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
|
141 |
wb+h, n-h, b, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
142 |
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
|
143 |
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
|
144 |
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
|
145 |
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
|
146 |
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
|
147 |
b+q, h-q, wb, g, c)); |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
148 |
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
|
149 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
150 |
n = q; |
14925 | 151 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
152 |
TimSort.sort(a, b, b + n, c, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
153 |
s.tryComplete(); |
14925 | 154 |
} |
155 |
} |
|
156 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
157 |
static final class Merger<T> extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
158 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
159 |
static final long serialVersionUID = 2446542900576103244L; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
160 |
// main and workspace arrays |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
161 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
162 |
final T[] a; |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
163 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
164 |
final T[] w; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
165 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
58520
e036ee8bae56
8231202: Suppress warnings on non-serializable non-transient instance fields in serializable classes
darcy
parents:
57956
diff
changeset
|
166 |
@SuppressWarnings("serial") // Not statically typed as Serializable |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
167 |
Comparator<? super T> comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
168 |
Merger(CountedCompleter<?> par, T[] a, T[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
169 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
170 |
int rsize, int wbase, int gran, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
171 |
Comparator<? super T> comparator) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
172 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
173 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
174 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
175 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
176 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
177 |
this.comparator = comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
178 |
} |
14925 | 179 |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
180 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
181 |
Comparator<? super T> c = this.comparator; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
182 |
T[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
183 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
184 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
185 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0 || |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
186 |
c == null) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
187 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
188 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
189 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
190 |
if (ln <= 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 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
193 |
T split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
194 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
195 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
196 |
if (c.compare(split, a[rm + rb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
197 |
rh = rm; |
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 = rm + 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 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
202 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
203 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
204 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
205 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
206 |
T split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
207 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
208 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
209 |
if (c.compare(split, a[lm + lb]) <= 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
210 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
211 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
212 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
213 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
214 |
} |
22078
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
215 |
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
|
216 |
rb + rh, rn - rh, |
bdec5d53e98c
8030851: Update code in java.util to use newer language features
psandoz
parents:
17712
diff
changeset
|
217 |
k + lh + rh, g, c); |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
218 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
219 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
220 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
221 |
m.fork(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
222 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
223 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
224 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
225 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
226 |
T t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
227 |
if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
228 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
229 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
230 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
231 |
rb++; t = ar; |
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 |
w[k++] = t; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
234 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
235 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
236 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
237 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
238 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
239 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
240 |
tryComplete(); |
14925 | 241 |
} |
242 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
243 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
244 |
} // FJObject |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
245 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
246 |
/** byte support class */ |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
247 |
static final class FJByte { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
248 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
249 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
250 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
251 |
final byte[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
252 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
253 |
Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
254 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
255 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
256 |
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
|
257 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
258 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
259 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
260 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
261 |
byte[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
262 |
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
|
263 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
264 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
265 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
266 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
267 |
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
|
268 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
269 |
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
|
270 |
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
|
271 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
272 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
273 |
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
|
274 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
275 |
n = q; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
276 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
277 |
DualPivotQuicksort.sort(a, b, b + n - 1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
278 |
s.tryComplete(); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
279 |
} |
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 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
283 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
284 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
285 |
final byte[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
286 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
287 |
Merger(CountedCompleter<?> par, byte[] a, byte[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
288 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
289 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
290 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
291 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
292 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
293 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
294 |
this.wbase = wbase; this.gran = gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
295 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
296 |
|
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
297 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
298 |
byte[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
299 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
300 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
301 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
302 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
303 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
304 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
305 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
306 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
307 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
308 |
byte split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
309 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
310 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
311 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
312 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
313 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
314 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
315 |
} |
14925 | 316 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
317 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
318 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
319 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
320 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
321 |
byte split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
322 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
323 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
324 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
325 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
326 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
327 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
328 |
} |
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 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
331 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
332 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
333 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
334 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
335 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
336 |
m.fork(); |
14925 | 337 |
} |
338 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
339 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
340 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
341 |
byte t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
342 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
343 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
344 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
345 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
346 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
347 |
} |
14925 | 348 |
w[k++] = t; |
349 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
350 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
351 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
352 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
353 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
354 |
tryComplete(); |
14925 | 355 |
} |
356 |
} |
|
357 |
} // FJByte |
|
358 |
||
359 |
/** char support class */ |
|
360 |
static final class FJChar { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
361 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
362 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
363 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
364 |
final char[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
365 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
366 |
Sorter(CountedCompleter<?> par, char[] a, char[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
367 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
368 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
369 |
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
|
370 |
this.wbase = wbase; this.gran = gran; |
14925 | 371 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
372 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
373 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
374 |
char[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
375 |
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
|
376 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
377 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
378 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
379 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
380 |
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
|
381 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
382 |
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
|
383 |
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
|
384 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
385 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
386 |
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
|
387 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
388 |
n = q; |
14925 | 389 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
390 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
391 |
s.tryComplete(); |
14925 | 392 |
} |
393 |
} |
|
394 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
395 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
396 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
397 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
398 |
final char[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
399 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
400 |
Merger(CountedCompleter<?> par, char[] a, char[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
401 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
402 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
403 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
404 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
405 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
406 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
407 |
this.wbase = wbase; this.gran = gran; |
14925 | 408 |
} |
409 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
410 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
411 |
char[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
412 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
413 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
414 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
415 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
416 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
417 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
418 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
419 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
420 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
421 |
char split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
422 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
423 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
424 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
425 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
426 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
427 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
428 |
} |
14925 | 429 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
430 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
431 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
432 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
433 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
434 |
char split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
435 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
436 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
437 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
438 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
439 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
440 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
441 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
442 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
443 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
444 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
445 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
446 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
447 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
448 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
449 |
m.fork(); |
14925 | 450 |
} |
451 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
452 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
453 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
454 |
char t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
455 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
456 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
457 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
458 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
459 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
460 |
} |
14925 | 461 |
w[k++] = t; |
462 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
463 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
464 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
465 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
466 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
467 |
tryComplete(); |
14925 | 468 |
} |
469 |
} |
|
470 |
} // FJChar |
|
471 |
||
472 |
/** short support class */ |
|
473 |
static final class FJShort { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
474 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
475 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
476 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
477 |
final short[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
478 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
479 |
Sorter(CountedCompleter<?> par, short[] a, short[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
480 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
481 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
482 |
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
|
483 |
this.wbase = wbase; this.gran = gran; |
14925 | 484 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
485 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
486 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
487 |
short[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
488 |
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
|
489 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
490 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
491 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
492 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
493 |
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
|
494 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
495 |
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
|
496 |
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
|
497 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
498 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
499 |
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
|
500 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
501 |
n = q; |
14925 | 502 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
503 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
504 |
s.tryComplete(); |
14925 | 505 |
} |
506 |
} |
|
507 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
508 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
509 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
510 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
511 |
final short[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
512 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
513 |
Merger(CountedCompleter<?> par, short[] a, short[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
514 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
515 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
516 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
517 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
518 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
519 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
520 |
this.wbase = wbase; this.gran = gran; |
14925 | 521 |
} |
522 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
523 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
524 |
short[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
525 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
526 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
527 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
528 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
529 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
530 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
531 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
532 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
533 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
534 |
short split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
535 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
536 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
537 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
538 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
539 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
540 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
541 |
} |
14925 | 542 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
543 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
544 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
545 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
546 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
547 |
short split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
548 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
549 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
550 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
551 |
lh = lm; |
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 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
554 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
555 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
556 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
557 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
558 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
559 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
560 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
561 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
562 |
m.fork(); |
14925 | 563 |
} |
564 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
565 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
566 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
567 |
short t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
568 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
569 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
570 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
571 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
572 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
573 |
} |
14925 | 574 |
w[k++] = t; |
575 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
576 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
577 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
578 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
579 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
580 |
tryComplete(); |
14925 | 581 |
} |
582 |
} |
|
583 |
} // FJShort |
|
584 |
||
585 |
/** int support class */ |
|
586 |
static final class FJInt { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
587 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
588 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
589 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
590 |
final int[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
591 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
592 |
Sorter(CountedCompleter<?> par, int[] a, int[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
593 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
594 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
595 |
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
|
596 |
this.wbase = wbase; this.gran = gran; |
14925 | 597 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
598 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
599 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
600 |
int[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
601 |
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
|
602 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
603 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
604 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
605 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
606 |
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
|
607 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
608 |
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
|
609 |
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
|
610 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
611 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
612 |
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
|
613 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
614 |
n = q; |
14925 | 615 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
616 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
617 |
s.tryComplete(); |
14925 | 618 |
} |
619 |
} |
|
620 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
621 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
622 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
623 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
624 |
final int[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
625 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
626 |
Merger(CountedCompleter<?> par, int[] a, int[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
627 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
628 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
629 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
630 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
631 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
632 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
633 |
this.wbase = wbase; this.gran = gran; |
14925 | 634 |
} |
635 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
636 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
637 |
int[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
638 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
639 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
640 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
641 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
642 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
643 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
644 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
645 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
646 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
647 |
int split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
648 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
649 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
650 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
651 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
652 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
653 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
654 |
} |
14925 | 655 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
656 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
657 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
658 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
659 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
660 |
int split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
661 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
662 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
663 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
664 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
665 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
666 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
667 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
668 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
669 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
670 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
671 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
672 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
673 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
674 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
675 |
m.fork(); |
14925 | 676 |
} |
677 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
678 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
679 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
680 |
int t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
681 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
682 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
683 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
684 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
685 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
686 |
} |
14925 | 687 |
w[k++] = t; |
688 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
689 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
690 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
691 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
692 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
693 |
tryComplete(); |
14925 | 694 |
} |
695 |
} |
|
696 |
} // FJInt |
|
697 |
||
698 |
/** long support class */ |
|
699 |
static final class FJLong { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
700 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
701 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
702 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
703 |
final long[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
704 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
705 |
Sorter(CountedCompleter<?> par, long[] a, long[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
706 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
707 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
708 |
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
|
709 |
this.wbase = wbase; this.gran = gran; |
14925 | 710 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
711 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
712 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
713 |
long[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
714 |
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
|
715 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
716 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
717 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
718 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
719 |
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
|
720 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
721 |
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
|
722 |
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
|
723 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
724 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
725 |
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
|
726 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
727 |
n = q; |
14925 | 728 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
729 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
730 |
s.tryComplete(); |
14925 | 731 |
} |
732 |
} |
|
733 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
734 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
735 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
736 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
737 |
final long[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
738 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
739 |
Merger(CountedCompleter<?> par, long[] a, long[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
740 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
741 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
742 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
743 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
744 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
745 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
746 |
this.wbase = wbase; this.gran = gran; |
14925 | 747 |
} |
748 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
749 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
750 |
long[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
751 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
752 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
753 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
754 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
755 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
756 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
757 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
758 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
759 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
760 |
long split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
761 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
762 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
763 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
764 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
765 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
766 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
767 |
} |
14925 | 768 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
769 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
770 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
771 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
772 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
773 |
long split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
774 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
775 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
776 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
777 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
778 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
779 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
780 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
781 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
782 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
783 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
784 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
785 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
786 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
787 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
788 |
m.fork(); |
14925 | 789 |
} |
790 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
791 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
792 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
793 |
long t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
794 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
795 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
796 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
797 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
798 |
rb++; t = ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
799 |
} |
14925 | 800 |
w[k++] = t; |
801 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
802 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
803 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
804 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
805 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
806 |
tryComplete(); |
14925 | 807 |
} |
808 |
} |
|
809 |
} // FJLong |
|
810 |
||
811 |
/** float support class */ |
|
812 |
static final class FJFloat { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
813 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
814 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
815 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
816 |
final float[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
817 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
818 |
Sorter(CountedCompleter<?> par, float[] a, float[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
819 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
820 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
821 |
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
|
822 |
this.wbase = wbase; this.gran = gran; |
14925 | 823 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
824 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
825 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
826 |
float[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
827 |
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
|
828 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
829 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
830 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
831 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
832 |
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
|
833 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
834 |
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
|
835 |
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
|
836 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
837 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
838 |
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
|
839 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
840 |
n = q; |
14925 | 841 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
842 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
843 |
s.tryComplete(); |
14925 | 844 |
} |
845 |
} |
|
846 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
847 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
848 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
849 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
850 |
final float[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
851 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
852 |
Merger(CountedCompleter<?> par, float[] a, float[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
853 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
854 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
855 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
856 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
857 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
858 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
859 |
this.wbase = wbase; this.gran = gran; |
14925 | 860 |
} |
861 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
862 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
863 |
float[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
864 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
865 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
866 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
867 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
868 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
869 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
870 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
871 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
872 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
873 |
float split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
874 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
875 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
876 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
877 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
878 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
879 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
880 |
} |
14925 | 881 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
882 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
883 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
884 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
885 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
886 |
float split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
887 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
888 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
889 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
890 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
891 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
892 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
893 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
894 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
895 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
896 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
897 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
898 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
899 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
900 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
901 |
m.fork(); |
14925 | 902 |
} |
903 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
904 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
905 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
906 |
float t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
907 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
908 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
909 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
910 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
911 |
rb++; t = ar; |
14925 | 912 |
} |
913 |
w[k++] = t; |
|
914 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
915 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
916 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
917 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
918 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
919 |
tryComplete(); |
14925 | 920 |
} |
921 |
} |
|
922 |
} // FJFloat |
|
923 |
||
924 |
/** double support class */ |
|
925 |
static final class FJDouble { |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
926 |
static final class Sorter extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
927 |
@java.io.Serial |
14925 | 928 |
static final long serialVersionUID = 2446542900576103244L; |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
929 |
final double[] a, w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
930 |
final int base, size, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
931 |
Sorter(CountedCompleter<?> par, double[] a, double[] w, int base, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
932 |
int size, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
933 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
934 |
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
|
935 |
this.wbase = wbase; this.gran = gran; |
14925 | 936 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
937 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
938 |
CountedCompleter<?> s = this; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
939 |
double[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
940 |
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
|
941 |
while (n > g) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
942 |
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
943 |
Relay fc = new Relay(new Merger(s, w, a, wb, h, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
944 |
wb+h, n-h, b, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
945 |
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
|
946 |
b+u, n-u, wb+h, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
947 |
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
|
948 |
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
|
949 |
Relay bc = new Relay(new Merger(fc, a, w, b, q, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
950 |
b+q, h-q, wb, g)); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
951 |
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
|
952 |
s = new EmptyCompleter(bc); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
953 |
n = q; |
14925 | 954 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
955 |
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
956 |
s.tryComplete(); |
14925 | 957 |
} |
958 |
} |
|
959 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
960 |
static final class Merger extends CountedCompleter<Void> { |
57956
e0b8b019d2f5
8229997: Apply java.io.Serial annotations in java.base
darcy
parents:
47216
diff
changeset
|
961 |
@java.io.Serial |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
962 |
static final long serialVersionUID = 2446542900576103244L; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
963 |
final double[] a, w; // main and workspace arrays |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
964 |
final int lbase, lsize, rbase, rsize, wbase, gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
965 |
Merger(CountedCompleter<?> par, double[] a, double[] w, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
966 |
int lbase, int lsize, int rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
967 |
int rsize, int wbase, int gran) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
968 |
super(par); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
969 |
this.a = a; this.w = w; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
970 |
this.lbase = lbase; this.lsize = lsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
971 |
this.rbase = rbase; this.rsize = rsize; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
972 |
this.wbase = wbase; this.gran = gran; |
14925 | 973 |
} |
974 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
975 |
public final void compute() { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
976 |
double[] a = this.a, w = this.w; // localize all params |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
977 |
int lb = this.lbase, ln = this.lsize, rb = this.rbase, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
978 |
rn = this.rsize, k = this.wbase, g = this.gran; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
979 |
if (a == null || w == null || lb < 0 || rb < 0 || k < 0) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
980 |
throw new IllegalStateException(); // hoist checks |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
981 |
for (int lh, rh;;) { // split larger, find point in smaller |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
982 |
if (ln >= rn) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
983 |
if (ln <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
984 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
985 |
rh = rn; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
986 |
double split = a[(lh = ln >>> 1) + lb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
987 |
for (int lo = 0; lo < rh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
988 |
int rm = (lo + rh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
989 |
if (split <= a[rm + rb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
990 |
rh = rm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
991 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
992 |
lo = rm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
993 |
} |
14925 | 994 |
} |
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
995 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
996 |
if (rn <= g) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
997 |
break; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
998 |
lh = ln; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
999 |
double split = a[(rh = rn >>> 1) + rb]; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1000 |
for (int lo = 0; lo < lh; ) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1001 |
int lm = (lo + lh) >>> 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1002 |
if (split <= a[lm + lb]) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1003 |
lh = lm; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1004 |
else |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1005 |
lo = lm + 1; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1006 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1007 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1008 |
Merger m = new Merger(this, a, w, lb + lh, ln - lh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1009 |
rb + rh, rn - rh, |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1010 |
k + lh + rh, g); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1011 |
rn = rh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1012 |
ln = lh; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1013 |
addToPendingCount(1); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1014 |
m.fork(); |
14925 | 1015 |
} |
1016 |
||
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1017 |
int lf = lb + ln, rf = rb + rn; // index bounds |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1018 |
while (lb < lf && rb < rf) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1019 |
double t, al, ar; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1020 |
if ((al = a[lb]) <= (ar = a[rb])) { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1021 |
lb++; t = al; |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1022 |
} |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1023 |
else { |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1024 |
rb++; t = ar; |
14925 | 1025 |
} |
1026 |
w[k++] = t; |
|
1027 |
} |
|
17712
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1028 |
if (rb < rf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1029 |
System.arraycopy(a, rb, w, k, rf - rb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1030 |
else if (lb < lf) |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1031 |
System.arraycopy(a, lb, w, k, lf - lb); |
b56c69500af6
8014076: Arrays parallel and serial sorting improvements
dl
parents:
14925
diff
changeset
|
1032 |
tryComplete(); |
14925 | 1033 |
} |
1034 |
} |
|
1035 |
} // FJDouble |
|
1036 |
||
1037 |
} |