J'ai appris les fonctions C ++ constexpr , et j'ai implémenté une fonction constexpr pour trouver le numéro Nth Fibonacci.
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
constexpr long long fibonacci(int num) {
if (num <= 2) return 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}
int main() {
auto start = clock();
long long num = fibonacci(70);
auto duration = (clock() - start) / (CLOCKS_PER_SEC / 1000.);
std::cout << num << "\n" << duration << std::endl;
}
Si je supprime l'identifiant constexpr de la fonction fibonacci () , alors fibonacci (70) prend un très long Em> temps pour évaluer (plus de 5 minutes). Lorsque je le garde tel quel, cependant, le programme se compile toujours dans les 3 secondes et imprime le résultat correct en moins de 0.1 millisecondes.
J'ai appris que Les fonctions constexpr sont évaluées au moment de la compilation , donc cela signifierait que fibonacci (70) est calculé par le compilateur en moins de 3 secondes! Cependant, il ne semble pas tout à fait vrai que le compilateur C ++ aurait de si meilleures performances de calcul que le code C ++.
Ma question est: le compilateur C ++ évalue-t-il réellement la fonction entre le moment où j'appuie sur la "construction "Le bouton et l'heure à laquelle la compilation se termine? Ou suis-je mal compris le mot clé constexpr ?
edit: ce programme a été compilé avec g ++ 7.5.0 avec - std = c + +17 .
4 Réponses :
Les fonctions constexpr n'ont pas d'effets secondaires et peuvent donc être mémorisés sans souci. Compte tenu de la disparité dans l'exécution, l'explication la plus simple est que le compilateur mémorise les fonctions constexpr pendant le temps de compilation. Cela signifie que fibonacci (n) n'est calculé qu'une seule fois pour chaque n , et tous les autres appels récursifs sont renvoyés d'une table de recherche.
Donc, essentiellement, le compilateur stocke les valeurs intermédiaires de fibonacci () et utilise essentiellement une programmation dynamique au lieu de la récursivité? Cela expliquerait certainement pourquoi le compilateur est tellement plus rapide que le programme lui-même, mais je n'ai jamais vu ce comportement mentionné auparavant. Est-ce mentionné quelque part dans la norme?
@ahskdjfk correct. C'est une optimisation que constexpr permet simplement à sa nature. Je ne crois pas que les compilateurs sont obligés pour faire cette optimisation, donc votre kilométrage peut varier.
C'est probablement un jeu sur la règle as-si . Le compilateur peut faire tout ce qu'il veut à votre code s'il pense qu'il sera plus rapide et ne change pas le comportement observable. Aucune raison, le compilateur ne peut pas le faire en interne lors du calcul du résultat d'une fonction constxepr . La question intéressante est de savoir si elle peut voir cette optimisation au moment de la compilation pour la fonction constexpr , pourquoi ne l'applique-t-elle pas la même chose à la version d'exécution?
@orlp: Comme je le mentionne dans les commentaires ci-dessus, différentes versions de GCC n'appliquent certainement pas cette optimisation (l'OP's 7.5, la version 10.2 la plus récente ne fait pas, du moins pas par défaut), Alors oui, certainement un cas variable de kilométrage.
Les fonctions constexpr n'ayant pas d'effets secondaires sont des nouvelles pour moi. Pourriez-vous pointer quelque part dans la norme qui nécessite cela? Il semble que cela soit implicite dans expr.const: 5.16 : "An L'expression E est une expression constante de base à moins que l'évaluation de E [...] évaluerait [...] une modification d'un objet [...] à moins qu'elle ne soit appliquée à une lveue non volatile de type littéral qui fait référence à un objet non volatile dont la durée de vie a commencé dans l'évaluation de E. " IIUC, cela exclut la modification des objets non locaux à l'expression constante, c'est-à-dire les effets secondaires
@ user4581301 - De nombreuses explications possibles pour expliquer pourquoi le compilateur "verrait" l'optimisation au moment de la compilation pour une fonction constexpr et non pour la "version d'exécution". constexpr permet au compilateur de supposer des choses mais doit faire l'analyse pour conclure ces choses pour la version "Runtime". Cette analyse peut ne pas être effectuée (elle peut être coûteuse), donc l'optimisation n'est pas effectuée. Inversement, un compilateur pourrait galoper à l'avance pour tenter d'évaluer une fonction constexpr jusqu'à ce qu'elle épuise la mémoire. La qualité de la mise en œuvre du compilateur dépend de beaucoup de choses.
Je ne serais pas satisfait de mon compilateur introduisant une table de hachage invisible, incontrôlable pour mémoriser mes fonctions lors de l'exécution. La mémoire au moment de la compilation est "bon marché", de sorte que la transformation semble raisonnable lors de l'évaluation de la constexpr.
@Alexreink Je ne vous dis rien de nouveau ici compte tenu de votre profil - les compilateurs introduisent beaucoup de données "invisibles et incontrôlables" dans votre programme, n'est-ce pas? Je préférerais une table de hachage à une pile incontrôlable à tout moment ;-).
@ Peter-ReinstateMonica Compile-Time L'évaluation a l'avantage de pouvoir s'assurer que c'est en fait un code d'exécution constant et donc mémorisable, et autrement simplement délégué à un code d'exécution non mémorisé.
@Deduplicator puisque le compilateur est si sûr au moment de la compilation, il pourrait bien compiler cela dans ;-).
@ Peter-Reinstatemonica prouvant que pour toutes les entrées (ou déterminez celles pour lesquelles il est vrai) est un tout autre jeu de balle pour démontrer que pour des valeurs spécifiques. Pour ne pas dire qu'il n'y a pas beaucoup de cas qui sont possibles.
@Deduplicator Oui Oui, mais je ne parlais que de ce programme ici, avec cet argument constant spécifique à temps de compilation. vous a dit que le compilateur est "capable de vous assurer que [le résultat] est en fait une constante"! Maintenant, n'essayez pas de se retirer. ;-)
Pour ajouter quelques détails à ce que les autres ont souligné: La fonction constexpr ne doit pas être calculée à l'exécution et l'un des paramètres qui peut l'affecter est -fConstexpr-OPS-Limit .
sur gcc 10.2.0, -fconstexpr-ops-limit = 1000000000 (1b) et fibonacci (40) entraîne une valeur pré-compilée, mais si vous Déposez la limite à 10000000 (10m) puis la fonction est calculée au moment de l'exécution. Si vous souhaitez vous assurer que la valeur est toujours calculée au moment de la compilation, vous devez marquer Long Long Num comme constexpr En plus du fibonacci fonction.
Remarque: L'exemple opposé serait une fonction non-Consexpr calculée au moment de la compilation (optimisée) et le marquer avec __ attribut__ ((const)) pourrait aider le compilateur à prendre une telle décision. Cependant, mon compilateur ne l'a pas optimisé.
Remarque: Si vous utilisez constexpr Long Long Num , cela garantit qu'il ne sera pas calculé au moment de l'exécution. Il ne garantit pas qu'il sera calculé au moment de la compilation; Il garantit simplement que lorsque le compilateur pourrait autrement se replier à l'évaluation de l'exécution, la compilation échoue à la place.
Dans G ++ 8.3.0, si vous utilisez constexpr dans ce cas, il calcule la valeur que vous utilisez et publie le résultat comme une constante. Ceci est même sans optimisations:
.file "constexpr.cc"
.text
.globl main
.type main, @function
main:
.LFB1:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl %edi, -20(%rbp)
movq %rsi, -32(%rbp)
movabsq $190392490709135, %rax
movq %rax, -8(%rbp)
movl $0, %eax
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE1:
.size main, .-main
.ident "GCC: (Debian 8.3.0-6) 8.3.0"
.section .note.GNU-stack,"",@progbits
//#include <iostream>
constexpr long long fibonacci(int num){
if(num <= 2){return 1;}
return fibonacci(num - 1) + fibonacci(num - 2);
}
int main(int argc, char** argv)
{
//double start = clock();
long long num = fibonacci(70);
//std::cout << num << std::endl;
//cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << endl;
return 0;
}
Je me demandais pourquoi il y avait une si grande différence entre le code et le compilateur en termes de temps d'exécution.
Il semble qu'il le calcule sans récursivité. Avec la récursivité est tout simplement trop lente.
Ce qui me surprend, c'est qu'il peut convertir une fonction récursive en une fonction itérative, même sans optimisation, au moment de la compilation. C'est du moins ce qu'il semble.
Comme déjà mentionné dans les commentaires ci-dessus est effectué dans l'exécution. Les compilateurs en ligne tuent simplement le programme de course en raison du délai d'expiration: https://gccc.godbolt.org/z / G8mvytf9h Si vous souhaitez évaluer la fonction pendant la compilation, ajoutez un autre CONSEXPR L'appel de fonction comme dans la question: #include <iostream>
template<int N> constexpr size_t fib = fib<N-1> + fib<N-2>;
template<> constexpr size_t fib<1> = 1;
template<> constexpr size_t fib<2> = 1;
int main() { std::cout << fib<70>; }
constexpr : consteval long long fibonacci(int num)
constexpr long long num = fibonacci(70);
Dans les deux cas, vous obtiendrez une erreur de compilation dans n'importe quel moderne compilateur en raison de "l'évaluation dépassant la limite des étapes" ou similaire, démo: https://gcc.godbolt.org/ Z / 9919G4STH
Une bonne alternative à la fonction récursive Fibonacci de calcul facile et très rapide dans les constantes de compilation est via le modèle constexpr :
long long num = fibonacci(70);
Quel compilateur? Godbolt a chronométré sur votre code avec GCC 10.2 et Clang 11.0 lorsqu'il est compilé avec
-std = c ++ 17(avec ou sans-o3). Les deux compilateurs ont décidé que leconstexprétait trop profondément récursif, l'a compilé pour calculer au moment de l'exécution, puis a chronométré au moment de l'exécution.La force brute Fibonacci est lente comme l'enfer. Le compilateur a trouvé une meilleure façon.
À une supposition - reconnaître une forme itérative équivalente de la récursivité, combinée à la mémoire. Mais, en fin de compte, cela dépendra de la qualité de la mise en œuvre du compilateur.
@Shadowranger tort. OP est droit - pas de délai avec
constexpr@Bloody: Soupir ... "Mauvais" implique qu'il y a une bonne réponse. J'ai deux exemples où il n'a pas compilé l'optimisation du temps ; Cela n'exclut pas la possibilité que d'autres compilateurs, drapeaux, etc. puissent fonctionner, mais l'OP doit être clair. Si j'ai fait
Long Long num = Fibonacci (70);devenezconstexpr Long Long Num = Fibonacci (70);pour forcer l'évaluation du temps de compilation, ils sont tous deux morts de se plaindre d'un excès récursivité. C'est pourquoi j'ai demandé comment l'OP avait compilé leur code; Je ne pense pas qu'ils se trompent, mais il faut reproduire leur résultat.@Bloody: Et je viens de vérifier.
g ++7.5 sur godbolt fait exactement ce que l'OP a dit,g ++10.2 ne fait pas. Apparemment, c'est une optimisation qui a été perdue dans le compilateur le plus récent (ou peut-être une limite configurable surconstexprRecursion qui par défaut est une valeur inférieure dans le compilateur plus récent), ce qui est utile à savoir.@Shadowranger en effet avec GCC 10.2 IT Timeouts avec constexpr (mais pas avec 9.2). Vous aviez raison, désolé pour une épithète impulsive.
(NitPick hors sujet: Si vous vous souciez des performances, vous n'utiliseriez pas
std :: endlpour forcer le rinçage inutile de coute entre les lignes, même lorsque la sortie est un tuyau.)