Systèmes d'exploitation par l'exemple/Travail pratique/Performance

Début de la boite de navigation du travail pratique

But de ce TP

Parfois, la première intuition n'est pas toujours la bonne. Les performances d'un processus sont influencées par de nombreux facteurs. Les codes suivant illustrent différents points.

Exemple 1: Synchronisations implicites entre processus

Le premier exemple compare l'exécution de deux versions d'une fonction d'un petit programme C. La deuxième version est beaucoup plus verbeuse, et effectue de nombreux printf. Créer un fichier fibo.c contenant le code suivant.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

long long int fibo(int n) {
    if (n < 2)
	  return n;

    return fibo(n-1) + fibo(n-2);
}

long long int fibo_printf(int n) {
    if (n < 2)
	  return n;

    long long int val = fibo_printf(n-1) + fibo_printf(n-2);
    printf("%lld\n", val);

    return val;
}

int main(int argc, char *argv[]) {
    int n=20;
    if (argc == 2)
	n = atoi(argv[1]);
    
    struct timespec debut, milieu, fin;

    clock_gettime(CLOCK_REALTIME, & debut);
    long long int res = fibo(n);
    clock_gettime(CLOCK_REALTIME, & milieu);
    long long int res_printf = fibo_printf(n);
    clock_gettime(CLOCK_REALTIME, & fin);

    long long int delta = (milieu.tv_sec - debut.tv_sec)* 1000000000LL
	+ (milieu.tv_nsec - debut.tv_nsec);
    long long int delta_printf = (fin.tv_sec - milieu.tv_sec)* 1000000000LL
	+ (fin.tv_nsec - milieu.tv_nsec);

    long double ratio = delta_printf / (long double) delta;
    
    fprintf(stderr,
	    "c %d valeurs: %lld %lld en %lld ns et %lld ns (ratio %Lg)\n",
	    n, res, res_printf, delta, delta_printf, ratio);
}

Les consignes

1. Compiler (avec optimisation, -O3) et lancer le programme ./fibo.
2. Exécuter le programme. Il devrait afficher que l'exécution de la version avec printf est beaucoup plus lente (plusieurs centaines ou plusieurs milliers de fois plus lente).
3. Vous pouvez essayer la même expérience avec d'autres langages, Vous devriez obtenir des résultats similaires pour la performance avec le printf et de grosses variations sur la performance sans printf, suivant les langages, mais toujours bien meilleures.

Pourquoi la version avec un printf est-elle plus lente ?

Quelques hypothèses ?

