summaryrefslogtreecommitdiff
path: root/staging/linux-x86/sample/forkjoin/mergesort/MergeDemo.java
blob: 528f383f2f3ff0c67901a0c873900365e9ab3b07 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
/*
 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *   - Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 *   - Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 *   - Neither the name of Oracle nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * This source code is provided to illustrate the usage of a given feature
 * or technique and has been deliberately simplified. Additional steps
 * required for a production-quality application, such as security checks,
 * input validation and proper error handling, might not be present in
 * this sample code.
 */


import java.util.Arrays;
import java.util.Random;

import static java.lang.Integer.parseInt;

/**
 * MergeExample is a class that runs a demo benchmark of the {@code ForkJoin} framework
 * by benchmarking a {@link MergeSort} algorithm that is implemented using
 * {@link java.util.concurrent.RecursiveAction}.
 * The {@code ForkJoin} framework is setup with different parallelism levels
 * and the sort is executed with arrays of different sizes to see the
 * trade offs by using multiple threads for different sizes of the array.
 */
public class MergeDemo {
    // Use a fixed seed to always get the same random values back
    private final Random random = new Random(759123751834L);
    private static final int ITERATIONS = 10;

    /**
     * Represents the formula {@code f(n) = start + (step * n)} for n = 0 & n < iterations
     */
    private static class Range {
        private final int start;
        private final int step;
        private final int iterations;

        private Range(int start, int step, int iterations) {
            this.start = start;
            this.step = step;
            this.iterations = iterations;
        }

        /**
         * Parses start, step and iterations from args
         * @param args the string array containing the arguments
         * @param start which element to start the start argument from
         * @return the constructed range
         */
        public static Range parse(String[] args, int start) {
            if (args.length < start + 3) {
                throw new IllegalArgumentException("Too few elements in array");
            }
            return new Range(parseInt(args[start]), parseInt(args[start + 1]), parseInt(args[start + 2]));
        }

        public int get(int iteration) {
            return start + (step * iteration);
        }

        public int getIterations() {
            return iterations;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append(start).append(" ").append(step).append(" ").append(iterations);
            return builder.toString();
        }
    }

    /**
     * Wraps the different parameters that is used when running the MergeExample.
     * {@code sizes} represents the different array sizes
     * {@code parallelism} represents the different parallelism levels
     */
    private static class Configuration {
        private final Range sizes;
        private final Range parallelism;

        private final static Configuration defaultConfig = new Configuration(new Range(20000, 20000, 10),
                new Range(2, 2, 10));

        private Configuration(Range sizes, Range parallelism) {
            this.sizes = sizes;
            this.parallelism = parallelism;
        }

        /**
         * Parses the arguments and attempts to create a configuration containing the
         * parameters for creating the array sizes and parallelism sizes
         * @param args the input arguments
         * @return the configuration
         */
        public static Configuration parse(String[] args) {
            if (args.length == 0) {
                return defaultConfig;
            } else {
                try {
                    if (args.length == 6) {
                        return new Configuration(Range.parse(args, 0), Range.parse(args, 3));
                    }
                } catch (NumberFormatException e) {
                    System.err.println("MergeExample: error: Argument was not a number.");
                }
                System.err.println("MergeExample <size start> <size step> <size steps> <parallel start> <parallel step>" +
                        " <parallel steps>");
                System.err.println("example: MergeExample 20000 10000 3 1 1 4");
                System.err.println("example: will run with arrays of sizes 20000, 30000, 40000" +
                        " and parallelism: 1, 2, 3, 4");
                return null;
            }
        }

        /**
         * Creates an array for reporting the test result time in
         * @return an array containing {@code sizes.iterations * parallelism.iterations} elements
         */
        private long[][] createTimesArray() {
            return new long[sizes.getIterations()][parallelism.getIterations()];
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder("");
            if (this == defaultConfig) {
                builder.append("Default configuration. ");
            }
            builder.append("Running with parameters: ");
            builder.append(sizes);
            builder.append(" ");
            builder.append(parallelism);
            return builder.toString();
        }
    }

