1 /* 2 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * - Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * - Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * - Neither the name of Oracle nor the names of its 16 * contributors may be used to endorse or promote products derived 17 * from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 20 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * This source code is provided to illustrate the usage of a given feature 34 * or technique and has been deliberately simplified. Additional steps 35 * required for a production-quality application, such as security checks, 36 * input validation and proper error handling, might not be present in 37 * this sample code. 38 */ 39 40 41 import java.util.Arrays; 42 import java.util.Random; 43 44 import static java.lang.Integer.parseInt; 45 46 /** 47 * MergeExample is a class that runs a demo benchmark of the {@code ForkJoin} framework 48 * by benchmarking a {@link MergeSort} algorithm that is implemented using 49 * {@link java.util.concurrent.RecursiveAction}. 50 * The {@code ForkJoin} framework is setup with different parallelism levels 51 * and the sort is executed with arrays of different sizes to see the 52 * trade offs by using multiple threads for different sizes of the array. 53 */ 54 public class MergeDemo { 55 // Use a fixed seed to always get the same random values back 56 private final Random random = new Random(759123751834L); 57 private static final int ITERATIONS = 10; 58 59 /** 60 * Represents the formula {@code f(n) = start + (step * n)} for n = 0 & n < iterations 61 */ 62 private static class Range { 63 private final int start; 64 private final int step; 65 private final int iterations; 66 67 private Range(int start, int step, int iterations) { 68 this.start = start; 69 this.step = step; 70 this.iterations = iterations; 71 } 72 73 /** 74 * Parses start, step and iterations from args 75 * @param args the string array containing the arguments 76 * @param start which element to start the start argument from 77 * @return the constructed range 78 */ 79 public static Range parse(String[] args, int start) { 80 if (args.length < start + 3) { 81 throw new IllegalArgumentException("Too few elements in array"); 82 } 83 return new Range(parseInt(args[start]), parseInt(args[start + 1]), parseInt(args[start + 2])); 84 } 85 86 public int get(int iteration) { 87 return start + (step * iteration); 88 } 89 90 public int getIterations() { 91 return iterations; 92 } 93 94 @Override 95 public String toString() { 96 StringBuilder builder = new StringBuilder(); 97 builder.append(start).append(" ").append(step).append(" ").append(iterations); 98 return builder.toString(); 99 } 100 } 101 102 /** 103 * Wraps the different parameters that is used when running the MergeExample. 104 * {@code sizes} represents the different array sizes 105 * {@code parallelism} represents the different parallelism levels 106 */ 107 private static class Configuration { 108 private final Range sizes; 109 private final Range parallelism; 110 111 private final static Configuration defaultConfig = new Configuration(new Range(20000, 20000, 10), 112 new Range(2, 2, 10)); 113 114 private Configuration(Range sizes, Range parallelism) { 115 this.sizes = sizes; 116 this.parallelism = parallelism; 117 } 118 119 /** 120 * Parses the arguments and attempts to create a configuration containing the 121 * parameters for creating the array sizes and parallelism sizes 122 * @param args the input arguments 123 * @return the configuration 124 */ 125 public static Configuration parse(String[] args) { 126 if (args.length == 0) { 127 return defaultConfig; 128 } else { 129 try { 130 if (args.length == 6) { 131 return new Configuration(Range.parse(args, 0), Range.parse(args, 3)); 132 } 133 } catch (NumberFormatException e) { 134 System.err.println("MergeExample: error: Argument was not a number."); 135 } 136 System.err.println("MergeExample <size start> <size step> <size steps> <parallel start> <parallel step>" + 137 " <parallel steps>"); 138 System.err.println("example: MergeExample 20000 10000 3 1 1 4"); 139 System.err.println("example: will run with arrays of sizes 20000, 30000, 40000" + 140 " and parallelism: 1, 2, 3, 4"); 141 return null; 142 } 143 } 144 145 /** 146 * Creates an array for reporting the test result time in 147 * @return an array containing {@code sizes.iterations * parallelism.iterations} elements 148 */ 149 private long[][] createTimesArray() { 150 return new long[sizes.getIterations()][parallelism.getIterations()]; 151 } 152 153 @Override 154 public String toString() { 155 StringBuilder builder = new StringBuilder(""); 156 if (this == defaultConfig) { 157 builder.append("Default configuration. "); 158 } 159 builder.append("Running with parameters: "); 160 builder.append(sizes); 161 builder.append(" "); 162 builder.append(parallelism); 163 return builder.toString(); 164 } 165 } 166 167 /** 168 * Generates an array of {@code elements} random elements 169 * @param elements the number of elements requested in the array 170 * @return an array of {@code elements} random elements 171 */ 172 private int[] generateArray(int elements) { 173 int[] array = new int[elements]; 174 for (int i = 0; i < elements; ++i) { 175 array[i] = random.nextInt(); 176 } 177 return array; 178 } 179 180 /** 181 * Runs the test 182 * @param config contains the settings for the test 183 */ 184 private void run(Configuration config) { 185 Range sizes = config.sizes; 186 Range parallelism = config.parallelism; 187 188 // Run a couple of sorts to make the JIT compile / optimize the code 189 // which should produce somewhat more fair times 190 warmup(); 191 192 long[][] times = config.createTimesArray(); 193 194 for (int size = 0; size < sizes.getIterations(); size++) { 195 runForSize(parallelism, sizes.get(size), times, size); 196 } 197 198 printResults(sizes, parallelism, times); 199 } 200 201 /** 202 * Prints the results as a table 203 * @param sizes the different sizes of the arrays 204 * @param parallelism the different parallelism levels used 205 * @param times the median times for the different sizes / parallelism 206 */ 207 private void printResults(Range sizes, Range parallelism, long[][] times) { 208 System.out.println("Time in milliseconds. Y-axis: number of elements. X-axis parallelism used."); 209 long[] sums = new long[times[0].length]; 210 System.out.format("%8s ", ""); 211 for (int i = 0; i < times[0].length; i++) { 212 System.out.format("%4d ", parallelism.get(i)); 213 } 214 System.out.println(""); 215 for (int size = 0; size < sizes.getIterations(); size++) { 216 System.out.format("%8d: ", sizes.get(size)); 217 for (int i = 0; i < times[size].length; i++) { 218 sums[i] += times[size][i]; 219 System.out.format("%4d ", times[size][i]); 220 } 221 System.out.println(""); 222 } 223 System.out.format("%8s: ", "Total"); 224 for (long sum : sums) { 225 System.out.format("%4d ", sum); 226 } 227 System.out.println(""); 228 } 229 230 private void runForSize(Range parallelism, int elements, long[][] times, int size) { 231 for (int step = 0; step < parallelism.getIterations(); step++) { 232 long time = runForParallelism(ITERATIONS, elements, parallelism.get(step)); 233 times[size][step] = time; 234 } 235 } 236 237 /** 238 * Runs <i>iterations</i> number of test sorts of a random array of <i>element</i> length 239 * @param iterations number of iterations 240 * @param elements number of elements in the random array 241 * @param parallelism parallelism for the ForkJoin framework 242 * @return the median time of runs 243 */ 244 private long runForParallelism(int iterations, int elements, int parallelism) { 245 MergeSort mergeSort = new MergeSort(parallelism); 246 long[] times = new long[iterations]; 247 248 for (int i = 0; i < iterations; i++) { 249 // Suggest the VM to run a garbage collection to reduce the risk of getting one 250 // while running the test run 251 System.gc(); 252 long start = System.currentTimeMillis(); 253 mergeSort.sort(generateArray(elements)); 254 times[i] = System.currentTimeMillis() - start; 255 } 256 257 return medianValue(times); 258 } 259 260 /** 261 * Calculates the median value of the array 262 * @param times array of times 263 * @return the median value 264 */ 265 private long medianValue(long[] times) { 266 if (times.length == 0) { 267 throw new IllegalArgumentException("Empty array"); 268 } 269 // Make a copy of times to avoid having side effects on the parameter value 270 Arrays.sort(times.clone()); 271 long median = times[times.length / 2]; 272 if (times.length > 1 && times.length % 2 != 0) { 273 median = (median + times[times.length / 2 + 1]) / 2; 274 } 275 return median; 276 } 277 278 /** 279 * Generates 1000 arrays of 1000 elements and sorts them as a warmup 280 */ 281 private void warmup() { 282 MergeSort mergeSort = new MergeSort(Runtime.getRuntime().availableProcessors()); 283 for (int i = 0; i < 1000; i++) { 284 mergeSort.sort(generateArray(1000)); 285 } 286 } 287 288 public static void main(String[] args) { 289 Configuration configuration = Configuration.parse(args); 290 if (configuration == null) { 291 System.exit(1); 292 } 293 System.out.println(configuration); 294 new MergeDemo().run(configuration); 295 } 296 } 297