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

150

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.

Magnus Hoff
źródło

Odpowiedzi:

129

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ć.

Konrad Rudolph
źródło
Myślę, że ICC by to zrobiło. O ile wiem, ICC tworzy najszybszy kod na rynku.
Paul Nathan,
35
@Paul Pytanie brzmi, jak duża część szybkości kodu ICC jest spowodowana optymalizacjami algorytmicznymi, takimi jak optymalizacje wywołań końcowych, a ile jest spowodowana optymalizacjami pamięci podręcznej i mikroinstrukcji, które może zrobić tylko Intel, mając dogłębną wiedzę na temat swoich własnych procesorów.
Imagist
6
gccma węższą opcję -foptimize-sibling-calls„optymalizacji rodzeństwa i ogonienia wywołań rekurencyjnych”. Opcja ta (według gcc(1)stron podręcznika dla wersji 4.4, 4.7 i 4.8 kierowania różnych platform) jest włączona na poziomach -O2, -O3, -Os.
FooF
Ponadto działanie w trybie DEBUG bez jawnego żądania optymalizacji NIE spowoduje ŻADNEJ optymalizacji. Możesz włączyć PDB dla EXE trybu prawdziwego wydania i spróbować przejść przez to, ale pamiętaj, że debugowanie w trybie wydania ma swoje komplikacje - zmienne niewidoczne / pozbawione, zmienne scalone, zmienne wychodzące poza zakres w nieznanym / nieoczekiwanym zakresie, zmienne, do których nigdy nie trafiają zakres i stały się prawdziwymi stałymi z adresami na poziomie stosu i - cóż - scalonymi lub brakującymi ramkami stosu. Zwykle scalone ramki stosu oznaczają, że wywołanie wywoływane jest wbudowane, a brakujące / scalone ramki prawdopodobnie wywołują efekt końcowy.
Петър Петров
21

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;
}
Tom Barta
źródło
1
Możesz jednak aktywować optymalizację czasu łącza i myślę, że nawet externmetoda może być wtedy wbudowana .
Konrad Rudolph
5
Dziwne. Właśnie testowane gcc 4.2.3 (x86 Slackware'a 12.1) i gcc 4.6.2 (AMD64 Debian świszczącego) oraz z-O1 nie ma inline i bez optymalizacji ogon rekursji . Trzeba użyć -O2do tego (no, w 4.2.x, która jest raczej starożytny teraz, to nadal nie będzie inline). BTW Warto też dodać, że gcc może optymalizować rekurencję, nawet jeśli nie jest to ściśle ogonowa (jak silnia bez akumulatora).
przemoc
16

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.

Martin Bonner wspiera Monikę
źródło
Nie działa na mnie. System informuje mnie, że mój głos jest zablokowany, dopóki odpowiedź nie zostanie zmieniona.
hmuelner
Po prostu zredagowałem odpowiedź (usunąłem zwroty) i teraz mogłem cofnąć swój głos przeciw.
hmuelner
11

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 ...

Greg Whitfield
źródło
2
spróbuj gcc, dlaczego -g -O3 i uzyskaj optymalizacje w kompilacji do debugowania. xlC ma to samo zachowanie.
g24l
Kiedy mówisz „większość kompilatorów”: jakie kolekcje kompilatorów bierzesz pod uwagę? Jak wskazano, istnieją co najmniej dwa kompilatory, które przeprowadzają optymalizacje podczas kompilacji debugowania - i o ile wiem, VC również to robi (chyba że włączasz być może modyfikuj i kontynuuj).
jazda na nartach
7

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ę. :-(

0124816
źródło