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 * @library /test/lib 30 * @run junit/othervm -Xms256m -Xmx1024m ParallelPrefix 31 */ 32 33 import java.lang.management.ManagementFactory; 34 import java.util.Arrays; 35 import java.util.function.BinaryOperator; 36 import java.util.function.DoubleBinaryOperator; 37 import java.util.function.Function; 38 import java.util.function.IntBinaryOperator; 39 import java.util.function.LongBinaryOperator; 40 import java.util.stream.IntStream; 41 import java.util.stream.LongStream; 42 import com.sun.management.OperatingSystemMXBean; 43 44 import jdk.test.lib.valueclass.AsValueClass; 45 46 import static org.junit.jupiter.api.Assertions.*; 47 import org.junit.jupiter.api.BeforeAll; 48 import org.junit.jupiter.api.Test; 49 import org.junit.jupiter.api.TestInstance; 50 import org.junit.jupiter.api.function.Executable; 51 import org.junit.jupiter.params.ParameterizedTest; 52 import org.junit.jupiter.params.provider.MethodSource; 53 54 @TestInstance(TestInstance.Lifecycle.PER_CLASS) 55 public class ParallelPrefix { 56 //Array size less than MIN_PARTITION 57 private static final int SMALL_ARRAY_SIZE = 1 << 3; 58 59 //Array size equals MIN_PARTITION 60 private static final int THRESHOLD_ARRAY_SIZE = 1 << 4; 61 62 //Array size greater than MIN_PARTITION 63 private static final int MEDIUM_ARRAY_SIZE = 1 << 8; 64 65 //Array size much greater than MIN_PARTITION 66 private static final int LARGE_ARRAY_SIZE = 1 << 14; 67 68 private static int[] arraySizeCollection; 69 70 @AsValueClass 71 record VInt(int value) {} 72 73 @BeforeAll 74 public static void setup() { 75 java.lang.management.OperatingSystemMXBean bean = 76 ManagementFactory.getOperatingSystemMXBean(); 77 if (bean instanceof OperatingSystemMXBean) { 78 OperatingSystemMXBean os = (OperatingSystemMXBean)bean; 79 long physicalMemorySize = os.getTotalPhysicalMemorySize() / (1024 * 1024); 80 System.out.println("System memory size: " + physicalMemorySize + "M"); 81 // when we can get system memory size, and it's larger than 2G, 82 // then we enable large array size test below, 83 // else disable large array size test below. 84 if (physicalMemorySize > (2 * 1024)) { 85 arraySizeCollection = new int[]{ 86 SMALL_ARRAY_SIZE, 87 THRESHOLD_ARRAY_SIZE, 88 MEDIUM_ARRAY_SIZE, 89 LARGE_ARRAY_SIZE 90 }; 91 System.out.println("System memory is large enough, add large array size test"); 92 return; 93 } 94 } 95 arraySizeCollection = new int[]{ 96 SMALL_ARRAY_SIZE, 97 THRESHOLD_ARRAY_SIZE, 98 MEDIUM_ARRAY_SIZE 99 }; 100 System.out.println("System memory is not large enough, remove large array size test"); 101 } 102 103 public static Object[][] intSet(){ 104 return genericData(size -> IntStream.range(0, size).toArray(), 105 new IntBinaryOperator[]{ 106 Integer::sum, 107 Integer::min}); 108 } 109 110 public static Object[][] longSet(){ 111 return genericData(size -> LongStream.range(0, size).toArray(), 112 new LongBinaryOperator[]{ 113 Long::sum, 114 Long::min}); 115 } 116 117 public static Object[][] doubleSet(){ 118 return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(), 119 new DoubleBinaryOperator[]{ 120 Double::sum, 121 Double::min}); 122 } 123 124 public static Object[][] stringSet(){ 125 Function<Integer, String[]> stringsFunc = size -> 126 IntStream.range(0, size).mapToObj(Integer::toString).toArray(String[]::new); 127 BinaryOperator<String> concat = String::concat; 128 return genericData(stringsFunc, 129 (BinaryOperator<String>[]) new BinaryOperator[]{ 130 concat }); 131 } 132 133 private static <T, OPS> Object[][] genericData(Function<Integer, T> generateFunc, OPS[] ops) { 134 //test arrays which size is equals n-1, n, n+1, test random data 135 Object[][] data = new Object[arraySizeCollection.length * 3 * ops.length][4]; 136 for(int n = 0; n < arraySizeCollection.length; n++ ) { 137 for(int testValue = -1 ; testValue <= 1; testValue++) { 138 int array_size = arraySizeCollection[n] + testValue; 139 for(int opsN = 0; opsN < ops.length; opsN++) { 140 int index = n * 3 * ops.length + (testValue + 1) * ops.length + opsN; 141 data[index][0] = generateFunc.apply(array_size); 142 data[index][1] = array_size / 3; 143 data[index][2] = 2 * array_size / 3; 144 data[index][3] = ops[opsN]; 145 } 146 } 147 } 148 return data; 149 } 150 151 public static Object[][] valueSet() { 152 Function<Integer, VInt[]> vIntFunc = size -> 153 IntStream.range(0, size).mapToObj(VInt::new).toArray(VInt[]::new); 154 BinaryOperator<VInt> sumOp = (a, b) -> new VInt(a.value() + b.value()); 155 BinaryOperator<VInt> minOp = (a, b) -> a.value() <= b.value() ? a : b; 156 return genericData(vIntFunc, 157 (BinaryOperator<VInt>[]) new BinaryOperator[]{sumOp, minOp}); 158 } 159 160 @ParameterizedTest 161 @MethodSource("intSet") 162 public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) { 163 int[] sequentialResult = data.clone(); 164 for (int index = fromIndex + 1; index < toIndex; index++) { 165 sequentialResult[index ] = op.applyAsInt(sequentialResult[index - 1], sequentialResult[index]); 166 } 167 168 int[] parallelResult = data.clone(); 169 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op); 170 assertArraysEqual(sequentialResult, parallelResult); 171 172 int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex); 173 Arrays.parallelPrefix(parallelRangeResult, op); 174 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult); 175 } 176 177 @ParameterizedTest 178 @MethodSource("longSet") 179 public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) { 180 long[] sequentialResult = data.clone(); 181 for (int index = fromIndex + 1; index < toIndex; index++) { 182 sequentialResult[index ] = op.applyAsLong(sequentialResult[index - 1], sequentialResult[index]); 183 } 184 185 long[] parallelResult = data.clone(); 186 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op); 187 assertArraysEqual(sequentialResult, parallelResult); 188 189 long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex); 190 Arrays.parallelPrefix(parallelRangeResult, op); 191 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult); 192 } 193 194 @ParameterizedTest 195 @MethodSource("doubleSet") 196 public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) { 197 double[] sequentialResult = data.clone(); 198 for (int index = fromIndex + 1; index < toIndex; index++) { 199 sequentialResult[index ] = op.applyAsDouble(sequentialResult[index - 1], sequentialResult[index]); 200 } 201 202 double[] parallelResult = data.clone(); 203 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op); 204 assertArraysEqual(sequentialResult, parallelResult); 205 206 double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex); 207 Arrays.parallelPrefix(parallelRangeResult, op); 208 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult); 209 } 210 211 @ParameterizedTest 212 @MethodSource("stringSet") 213 public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) { 214 String[] sequentialResult = data.clone(); 215 for (int index = fromIndex + 1; index < toIndex; index++) { 216 sequentialResult[index ] = op.apply(sequentialResult[index - 1], sequentialResult[index]); 217 } 218 219 String[] parallelResult = data.clone(); 220 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op); 221 assertArraysEqual(sequentialResult, parallelResult); 222 223 String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex); 224 Arrays.parallelPrefix(parallelRangeResult, op); 225 assertArraysEqual(Arrays.copyOfRange(sequentialResult, fromIndex, toIndex), parallelRangeResult); 226 } 227 228 @ParameterizedTest 229 @MethodSource("valueSet") 230 public void testParallelPrefixForValue(VInt[] data, int fromIndex, int toIndex, BinaryOperator<VInt> op) { 231 VInt[] sequentialResult = data.clone(); 232 for (int index = fromIndex + 1; index < toIndex; index++) { 233 sequentialResult[index] = op.apply(sequentialResult[index - 1], sequentialResult[index]); 234 } 235 236 VInt[] parallelResult = data.clone(); 237 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op); 238 assertArraysEqual(parallelResult, sequentialResult); 239 240 VInt[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex); 241 Arrays.parallelPrefix(parallelRangeResult, op); 242 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex)); 243 } 244 245 @Test 246 public void testNPEs() { 247 // null array 248 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, Integer::max)); 249 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, Long::max)); 250 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, Double::max)); 251 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, String::concat)); 252 assertThrowsNPE(() -> Arrays.parallelPrefix((VInt[]) null, (a, b) -> new VInt(a.value() + b.value()))); 253 254 // null array w/ range 255 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max)); 256 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max)); 257 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max)); 258 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat)); 259 assertThrowsNPE(() -> Arrays.parallelPrefix((VInt[]) null, 0, 0, (a, b) -> new VInt(a.value() + b.value()))); 260 261 // null op 262 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, null)); 263 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, null)); 264 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, null)); 265 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, null)); 266 assertThrowsNPE(() -> Arrays.parallelPrefix(new VInt[] {}, (BinaryOperator<VInt>) null)); 267 268 // null op w/ range 269 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, 0, 0, null)); 270 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, 0, 0, null)); 271 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, 0, 0, null)); 272 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, 0, 0, null)); 273 assertThrowsNPE(() -> Arrays.parallelPrefix(new VInt[] {}, 0, 0, (BinaryOperator<VInt>) null)); 274 } 275 276 @Test 277 public void testIAEs() { 278 assertThrowsIAE(() -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max)); 279 assertThrowsIAE(() -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max)); 280 assertThrowsIAE(() -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max)); 281 assertThrowsIAE(() -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat)); 282 assertThrowsIAE(() -> Arrays.parallelPrefix(new VInt[] {}, 1, 0, (a, b) -> new VInt(a.value() + b.value()))); 283 } 284 285 @Test 286 public void testAIOOBEs() { 287 // bad "fromIndex" 288 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max)); 289 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max)); 290 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max)); 291 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat)); 292 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new VInt[] {}, -1, 0, (a, b) -> new VInt(a.value() + b.value()))); 293 294 // bad "toIndex" 295 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max)); 296 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max)); 297 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max)); 298 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat)); 299 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new VInt[] {}, 0, 1, (a, b) -> new VInt(a.value() + b.value()))); 300 } 301 302 // "library" code 303 304 private void assertThrowsNPE(Executable r) { 305 assertThrows(NullPointerException.class, r); 306 } 307 308 private void assertThrowsIAE(Executable r) { 309 assertThrows(IllegalArgumentException.class, r); 310 } 311 312 private void assertThrowsAIOOB(Executable r) { 313 assertThrows(ArrayIndexOutOfBoundsException.class, r); 314 } 315 316 static void assertArraysEqual(int[] expected, int[] actual) { 317 try { 318 assertArrayEquals(expected, actual, ""); 319 } catch (AssertionError x) { 320 throw new AssertionError(String.format("Expected:%s, actual:%s", 321 Arrays.toString(expected), Arrays.toString(actual)), x); 322 } 323 } 324 325 static void assertArraysEqual(long[] expected, long[] actual) { 326 try { 327 assertArrayEquals(expected, actual, ""); 328 } catch (AssertionError x) { 329 throw new AssertionError(String.format("Expected:%s, actual:%s", 330 Arrays.toString(expected), Arrays.toString(actual)), x); 331 } 332 } 333 334 static void assertArraysEqual(double[] expected, double[] actual) { 335 try { 336 assertArrayEquals(expected, actual, ""); 337 } catch (AssertionError x) { 338 throw new AssertionError(String.format("Expected:%s, actual:%s", 339 Arrays.toString(expected), Arrays.toString(actual)), x); 340 } 341 } 342 343 static void assertArraysEqual(String[] expected, String[] actual) { 344 try { 345 assertArrayEquals(expected, actual, ""); 346 } catch (AssertionError x) { 347 throw new AssertionError(String.format("Expected:%s, actual:%s", 348 Arrays.toString(expected), Arrays.toString(actual)), x); 349 } 350 } 351 352 static void assertArraysEqual(VInt[] actual, VInt[] expected) { 353 try { 354 assertArrayEquals(actual, expected, ""); 355 } catch (AssertionError x) { 356 throw new AssertionError(String.format("Expected:%s, actual:%s", 357 Arrays.toString(expected), Arrays.toString(actual)), x); 358 } 359 } 360 } 361 --- EOF ---