爲什麼這個函數的遞歸版本更快？

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

當我更換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使用unix用戶時間獲取。代碼使用gcc-4.7編譯，選項-std=c++11 -O3（但我認爲它應該可以在gcc-4.6上使用c++0x）。遞歸版本花費了13s，迭代版本花費了30s。兩者都需要相同數量的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 ]; 
    } 
    } 

：現在，一旦進行改造，遞歸函數將類似於此。循環，如果你仔細觀察，相當於

for(; index_to_advance < N-1 && !in_range(index_to_advance);++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）