Java iterative vs recursive

Question

Can anyone explain why the following recursive method is faster than the iterative one (Both are doing it string concatenation) ? Isn't the iterative approach suppose to beat up the recursive one ? plus each recursive call adds a new layer on top of the stack which can be very space inefficient.

    private static void string_concat(StringBuilder sb, int count){
        if(count >= 9999) return;
        string_concat(sb.append(count), count+1);
    }
    public static void main(String [] arg){

        long s = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 9999; i++){
            sb.append(i);
        }
        System.out.println(System.currentTimeMillis()-s);
        s = System.currentTimeMillis();
        string_concat(new StringBuilder(),0);
        System.out.println(System.currentTimeMillis()-s);

    }

I ran the program multiple time, and the recursive one always ends up 3-4 times faster than the iterative one. What could be the main reason there that is causing the iterative one slower ?

Make sure you learn how to properly microbenchmark. You should be timing many iterations of both and averaging these for your times. Aside from that, you should make sure the VM isn't giving the second an unfair advantage by not compiling the first. — obataku
– obataku, Commented Sep 5, 2012 at 3:30
Also, change their order, repeat the whole test in a loop at least five times (discarding the first two for warmup) and use System.nanoTime — Thilo
– Thilo, Commented Sep 5, 2012 at 3:32
In fact, the default HotSpot compilation threshold (configurable via -XX:CompileThreshold) is 10,000 invokes, which might explain the reuslts you see here. HotSpot doesn't really do any tail optimizations so it's quite strange that the recursive solution is faster. — obataku
– obataku, Commented Sep 5, 2012 at 3:32
Try to reverse the positions of recursive method and iterative method. You will see the reverse of your observation :) — Vikdor
– Vikdor, Commented Sep 5, 2012 at 3:33
Your recursive approach is faster simply because the JVM hasn't yet warmed up when you run the iterative approach. — FThompson
– FThompson, Commented Sep 5, 2012 at 3:34

Community · Accepted Answer · 2017-05-23 11:53:21Z

See my comments.

Make sure you learn how to properly microbenchmark. You should be timing many iterations of both and averaging these for your times. Aside from that, you should make sure the VM isn't giving the second an unfair advantage by not compiling the first.

In fact, the default HotSpot compilation threshold (configurable via -XX:CompileThreshold) is 10,000 invokes, which might explain the results you see here. HotSpot doesn't really do any tail optimizations so it's quite strange that the recursive solution is faster. It's quite plausible that StringBuilder.append is compiled to native code primarily for the recursive solution.

I decided to rewrite the benchmark and see the results for myself.

public final class AppendMicrobenchmark {

  static void recursive(final StringBuilder builder, final int n) {
    if (n > 0) {
      recursive(builder.append(n), n - 1);
    }
  }

  static void iterative(final StringBuilder builder) {
    for (int i = 10000; i >= 0; --i) {
      builder.append(i);
    }
  }

  public static void main(final String[] argv) {
    /* warm-up */
    for (int i = 200000; i >= 0; --i) {
      new StringBuilder().append(i);
    }

    /* recursive benchmark */
    long start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      recursive(new StringBuilder(), 10000);
    }
    System.out.printf("recursive: %.2fus\n", (System.nanoTime() - start) / 1000000D);

    /* iterative benchmark */
    start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      iterative(new StringBuilder());
    }
    System.out.printf("iterative: %.2fus\n", (System.nanoTime() - start) / 1000000D);
  }
}

Here are my results...

C:\dev\scrap>java AppendMicrobenchmark
recursive: 405.41us
iterative: 313.20us

C:\dev\scrap>java -server AppendMicrobenchmark
recursive: 397.43us
iterative: 312.14us

These are times for each approach averaged over 1000 trials.

Essentially, the problems with your benchmark are that it doesn't average over many trials (law of large numbers), and that it is highly dependent on the ordering of the individual benchmarks. The original result I was given for yours:

C:\dev\scrap>java StringBuilderBenchmark
80
41

This made very little sense to me. Recursion on the HotSpot VM is more than likely not going to be as fast as iteration because as of yet it does not implement any sort of tail optimization that you might find used for functional languages.

Now, the funny thing that happens here is that the default HotSpot JIT compilation threshold is 10,000 invokes. Your iterative benchmark will more than likely be executing for the most part before append is compiled. On the other hand, your recursive approach should be comparatively fast since it will more than likely enjoy append after it is compiled. To eliminate this from influencing the results, I passed -XX:CompileThreshold=0 and found...

C:\dev\scrap>java -XX:CompileThreshold=0 StringBuilderBenchmark
8
8

So, when it comes down to it, they're both roughly equal in speed. Note however that the iterative appears to be a bit faster if you average with higher precision. Order might still make a difference in my benchmark, too, as the latter benchmark will have the advantage of the VM having collected more statistics for its dynamic optimizations.

What does the 2nd paragraph mean ? recursive sometimes could be faster or even tie up with the iterative approach after the warm up ?
@user1389813 you observe the recursive solution being faster because HotSpot by default will compile a method to native code after 10,000 calls. If you swap the order, you will more than likely observe the opposite.

Collectives™ on Stack Overflow

Java iterative vs recursive

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related