More‎ > ‎

Library to Empirically Estimate Big-O Time Efficiency and Check Results of Analysis in JUnit Tests with Java 8

BY MARKUS SPRUNCK


The library Big-O-Test provides support to measure the Big-O time efficiency and checks results of this analysis in standard JUnit tests. In a Big-O-Test the system under test (method of a class) is called with a measurement of elapsed time. For the measurements a proxy of the class is created and all the measurement happens in the background when calling a method of this proxy. Based on this data points the library tries to fits several possible functions. You may write the test code with an without Lambda Expressions - in the following article you find a first test sample for both implementations. 

A First BigOTest Case - without Lambda Expressions

BigOTest.jar supports JUnit test cases in the following form:

public class HeapSortTest {

   @Test
   public void assertLogLinear_RunHeapSort_DetectLogLinear() {

      // ARRANGE
      final BigOAnalyser boa = new BigOAnalyser();
      final HeapSort sut = (HeapSort) boa.createProxy(HeapSort.class);

      // ACT
      for (int x = (16 * 1024); x >= 1024; x /= 2) {
         sut.sort(createSortInput(x));
      }
      traceReport(boa, "sort");

      // ASSERT
      BigOAssert.assertLogLinearOrPowerLaw(boa, "sort");

   }

   private static List<Long> createSortInput(int size) {
      final List<Long> result = new ArrayList<Long>(size);
      for (int i = 0; i < size; i++) {
         result.add(Math.round(Long.MAX_VALUE * Math.random()));
      }
      return result;
   }

   private static void traceReport(final BigOAnalyser boa, String method) {
      System.out.println("--- HeapSortTest -----------------------");
      System.out.println();
      final Table<Integer, String, Double> data = boa.getDataChecked(method);
      System.out.println(BigOReports.getPolynomialDegree(data));
      System.out.println(BigOReports.getBestFunctionsReport(data));
      System.out.println(BigOReports.getDataReport(data));
   }

}

With the system under test (sut): 

 public class HeapSort { 

       public Long[] sort(@BigOParameter List<Long> unsorted) {
             ...      
       }
       ...
    }

The annotation @BigOParameter marks the parameter which is the driver of the run time. At the moment all marked parameters will be measured, but just the first will be analysed (in later versions this should be possible).

A First BigOTest Case - with Lambda Expressions

With Lambda Expressions you can express the same in a shorter way: 

public class LambdaTest {

    @Test
    public void heapSortDetectLogLinear() {

        // ARRANGE
        List<List<Long>> values = LongStream.range(6, 14) 
           .mapToInt(i -> 1 << i) 
           .mapToObj(x -> HeapSortTest.createSortInput(x)) 
           .collect(Collectors.toList());

        // ACT
        BigOResult actual = BigOAnalyser.classUnderTest(HeapSort.class) 
           .execute((HeapSort o) -> values.stream().forEach(value -> o.sort(value))) 
           .trace();

        // ASSERT
        BigOAssert.assertLogLinearOrPowerLaw(actual.getBigOAnalyser(), "sort");
    }
}   

The class BigOResult provides with the method execude the implementation of an Execute Around Pattern. In the execute Method the code is executed twice. Once to give the JIT compiler the chance to optimize code and the second once to measure the performance.

 public <P> BigOResult execute(BigOTestAction<P> action) {

      Preconditions.checkNotNull(action);
      Preconditions.checkNotNull(clazzUnderTest);

      @SuppressWarnings("unchecked")
      final P sut = (P) this.boa.createProxy(clazzUnderTest);

      // give JIT compiler the chance to optimize
      this.boa.deactivate();
      action.apply(sut);

      // here the measurement starts
      this.boa.activate();
      action.apply(sut);

      return this;
   }

Estimate the Polynomial Degree

Estimating the Polynomial Degree is quite simple. You need some measured data and plot them in a log-log-graph. Try to fit a line and the slope of the line is a good estimation of the polynomial degree.

For real polynomial functions the slope is close to an integer, e.g. 3 for cubic, 2 for quadratic, 1 for linear or 0 for constant functions. 
 
Figure 1: Slope of a fitted line in the log-log plot of measured data

If the estimated degree is not close to an integer, then you may have another function. The Log-Linear function has a slope of about 1.1 in a small data range. Estimations of polynomial degrees are a good starting point to find a proper fitting function.

Best Fitting Function

At the moment of writing this Big-O-Test supports the following functions:
  • Polynomial (const, linear, quadratic and higher polynomials)
  • PowerLaw
  • Exponential
  • LogLinear
  • Logarithmic