1. printf est innocent. Le coupable est ailleurs !
2. appeler une fonction supplémentaire (ici printf) dans un code coûte cher. (fibo ne fait qu'une addition)
3. L'interprétation du format "%d.." coute cher.
4. Appeler le système pour faire l'entrée-sortie coûte cher.

Solution

Printf et les appels systèmes sont innocents ! Enfin, à 90% innocents. Et c'est facile à prouver en redirigeant la sortie du processus vers /dev/null.

$ gcc -O3 -o fibo fibo.c -g -Wall -Wextra -fanalyzer
$ ./fibo
  ... les affichages des printf ...
c 20 valeurs: 6765 6765 en 32087 ns et 13649700 ns (ratio 425.397)
$ ./fibo > /dev/null
c 20 valeurs: 6765 6765 en 29301 ns et 1313784 ns (ratio 44.8375)

Dans les deux exécutions, il y a toujours les mêmes appels au système et le même nombre de printf.

C'est le terminal qui n'arrive pas à suivre le flot d'information à afficher. Afficher ses informations (calculs des fontes, déplacement des écritures, etc.) est bien plus couteux que de faire une addition ou le printf d'une ligne. La communication entre fibo et le terminal se fait au travers d'un pseudo-fichier qui sert de tampon (ici un TTY), qui finit par être saturé, votre mémoire n'étant pas infinie. Le programme fibo est donc stoppé temporairement par le système lorsqu'il essaye d'écrire dans le tampon saturé pour laisser le temps au terminal de vider un peu le tampon intermédiaire.

Le problème de performance est donc lié à la synchronisation (implicite) de l'affichage entre le fibo et votre terminal.

 

Exemple 2: Initialisation de la mémoire dans un programme en faisant une utilisation creuse

Le deuxième exemple compare l'exécution de plusieurs versions d'un petit programme dynamique C. Cet exemple provient d'un talk de la conférence ROADEF 2022 Is there any O(2^n) algorithm you OS can run in almost no time?, Daniel Cosmin Porumbel, CNAM, Roadef 2022, Lyon.

// Cet exemple provient d'un talk de ROADEF 2022
// Is there any O(2^n) algorithm you OS can run in almost no time?
// - Daniel Cosmin Porumbel, CNAM, Roadef 2022, Lyon.

// Tests réalisés avec g++ 15.2.0, glibc 2.41
// rapide: quelques millisecondes
// lent: 1 seconde
// très lent: 4 secondes

// compilation
// g++ -std=gnu++23 dp.cpp -o dp
// g++ -std=gnu++23 -O3 dp.cpp -o dpO3
// g++ -std=gnu++23 -DCPPVAR_VECTOR dp.cpp -o dpvec
// g++ -std=gnu++23 -DCPPVAR_VALARRAY dp.cpp -o dpval

// execution
// /usr/bin/time ./dp 0   # puis 1, 2, 3, 4
// /usr/bin/time ./dpO3 0   # puis 1, 2, 3, 4
// /usr/bin/time ./dpvec 0
// /usr/bin/time ./dpval 0

#include <cassert>
#include <cstdlib>
#include <cstring>
#include <print>
#include <valarray>
#include <vector>
using namespace std;

constexpr int n = 30;
constexpr int z = (1 << n) + 1;

int main(int argc, char *argv[]) {
  int cvariante = 0;
  assert(argc == 2);
  cvariante = atoi(argv[1]);

#ifndef CPPVAR_VECTOR
#ifndef CPPVAR_VALARRAY
  int *tab = nullptr;
  switch (cvariante) {
  case 0: // tres lent si compilation sans optimisation
    tab = (int *)malloc(sizeof(int[z])); // lent !
    for (int i = 0; i < z; i++)
      tab[i] = 0;
    break;
  case 1: // lent si  compilation sans optimisation
    tab = (int *)malloc(sizeof(int[z])); // lent !
    memset(tab, 0, sizeof(int[z]));
    break;
  case 2: // très lent si compilation sans optimisation
    tab = new int[z];
    for (int i = 0; i < z; i++)
      tab[i] = 0;
    break;
  case 3: // toujours rapide
    tab = new int[z];
    break;
  case 4: // toujours rapide
    tab = static_cast<int *>(calloc(z, sizeof(int)));
    break;
  default:
      assert(0);
  }
#endif
#endif

#ifdef CPPVAR_VECTOR
  vector<int> tab(z); // très lent sans optimisation, lent avec
#endif

#ifdef CPPVAR_VALARRAY
  valarray<int> tab; //  très lent sans optimisation, lent avec
  tab.resize(z);
#endif

  for (int i = 0; i < n; i++)
    if (tab[1 << (i + 1)] < 7 + tab[1 << i])
      tab[1 << (i + 1)] = 7 + tab[1 << i];
  println("{}", tab[z - 1]); // always 7*n: (n == 29) => affiche 203
}

Les consignes

Compiler (avec et sans optimisation, -O3) et lancer les programmes ./dp... en mesurant leur temps d'exécution

# compilation
$ g++ -std=gnu++23 dp.cpp -o dp
$ g++ -std=gnu++23 -O3 dp.cpp -o dpO3
$ g++ -std=gnu++23 -DCPPVAR_VECTOR dp.cpp -o dpvec
$ g++ -std=gnu++23 -DCPPVAR_VALARRAY dp.cpp -o dpval

# execution
$ /usr/bin/time ./dp 0   # puis 1, 2, 3, 4
$ /usr/bin/time ./dpO3 0   # puis 1, 2, 3, 4
$ /usr/bin/time ./dpvec 0
$ /usr/bin/time ./dpval 0

Le point important à observer est le temps d'exécution à chaque cas. Le programme dynamique a une utilisation sporadique de la mémoire. Il ne lit et modifie que très peu de données dans un grand tableau/vecteur/valarray.

L'affichage de time donne aussi beaucoup d'information sur la mémorie (taille max, page fault mineurs et majeurs).

Pourquoi existe-t-il des versions rapide (en ms), lentes (1 sec) et très lentes (plusieurs secondes)

Quelques hypothèses ?

1. C++ gère mal sa mémoire. Il vaut mieux utiliser C.
2. C gère mal sa mémoire. Il vaut mieux utiliser C++
3. Il faut initialiser toute la mémoire à 1 au lieu de 0.

Solution

Le point crucial pour la performance ici est le fait de NE PAS écrire les données qui doivent valoir 0. Dans le programme c'est la quasi-totalité des données.

Les mécanismes sous-jacents importants sont la mémoire virtuelle et la pagination. Pour rester simple, chaque processus s'exécute dans un espace de mémoire virtuelle, découpé en pages (4 kio ou 2Mio), des pages qui sont chargées de manière paresseuse dans la mémoire physique. GNU Linux utilise quelques pages pleines de 0 (en x86_64 une page de 4Kio et une de 2 Mio) pour toutes les grosses initialisations. Les lectures de pages initialisées à 0 lisent en fait une seule même page physique, quelque soit l'adresse. Ce n'est que lors d'une écriture que les pages correspondantes sont remplacées.

Comme GNU/Linux garantit pour les grandes allocations en mémoire qu'il fournit des zones initialisées à 0 et que g++ le sait, dans les versions optimisées, g++ supprime les écritures de 0 quand il le peut (les boucles, les memset à 0). Pour certaines versions (calloc, new sans sur-initialisation), g++ sait qu'il n'a rien à faire, même dans le cas non-optimisé.

En utilisant les structures de haut-niveau (vector, valarray), g++ n'arrive pas à supprimer ces initialisations.

La différence entre 'lent' et 'très lent' est dû probablement à l'usage d'instructions vectorielles pour l'initialisation à 0.

Questions pour le lecteur

1. est-ce que clang++ sur GNU/Linux a les mêmes comportements ?
2. Que se passe-t-il sous Windows ?
3. Que se passe-t-il sous WSL ?
4. Que se passe-t-il sous MacOS ?

 

Exemple 3: Comment écrire un produit scalaire performant de deux gros vecteurs ?

Si l'on veut obtenir un produit scalaire performant sur deux gros vecteurs aléatoires, que faut-il faire ?

Ce n'est pas la première question. La première question est que faut-il éviter pour ne pas être lent ?

Un produit scalaire n'a aucune variabilité dans son algorithme. Pour des vecteurs flottants de 300 millions d'éléments, il faut réaliser 300 millions de multiplications et 300 millions d'additions.

Les codes suivants illustrent certains de ces points.

Être lent 1: utiliser un langage de haut niveau inadapté (Python, Perl, Raku, ...)

Essayons de mesurer le temps d'exécution d'un code naïf en python. Ce qui est naïf dans ce code est de croire que les tableaux Python sont des tableaux (la structure de données).

Attention, sur ma machine, la troisième version plante (en sur-utilisation mémoire), mais pas avec toutes les versions de python. La compréhension de liste force probablement la création d'une copie intermédiaire supplémentaire.

La façon d'écrire un algorithme va avoir une influence sur l'efficacité de l'exécution, même pour ce problème, ou l'on effectue toujours juste 300 millions de multiplications et 300 millions d'additions.

import time
import random

def dotp_fonctionnel(a,b):
    return sum(aterm * bterm for aterm,bterm in zip(a, b))

def dotp_iteratif(a,b):
    somme = 0.0
    for i in range(len(a)):
        somme += a[i] * b[i]
    return somme

def dotp_iteratif_copie(a,b):
    return sum( [ a[i] * b[i] for i in range(len(a)) ] )


a = [ random.random() for i in range( 300000000 )]
b = [ random.random() for i in range( 300000000 )]

debut = time.time()
val = dotp_fonctionnel(a, b)
fin = time.time()

print("valeur= ", val)
print("temps fonctionnel= ", fin - debut, " s")

debut = time.time()
val = dotp_iteratif(a, b)
fin = time.time()

print("valeur= ", val)
print("temps itératif= ", fin - debut, " s")

debut = time.time()
val = dotp_iteratif_copie(a, b)
fin = time.time()

print("valeur= ", val)
print("temps itératif= ", fin - debut, " s")

Si le code est écrit dans un fichier dot_plain.py, cela donne l'exécution suivante (python 3.13)

$ python dot_plain.py 
valeur=  74997890.78630553
temps fonctionnel=  36.495516300201416  s
valeur=  74997890.78631526
temps itératif=  8.559763431549072  s
zsh: killed     python dot_plain.py

Solution

Utiliser une bibliothèque !

La bonne solution en Python, est de ne pas utiliser la structure du langage, mais une bibliothèque (Numpy) qui implémente des tableaux.

import numpy as np
import time

a = np.zeros(shape=(300000000,), dtype=float)
b = np.zeros(shape=(300000000,), dtype=float)

a = a + np.random.random(size=300000000)
b = b + np.random.random(size=300000000)



debut = time.time()
val = np.dot(a, b)
fin = time.time()

print("valeur= ", val)
print("temps= ", fin - debut, " s")

# to test
# a = np.add(a, np.random.random(size=300000000), dtype=float)
# b = np.add(b, np.random.random(size=300000000), dtype=float)

Mais le plus intéressant est de regarder comment.

$ /usr/bin/time python dot_numpy.py
valeur=  74993510.06512499
temps=  0.14528942108154297  s
7.20user 0.22system 0:03.27elapsed 227%CPU (0avgtext+0avgdata 4721892maxresident)k
680inputs+0outputs (3major+10700minor)pagefaults 0swaps

Le programme utilise 227% de CPU, c'est-à-dire qu'il s'exécute simultanément sur plusieurs cœurs ! L'exécution est parallèle.

 

Être lent 2: oublier de demander au compilateur de maximiser la performance

gcc cherche à maximiser la précision sur les calculs flottants, ce qui limite ses optimisations par défaut. Au minimum, pour gcc, l'option -O2 est à utiliser systématiquement. C'est le cas des distributions GNU/Linux pourtant conservatrices comme Debian. -O3 autorise gcc à interpréter votre code de manière plus libérale, ce qui pourrait changer les résultats dans les cas aux bords liés aux comportements indéfinis dans votre code.

Consignes

Compiler le code suivant en deux versions, une avec les optimisations -O3 -std=gnu23 -march=native -mtune=native et l'autre en ajoutant une option pour indiquer à gcc que c'est la vitesse et non la précision qui compte -ffast-math.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

float dotp(const int n, const float x [static n], const float y[static n]) {
  double v = 0.0;
  for (int i = 0; i < n; i++) {
    v += x[i] * y[i];
  }
  return v;
}

int main(int argc, char **argv) {
  constexpr int n = 300000256;

  float *x = aligned_alloc(512, sizeof(float[n]));
  float *y = aligned_alloc(512, sizeof(float[n]));

  assert(x);
  assert(y);
  srand48(123456); // fixation de la graine, les vecteurs sont toujours identiques
  for (int i = 0; i < n; i++) {
    x[i] = drand48();
    y[i] = drand48();
  }

  struct timespec debut, fin;
  clock_gettime(CLOCK_REALTIME, &debut);
  float v1 = dotp(n, x, y);
  clock_gettime(CLOCK_REALTIME, &fin);
  printf("for loop: calcul %f en %g s\n", v1,
         (fin.tv_sec - debut.tv_sec) +
             (fin.tv_nsec - debut.tv_nsec) / 1000000000.0);
}

Solution

Vous devriez obtenir un affichage des deux versions

$ gcc -O3 -std=gnu23 -march=native -mtune=native c_dotp_mini.c -o c_dotp_mini 
$ ./c_dotp_mini 
for loop: calcul 74991360.000000 en 0.285727 s
$ gcc -O3 -ffast-math -std=gnu23 -march=native -mtune=native c_dotp_mini.c -o c_dotp_mini_fastmath
$ ./c_dotp_mini_fastmath
for loop: calcul 74991360.000000 en 0.0982492 s

Un rapport 3 sur la vitesse. NB: clang semble moins conservateur par défaut que gcc sur ce point précis.

 

Être rapide: utiliser efficacement vos multi-cœurs

C propose des extensions permettant de faire une exécution parallèle d'un code, comme OpenMP. Le code est identique à la version précédente, en ajoutant une seule ligne et en comptant le lancement des threads.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

float dotp(const int n, const float x [static n], const float y[static n]) {
  double v = 0.0;
#pragma omp parallel for simd reduction(+ : v) schedule(guided, 1000000)  
  for (int i = 0; i < n; i++) {
    v += x[i] * y[i];
  }
  return v;
}

int main(int argc, char **argv) {
  constexpr int n = 300000256;

  float *x = aligned_alloc(512, sizeof(float[n]));
  float *y = aligned_alloc(512, sizeof(float[n]));

  assert(x);
  assert(y);
  srand48(123456); // fixation de la graine, les vecteurs sont toujours identiques
  for (int i = 0; i < n; i++) {
    x[i] = drand48();
    y[i] = drand48();
  }

  struct timespec debut, fin;
  clock_gettime(CLOCK_REALTIME, &debut);
  float v1 = dotp(n, x, y);
  clock_gettime(CLOCK_REALTIME, &fin);
  printf("for Openmp: calcul %f en %g s\n", v1,
         (fin.tv_sec - debut.tv_sec) +
             (fin.tv_nsec - debut.tv_nsec) / 1000000000.0);
}

Compiler et exécuter le code, en activant l'optimisation et OpenMP -fopenmp.

Solution

$ gcc -O3 -std=gnu23 -march=native -mtune=native -fopenmp c_dotp_mini_omp.c -o c_dotp_mini_omp
 ± ./c_dotp_mini_omp
for Openmp: calcul 74991360.000000 en 0.0723808 s

Il est à noter que pour ce produit scalaire, la performance est certes plus rapide que la version séquentielle de la question précédente, mais uniquement d'environ 20% sur la machine utilisée. Un produit scalaire demande une quantité de données importante par rapport aux calculs réalisés avec. Le goulot d'étranglement est plutôt la mémoire.

La performance est aussi 2 fois plus rapide que Numpy en Python dans la première question. Il y a un compromis entre le temps de développement et la performance finale.

Le compromis entre l'occupation des cœurs, l'énergie utilisée, le temps de développement et la performance est complexe.