# 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