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 Big-O-Test 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 Big-O-Test 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));

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);

}

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

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