4

For an assignment I'm currently trying to measure the performance (space/time) difference between an iterative solution to the matrix chain problem and a recursive one.

The gist of the problem and the solution I'm using for the iterative version can be found here: http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/

I'm running a given input through both functions 10 times, measuring the space and time performance of each function. The very interesting thing is that while the recursive solution runs much slower than the iterative solution on the first call it's performance is much better on successive calls it is much faster. The functions are not making use of any class-global variables other than one for counting memory usage. Why is this occurring? Is it something the compiler is doing or am I missing something obvious?

Note: I know my way of measuring memory is wrong, planning on changing it.

Main: Initializes Array and passes it to run functions

    public static void main(String[] args) {

    int s[] = new int[] {30,35,15,5,10,100,25,56,78,55,23};
    runFunctions(s, 15);

}

runFunctions: Runs both functions 2 * n times, measuring space and time and printing results at the end

private static void runFunctions(int[]arr , int n){
    final Runtime rt = Runtime.getRuntime();

    long iterativeTime[] = new long [n],
         iterativeSpace[] = new long [n],
         recursiveSpace[] = new long [n],
         recursiveTime[] = new long [n];

    long startTime, stopTime, elapsedTime, res1, res2;

    for (int i = 0; i <n; i++){

        System.out.println("Measuring Running Time");

        //measure running time of iterative
        startTime = System.nanoTime();
        res1 = solveIterative(arr, false);
        stopTime = System.nanoTime();
        elapsedTime = stopTime - startTime;
        iterativeTime[i] = elapsedTime;

        //measure running time of recursive
        startTime = System.nanoTime();
        res2 = solveRecursive(arr, false);
        stopTime = System.nanoTime();
        elapsedTime = stopTime - startTime;
        recursiveTime[i] = elapsedTime;

        System.out.println("Measuring Space");

        //measure space usage of iterative
        rt.gc();
        res1 = solveIterative(arr, true);
        iterativeSpace[i] = memoryUsage;

        //measure space usage of recursive
        rt.gc();
        res2 = solveRecursive(arr, true);
        recursiveSpace[i] = memoryUsage;
        rt.gc();

        if (res1 != res2){
            System.out.println("Error! Results do not match! Iterative Result: " + res1 + " Recursive Result: " + res2);
        }
    }

    System.out.println("Time Iterative: " + Arrays.toString(iterativeTime));
    System.out.println("Time Recursive: " + Arrays.toString(recursiveTime));
    System.out.println("Space Iterative: " + Arrays.toString(iterativeSpace));
    System.out.println("Space Recursive: " + Arrays.toString(recursiveSpace));
}

solveRecursive: bootstrap for doRecursion

private static int solveRecursive(int[] s, boolean measureMemory){

    memoryUsage = 0;
    maxMemory = 0;

    int n = s.length - 1;
    int[][]  m = new int[n][n];
    int result;

    if (measureMemory){
        memoryUsage += MemoryUtil.deepMemoryUsageOf(n);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(s);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(m);
        result = doRecursion(0, n - 1, m,  s);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(result);
        System.out.println("Memory Used: " + memoryUsage);
    }
    else
    {
        result = doRecursion(0, n - 1, m,  s);
    }
    return result;
}

doRecursion: solves the function recursively

private static int doRecursion(int i, int j, int[][] m, int s[]){

    if (m[i][j] != 0){
        return m[i][j];
    }
    if (i == j){
        return 0;
    }
    else
    {
        m[i][j] = Integer.MAX_VALUE / 3;
        for (int k = i; k <= j - 1; k++){
            int q = doRecursion(i, k, m, s) + doRecursion(k + 1, j, m, s) + (s[i] * s[k + 1] * s[j + 1]);
            if (q < m[i][j]){
                m[i][j] = q;
            }
        }
    }
    return m[i][j];
}

solveIterative: Solves the problem iteratively

