Java - test algorithm performance

In this article, we would like to show how to test algorithms' performance in Java.

Usually, when we compare algorithms that execution times are short, we repeat computations multiple times to get precise results. The number of repeats is selected empirically. The source code that is not an algorithm part shouldn't be measured.

Main concept:

public class Program {

    public static void main(String[] args) {
        
        // Usage example:

        int repeats = 100000;  // set number of repeats depending on cases complexity

        PerformanceUtils.test(repeats, "case 1", () -> { /* source code case 1 */ });
        PerformanceUtils.test(repeats, "case 2", () -> { /* source code case 2 */ });
        PerformanceUtils.test(repeats, "case 3", () -> { /* source code case 3 */ });

        // add more cases here ...
    }
}

PerformanceUtils.java file:

public class PerformanceUtils {

    public static void test(int repeats, String description, Runnable function) {
        long t1 = System.nanoTime();
        for (int i = 0; i < repeats; ++i) {
            function.run();
        }
        long t2 = System.nanoTime();
        long dt = t2 - t1;
        System.out.println(description + ": total time is " + (dt / 1000000) + " ms");
    }
}

Hint: presented concept describes only a simple way how to test performance - in practice tests made by benchmarks are more complex.

Practical example

In the below example we compare algorithms that computes Fibonacci sequence values.

In the test, we made 100000 repeats on Fibonacci algorithms using Ryzen 9 x5900 processor and Java 11 under Window 11.

Test result:

Iterative algorithm: total time is 25 ms
Binet's formula: total time is 36 ms

Conclusion: iterative algorithm is ~1.5 times faster in the tested cases.

Test source code:

public class Program {

    // Tested algorithms:

    private static double fibonacci1(double number) {
        if (number < 1) return 0;
        if (number < 2) return 1;
        return fibonacci1(number - 2) + fibonacci1(number - 1);
    };

    private static double fibonacci2(double number) {
        double a = Math.pow(1 + 2.23606797749979, number);
        double b = Math.pow(1 - 2.23606797749979, number);
        double c = 2.23606797749979 * Math.pow(2, number);
        return Math.round((a - b) / c);
    }


    // Usage example:

    public static void main(String[] args) {

        Runnable case1 = () -> {
            for (int i = 1; i < 10; ++i) {
                fibonacci1(i);
            }
        };
        Runnable case2 = () -> {
            for (int i = 1; i < 10; ++i) {
                fibonacci2(i);
            }
        };

        int repeats = 100000;  // set number of repeats depending on cases complexity

        PerformanceUtils.test(repeats, "Iterative algorithm", case1);
        PerformanceUtils.test(repeats, "Binet's formula", case2);
    }
}

Hint: PerformanceUtils class used in this test is located on the article top.