자바 반복 대 재귀

Question

누구나 다음과 같은 재귀 메서드가 반복적 인 것보다 빠르다는 이유를 설명 할 수 있습니까? (모두 문자열 연결을 수행하고 있습니다)? 반복적 인 접근법이 재귀 적 접근법을 깨뜨리는 것이 아닌가? 더하기 각 재귀 호출 스택의 맨 위에 새로운 공간을 비효율적으로 만들 수있는 새로운 레이어를 추가합니다.

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); 

    } 

프로그램을 여러 번 실행했지만 반복적 인 프로그램은 항상 반복적 인 프로그램보다 3-4 배 빠릅니다. 반복적 인 것을 더 느리게하는 주된 이유는 무엇일까요?

Answer 1

my comments을 참조하십시오.

올바르게 마이크로 벤치 마크하는 법을 배우십시오. 당신은 두 시간 동안 많은 반복을해야하고, 당신의 시간을 평균화해야합니다. 그 외에도, VM이 첫 번째 컴파일 링을하지 않으면 두 번째로 불공정 한 이점을주지 못하게해야합니다.

실제로 기본값 인 HotSpot 컴파일 임계 값 (-XX:CompileThreshold을 통해 구성 가능)은 10,000 호출이며 여기서 볼 수있는 결과를 설명 할 수 있습니다. HotSpot은 꼬리 최적화를 실제로 수행하지 않으므로 재귀 솔루션이 더 빠르다는 것이 이상합니다. StringBuilder.append은 주로 재귀 적 솔루션을위한 원시 코드로 컴파일됩니다.

벤치 마크를 다시 작성하고 직접 결과를 확인했습니다. 여기

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); 
    } 
} 

는 각각의 접근 방식은 1000 개 시험에서 평균에 대한

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

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

이이 시간입니다 ... 내 결과입니다.

기본적으로 벤치 마크의 문제점은 여러 번의 시도 (law of large numbers)에 걸쳐 평균을 나타내지 않으며 개별 벤치 마크의 순서에 크게 의존한다는 것입니다. 내가 당신을 위해 주어진 원래 결과 :

C:\dev\scrap>java StringBuilderBenchmark 
80 
41 

이 나에게 약간의 감각을했다. HotSpot VM의 재귀는 아직까지는 반복만큼 빠르지 않을 가능성이 높습니다. 왜냐하면 아직 기능적 언어에 사용되는 꼬리 최적화를 구현하지 않기 때문입니다.

여기서 일어나는 재미있는 일은 기본 HotSpot JIT 컴파일 임계 값이 10,000 호출이라는 것입니다. 반복적 인 벤치 마크는 컴파일 될 때까지 보다 더 많이 실행될 가능성이 높습니다.append이 컴파일됩니다. 반면, 재귀 접근법은 append이후에 컴파일 될 것이므로 이후에 비교적 빠를 것입니다. 결과에 영향을 미치는에서이 문제를 제거하기 위해, 나는 -XX:CompileThreshold=0 발견 ... 그것이 그것에 내릴 때

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

그래서, 그들은 모두 속도에 거의 동일한 것을 통과시켰다. 그러나 반복 정밀도가 더 높은 정밀도로 평균을 내면 조금 더 빨라지는 것에 유의하십시오.후자의 벤치 마크는 VM이 ​​동적 최적화를 위해 더 많은 통계를 수집한다는 이점을 갖기 때문에 주문은 여전히 ​​내 벤치 마크에서 차이를 만들 수 있습니다.