private static int solveIterative(int[] s, boolean measureMemory) {
    memoryUsage = 0;
    maxMemory = 0;
    int n = s.length - 1;
    int i = 0, j = 0, k= 0, v = 0;
    int[][]  m = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (i = 0; i + len <= n; i++) {
            j = i + len - 1;
            m[i][j] = Integer.MAX_VALUE;
            for (k = i; k < j; k++) {
                v = m[i][k] + m[k + 1][j] + s[i] * s[k + 1] * s[j + 1];
                if (m[i][j] > v) {
                    m[i][j] = v;
                }
            }
        }
    }

    if (measureMemory){
        memoryUsage += MemoryUtil.deepMemoryUsageOf(n);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(m);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(i);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(j);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(k);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(v);
        memoryUsage += MemoryUtil.deepMemoryUsageOf(s);

        System.out.println("Memory Used: " + memoryUsage);
    }

    return m[0][n - 1];
}

Output:

Time Iterative: [35605, 12039, 20492, 17674, 17674, 12295, 11782, 19467, 16906, 18442, 21004, 19980, 18955, 12039, 13832]
Time Recursive: [79918, 4611, 8453, 6916, 6660, 6660, 4354, 6916, 18699, 7428, 13576, 5635, 4867, 3330, 3586]
Space Iterative: [760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760, 760]
Space Recursive: [712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712, 712]
apangin
  • 92,924
  • 10
  • 193
  • 247
cferrier1995
  • 83
  • 2
  • 4
    Welcome to the world of dynamically optimizing, JIT-compiling Java runtime. – Marko Topolnik Oct 06 '16 at 20:03
  • It might not just be the JIT compilation. It could be some other expensive startup overheads such as class loading. – bhspencer Oct 06 '16 at 20:07
  • If you turn off the JIT compilation (using the VM arg `-Djava.compiler=NONE`) you might get a more consistent side-by-side comparison. Either way your first iteration could be an outlier though. – nbrooks Oct 06 '16 at 20:10
  • The interesting thing is it's a consistent outlier, every time I run it the recursive call is absolutely horrendous but gets much better than the iterative version on successive calls. It's also interesting that it improves a lot more than the iterative version. Thanks for the tip on disabling JIT, I'll make sure to do that for accuracy. – cferrier1995 Oct 06 '16 at 20:16
  • 1
    Ehhhhhh. Depends what you mean by "accuracy." If you want to measure which one is going to be faster in real program use, the JIT should be on. Measuring without JIT will get you _consistent_ results, but not necessarily meaningful results. – Louis Wasserman Oct 06 '16 at 21:41
  • Possible duplicate of [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – the8472 Oct 07 '16 at 06:34

2 Answers2

3

The problem is that your test runs too short. JIT has not enough time to optimize the methods well enough.

Try repeating the test at least 200 times (instead of 15) and you'll see the difference.

Note that JIT compilation does not happen just once. Methods can be recompiled several times as JVM collects more runtime statistics. You've hit the situation where solveRecursive survived more levels of optimization than solveIterative.

In this answer I've described how JIT decides to compile a method. Basically there are two main compilation triggers: the method invocation threshold and the backedge threshold (i.e. loop iteration counter).

Note that those two methods have different compilation triggers:

  • solveRecursive does more calls => it is compiled when invocation threshold is reached;
  • solveIterative runs more loops => it is compiled when backedge threshold is reached.

These thresholds are not equal, and it happens that on a short distance solveRecursive is compiled earlier. But as soon as solveIterative is optimized, it starts to perform even better.

There is also a trick to make solveIterative compiled earlier: move the innermost loop for (k = i; k < j; k++) to a separate method. Yes, it may sound strange, but JIT is better in compiling several small methods instead of compiling one big method. Smaller methods are easier to understand and to optimize not only for humans, but also for computers :)

Community
  • 1
  • 1
apangin
  • 92,924
  • 10
  • 193
  • 247
  • To make sure the code has been compiled with `-XX:+PrintCompilation` the test should be run long enough so that you see all the methods have been compiled. +1 – Peter Lawrey Oct 07 '16 at 12:25
-1

It is absolutely 100% normal for Java code to get faster after you use it more. That's more or less the whole point of the JIT compiler -- to optimize at runtime code that's getting used more heavily.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • True. However, this does not answer the question why `solveRecursive` is eventually faster than `solveIterative` (which is somewhat counterintuitive). JIT compilation should make both methods faster. – apangin Oct 06 '16 at 23:36
  • The JIT is made of magic. It's not exactly super predictable what works better than what. – Louis Wasserman Oct 06 '16 at 23:37