Tworzenie rekurencji ogona w C++

Question

Moja funkcja może być napisana znacznie prościej, jeśli wykonam rekursję wywołania ogona (w przeciwieństwie do pętli for (;;)...break). Obawiam się jednak, że wystąpią problemy z wydajnością, jeśli kompilator nie zoptymalizuje go, szczególnie dlatego, że zostanie skompilowany przez użytkownika końcowego.

1. Czy istnieje sposób, aby poinformować kompilator „upewnij się zoptymalizować połączenie ogon, albo dać mi błąd” (np Scala obsługuje tę funkcję)

2. Jeśli kompilator nie może zoptymalizować go z dala, jakie są granice wydajności? O ilu ogonach mogę się spodziewać, że będę mógł biegać bez zrywania stosu?

---

UPDATE:

są kompilatory gcc i MSVC.

Zazwyczaj oczekuję kilkunastu połączeń ogona. Ale skrajny przypadek może mieć tysiące. Platforma to typowy komputer przenośny typu low-end (np. Core i3 lub i5).

Answer 1

Nie, nie ma sposobu, aby powiedzieć kompilatorowi, że rekurencja ogona jest wymagana. Niektóre kompilatory (których nie znam) mogą obsługiwać adnotacje związane z implementacją, ale wymaga to użycia tego konkretnego kompilatora. Niektóre inne kompilatory, w niektórych trybach, celowo nigdy nie obsługują wywołań ogonkowych, ponieważ mogą zapewnić lepsze wrażenia debugowania poprzez nieobsługiwanie wywołań ogonowych. Użytkownik może używać takiego kompilatora.

Dozwolona głębokość rekursji zależy w dużym stopniu od programu, funkcji i implementacji i nie można podać dla niej żadnych sensownych liczb. Biorąc pod uwagę konkretną platformę, możesz prawdopodobnie określić domyślny rozmiar stosu, zbadać rozmiar ramki dla konkretnego kompilatora na tej platformie i wykonać prosty podział, aby uzyskać przybliżoną liczbę połączeń zagnieżdżonych, jakie możesz mieć.

Polecam przepisanie go w sposób, który wyjaśnia czytelnikowi, co się dzieje, ale nie polega na kompilatorze optymalizującym ogonki. Chociaż znienawidzone, instrukcja goto może być bardzo przydatna.

Weźmy prosty ogon rekurencyjnej funkcji bit licznikami:

int bitcount(unsigned int n, int acc = 0) { 
    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

Można trywialnie przepisany jako

int bitcount(unsigned int n, int acc = 0) { 
tail_recurse: 
    if (n == 0) 
    return acc; 

    // tail return bitcount(n >> 1, acc + (n & 1)); 
    acc += n & 1; 
    n = n >> 1; 
    goto tail_recurse; 
} 

Oczywiście jest to proste wersję, która jest trywialnie przepisany w celu uniknięcia rekursji całkowicie , i prawdopodobnie nie powinien nawet zostać zaimplementowany ręcznie, ale konkretna transformacja, której użyłem tutaj, to taka, którą można zastosować do dowolnej funkcji, gdzie rekurencja ogona jest możliwa i gdzie potrzebna jest rekurencja ogona. Komentarz powinien upewnić się, że czytelnik nadal może łatwo zauważyć, co się dzieje.

Answer 2

z GCC można dodać kontrolę wykonania przy użyciu funkcji backtrace():

#include <cassert> 
#include <iostream> 
#include <execinfo.h> 

size_t start; 

size_t stack_frames() 
{ 
    void *array[16]; 
    size_t size = backtrace(array, 16); 

    // std::cout << "Obtained " << size << " stack frames.\n"; 
    return size; 
} 

bool missing_tail() 
{ 
    return stack_frames() > start + 2; 
} 

int bitcount(unsigned int n, int acc = 0) 
{ 
    assert(!missing_tail()); 

    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

int main() 
{ 
    start = stack_frames(); 

    std::cout << bitcount(10) << '\n'; 

    return 0; 
} 

Kiedy skompilowany z poziomu optymalizacji niższy niż -O2 (brak optymalizacji ogon rekurencji) masz awarię twierdzenia.