Why dynamic programming and naive solutions taking same execution time?

Question

I'm trying implement simple solution for rod cutting problem. Below is the code for naive and dynamic programming solutions,

public static int rodCutNaive(int[] a, int n) {
    if (n == 1) {
        return a[0];
    }
    int q = 0;
    for (int i = 1; i <= n; i++) {
        int optimalCut = a[i - 1] + rodCutNaive(a, n - i);
        if (q < optimalCut) {
            q = optimalCut;
        }
    }
    return q;
}

public static int rodCutDPBottomUp(int[] a, int n) {
    if (n == 1) {
        return a[0];
    }
    int[] s = new int[a.length];
    s[0] = a[0];

    for (int i = 2; i <= n; i++) {
        s[i - 1] = a[i - 1];
        for (int j = 1; j <= i - 1; j++) {
            int optimalCut = a[j - 1] + s[i - j - 1];
            if (s[i - 1] < optimalCut) {
                s[i - 1] = optimalCut;
            }
        }
    }

    return s[n - 1];
}

And I tested with below method,

public void testRodCutEfficiency() {
    int[] a = { 1, 5, 8, 9, 10, 17, 17, 20, 22, 25, 26, 29, 34, 35, 39, 45,
            46, 47, 50, 51 };

    long t1 = System.nanoTime();
    for (int i = 0; i < 1000; i++)
        Rod.rodCutNaive(a, a.length);
    long t2 = System.nanoTime();
    for (int i = 0; i < 1000; i++)
        Rod.rodCutDPBottomUp(a, a.length);
    long t3 = System.nanoTime();

    System.out.println("Problem size = " + a.length);
    System.out.println("Naive = " + (t2 - t1));
    System.out.println("DP    = " + (t3 - t2));
}

Output:

Problem size = 20
Naive = 7989627046
DP    = 7913165707

May be compiler doing some kind of tail recursion optimization with naive version or is it possible that JVM remebers solutions to previous calls of methods?

Oh, Sorry guys. It's a copy paste mistake. I called same method both the times. Now I've changed it and new output is,

Problem size = 20
Naive = 7764056945
DP    = 1324966

I tried to delete the question but it already has answers.

What is naive is your microbenchmarking. There are many precautions to follow. Check out the Google Caliper library, that's the simplest way to get (semi-)reliable results. — Marko Topolnik
Yup, don't worry about it. It's useful to accept an answer though so other users know not to spend too much time looking at the question. — David Kanarek

Peter Lawrey Peter Lawrey · Accepted Answer · 2012-11-15T11:05:18

May be compiler doing some kind of tail recursion optimization with naive version or is it possible that JVM remebers solutions to previous calls of methods?

The javac compiler does almost no optimisations, however the JIT optimises code after it has iterated 10,000 times which can ipact your result.

The HotSpot JVM doesn't support tail recursion optimisation and it doesn't remember previous results.

If I run the test repeatedly I see small improvement from

Problem size = 20
Naive = 5792466746
DP    = 8779592

to

Problem size = 20
Naive = 5701799026
DP    = 472377

Why dynamic programming and naive solutions taking same execution time?

3 Answers