The optimal fitting function will be dependent from:
  • the Estimations of Polynomial Degree and 
  • the Adjusted Coefficient of Determination (R^2)
With the Estimated Polynomial Degree a set of possible functions can be selected, and then these functions will be fitted to the measured data. 

The Adjusted Coefficient of Determination of each fit function gives a hint what function could be the best. This is the information checked by the BigOAssert methods.

Supported Assert Methods

At the moment the following assert methods are supported:
  • static void assertPolynomialDegree(BigOAnalyser boa, String method, double expected, double delta) 
  • static void assertConstant(BigOAnalyser boa, String method) 
  • static void assertLinear(BigOAnalyser boa, String method) 
  • static void assertLogLinearOrPowerLaw(BigOAnalyser boa, String method) 
  • static void assertQuadratic(BigOAnalyser boa, String method)
  • static void assertPowerLaw(BigOAnalyser boa, String method) 
Convenience methods For Lambda Syntax:
  • static void assertPolynomialDegree(BigOResult result, String method, double expected, double delta)
  • static void assertConstant(BigOResult result, String method) 
  • static void assertLinear(BigOResult result, String method) 
  • static void assertLogLinearOrPowerLaw(BigOResult result, String method) 
  • static void assertQuadratic(BigOResult result, String method) 
  • static void assertPowerLaw(BigOResult result, String method) 

The most important assert method is assertPolynomialDegree, because it provides a very reliable measure especially in cases several fit functions are good candidates.

Fitting and Data Reports

The BigOReports class provides some methods to get more detailed data about the measured data points, estimated polynomial degree, adjusted coefficient of determination and fitted functions. 

Just write some code like this:


final Table<Integer, String, Double> data = boa.getDataChecked(method);
System.out.println(BigOReports.getPolynomialDegree(data));
System.out.println(BigOReports.getBestFunctionsReport(data));
System.out.println(BigOReports.getDataReport(data));

and you should get an output like: 


--- HeapSortTest -----------------------

ESTIMATED-POLYNOMIAL-DEGREE
1.1311

TYPE        R^2 (adjusted)  FUNCTION
LogLinear   0.9984          y = 1.43E+02 * x * log( 1.12E+00 * x )
Logarithmic 0.7853          y = -5.44E+07 + 7.54E+06 * log ( x )
Exponential 0.7359          y = 2.60E+06 * exp ( 1.37E-04 * x )


N1      TIME
1024    961666
2048    2402231
4096    4799169
8192    10723234
16384   22943745

System Under Test Wrapper

In some cased you may have no access to the source code or like to test static methods. In these cases, you can use a simple wrapper method: 
 

 public void sortWrapper(@BigOParameter List<Long> values) {
      Collections.sort(values);
 }

 @Test
 public void sortWrapper_RunJavaCollectionsSort_DetectPolynomialDegree() {

      // ARRANGE
      final BigOAnalyser boa = new BigOAnalyser();
      final WrapperTest sut = (WrapperTest) boa.createProxy(WrapperTest.class);

      // ACT
      for (int x = (32 * 1024); x >= 64; x /= 2) {
         sut.sortWrapper(createSortInput(x));
      }

      // ASSERT
      BigOAssert.assertPolynomialDegree(boa, "sortWrapper", 1.25, 0.5);
 }

Used Third-Party Libraries

The current version is developed and compiled with Eclipse Standard/SDK (Kepler Service Release 1).
  • commons-math3-3.2.jar - for fitting and solving linear equations
  • guava-18.0.jar - preconditions and some functionality from container classes
  • javassist.jar - creating and calling the proxies for measurements
These three libraries are included in the BigOTest.jar file (which you may find in the build folder).

Development Environment

  • Project : Eclipse Java EE IDE for Web Developers
  • Eclipse : Mars Release (4.5.0)
  • Build id : 20150621-1200
  • Java Version : JRE 8

Handle Just-in-time Compiler

In some cases the Just-in-time compiler need calls to optimize the code. So, the first measurements will be wrong. If this happens, you may have to deactivate the measurement, do some work and activate the measurement again like in the following code example:


boa.deactivate();                       // measurement is deactivated
sut.sort(createSortInput(1024));        // give JIT compiler the chance to optimize
boa.activate();                         // measurement is active

Getting Started

  • Fork on GitHub or download zip version from GitHub
  • The best starting point are the three example unit tests in the sub-project BigOTest-Demo (see GitHub) 
  • Start with BigOAssert.assertPolynomialDegree, later check for functions 
  • Use the BigOReports methods to get details about fit quality and measured data 
  • Run your test cases with and without Just-in-time compilation; use VM option -Xint

Find Code on GitHub

Sponsored Link