darwin-x86/sample/forkjoin/mergesort/MergeDemo.java - platform/prebuilts/jdk/jdk8 - Git at Google

 /*
  * 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);
     }
 }
	/*
	* 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);
	}
	}