C/C++ offre-t-il une garantie de temps d'exécution minimal ?

Question

Pourquoi les compilateurs semblent-ils être polis envers les boucles qui ne font rien et ne les éliminent pas ?

La norme C exige-t-elle que les boucles prennent du temps ?

Exemple, le code suivant :

void foo(void) {
    while(1) {
        for(int k = 0; k < 1000000000; ++k);
        printf("Foo\n");
    }
}

fonctionne plus lentement que celui-ci :

void foo(void) {
    while(1) {
        for(int k = 0; k < 1000; ++k);
        printf("Foo\n");
    }
}

même avec -O3 niveau d'optimisation. Je m'attendrais à ce que la suppression des boucles vides soit autorisée et donc à ce que la vitesse soit la même pour les deux codes.

Le "temps passé" est-il un effet secondaire qui doit être préservé par un compilateur ?

Answer 1

Non, le temps passé n'est pas considéré comme un comportement observable protégé par la règle "comme si" :

[C++14: 1.8/5]: Une implémentation conforme exécutant un programme bien formé doit produire le même comportement observable que l'une des exécutions possibles de l'instance correspondante de la machine abstraite avec le même programme et la même entrée. Toutefois, si une telle exécution contient une opération non définie, la présente Norme internationale n'impose aucune exigence à la mise en œuvre qui exécute ce programme avec cette entrée (pas même en ce qui concerne les opérations précédant la première opération non définie).

[C++14: 1.5/8]: Les exigences minimales imposées à une mise en œuvre conforme sont les suivantes :

• L'accès aux objets volatils est évalué strictement selon les règles de la machine abstraite.
• À la fin du programme, toutes les données écrites dans les fichiers doivent être identiques à l'un des résultats possibles que l'exécution du programme selon la sémantique abstraite aurait produit.
• La dynamique d'entrée et de sortie des dispositifs interactifs doit se dérouler de manière à ce que la sortie de l'invite soit effectivement délivrée avant qu'un programme n'attende l'entrée. Ce qui constitue un dispositif interactif est défini par l'implémentation.

L'ensemble de ces éléments est désigné sous le nom de comportement observable du programme. [ Note : Des correspondances plus strictes entre la sémantique abstraite et la sémantique réelle peuvent être définies par chaque mise en œuvre. -note de fin ]

Ces boucles peuvent être légalement optimisées et, en effet, il y a des scénarios dans lesquels la norme fait de l'utilisation de l'eau une priorité. délibéré tente d'en faciliter l'accès :

[C++14: 1.10/24]: L'implémentation peut supposer qu'un thread effectuera finalement l'une des opérations suivantes :

• résilier,
• faire un appel à une fonction d'E/S de la bibliothèque,
• accéder à un objet volatil ou le modifier, ou
• effectuer une opération de synchronisation ou une opération atomique.

[ Note : Il s'agit de permettre des transformations du compilateur telles que la suppression des boucles vides, même lorsque la terminaison ne peut pas être prouvée. -note de fin ]

Votre compilateur peut en fait être "poli" en remarquant que l'intention de la boucle en ces semble être de ralentir l'émission de textes répétés :)

Answer 2

Vous n'avez pas précisé le compilateur, mais supposons qu'il s'agit de gcc .

gcc fait pas supprimer les boucles vides, du moins pas selon l'approche de la la documentation . Il contient le texte suivant :

Historiquement, GCC n'a pas supprimé les boucles "vides" en partant du principe que la raison la plus probable pour laquelle vous en mettriez une dans un programme est d'avoir un délai, donc les supprimer ne rendra pas les programmes réels plus rapides.

Toutefois, il peut supprimer les boucles vides si elles sont "vidées" par l'optimiseur, c'est-à-dire si la boucle contient du code que l'optimiseur peut déplacer en dehors de la boucle, et que la boucle résultante est vide.

La documentation n'indique pas clairement si c'est toujours le cas dans la version la plus récente. Le manuel mentionne "historiquement" sans préciser pourquoi. Si vous mettez à jour votre question avec des informations sur votre plateforme et votre compilateur exacts, peut-être qu'une meilleure réponse pourra être donnée.

Answer 3

Il n'y a pas de temps d'exécution minimal pour un exécutable C ou C++, car le temps d'exécution dépend de nombreux aspects spécifiques à la plate-forme, tels que

1. Fréquence d'horloge du processeur.
2. Cycles d'horloge par instruction.
3. Optimisation de l'exécution du processeur interne.
4. Interruptions.
5. Jeu d'instructions / capacités du processeur.

Certains processeurs prennent en charge la multiplication, d'autres non. Les processeurs qui ne prennent pas en charge la multiplication mettront plus de temps à exécuter un programme qu'un processus qui dispose d'instructions de multiplication. Il en va de même pour la virgule flottante.

La vitesse de fonctionnement interne d'un processeur varie. Il existe une unité de mesure commune appelée "cycle d'horloge". La plupart des fournisseurs de processeurs spécifient la durée d'une instruction en cycles d'horloge. Cette mesure peut s'avérer difficile en raison d'un support interne, tel que la gestion de la mémoire cache.

Certains processeurs sont dotés d'une logique qui permet d'optimiser l'exécution des instructions ou des schémas d'instructions. L'une de ces optimisations est prédiction des branches .

De nombreuses plates-formes disposent d'interruptions. Par exemple, il peut y avoir une interruption "system tick" qui permet au système d'exploitation de savoir quand passer l'exécution à un autre programme. Certaines interruptions ne sont pas aussi périodiques, par exemple lorsque des entrées/sorties se produisent. Un temps d'exécution minimum ne peut être garanti lorsque le programme est interrompu.

La fixation d'un temps d'exécution minimum aurait des conséquences néfastes sur la portabilité des langages C et C++. Certaines plates-formes voudraient exécuter le code plus rapidement que le temps minimum. D'autres plateformes pourraient ne pas être en mesure d'atteindre un temps d'exécution minimum (mais elles pourraient bénéficier d'un langage de haut niveau comme le C).

Par ailleurs, comment le temps serait-il mesuré ?

Le temps d'exécution minimal s'applique-t-il aux boucles de temporisation ou à l'interrogation ?

Answer 4

Non, il n'y a pas de garantie : (citation de N1570, 5.1.2.3 Exécution du programme )

1 Les descriptions sémantiques de la présente Norme internationale décrivent le comportement d'une machine abstraite dans laquelle les questions d'optimisation ne sont pas pertinentes.

Quoi qu'il en soit, la norme C ne spécifie que le comportement de votre programme lorsqu'il est exécuté sur une machine abstraite, qui peut avoir une mémoire et/ou des unités centrales infinies.