Comment la compilation peut-elle être (exponentielle) plus rapide que l’exécution?

Le code ci-dessous calcule les nombres de Fibonacci par un algorithme exponentiellement lent :

#include  #include  #define DEBUG(var) { std::cout << #var << ": " << (var) < long long { return n < 2 ? 1: fib(n - 1) + fib(n - 2); } int main(int argc, char *argv[]) { const long long fib91 = fib(91); DEBUG( fib91 ); DEBUG( fib(45) ); return EXIT_SUCCESS; } 

Et je calcule le 45ème nombre de Fibonacci à l’exécution et le 91ème à la compilation.

Le fait intéressant est que GCC 4.9 comstack le code et calcule fib91 en une fraction de seconde, mais il faut un certain temps pour cracher fib(45) .

Ma question: si GCC est suffisamment intelligent pour optimiser le calcul de fib(91) et ne pas prendre le chemin exponentiellement lent, qu’est-ce qui l’empêche de faire la même chose pour fib(45) ?

Est-ce que la moyenne de GCC ci-dessus produit deux versions compilées de la fonction fib , l’une étant rapide et l’autre exponentiellement lente?

La question n’est pas de savoir comment le compilateur optimise le calcul de fib(91) (oui, il utilise une sorte de mémo), mais s’il sait optimiser la fonction fib , pourquoi ne fait-il pas la même chose pour fib(45) ? Et, existe-t-il deux compilations distinctes de la fonction fib ? Un lent, et l’autre rapide?

GCC est probablement en train de constexpr fonctions constexpr (permettant un calcul de fib(n) (n) de fib(n) ). Cela est sans danger pour le compilateur car les fonctions constexpr sont purement fonctionnelles.

Comparez le algorithm (n) “algorithme du compilateur” (en utilisant la mémorisation) à votre algorithme d’exécution Θ (φ n ) (où φ est le nombre d’or) et soudainement, il est parfaitement logique que le compilateur soit beaucoup plus rapide.

De la page constexpr sur cppreference (emphase ajoutée):

Le spécificateur constexpr déclare qu’il est possible d’évaluer la valeur de la fonction ou de la variable au moment de la compilation.

Le spécificateur constexpr ne déclare pas qu’il est nécessaire d’évaluer la valeur de la fonction ou de la variable au moment de la compilation. Ainsi, on ne peut que deviner quelle heuristique GCC utilise pour choisir si elle doit évaluer au moment de la compilation ou à l’exécution, lorsqu’un calcul de compilation n’est pas requirejs par les règles de langage. Il peut choisir l’un ou l’autre, au cas par cas, et être toujours correct.

Si vous voulez forcer le compilateur à évaluer votre fonction constexpr au moment de la compilation, voici un truc simple qui le fera.

 constexpr auto compute_fib(const size_t n) -> long long { return n < 2 ? n : compute_fib(n - 1) + compute_fib(n - 2); } template  struct fib { static_assert(N >= 0, "N must be nonnegative."); static const long long value = compute_fib(N); }; 

Dans le rest de votre code, vous pouvez alors accéder à fib<45>::value ou fib<91>::value avec la garantie qu’ils seront évalués au moment de la compilation.

Au moment de la compilation, le compilateur peut mémoriser le résultat de la fonction. Ceci est sûr, car la fonction est un constexpr et renverra donc toujours le même résultat des mêmes entrées.

Au moment de l’exécution, il pourrait en théorie en faire autant. Cependant, la plupart des programmeurs C ++ se méfieraient des passages d’optimisation qui entraînent des allocations de mémoire masquées.

Lorsque vous demandez à fib (91) de donner une valeur à votre const fib91 dans le code source, le compilateur est obligé de calculer cette valeur à partir de const expr. Il ne comstack pas la fonction (comme vous semblez le penser), il suffit de voir que pour calculer fib91, il a besoin de fib (90) et de fib (89), pour le calculer, il a besoin de fib (87) … fib (1) qui est donné. C’est un algorithme $ O (n) $ et le résultat est calculé assez rapidement.

Cependant, lorsque vous demandez à évaluer fib (45) à l’exécution, le compilateur doit choisir d’utiliser l’appel de fonction ou de précalculer le résultat. Finalement, il décide d’utiliser la fonction compilée. Maintenant, la fonction compilée doit exécuter exactement l’algorithme exponentiel que vous avez décidé qu’il est impossible pour le compilateur de mettre en œuvre la mémorisation pour optimiser une fonction récursive (pensez à allouer du cache et à comprendre combien de valeurs conserver et gérer) eux entre les appels de fonction).