    /**
     * Generates an array of {@code elements} random elements
     * @param elements the number of elements requested in the array
     * @return an array of {@code elements} random elements
     */
    private int[] generateArray(int elements) {
        int[] array = new int[elements];
        for (int i = 0; i < elements; ++i) {
            array[i] = random.nextInt();
        }
        return array;
    }

    /**
     * Runs the test
     * @param config contains the settings for the test
     */
    private void run(Configuration config) {
        Range sizes = config.sizes;
        Range parallelism = config.parallelism;

        // Run a couple of sorts to make the JIT compile / optimize the code
        // which should produce somewhat more fair times
        warmup();

        long[][] times = config.createTimesArray();

        for (int size = 0; size < sizes.getIterations(); size++) {
            runForSize(parallelism, sizes.get(size), times, size);
        }

        printResults(sizes, parallelism, times);
    }

    /**
     * Prints the results as a table
     * @param sizes the different sizes of the arrays
     * @param parallelism the different parallelism levels used
     * @param times the median times for the different sizes / parallelism
     */
    private void printResults(Range sizes, Range parallelism, long[][] times) {
        System.out.println("Time in milliseconds. Y-axis: number of elements. X-axis parallelism used.");
        long[] sums = new long[times[0].length];
        System.out.format("%8s  ", "");
        for (int i = 0; i < times[0].length; i++) {
            System.out.format("%4d ", parallelism.get(i));
        }
        System.out.println("");
        for (int size = 0; size < sizes.getIterations(); size++) {
            System.out.format("%8d: ", sizes.get(size));
            for (int i = 0; i < times[size].length; i++) {
                sums[i] += times[size][i];
                System.out.format("%4d ", times[size][i]);
            }
            System.out.println("");
        }
        System.out.format("%8s: ", "Total");
        for (long sum : sums) {
            System.out.format("%4d ", sum);
        }
        System.out.println("");
    }

    private void runForSize(Range parallelism, int elements, long[][] times, int size) {
        for (int step = 0; step < parallelism.getIterations(); step++) {
            long time = runForParallelism(ITERATIONS, elements, parallelism.get(step));
            times[size][step] = time;
        }
    }

    /**
     * Runs <i>iterations</i> number of test sorts of a random array of <i>element</i> length
     * @param iterations number of iterations
     * @param elements number of elements in the random array
     * @param parallelism parallelism for the ForkJoin framework
     * @return the median time of runs
     */
    private long runForParallelism(int iterations, int elements, int parallelism) {
        MergeSort mergeSort = new MergeSort(parallelism);
        long[] times = new long[iterations];

        for (int i = 0; i < iterations; i++) {
            // Suggest the VM to run a garbage collection to reduce the risk of getting one
            // while running the test run
            System.gc();
            long start = System.currentTimeMillis();
            mergeSort.sort(generateArray(elements));
            times[i] = System.currentTimeMillis() - start;
        }

        return medianValue(times);
    }

    /**
     * Calculates the median value of the array
     * @param times array of times
     * @return the median value
     */
    private long medianValue(long[] times) {
        if (times.length == 0) {
            throw new IllegalArgumentException("Empty array");
        }
        // Make a copy of times to avoid having side effects on the parameter value
        Arrays.sort(times.clone());
        long median = times[times.length / 2];
        if (times.length > 1 && times.length % 2 != 0) {
            median = (median + times[times.length / 2 + 1]) / 2;
        }
        return median;
    }

    /**
     * Generates 1000 arrays of 1000 elements and sorts them as a warmup
     */
    private void warmup() {
        MergeSort mergeSort = new MergeSort(Runtime.getRuntime().availableProcessors());
        for (int i = 0; i < 1000; i++) {
            mergeSort.sort(generateArray(1000));
        }
    }

    public static void main(String[] args) {
        Configuration configuration = Configuration.parse(args);
        if (configuration == null) {
            System.exit(1);
        }
        System.out.println(configuration);
        new MergeDemo().run(configuration);
    }
}