1 /*
2 * Copyright (c) 2013, 2017, 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 * @author Tristan Yan
29 * @modules java.management jdk.management
30 * @run testng/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 import static org.testng.Assert.*;
44 import org.testng.annotations.DataProvider;
45 import org.testng.annotations.Test;
46 import org.testng.annotations.BeforeSuite;
47
48 public class ParallelPrefix {
49 //Array size less than MIN_PARTITION
50 private static final int SMALL_ARRAY_SIZE = 1 << 3;
51
52 //Array size equals MIN_PARTITION
53 private static final int THRESHOLD_ARRAY_SIZE = 1 << 4;
54
55 //Array size greater than MIN_PARTITION
56 private static final int MEDIUM_ARRAY_SIZE = 1 << 8;
57
58 //Array size much greater than MIN_PARTITION
59 private static final int LARGE_ARRAY_SIZE = 1 << 14;
60
61 private static int[] arraySizeCollection;
62
63 @BeforeSuite
64 public static void setup() {
65 java.lang.management.OperatingSystemMXBean bean =
66 ManagementFactory.getOperatingSystemMXBean();
67 if (bean instanceof OperatingSystemMXBean) {
68 OperatingSystemMXBean os = (OperatingSystemMXBean)bean;
69 long physicalMemorySize = os.getTotalPhysicalMemorySize() / (1024 * 1024);
70 System.out.println("System memory size: " + physicalMemorySize + "M");
71 // when we can get system memory size, and it's larger than 2G,
72 // then we enable large array size test below,
73 // else disable large array size test below.
74 if (physicalMemorySize > (2 * 1024)) {
75 arraySizeCollection = new int[]{
76 SMALL_ARRAY_SIZE,
77 THRESHOLD_ARRAY_SIZE,
78 MEDIUM_ARRAY_SIZE,
79 LARGE_ARRAY_SIZE
80 };
81 System.out.println("System memory is large enough, add large array size test");
82 return;
83 }
84 }
85 arraySizeCollection = new int[]{
86 SMALL_ARRAY_SIZE,
87 THRESHOLD_ARRAY_SIZE,
88 MEDIUM_ARRAY_SIZE
89 };
90 System.out.println("System memory is not large enough, remove large array size test");
91 }
92
93 @DataProvider(name = "intSet")
94 public static Object[][] intSet(){
95 return genericData(size -> IntStream.range(0, size).toArray(),
96 new IntBinaryOperator[]{
97 Integer::sum,
98 Integer::min});
99 }
100
101 @DataProvider(name = "longSet")
102 public static Object[][] longSet(){
103 return genericData(size -> LongStream.range(0, size).toArray(),
104 new LongBinaryOperator[]{
105 Long::sum,
106 Long::min});
107 }
108
109 @DataProvider(name = "doubleSet")
110 public static Object[][] doubleSet(){
111 return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(),
112 new DoubleBinaryOperator[]{
113 Double::sum,
114 Double::min});
115 }
116
117 @DataProvider(name = "stringSet")
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 @Test(dataProvider="intSet")
146 public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) {
147 int[] sequentialResult = data.clone();
148 for (int index = fromIndex + 1; index < toIndex; index++) {
149 sequentialResult[index ] = op.applyAsInt(sequentialResult[index - 1], sequentialResult[index]);
150 }
151
152 int[] parallelResult = data.clone();
153 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
154 assertArraysEqual(parallelResult, sequentialResult);
155
156 int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
157 Arrays.parallelPrefix(parallelRangeResult, op);
158 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
159 }
160
161 @Test(dataProvider="longSet")
162 public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) {
163 long[] sequentialResult = data.clone();
164 for (int index = fromIndex + 1; index < toIndex; index++) {
165 sequentialResult[index ] = op.applyAsLong(sequentialResult[index - 1], sequentialResult[index]);
166 }
167
168 long[] parallelResult = data.clone();
169 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
170 assertArraysEqual(parallelResult, sequentialResult);
171
172 long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
173 Arrays.parallelPrefix(parallelRangeResult, op);
174 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
175 }
176
177 @Test(dataProvider="doubleSet")
178 public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) {
179 double[] sequentialResult = data.clone();
180 for (int index = fromIndex + 1; index < toIndex; index++) {
181 sequentialResult[index ] = op.applyAsDouble(sequentialResult[index - 1], sequentialResult[index]);
182 }
183
184 double[] parallelResult = data.clone();
185 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
186 assertArraysEqual(parallelResult, sequentialResult);
187
188 double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
189 Arrays.parallelPrefix(parallelRangeResult, op);
190 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
191 }
192
193 @Test(dataProvider="stringSet")
194 public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) {
195 String[] sequentialResult = data.clone();
196 for (int index = fromIndex + 1; index < toIndex; index++) {
197 sequentialResult[index ] = op.apply(sequentialResult[index - 1], sequentialResult[index]);
198 }
199
200 String[] parallelResult = data.clone();
201 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
202 assertArraysEqual(parallelResult, sequentialResult);
203
204 String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
205 Arrays.parallelPrefix(parallelRangeResult, op);
206 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
207 }
208
209 @Test
210 public void testNPEs() {
211 // null array
212 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, Integer::max));
213 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, Long::max));
214 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, Double::max));
215 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, String::concat));
216
217 // null array w/ range
218 assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max));
219 assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max));
220 assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max));
221 assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat));
222
223 // null op
224 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, null));
225 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, null));
226 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, null));
227 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, null));
228
229 // null op w/ range
230 assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, 0, 0, null));
231 assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, 0, 0, null));
232 assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, 0, 0, null));
233 assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, 0, 0, null));
234 }
235
236 @Test
237 public void testIAEs() {
238 assertThrowsIAE(() -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max));
239 assertThrowsIAE(() -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max));
240 assertThrowsIAE(() -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max));
241 assertThrowsIAE(() -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat));
242 }
243
244 @Test
245 public void testAIOOBEs() {
246 // bad "fromIndex"
247 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max));
248 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max));
249 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max));
250 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat));
251
252 // bad "toIndex"
253 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max));
254 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max));
255 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max));
256 assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat));
257 }
258
259 // "library" code
260
261 private void assertThrowsNPE(ThrowingRunnable r) {
262 assertThrows(NullPointerException.class, r);
263 }
264
265 private void assertThrowsIAE(ThrowingRunnable r) {
266 assertThrows(IllegalArgumentException.class, r);
267 }
268
269 private void assertThrowsAIOOB(ThrowingRunnable r) {
270 assertThrows(ArrayIndexOutOfBoundsException.class, r);
271 }
272
273 static void assertArraysEqual(int[] actual, int[] expected) {
274 try {
275 assertEquals(actual, expected, "");
276 } catch (AssertionError x) {
277 throw new AssertionError(String.format("Expected:%s, actual:%s",
278 Arrays.toString(expected), Arrays.toString(actual)), x);
279 }
280 }
281
282 static void assertArraysEqual(long[] actual, long[] expected) {
283 try {
284 assertEquals(actual, expected, "");
285 } catch (AssertionError x) {
286 throw new AssertionError(String.format("Expected:%s, actual:%s",
287 Arrays.toString(expected), Arrays.toString(actual)), x);
288 }
289 }
290
291 static void assertArraysEqual(double[] actual, double[] expected) {
292 try {
293 assertEquals(actual, expected, "");
294 } catch (AssertionError x) {
295 throw new AssertionError(String.format("Expected:%s, actual:%s",
296 Arrays.toString(expected), Arrays.toString(actual)), x);
297 }
298 }
299
300 static void assertArraysEqual(String[] actual, String[] expected) {
301 try {
302 assertEquals(actual, expected, "");
303 } catch (AssertionError x) {
304 throw new AssertionError(String.format("Expected:%s, actual:%s",
305 Arrays.toString(expected), Arrays.toString(actual)), x);
306 }
307 }
308 }
309