Pourquoi cette boucle à retard commence-t-elle à s'exécuter plus rapidement après plusieurs itérations sans sommeil ?

Question

Pensez-y :

#include <time.h>
#include <unistd.h>
#include <iostream>
using namespace std;

const int times = 1000;
const int N = 100000;

void run() {
  for (int j = 0; j < N; j++) {
  }
}

int main() {
  clock_t main_start = clock();
  for (int i = 0; i < times; i++) {
    clock_t start = clock();
    run();
    cout << "cost: " << (clock() - start) / 1000.0 << " ms." << endl;
    //usleep(1000);
  }
  cout << "total cost: " << (clock() - main_start) / 1000.0 << " ms." << endl;
}

Voici l'exemple de code. Dans les 26 premières itérations de la boucle de chronométrage, la fonction run coûte environ 0,4 ms, mais le coût est ensuite réduit à 0,2 ms.

Lorsque le usleep est décommenté, la boucle à retard prend 0,4 ms pour toutes les exécutions, sans jamais s'accélérer. Pourquoi ?

Le code est compilé avec g++ -O0 (pas d'optimisation), donc la boucle de retard n'est pas optimisée. Il est exécuté sur Intel(R) Core(TM) i3-3220 CPU @ 3.30 GHz, avec 3.13.0-32-générique Ubuntu 14.04.1 LTS (Trusty Tahr).

Answer 1

Après 26 itérations, Linux fait passer le CPU à la vitesse d'horloge maximale, car votre processus utilise toute sa puissance. tranche de temps plusieurs fois de suite.

Si vous vérifiez avec des compteurs de performance plutôt qu'avec le temps d'horloge murale, vous verrez que les cycles d'horloge du noyau par boucle de retard sont restés constants, ce qui confirme qu'il s'agit simplement d'un effet de l'algorithme de l'horloge murale. DVFS (que tous les processeurs modernes utilisent pour fonctionner à une fréquence et une tension plus efficaces sur le plan énergétique la plupart du temps).

Si vous avez testé sur un Skylake avec le support du noyau pour le nouveau mode de gestion de l'énergie (où le matériel prend le contrôle total de la vitesse d'horloge) la montée en puissance serait beaucoup plus rapide.

Si vous le laissez fonctionner pendant un certain temps sur un Processeur Intel avec Turbo Vous verrez probablement le temps par itération augmenter à nouveau légèrement lorsque les limites thermiques exigeront que la vitesse d'horloge soit ramenée à la fréquence maximale soutenue. (Voir Pourquoi mon CPU n'arrive-t-il pas à maintenir des performances optimales en HPC ? pour en savoir plus sur le Turbo qui laisse le CPU fonctionner plus vite qu'il ne peut le supporter pour les charges de travail à haute puissance).

---

Présentation d'un usleep empêche Le gouverneur de fréquence du CPU de Linux d'augmenter la vitesse d'horloge, car le processus ne génère pas une charge de 100 % même à la fréquence minimale. (C'est-à-dire que l'heuristique du noyau décide que le CPU tourne suffisamment vite pour la charge de travail qui s'y exécute).

---

---

commentaires sur d'autres théories :

re : La théorie de David selon laquelle un changement de contexte potentiel de usleep pourrait polluer les caches : Ce n'est pas une mauvaise idée en général, mais cela n'aide pas à expliquer ce code.

La pollution du cache / TLB n'est pas du tout importante pour cette expérience. . Il n'y a pratiquement rien à l'intérieur de la fenêtre de timing qui touche la mémoire autre que la fin de la pile. La plupart du temps est passé dans une minuscule boucle (1 ligne de cache d'instruction) qui ne touche qu'une seule ligne de mémoire. int de la mémoire de la pile. Toute pollution potentielle du cache pendant usleep est une fraction minuscule du temps pour ce code (le code réel sera différent) !

Plus en détail pour x86 :

L'appel à clock() peut lui-même manquer de cache, mais un manque de code en cache retarde la mesure du temps de démarrage, au lieu de faire partie de ce qui est mesuré. Le deuxième appel à clock() ne sera presque jamais retardée, car elle devrait être encore chaude dans le cache.

El run peut se trouver dans une ligne de cache différente de celle de la fonction main (depuis que gcc marque main comme "froide", elle est donc moins optimisée et placée avec d'autres fonctions/données froides). Nous pouvons nous attendre à un ou deux manquements au cache d'instruction . Ils sont probablement toujours dans la même page 4k, cependant, alors main aura déclenché le manque potentiel de TLB avant d'entrer dans la région temporisée du programme.

gcc -O0 compilera le code de l'OP en quelque chose comme ceci (explorateur de compilateur Godbolt),filterAsm:(commentOnly:!t,directives:!t,intel:!t,labels:!t),version:3) : garder le compteur de boucle en mémoire sur la pile.

La boucle vide conserve le compteur de boucle dans la mémoire de la pile, de sorte que sur un ordinateur typique CPU Intel x86 la boucle s'exécute à une itération par ~6 cycles sur le CPU IvyBridge du PO, grâce à la latence de transfert de mémoire qui fait partie de l'architecture de l'ordinateur. add avec une destination mémoire (lecture-modification-écriture). 100k iterations * 6 cycles/iteration est de 600 000 cycles, ce qui domine la contribution d'au plus quelques manques de cache (~200 cycles chacun pour les manques de code-fetch qui empêchent l'émission d'autres instructions jusqu'à ce qu'ils soient résolus).

L'exécution en dehors de l'ordre et le store-forwarding devraient permettre de masquer le risque d'erreur de cache lors de l'accès à la pile (dans le cadre du processus d'exécution de l'ordre). call instruction).

Même si le compteur de boucle était conservé dans un registre, 100 000 cycles, c'est beaucoup.

Answer 2

Un appel à usleep peut ou non entraîner un changement de contexte. Si c'est le cas, cela prendra plus de temps que si ce n'est pas le cas.