이 함수의 재귀 버전이 더 빠른 이유는 무엇입니까?

Question

여기

다차원 수치 범위에 걸쳐 반복하는 단순 클래스 :

#include <array> 
#include <limits> 

template <int N> 
class NumericRange 
{ 
public: 
    // typedef std::vector<double>::const_iterator const_iterator; 
    NumericRange() { 
    _lower.fill(std::numeric_limits<double>::quiet_NaN()); 
    _upper.fill(std::numeric_limits<double>::quiet_NaN()); 
    _delta.fill(std::numeric_limits<double>::quiet_NaN()); 
    } 
    NumericRange(const std::array<double, N> & lower, const std::array<double, N> & upper, const std::array<double, N> & delta): 
    _lower(lower), _upper(upper), _delta(delta) { 
    _state.fill(std::numeric_limits<double>::quiet_NaN()); 
    _next_index_to_advance = 0; 
    } 

    const std::array<double, N> & get_state() const { 
    return _state; 
    } 

    void start() { 
    _state = _lower; 
    } 

    bool in_range(int index_to_advance = N-1) const { 
    return (_state[ index_to_advance ] - _upper[ index_to_advance ]) < _delta[ index_to_advance ]; 
    } 

    void advance(int index_to_advance = 0) { 
    _state[ index_to_advance ] += _delta[ index_to_advance ]; 
    if (! in_range(index_to_advance)) { 
     if (index_to_advance < N-1) { 
    // restart index_to_advance 
    _state[index_to_advance] = _lower[index_to_advance]; 

    // carry 
    index_to_advance; 
    advance(index_to_advance+1); 
     } 
    } 
    } 

private: 
    std::array<double, N> _lower, _upper, _delta, _state; 
    int _next_index_to_advance; 
}; 

int main() { 
    std::array<double, 7> lower{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0}; 
    std::array<double, 7> upper{1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0}; 
    std::array<double, 7> delta{0.03, 0.06, 0.03, 0.06, 0.03, 0.06, 0.03}; 

    NumericRange<7> nr(lower, upper, delta); 
    int c = 0; 
    for (nr.start(); nr.in_range(); nr.advance()) { 
    const std::array<double, 7> & st = nr.get_state(); 
    ++c; 
    } 
    std::cout << "took " << c << " steps" << std::endl; 

    return 0; 
} 

I가 증가을 비 재귀 적 변형과 advance 함수 런타임를 교체 할 때 :

void advance(int index_to_advance = 0) { 
    bool carry; 
    do { 
    carry = false; 
    _state[ index_to_advance ] += _delta[ index_to_advance ]; 
    if (! in_range(index_to_advance)) { 
     if (index_to_advance < N-1) { 
    // restart index_to_advance 
    _state[index_to_advance] = _lower[index_to_advance]; 

    // carry 
    ++index_to_advance; 
    carry = true; 
    // advance(index_to_advance); 
     } 
    } 
    } while (carry); 
} 

런타임이었다 time 명령을 통해 유닉스 사용자 시간을 사용하여 가져 왔습니다. 이 코드는 옵션 -std=c++11 -O3을 사용하여 gcc-4.7을 사용하여 컴파일되었습니다 (그러나 gcc-4.6의 c++0x에서 작동해야한다고 생각합니다). 재귀 버전에는 13 초가 걸렸으며 반복 버전에는 30 초가 걸렸습니다. 둘 다 동일한 숫자의 advance 호출을 요구합니다 (for(ns.start()...) 루프 내에 nr.get_state() 어레이를 인쇄하는 경우 모두 동일한 작업을 수행합니다).

이것은 재미있는 수수께끼입니다. 재귀가 왜 더 효율적이고 최적화가 가능한지 알아 내도록 도와주세요.

Answer 1

재귀 버전은 꼬리 - 재귀의 예입니다. 이는 컴파일러가 재귀를 반복으로 변형 할 수 있음을 의미합니다. 변환이 수행되면 이제, 재귀 기능은 다음과 유사합니다 :

void advance(int index_to_advance = 0) { 
    _state[ index_to_advance ] += _delta[ index_to_advance ]; 
    while (!in_range(index_to_advance) && index_to_advance < N-1) { 
     // restart index_to_advance 
     _state[index_to_advance] = _lower[index_to_advance]; 

     // carry 
     ++index_to_advance; 
     _state[ index_to_advance ] += _delta[ index_to_advance ]; 
    } 
    } 

당신이 버전이 하나 개 추가 테스트 및 상태 변수를 포함시피. 당신이 자세히 보면 루프는, (끝에 ++index_to_advance을 제거)

for(; index_to_advance < N-1 && !in_range(index_to_advance);++index_to_advance) 

에 해당하고, 최적화는을 줄이기의 더 나은 기회가있을 수 있습니다.

반복되는 버전이 반복적 인 버전보다 왜 그렇게 느리지 않은지 설명하지만, 나는 이것이 거대한 시간 차이를 설명한다고 생각하지 않습니다. 컴파일러가 실제로 무엇을했는지 보려면 생성 된 어셈블리를 확인하십시오.

꼬리 재귀 최적화와

, 함수가된다 :

Answer 2

그냥 데이비드 로드리게스가 한 말에 자세한 내용을 추가 할 수

void advance(int index_to_advance = 0) { 
    top: 
    _state[ index_to_advance ] += _delta[ index_to_advance ]; 
    if (! in_range(index_to_advance)) { 
    if (index_to_advance < N-1) { 
     // restart index_to_advance 
     _state[index_to_advance] = _lower[index_to_advance]; 

     // carry 
     ++index_to_advance; 
     goto top; 
    } 
    } 
} 

을이 참으로 내 시스템에 재귀 버전과 동일한 성능을 가지고 않습니다 (g ++ 4.6.3 -std = C++ 0x)