11
\$\begingroup\$

Performance benchmarking small functions in Java is notoriously difficult, and there are a number of tools out there to help (caliper, others). Those other tools require a fair amount of setup and installation to get them working.

This code is adapted from a question @skiwi asked. He produced this ProjectEuler framework, and I have adapted it to be more performance-monitoring friendly.

The basic premise is that you want to run a method multiple times. Some of those are warmup times, and the others are 'real' runs. The tool performs the warmup, then later does the real run. It averages the execution times for the real run to produce the performance time for the method.

The bulk of the logic is incorporated in to a class called Problem which has an execute() method that is abstract.

package euler;

public abstract class Problem<T> {
    private final String name;
    private final int warmup;
    private final int realruns;

    public Problem(String name, int warmups, int realruns) {
        this.name = name;
        this.warmup = warmups;
        this.realruns = realruns;
    }

    public String getResult() {
        return String.valueOf(execute());
    }

    public final int getWarmups() {
        return warmup;
    }

    public final int getRealRuns() {
        return realruns;
    }

    public final String getName() {
        return name;
    }

    public abstract T execute();

}

A typical implementation of this Problem, for example, is to calculate the average of an array of integers, and it would be implemented as:

public class AverageIntegers extends Problem<Double>{

    private static final int[] DATA = {1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    public AverageIntegers() {
        super("Average Integers", 1000, 10000);
    }

    @Override
    public Double execute() {
        int sum = 0;
        for (int v : DATA) {
            sum += v;
        }
        return sum / (double)DATA.length;
    }
}

With the above implementation, you can incorporate it in to the benchmark class:

package euler;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

public class ProjectEuler {

    /**
     * @param args
     *            the command line arguments
     */
    public static void main(String[] args) {
        ProjectEuler pe = new ProjectEuler();
        pe.process();
        System.out.println("\n\nWarmup Complete\n\n");
        pe.process();
    }

    private static final int longestName(List<Problem<?>> probs) {
        int namelen = 0;
        for (Problem<?> p : probs) {
            namelen = Math.max(namelen, p.getName().length());
        }
        return namelen;
    }


    private static final double MILLION = 1_000_000.0;


    private final List<Problem<?>> problems = new ArrayList<>();
    private final int longestname;

    public ProjectEuler() {

        /* **********************************
         * ADD YOUR PROBLEMS HERE!
         * ***********************************/

        problems.add(new AverageIntegers());
        // problems.add(new AlternativeImplementation1());
        // problems.add(new AlternativeImplementation2());
        // ....

        longestname = longestName(problems);
    }

    private void process() {
        problems.stream().forEachOrdered(new ProblemConsumer());
    }

