इस फ़ंक्शन का रिकर्सिव संस्करण क्यों तेज़ है?

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

Runtimes थे time कमांड के माध्यम से यूनिक्स उपयोगकर्ता समय का उपयोग करके लिया गया। कोड -std=c++11 -O3 विकल्पों के साथ जीसीसी -4.7 का उपयोग करके संकलित किया गया था (लेकिन मुझे लगता है कि इसे जीसीसी-4.6 पर c++0x के साथ काम करना चाहिए)। रिकर्सिव संस्करण 13s ले लिया और पुनरावृत्त संस्करण 30s लिया। दोनों को advance कॉल की समान संख्या की आवश्यकता होती है (और यदि आप लूप के अंदर 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 को हटाने) के बराबर है, और अनुकूलक कि unrolling का एक बेहतर मौका हो सकता है।

ऐसा कहा जा रहा है कि, मुझे नहीं लगता कि यह बड़ा समय अंतर बताता है, हालांकि यह समझाता है कि पुनरावर्ती संस्करण पुनरावर्तक से बहुत धीमा क्यों नहीं है। वास्तव में संकलक क्या किया यह देखने के लिए जेनरेटेड असेंबली की जांच करें।

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

और वास्तव में यही अपने सिस्टम पर पुनरावर्ती संस्करण के समान प्रदर्शन है (जी ++ 4.6.3-एसडीडी = सी ++ 0 एक्स)