Które kompilatory C++ optymalizują rekurencję ogonową?

Question

Które kompilatory C++ optymalizują rekurencję ogonową?

Wydaje mi się, że optymalizacja rekurencji ogonowej w C i C++ będzie działać idealnie, jednak podczas debugowania nigdy nie widzę stosu ramek, który wskazywałby na taką optymalizację. To trochę dobrze, ponieważ stos mówi mi, jak głęboka jest rekurencja. Jednak optymalizacja byłaby również przyjemna.

Czy jakieś kompilatory C++ robią taką optymalizację? Dlaczego? Dlaczego nie?

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

dla MSVC: /O2 lub /Ox
dla GCC: -O2 lub -O3

Może Sprawdzimy, czy kompilator zrobił to w konkretnym przypadku?

dla MSVC, włącz wyjście PDB, aby móc śledzić kod, a następnie sprawdź kod
dla GCC..?

Nadal przyjmowałbym sugestie, jak określić, czy dana funkcja jest tak zoptymalizowana przez kompilator (chociaż uważam, że to pocieszające, że Konrad każe mi ją założyć)

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

Po kilku testach odkryłem, że destruktory niszczą możliwość dokonania tej optymalizacji. Czasem warto zmienić zakres pewne zmienne i tymczasowe, aby upewnić się, że wyjdą poza zakres przed rozpoczęciem instrukcji return -.

Jeśli jakikolwiek Destruktor musi być uruchomiony po wywołaniu tail-call, optymalizacja tail-call nie może być wykonana.

136

c++optimization tail-recursion

Author: Magnus Hoff, 0000-00-00

Source

1 answers

score 112 · Accepted Answer

Wszystkie obecne Kompilatory głównego nurtu wykonują optymalizację wywołań ogonowych dość dobrze (i robią to przez ponad dekadę), nawet dla wzajemnie rekurencyjnych wywołań , 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);
}

Pozwala kompilatorowi na optymalizację jest proste: wystarczy włączyć optymalizację dla szybkości:

dla MSVC użyj /O2 lub /Ox.
dla GCC, Clang i ICC, użyj -O3

Łatwym sposobem sprawdzenia, czy kompilator wykonał optymalizację jest wykonanie wywołania w przeciwnym razie spowodowałoby to przepełnienie stosu - lub spojrzenie na wyjście złożenia.

Jako ciekawostkę historyczną, optymalizacja wywołania ogonowego dla C została dodana do GCC w trakcie pracy dyplomowej przez Marka Probsta. W pracy opisano kilka ciekawych zastrzeżeń w implementacji. Warto przeczytać.