Czy to może być optymalizacja połączenia z ogonem? Jeśli tak, jaki jest tego specjalny powód?

Question

Sprawdziłem dane wyjściowe zespołu na wielu poziomach optymalizacji z gcc 4.8.1 i clang 3.4.190255, bez optymalizacji połączeń ogonowych dla tego rodzaju kodu.

Czy istnieje jakiś szczególny powód, dla którego collatz_aux nie otrzymuje optymalizacji połączeń?

#include <vector> 
#include <cassert> 

using namespace std; 

vector<unsigned> concat(vector<unsigned> v, unsigned n) { 
    v.push_back(n); 
    return v; 
} 

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { 
    return n == 1 
     ? result 
     : n % 2 == 0 
      ? collatz_aux(n/2, concat(move(result), n)) 
      : collatz_aux(3 * n + 1, concat(move(result), n)); 
} 

vector<unsigned> collatz_vec(unsigned n) { 
    assert(n != 0); 
    return collatz_aux(n, {}); 
} 

int main() { 
    return collatz_vec(10).size(); 
} 

Answer 1

Destruktor dla parametru vector<unsigned> musi zostać wywołany po powrocie.

Answer 2

Nie powinieneś polegać na tym celu. Sądzę, że jest mało prawdopodobne, aby optymalizator wykrył, że połączenia rekursywne mogą być optymalizowane pod kątem ogółu.

Oto wersja nierekurencyjna.

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { 
    while(true){ 
    if(n == 1) return result; 
    result = concat(move(result), n); 
    if(n % 2 == 0) 
    { 
     n=n/2; 
    }else{ 
     n= 3 * n + 1; 
    } 
    } 
} 

Answer 3

tylko w celach informacyjnych, ja manipulowane wersję rekurencyjną, aby ogon rekursji, aby w ten sposób:

#include <vector> 
#include <cassert> 

using namespace std; 

template<class container> 
container &&collatz_aux(unsigned n, container &&result) { 
    static auto concat = [](container &&c, unsigned n) -> container &&{ 
     c.push_back(n); 
     return forward<container>(c); 
    }; 

    return n == 1 
     ? forward<container>(result) 
     : n % 2 == 0 
      ? collatz_aux(n/2, concat(forward<container>(result), n)) 
      : collatz_aux(3 * n + 1, concat(forward<container>(result), n)); 
} 

vector<unsigned> collatz_vec(unsigned n) { 
    assert(n != 0); 
    return collatz_aux(n, vector<unsigned>{}); 
} 

int main() { 
    return collatz_vec(10).size(); 
}