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