1 /*
2 * Copyright (c) 2013, 2026, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 8014076 8025067
27 * @summary unit test for Arrays.ParallelPrefix().
28 * @modules java.management jdk.management
29 * @run junit/othervm -Xms256m -Xmx1024m ParallelPrefix
30 */
31
32 import java.lang.management.ManagementFactory;
33 import java.util.Arrays;
34 import java.util.function.BinaryOperator;
35 import java.util.function.DoubleBinaryOperator;
36 import java.util.function.Function;
37 import java.util.function.IntBinaryOperator;
38 import java.util.function.LongBinaryOperator;
39 import java.util.stream.IntStream;
40 import java.util.stream.LongStream;
41 import com.sun.management.OperatingSystemMXBean;
42
43 import static org.junit.jupiter.api.Assertions.*;
44 import org.junit.jupiter.api.BeforeAll;
45 import org.junit.jupiter.api.Test;
46 import org.junit.jupiter.api.TestInstance;
47 import org.junit.jupiter.api.function.Executable;
48 import org.junit.jupiter.params.ParameterizedTest;
49 import org.junit.jupiter.params.provider.MethodSource;
50
51 @TestInstance(TestInstance.Lifecycle.PER_CLASS)
52 public class ParallelPrefix {
53 //Array size less than MIN_PARTITION
54 private static final int SMALL_ARRAY_SIZE = 1 << 3;
55
56 //Array size equals MIN_PARTITION
57 private static final int THRESHOLD_ARRAY_SIZE = 1 << 4;
58
59 //Array size greater than MIN_PARTITION
60 private static final int MEDIUM_ARRAY_SIZE = 1 << 8;
61
62 //Array size much greater than MIN_PARTITION
63 private static final int LARGE_ARRAY_SIZE = 1 << 14;
64
65 private static int[] arraySizeCollection;
66
67 @BeforeAll
68 public static void setup() {
69 java.lang.management.OperatingSystemMXBean bean =
70 ManagementFactory.getOperatingSystemMXBean();
71 if (bean instanceof OperatingSystemMXBean) {
72 OperatingSystemMXBean os = (OperatingSystemMXBean)bean;
73 long physicalMemorySize = os.getTotalPhysicalMemorySize() / (1024 * 1024);
74 System.out.println("System memory size: " + physicalMemorySize + "M");
75 // when we can get system memory size, and it's larger than 2G,
76 // then we enable large array size test below,
77 // else disable large array size test below.
78 if (physicalMemorySize > (2 * 1024)) {
79 arraySizeCollection = new int[]{
80 SMALL_ARRAY_SIZE,
81 THRESHOLD_ARRAY_SIZE,
82 MEDIUM_ARRAY_SIZE,
83 LARGE_ARRAY_SIZE
84 };
85 System.out.println("System memory is large enough, add large array size test");
86 return;
87 }
88 }
89 arraySizeCollection = new int[]{
90 SMALL_ARRAY_SIZE,
91 THRESHOLD_ARRAY_SIZE,
92 MEDIUM_ARRAY_SIZE
93 };
94 System.out.println("System memory is not large enough, remove large array size test");
95 }
96
97 public static Object[][] intSet(){
98 return genericData(size -> IntStream.range(0, size).toArray(),
99 new IntBinaryOperator[]{
100 Integer::sum,
101 Integer::min});
102 }
103
104 public static Object[][] longSet(){
105 return genericData(size -> LongStream.range(0, size).toArray(),
106 new LongBinaryOperator[]{
107 Long::sum,
108 Long::min});
109 }
110
111 public static Object[][] doubleSet(){
112 return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(),
113 new DoubleBinaryOperator[]{
114 Double::sum,
115 Double::min});
116 }
117
118 public static Object[][] stringSet(){
119 Function<Integer, String[]> stringsFunc = size ->
120 IntStream.range(0, size).mapToObj(Integer::toString).toArray(String[]::new);
121 BinaryOperator<String> concat = String::concat;
122 return genericData(stringsFunc,
123 (BinaryOperator<String>[]) new BinaryOperator[]{
124 concat });
125 }
126
127 private static <T, OPS> Object[][] genericData(Function<Integer, T> generateFunc, OPS[] ops) {
128 //test arrays which size is equals n-1, n, n+1, test random data
129 Object[][] data = new Object[arraySizeCollection.length * 3 * ops.length][4];
130 for(int n = 0; n < arraySizeCollection.length; n++ ) {
131 for(int testValue = -1 ; testValue <= 1; testValue++) {
132 int array_size = arraySizeCollection[n] + testValue;
133 for(int opsN = 0; opsN < ops.length; opsN++) {
134 int index = n * 3 * ops.length + (testValue + 1) * ops.length + opsN;
135 data[index][0] = generateFunc.apply(array_size);
136 data[index][1] = array_size / 3;
137 data[index][2] = 2 * array_size / 3;
138 data[index][3] = ops[opsN];
139 }
140 }
141 }
142 return data;
143 }
144
145 @ParameterizedTest
146 @MethodSource("intSet")
147 public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) {
148 int[] sequentialResult = data.clone();
149 for (int index = fromIndex + 1; index < toIndex; index++) {
150 sequentialResult[index ] = op.applyAsInt(sequentialResult[index - 1], sequentialResult[index]);
151 }
152
153 int[] parallelResult = data.clone();
154 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
155 assertArraysEqual(sequentialResult, parallelResult);
156
157 int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
158 Arrays.parallelPrefix(parallelRangeResult, op);
159 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult);
160 }
161
162 @ParameterizedTest
163 @MethodSource("longSet")
164 public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) {
165 long[] sequentialResult = data.clone();
166 for (int index = fromIndex + 1; index < toIndex; index++) {
167 sequentialResult[index ] = op.applyAsLong(sequentialResult[index - 1], sequentialResult[index]);
168 }
169
170 long[] parallelResult = data.clone();
171 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
172 assertArraysEqual(sequentialResult, parallelResult);
173
174 long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
175 Arrays.parallelPrefix(parallelRangeResult, op);
176 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult);
177 }
178
179 @ParameterizedTest
180 @MethodSource("doubleSet")
181 public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) {
182 double[] sequentialResult = data.clone();
183 for (int index = fromIndex + 1; index < toIndex; index++) {
184 sequentialResult[index ] = op.applyAsDouble(sequentialResult[index - 1], sequentialResult[index]);
185 }
186
187 double[] parallelResult = data.clone();
188 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
189 assertArraysEqual(sequentialResult, parallelResult);
190
191 double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
192 Arrays.parallelPrefix(parallelRangeResult, op);
193 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult);
194 }
195
196 @ParameterizedTest
197 @MethodSource("stringSet")
198 public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) {
199 String[] sequentialResult = data.clone();
200 for (int index = fromIndex + 1; index < toIndex; index++) {
201 sequentialResult[index ] = op.apply(sequentialResult[index - 1], sequentialResult[index]);
202 }
203
204 String[] parallelResult = data.clone();
205 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
206 assertArraysEqual(sequentialResult, parallelResult);
207
208 String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
209 Arrays.parallelPrefix(parallelRangeResult, op);
210 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult);
211 }
212
213 @Test
214 public void testNPEs() {
215 // null array
216 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, Integer::max));
217 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, Long::max));
218 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, Double::max));
219 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, String::concat));
220
221 // null array w/ range
222 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max));
223 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max));
224 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max));
225 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat));
226
227 // null op
228 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, null));
229 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, null));
230 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, null));
231 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, null));
232
233 // null op w/ range
234 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, 0, 0, null));
235 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, 0, 0, null));
236 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, 0, 0, null));
237 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, 0, 0, null));
238 }
239
240 @Test
241 public void testIAEs() {
242 assertThrowsIAE(() -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max));
243 assertThrowsIAE(() -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max));
244 assertThrowsIAE(() -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max));
245 assertThrowsIAE(() -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat));
246 }
247
248 @Test
249 public void testAIOOBEs() {
250 // bad "fromIndex"
251 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max));
252 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max));
253 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max));
254 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat));
255
256 // bad "toIndex"
257 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max));
258 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max));
259 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max));
260 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat));
261 }
262
263 // "library" code
264
265 private void assertThrowsNPE(Executable r) {
266 assertThrows(NullPointerException.class, r);
267 }
268
269 private void assertThrowsIAE(Executable r) {
270 assertThrows(IllegalArgumentException.class, r);
271 }
272
273 private void assertThrowsAIOOB(Executable r) {
274 assertThrows(ArrayIndexOutOfBoundsException.class, r);
275 }
276
277 static void assertArraysEqual(int[] expected, int[] actual) {
278 try {
279 assertArrayEquals(expected, actual, "");
280 } catch (AssertionError x) {
281 throw new AssertionError(String.format("Expected:%s, actual:%s",
282 Arrays.toString(expected), Arrays.toString(actual)), x);
283 }
284 }
285
286 static void assertArraysEqual(long[] expected, long[] actual) {
287 try {
288 assertArrayEquals(expected, actual, "");
289 } catch (AssertionError x) {
290 throw new AssertionError(String.format("Expected:%s, actual:%s",
291 Arrays.toString(expected), Arrays.toString(actual)), x);
292 }
293 }
294
295 static void assertArraysEqual(double[] expected, double[] actual) {
296 try {
297 assertArrayEquals(expected, actual, "");
298 } catch (AssertionError x) {
299 throw new AssertionError(String.format("Expected:%s, actual:%s",
300 Arrays.toString(expected), Arrays.toString(actual)), x);
301 }
302 }
303
304 static void assertArraysEqual(String[] expected, String[] actual) {
305 try {
306 assertArrayEquals(expected, actual, "");
307 } catch (AssertionError x) {
308 throw new AssertionError(String.format("Expected:%s, actual:%s",
309 Arrays.toString(expected), Arrays.toString(actual)), x);
310 }
311 }
312 }
313