Tại sao phiên bản đệ quy của hàm này nhanh hơn?

Question

Đây là một lớp đơn giản để lặp lại trên một phạm vi số đa chiều:

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

Khi tôi thay thế advance chức năng với một biến thể không đệ quy, thời gian chạy tăng:

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

Runtimes là sử dụng thời gian người dùng unix thông qua lệnh time. Mã được biên dịch bằng gcc-4.7 với các tùy chọn -std=c++11 -O3 (nhưng tôi nghĩ nó nên hoạt động với c++0x trên gcc-4.6). Phiên bản đệ quy mất 13 giây và phiên bản lặp lại mất 30 giây. Cả hai yêu cầu cùng một số cuộc gọi advance để chấm dứt (và nếu bạn in mảng nr.get_state() bên trong vòng lặp for(ns.start()...), cả hai đều thực hiện tương tự).

Đây là một câu đố vui nhộn! Giúp tôi tìm ra lý do tại sao đệ quy sẽ hiệu quả hơn/tối ưu hơn.

Answer 1

Phiên bản đệ quy là ví dụ về đệ quy đuôi có nghĩa là trình biên dịch có thể chuyển đổi đệ quy thành lặp lại. Bây giờ, khi việc chuyển đổi được thực hiện, hàm đệ quy sẽ trông giống như sau:

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

Khi bạn thấy phiên bản của bạn chứa thêm một kiểm tra và biến điều kiện. Các vòng lặp, nếu bạn nhìn kỹ là tương đương với

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

(loại bỏ các ++index_to_advance ở cuối), và tôi ưu hoa có thể có một cơ hội tốt hơn unrolling đó.

Điều đó đang được nói, tôi không nghĩ rằng điều này giải thích sự khác biệt thời gian rất lớn, mặc dù nó giải thích tại sao phiên bản đệ quy không chậm hơn nhiều so với phiên bản lặp lại. Kiểm tra hội đồng được tạo ra để xem những gì trình biên dịch thực sự đã làm.

Answer 2

Chỉ cần thêm chi tiết hơn với những gì David Rodriguez nói:

Với tối ưu hóa đệ quy đuôi, chức năng trở thành:

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

và điều này thực sự có hiệu năng giống như các phiên bản đệ quy trên hệ thống của tôi (g ++ 4.6.3 -std = C++ 0x)