¿Por qué la versión recursiva de esta función es más rápida?

Question

Aquí es una clase simple para iterar sobre un rango numérico multidimensional:

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

Cuando se sustituye la función advance con una variante no recursiva, el tiempo de ejecución aumenta:

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 eran tomado usando el tiempo de usuario de Unix a través del comando time. El código se compiló usando gcc-4.7 con las opciones -std=c++11 -O3 (pero creo que debería funcionar con c++0x en gcc-4.6). La versión recursiva tomó 13s y la versión iterativa tomó 30s. Ambas requieren el mismo número de llamadas advance para terminar (y si imprime la matriz nr.get_state() dentro del bucle for(ns.start()...), ambas hacen lo mismo).

¡Este es un acertijo divertido! Ayúdame a descubrir por qué el recursivo sería más eficiente/más optimizable.

Answer 1

La versión recursiva es un ejemplo de cola-recursión lo que significa que el compilador puede transformar la recursión en iteración. Ahora, una vez que se lleva a cabo la transformación, la función recursiva tendría un aspecto similar a este:

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

Como se puede ver su versión contiene una prueba adicional y la variable de estado. El bucle, si se mira de cerca es equivalente a

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

(eliminación de la ++index_to_advance al final), y el optimizador podría tener una mejor oportunidad de desenrollar eso.

Dicho esto, no creo que esto explique la gran diferencia de tiempo, aunque sí explica por qué la versión recursiva no es mucho más lenta que la iterativa. Compruebe el ensamblaje generado para ver qué hizo realmente el compilador.

Answer 2

Sólo para añadir más detalle a lo que dijo David Rodríguez:

Con la optimización de recursión de cola, la función se convierte en:

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

y esto en efecto, tener el mismo rendimiento que la versión recursiva en mi sistema (g ++ 4.6.3 -std = C++ 0x)