jdk/test/java/util/Arrays/TimSortStackSize2.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 /*
  * @test
  * @bug 8072909
  * @library /lib/testlibrary /../../test/lib
  * @build jdk.testlibrary.*
  * @build TimSortStackSize2
  * @run main ClassFileInstaller sun.hotspot.WhiteBox
  * @run main/othervm -Xbootclasspath/a:. -XX:+UnlockDiagnosticVMOptions
  *     -XX:+WhiteBoxAPI TimSortStackSize2
  * @summary Test TimSort stack size on big arrays
  */
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.function.Consumer;

 import jdk.testlibrary.OutputAnalyzer;
 import jdk.testlibrary.ProcessTools;
 import jdk.testlibrary.Utils;
 import sun.hotspot.WhiteBox;

 public class TimSortStackSize2 {

     public static void main(String[] args) {
         if ( args == null || args.length == 0 ){
             startMeWithArgs();
         } else {
             doTestOfTwoTimSorts(Integer.parseInt(args[0]));
         }
     }

     private static void startMeWithArgs(){
         /*
          * big tests not for regular execution on all platforms:
          * run main/othervm -Xmx8g TimSortStackSize2 1073741824
          * run main/othervm -Xmx16g TimSortStackSize2 2147483644
          */
         try {
             Boolean compressedOops = WhiteBox.getWhiteBox()
                 .getBooleanVMFlag("UseCompressedOops");
             final String xmsValue = "-Xms" +
                 ((compressedOops == null || compressedOops) ? "385" : "770")
                 + "m";
             System.out.println( "compressedOops: " + compressedOops
                 + "; Test will be started with \"" + xmsValue + "\"");
             ProcessBuilder processBuilder = ProcessTools
                 .createJavaProcessBuilder(Utils.addTestJavaOpts(xmsValue,
                     "TimSortStackSize2", "67108864"
                 )
             );
             OutputAnalyzer output = ProcessTools.executeProcess(processBuilder);
             System.out.println(output.getOutput());
             output.shouldHaveExitValue(0);
         } catch( Exception e ){
             e.printStackTrace();
             throw new RuntimeException(e);
         }
     }

     private static void doTestOfTwoTimSorts(final int lengthOfTest){
         boolean passed = doTest("TimSort", lengthOfTest,
             (Integer [] a) -> Arrays.sort(a));
         passed = doTest("ComparableTimSort", lengthOfTest, (Integer [] a) ->
             Arrays.sort(a, (Object first, Object second) -> {
                 return ((Comparable<Object>)first).compareTo(second);
             }))
             && passed;
         if ( !passed ){
             throw new RuntimeException();
         }
     }

     private static boolean doTest(final String msg, final int lengthOfTest,
                                   final  Consumer<Integer[]> c){
         Integer [] a = null;
         try {
             a = new TimSortStackSize2(lengthOfTest).createArray();
             long begin = System.nanoTime();
             c.accept(a);
             long end = System.nanoTime();
             System.out.println(msg + " OK. Time: " + (end - begin) + "ns");
         } catch (ArrayIndexOutOfBoundsException e){
             System.out.println(msg + " broken:");
             e.printStackTrace();
             return false;
         } finally {
             a = null;
         }
         return true;
     }

     private static final int MIN_MERGE = 32;
     private final int minRun;
     private final int length;
     private final List<Long> runs = new ArrayList<Long>();

     public TimSortStackSize2(final int len) {
         this.length = len;
         minRun = minRunLength(len);
         fillRunsJDKWorstCase();
     }

     private static int minRunLength(int n) {
         assert n >= 0;
         int r = 0;      // Becomes 1 if any 1 bits are shifted off
         while (n >= MIN_MERGE) {
             r |= (n & 1);
             n >>= 1;
         }
         return n + r;
     }

     /**
      * Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br>
      * 1. X = x_1 + ... + x_n <br>
      * 2. x_j >= minRun for all j <br>
      * 3. x_1 + ... + x_{j-2}  <  x_j  <  x_1 + ... + x_{j-1} for all j <br>
      * These conditions guarantee that TimSort merges all x_j's one by one
      * (resulting in X) using only merges on the second-to-last element.
      * @param X  The sum of the sequence that should be added to runs.
      */
     private void generateJDKWrongElem(long X) {
         for(long newTotal; X >= 2 * minRun + 1; X = newTotal) {
             //Default strategy
             newTotal = X / 2 + 1;
             //Specialized strategies
             if(3 * minRun + 3 <= X && X <= 4*minRun+1) {
                 // add x_1=MIN+1, x_2=MIN, x_3=X-newTotal  to runs
                 newTotal = 2 * minRun + 1;
             } else if (5 * minRun + 5 <= X && X <= 6 * minRun + 5) {
                 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal  to runs
                 newTotal = 3 * minRun + 3;
             } else if (8 * minRun + 9 <= X && X <= 10 * minRun + 9) {
                 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal  to runs
                 newTotal = 5 * minRun + 5;
             } else if (13 * minRun + 15 <= X && X <= 16 * minRun + 17) {
                 // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal  to runs
                 newTotal = 8 * minRun + 9;
             }
             runs.add(0, X - newTotal);
         }
         runs.add(0, X);
     }

     /**
      * Fills <code>runs</code> with a sequence of run lengths of the form<br>
      * Y_n     x_{n,1}   x_{n,2}   ... x_{n,l_n} <br>
      * Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br>
      * ... <br>
      * Y_1     x_{1,1}   x_{1,2}   ... x_{1,l_1}<br>
      * The Y_i's are chosen to satisfy the invariant throughout execution,
      * but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>)
      * into an X_i that violates the invariant.
      * X is the sum of all run lengths that will be added to <code>runs</code>.
      */
     private void fillRunsJDKWorstCase() {
         long runningTotal = 0;
         long Y = minRun + 4;
         long X = minRun;

         while (runningTotal + Y + X <= length) {
             runningTotal += X + Y;
             generateJDKWrongElem(X);
             runs.add(0, Y);

             // X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1}
             X = Y + runs.get(1) + 1;

             // Y_{i+1} = X_{i+1} + Y_i + 1
             Y += X + 1;
         }

         if (runningTotal + X <= length) {
             runningTotal += X;
             generateJDKWrongElem(X);
         }

         runs.add(length - runningTotal);
     }

     private Integer [] createArray() {
         Integer [] a = new Integer[length];
         Arrays.fill(a, 0);
         int endRun = -1;
         for (long len : runs) {
             a[endRun += len] = 1;
         }
         a[length - 1] = 0;
         return a;
     }

 }
	/*
	* Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	/*
	* @test
	* @bug 8072909
	* @library /lib/testlibrary /../../test/lib
	* @build jdk.testlibrary.*
	* @build TimSortStackSize2
	* @run main ClassFileInstaller sun.hotspot.WhiteBox
	* @run main/othervm -Xbootclasspath/a:. -XX:+UnlockDiagnosticVMOptions
	* -XX:+WhiteBoxAPI TimSortStackSize2
	* @summary Test TimSort stack size on big arrays
	*/
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;
	import java.util.function.Consumer;

	import jdk.testlibrary.OutputAnalyzer;
	import jdk.testlibrary.ProcessTools;
	import jdk.testlibrary.Utils;
	import sun.hotspot.WhiteBox;

	public class TimSortStackSize2 {

	public static void main(String[] args) {
	if ( args == null \|\| args.length == 0 ){
	startMeWithArgs();
	} else {
	doTestOfTwoTimSorts(Integer.parseInt(args[0]));
	}
	}

	private static void startMeWithArgs(){
	/*
	* big tests not for regular execution on all platforms:
	* run main/othervm -Xmx8g TimSortStackSize2 1073741824
	* run main/othervm -Xmx16g TimSortStackSize2 2147483644
	*/
	try {
	Boolean compressedOops = WhiteBox.getWhiteBox()
	.getBooleanVMFlag("UseCompressedOops");
	final String xmsValue = "-Xms" +
	((compressedOops == null \|\| compressedOops) ? "385" : "770")
	+ "m";
	System.out.println( "compressedOops: " + compressedOops
	+ "; Test will be started with \"" + xmsValue + "\"");
	ProcessBuilder processBuilder = ProcessTools
	.createJavaProcessBuilder(Utils.addTestJavaOpts(xmsValue,
	"TimSortStackSize2", "67108864"
	)
	);
	OutputAnalyzer output = ProcessTools.executeProcess(processBuilder);
	System.out.println(output.getOutput());
	output.shouldHaveExitValue(0);
	} catch( Exception e ){
	e.printStackTrace();
	throw new RuntimeException(e);
	}
	}

	private static void doTestOfTwoTimSorts(final int lengthOfTest){
	boolean passed = doTest("TimSort", lengthOfTest,
	(Integer [] a) -> Arrays.sort(a));
	passed = doTest("ComparableTimSort", lengthOfTest, (Integer [] a) ->
	Arrays.sort(a, (Object first, Object second) -> {
	return ((Comparable<Object>)first).compareTo(second);
	}))
	&& passed;
	if ( !passed ){
	throw new RuntimeException();
	}
	}

	private static boolean doTest(final String msg, final int lengthOfTest,
	final Consumer<Integer[]> c){
	Integer [] a = null;
	try {
	a = new TimSortStackSize2(lengthOfTest).createArray();
	long begin = System.nanoTime();
	c.accept(a);
	long end = System.nanoTime();
	System.out.println(msg + " OK. Time: " + (end - begin) + "ns");
	} catch (ArrayIndexOutOfBoundsException e){
	System.out.println(msg + " broken:");
	e.printStackTrace();
	return false;
	} finally {
	a = null;
	}
	return true;
	}

	private static final int MIN_MERGE = 32;
	private final int minRun;
	private final int length;
	private final List<Long> runs = new ArrayList<Long>();

	public TimSortStackSize2(final int len) {
	this.length = len;
	minRun = minRunLength(len);
	fillRunsJDKWorstCase();
	}

	private static int minRunLength(int n) {
	assert n >= 0;
	int r = 0; // Becomes 1 if any 1 bits are shifted off
	while (n >= MIN_MERGE) {
	r \|= (n & 1);
	n >>= 1;
	}
	return n + r;
	}

	/**
	* Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br>
	* 1. X = x_1 + ... + x_n <br>
	* 2. x_j >= minRun for all j <br>
	* 3. x_1 + ... + x_{j-2} < x_j < x_1 + ... + x_{j-1} for all j <br>
	* These conditions guarantee that TimSort merges all x_j's one by one
	* (resulting in X) using only merges on the second-to-last element.
	* @param X The sum of the sequence that should be added to runs.
	*/
	private void generateJDKWrongElem(long X) {
	for(long newTotal; X >= 2 * minRun + 1; X = newTotal) {
	//Default strategy
	newTotal = X / 2 + 1;
	//Specialized strategies
	if(3 * minRun + 3 <= X && X <= 4*minRun+1) {
	// add x_1=MIN+1, x_2=MIN, x_3=X-newTotal to runs
	newTotal = 2 * minRun + 1;
	} else if (5 * minRun + 5 <= X && X <= 6 * minRun + 5) {
	// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal to runs
	newTotal = 3 * minRun + 3;
	} else if (8 * minRun + 9 <= X && X <= 10 * minRun + 9) {
	// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal to runs
	newTotal = 5 * minRun + 5;
	} else if (13 * minRun + 15 <= X && X <= 16 * minRun + 17) {
	// add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal to runs
	newTotal = 8 * minRun + 9;
	}
	runs.add(0, X - newTotal);
	}
	runs.add(0, X);
	}

	/**
	* Fills <code>runs</code> with a sequence of run lengths of the form<br>
	* Y_n x_{n,1} x_{n,2} ... x_{n,l_n} <br>
	* Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br>
	* ... <br>
	* Y_1 x_{1,1} x_{1,2} ... x_{1,l_1}<br>
	* The Y_i's are chosen to satisfy the invariant throughout execution,
	* but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>)
	* into an X_i that violates the invariant.
	* X is the sum of all run lengths that will be added to <code>runs</code>.
	*/
	private void fillRunsJDKWorstCase() {
	long runningTotal = 0;
	long Y = minRun + 4;
	long X = minRun;

	while (runningTotal + Y + X <= length) {
	runningTotal += X + Y;
	generateJDKWrongElem(X);
	runs.add(0, Y);

	// X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1}
	X = Y + runs.get(1) + 1;

	// Y_{i+1} = X_{i+1} + Y_i + 1
	Y += X + 1;
	}

	if (runningTotal + X <= length) {
	runningTotal += X;
	generateJDKWrongElem(X);
	}

	runs.add(length - runningTotal);
	}

	private Integer [] createArray() {
	Integer [] a = new Integer[length];
	Arrays.fill(a, 0);
	int endRun = -1;
	for (long len : runs) {
	a[endRun += len] = 1;
	}
	a[length - 1] = 0;
	return a;
	}

	}