    private class ProblemConsumer implements Consumer<Problem<?>> {
        @Override
        public void accept(final Problem<?> problem) {

            final long basetime = System.nanoTime();
            final int wreps = problem.getWarmups();
            final int rreps = problem.getRealRuns();

            long btime = System.nanoTime();
            final String result = problem.getResult();
            btime = System.nanoTime() - btime;
            for (int i = wreps; i > 0; i--) {

                String actual = problem.getResult();
                if (!result.equals(actual)) {
                    throw new IllegalStateException("Unexpected result "
                            + actual);
                }
                ;
            }

            System.gc();

            final long start = System.nanoTime();
            for (int i = rreps; i > 0; i--) {
                problem.execute();
            }
            final long end = System.nanoTime();
            final long elapsed = end - start;

            String actual = problem.getResult();

            System.out.printf("%-" + longestname
                    + "s => %s (hot %.5fms - cold %.3fms (total %.3fms))\n",
                    problem.getName(), actual, (elapsed / MILLION) / rreps,
                    btime / MILLION, (end - basetime) / MILLION);
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ What is going on with double warm up: one with the warmups the other two calls to process() with a println("\n\nWarmup Complete\n\n") in between? \$\endgroup\$ – abuzittin gillifirca Jun 4 '14 at 11:44
7
\$\begingroup\$

Framework

    /* **********************************
     * ADD YOUR PROBLEMS HERE!
     * ***********************************/

I'm sorry, did you just call this a framework? Never in my life have I seen a framework where I had to edit the sourcecode to make it usable.

Let users of the framework pass the List<Problem<?>> problems to the constructor instead.

And while you're at it, can I please have a public method from the ProjectEuler class? process for example, it'd be ideal as a public method.


Naming

The ProjectEuler class isn't restricted to only problems that implements the EulerProblem interface, is it? I'm sure you can find a better name. ProblemBenchmarker perhaps?


Abstract class?

I don't see the point of making Problem an abstract class. Personally, I think it makes more sense to add a field to the Problem class and a parameter to the constructor:

public Problem(String name, int warmups, int realruns, Supplier<T> supplier) {

And simply modify the execute method to:

public T execute() {
    return supplier.get();
}

This will provide the possibility to have multiple problems in the same class, which IMO provides a nice overview of the problems:

public static void main(String[] args) {
    List<Problem<?>> problems = new ArrayList<>();
    problems.add(new Problem<>("Averaging", 1000, 10000, ProblemMain::problemOne));
    problems.add(new Problem<>("Multiplying", 1000, 10000, ProblemMain::problemTwo));

    ProjectEuler euler = new ProjectEuler(problems);

    euler.process();
    System.out.println("\n\nWarmup Complete\n\n");
    euler.process();

}

private static final int[] DATA = {1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1};

public static Double problemOne() {
    int sum = 0;
    for (int v : DATA) {
        sum += v;
    }
    return sum / (double)DATA.length;
}

public static Integer problemTwo() {
    int sum = 0;
    for (int v : DATA) {
        sum *= v;
    }
    return sum;
}

Generics

I'm not so sure that the generics of the Problem<T> class does you any good. It's used in a List<Problem<?>> anyway so I don't see that the type safety of generics gives you anything. Consider removing the generics and use a Supplier<?> inside it instead, and have the execute() method return an Object.

Of course it'd be neat if it was possible to avoid the auto-boxing that Java does on primitive values, but I expect that would require some code duplication, and I'm not sure if the potential performance gain you could get out of it is worth the code to add it. (I bet you can answer that better than I can, but you have taught me that auto-boxing does affect the performance a bit)


Usefulness

Overall, I think this code will be extremely useful, especially when I can use it without having to modify it's source!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Performance benchmarking small functions in Java is notoriously difficult, and there are a number of tools out there to help (caliper, others). Those other tools require a fair amount of setup and installation to get them working.

That's a great initiative! I just don't think you're achieving it: this still requires a fair amount of setup, copy-pasting, and hardcoded code editing. This is not really easy to use, so I think you're missing your main goal.

Separation of responsibilities

The Problem<?> class is in charge of too many things:

  • Represents the subject of the benchmark (the thing you want to measure)
  • Tracks the result of the subject (the returned T of execute())
  • Contains the implementation of the subject (in execute() of sub-classes)

The biggest problem is tracking the result. Validating the correctness of the algorithm belongs to unit tests, not the benchmarking tool.

The implementation of the algorithm you're benchmarking should not be forced to extend Program<?>, but be free to stand on its own, unaware of the benchmark framework. A nice coding challenge solution should expose methods that make it easy to test or benchmark anyway.

An alternative approach

I'm thinking of a loosely coupled annotation-based framework, something like this:

@BenchmarkSuite(iterations = 100, warmUp = true)
public class Example {

    public void run(int[] input) {
        // make a call to the solution implementation
    }

    // can override default values set in @BenchmarkSuite
    @MeasureTime(iterations = 3)
    public void largeUnsortedSample() {
        // run(...);
    }

    @MeasureMemory
    public void largeSetWorstCaseScenario() {
        // run(...);
    }
}

This is extremely flexible, because the framework doesn't dictate how you run the subject code, it can be anything you need, there is no requirement on class types and method signatures.

I created a proof of concept, which is quite crappy for now, but could be the start of something:

https://github.com/janosgyerik/java-microbench

To benchmark multiple subjects, I'm thinking the following programming interface would be great, if possible:

interface Problem {
    void solve(int[] input);
}

@Subject
Problem problem1 = new Problem() {
    @Override
    public void solve(int[] input) {
        // call one implementation
    }
};

@Subject
Problem problem2 = new Problem() {
    @Override
    public void solve(int[] input) {
        // call a different implementation
    }
};

// the framework should alternate the value for each @Subject
// before running each benchmark method
@Work
Problem problem;

public void run(String message) {
    problem.solve(message);
}

That is, designate a @Work object, such that for each @Subject, the framework will alternate the value, making it easy to repeat the same tests for multiple implementations. The requirement is that all @Subject implement a common interface, corresponding to the type of @Work. Something like that. The Problem interface itself above is not part of the framework, it's just sample code.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.