Które kompilatory C ++, jeśli w ogóle, dokonują optymalizacji rekurencji ogonowej?

Wydaje mi się, że optymalizacja rekurencji ogonowej zarówno w C, jak i C ++ działałaby doskonale, ale podczas debugowania nigdy nie widzę stosu ramek, który wskazuje na tę optymalizację. To trochę dobrze, ponieważ stos mówi mi, jak głęboka jest rekursja. Jednak optymalizacja też byłaby miła.

Czy jakieś kompilatory C ++ wykonują tę optymalizację? Czemu? Dlaczego nie?

Jak mam powiedzieć kompilatorowi, żeby to zrobił?

• W przypadku MSVC: /O2lub/Ox
• W przypadku GCC: -O2lub-O3

Co powiesz na sprawdzenie, czy kompilator zrobił to w określonym przypadku?

• W przypadku MSVC włącz dane wyjściowe PDB, aby umożliwić śledzenie kodu, a następnie sprawdź kod
• Dla GCC ..?

Nadal brałbym sugestie, jak określić, czy dana funkcja jest zoptymalizowana w ten sposób przez kompilator (chociaż uważam za uspokajające, że Konrad mówi mi, żebym ją założył)

Zawsze można sprawdzić, czy kompilator w ogóle to robi, wykonując nieskończoną rekursję i sprawdzając, czy powoduje to nieskończoną pętlę lub przepełnienie stosu (zrobiłem to z GCC i okazało się, że -O2jest to wystarczające), ale chcę być w stanie sprawdzić pewną funkcję, o której wiem, że i tak się zakończy. Chciałbym mieć łatwy sposób na sprawdzenie tego :)

Po kilku testach odkryłem, że destruktory rujnują możliwość dokonania tej optymalizacji. Czasami warto zmienić zakres niektórych zmiennych i tymczasowych, aby upewnić się, że wykraczają poza zakres, zanim rozpocznie się instrukcja return.

Jeśli jakikolwiek destruktor musi być uruchomiony po wywołaniu końcowym, nie można przeprowadzić optymalizacji wywołania ogonowego.

Wszystkie obecne kompilatory głównego nurtu dość dobrze wykonują optymalizację wywołań ogonowych (i robią to przez ponad dekadę), nawet w przypadku wywołań rekurencyjnych, takich jak:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

Pozwalanie kompilatorowi na optymalizację jest proste: wystarczy włączyć optymalizację pod kątem szybkości:

• W przypadku MSVC użyj /O2lub /Ox.
• W przypadku GCC, Clang i ICC użyj -O3

Łatwym sposobem sprawdzenia, czy kompilator przeprowadził optymalizację, jest wykonanie wywołania, które w przeciwnym razie spowodowałoby przepełnienie stosu - lub sprawdzenie wyniku zestawu.

Jako interesująca uwaga historyczna, optymalizacja wywołań ogonowych dla C została dodana do GCC w trakcie pracy dyplomowej Marka Probsta. W pracy opisano kilka interesujących zastrzeżeń w realizacji. Warto przeczytać.

gcc 4.3.2 całkowicie wbudowuje tę funkcję (kiepska / trywialna atoi()implementacja) do main(). Poziom optymalizacji to -O1. Zauważam, że jeśli się nim bawię (nawet zmieniając go z staticna extern, rekurencja ogona znika dość szybko, więc nie polegałbym na tym w kwestii poprawności programu.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}

Poza oczywistością (kompilatory nie wykonują tego rodzaju optymalizacji, chyba że o to poprosisz), istnieje złożoność optymalizacji wywołań ogonowych w C ++: destruktory.

Biorąc pod uwagę coś takiego:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

Kompilator nie może (generalnie) tego zoptymalizować, ponieważ musi wywołać destruktor cls po powrocie wywołania rekurencyjnego.

Czasami kompilator widzi, że destruktor nie ma zewnętrznych widocznych skutków ubocznych (więc można to zrobić wcześniej), ale często nie.

Szczególnie powszechną formą tego jest sytuacja, w której Funkyfaktycznie występuje a std::vectorlub podobny.

Większość kompilatorów nie przeprowadza żadnej optymalizacji w kompilacji do debugowania.

Jeśli używasz VC, wypróbuj kompilację wydania z włączonymi informacjami PDB - pozwoli ci to prześledzić zoptymalizowaną aplikację i miejmy nadzieję, że zobaczysz, czego chcesz. Należy jednak pamiętać, że debugowanie i śledzenie zoptymalizowanej kompilacji przeskakuje z każdego miejsca i często nie można bezpośrednio sprawdzić zmiennych, ponieważ trafiają one tylko do rejestrów lub są całkowicie zoptymalizowane. To „ciekawe” doświadczenie ...

Jak wspomina Greg, kompilatory nie zrobią tego w trybie debugowania. W porządku, gdy kompilacje debugowania są wolniejsze niż kompilacje prod, ale nie powinny częściej ulegać awarii: a jeśli polegasz na optymalizacji wywołań końcowych, mogą zrobić dokładnie to. Z tego powodu często najlepiej jest przepisać wywołanie tail jako normalną pętlę. :-(