Mesurez un système et donnez un intervalle de confiance

L’équipe data du festival a réécrit le script qui agrège chaque nuit les ventes de billets. Sur son portable, l’ancienne version a mis 5,1 s et la nouvelle 4,7 s. Victoire ? Relancez les deux scripts : vous obtiendrez peut-être 4,9 s et 5,0 s. Une mesure de performance n’est pas un nombre fixe : c’est une variable aléatoire, perturbée par le cache, le système d’exploitation, les autres programmes.

Ce chapitre vous apprend à mesurer proprement (avec quels outils, en perturbant le moins possible) puis à conclure honnêtement, avec un intervalle de confiance plutôt qu’un chiffre isolé.

Pourquoi et comment mesurer

On mesure un système pour :

• trouver les portions de code les plus utilisées (les « points chauds »), là où une optimisation rapportera le plus ;
• trouver les goulots (chapitre 3) ;
• régler le système (taille des caches, nombre de fils d’exécution) ;
• caractériser la charge : combien de requêtes, de quels types, à quels moments ;
• paramétrer et valider les modèles : les demandes de service $D_i$ des chapitres 2 à 5 viennent de mesures.

Trois stratégies

Stratégie	Principe	Exemple	Coût
Événementielle	compter les occurrences d’événements choisis	nombre d’accès disque, de défauts de cache	faible
Traçage	enregistrer un état horodaté à chaque événement	journal de chaque requête avec sa durée	élevé (volume de données)
Échantillonnage	relever l’état du système à intervalles réguliers	toutes les 10 ms, noter la fonction en cours d’exécution	réglable

L’échantillonnage est à la base du profilage statistique : si la fonction agreger apparaît dans 60 % des relevés, elle consomme environ 60 % du temps processeur. On ne voit pas tout, mais on perturbe peu.

La stratégie événementielle ne garde qu'un compteur, le traçage garde tout, l'échantillonnage garde un relevé toutes les 10 ms : ici, agreger apparaît dans 7 relevés sur 10, soit environ 70 % du temps.

Les outils

• L’instrumentation : ajouter dans le code des compteurs, des minuteurs ou des journaux. C’est le plus précis sur ce qu’on cible, mais cela modifie le programme mesuré.
• Le traçage système : strace (appels système), tcpdump (paquets réseau), DTrace ou eBPF.
• Les temps de processus : la commande time donne trois durées. Le temps réel (real, ou wall-clock) est celui de la montre ; le temps utilisateur (user) est le temps processeur passé dans votre code ; le temps système (sys) celui passé dans le noyau pour votre compte. Si real est bien supérieur à user + sys, le programme attend (disque, réseau, verrou).
• Le suivi en temps réel : top, ps, vmstat (mémoire, processeur), iostat (disques), mpstat (par cœur), netstat (réseau). C’est de là qu’on tire les utilisations $U_i$.
• Le profilage : gprof et perf pour le code compilé, cProfile en Python.

En TP, nous avons profilé un programme C avec les outils GNU. On le compile avec les options -pg -fprofile-arcs -ftest-coverage, on l’exécute une fois, puis gprof donne le profil plat (temps passé dans chaque fonction, nombre d’appels) et le graphe d’appels (qui appelle qui, et combien cela coûte), tandis que gcov compte le nombre d’exécutions de chaque ligne. C’est la méthode la plus directe pour repérer une boucle qui s’exécute beaucoup plus souvent que prévu.

Attention

Toute mesure perturbe ce qu’elle mesure. Un journal écrit à chaque requête consomme du disque ; un profileur ralentit les petites fonctions plus que les grosses. De plus, une horloge a une résolution finie : chronométrer une opération de 1 µs avec une horloge qui avance par pas de 1 ms n’a aucun sens. On chronomètre alors une boucle de nombreuses répétitions et on divise.

Mesurer proprement en Python

Voici un petit banc de mesure qui applique les règles de base : une horloge monotone et précise (time.perf_counter), une phase de chauffe dont on jette les résultats, puis plusieurs répétitions.

import csv
import io
import random
import time

# Données de test inventées : 200 000 ventes (identifiant, prix, catégorie)
random.seed(0)
ventes = "\n".join(f"{i},{random.randint(10, 80)},{random.choice('ABC')}"
                   for i in range(200_000))

def agreger():
    """Chiffre d'affaires total à partir du CSV."""
    return sum(int(ligne[1]) for ligne in csv.reader(io.StringIO(ventes)))

def mesurer(fonction, repetitions=10, chauffe=2):
    for _ in range(chauffe):                 # caches, allocations : résultats jetés
        fonction()
    temps = []
    for _ in range(repetitions):
        debut = time.perf_counter()
        fonction()
        temps.append(time.perf_counter() - debut)
    return temps

temps = mesurer(agreger)
print([round(t, 3) for t in temps])

Lancez-le deux fois : les valeurs changent. C’est normal, et c’est justement ce qu’il faut quantifier.

Une mesure est une variable aléatoire

On répète donc la mesure $n$ fois, dans les mêmes conditions, et on obtient des valeurs $x_1, \dots, x_n$. La moyenne $\bar{x}$ estime la vraie moyenne $\mu$ (inconnue), mais avec une incertitude. L’intervalle de confiance (IC) à 95 % quantifie cette incertitude :

$$\bar{x} \pm t_{1 - \alpha/2 \,;\, n - 1} \, \frac{s}{\sqrt{n}}$$

• $\bar{x}$ est la moyenne des $n$ mesures, $s$ leur écart type (calculé avec $n - 1$) ;
• $\alpha = 0{,}05$ pour un niveau de confiance de 95 % ;
• $t_{1 - \alpha/2 \,;\, n - 1}$ est le quantile de la loi de Student à $n - 1$ degrés de liberté (2,262 pour $n = 10$, et il tend vers 1,96 quand $n$ grandit).

Cet intervalle suppose des mesures indépendantes et une moyenne à peu près normale, ce qui est raisonnable à partir d’une dizaine de mesures si leur distribution n’est pas trop asymétrique. Le cours de Statistiques détaille sa construction.

Exemple

Dix exécutions du script d’agrégation donnent (en secondes) : 2,31 ; 2,45 ; 2,28 ; 2,52 ; 2,39 ; 2,34 ; 2,61 ; 2,30 ; 2,42 ; 2,38.

• Moyenne : $\bar{x} = 2{,}40$ s ; écart type : $s \approx 0{,}104$ s.
• Demi-largeur : $2{,}262 \times 0{,}104/\sqrt{10} \approx 0{,}075$ s.
• IC à 95 % : $[2{,}325 \, ; \, 2{,}475]$ s, soit une précision d’environ ±3,1 %.

L'intervalle de confiance porte sur la moyenne, pas sur les mesures : il est bien plus étroit que leur dispersion, et il se resserre encore quand on ajoute des mesures.

import statistics
from scipy import stats

def intervalle(x, niveau=0.95):
    n, m, s = len(x), statistics.mean(x), statistics.stdev(x)
    demi = stats.t.ppf((1 + niveau) / 2, n - 1) * s / n ** 0.5
    return m - demi, m + demi

mesures = [2.31, 2.45, 2.28, 2.52, 2.39, 2.34, 2.61, 2.30, 2.42, 2.38]
print(intervalle(mesures))    # environ (2.325, 2.475)

Combien de répétitions ?

On veut souvent une précision relative donnée : « la moyenne à ±$r$ % près ». En partant d’une première série de mesures qui donne $\bar{x}$ et $s$, et en approchant le quantile par celui de la loi normale $z$ (1,96 à 95 %), on trouve :

$$n \approx \left( \frac{100 \, z \, s}{r \, \bar{x}} \right)^2$$

Pour le script d’agrégation, une précision de ±2 % demande $n \approx (100 \times 1{,}96 \times 0{,}104/(2 \times 2{,}40))^2 \approx 18{,}2$, soit 19 mesures ; une précision de ±1 % en demande environ 73. Diviser l’incertitude par deux coûte quatre fois plus de mesures.

La précision s'améliore en 1/√n : passer de ±2 % à ±1 % fait passer de 19 à 73 mesures. Aux petits n, le quantile de Student élargit un peu l'intervalle.

À retenir

Une mesure se rapporte avec son intervalle de confiance : $\bar{x} \pm t \, s/\sqrt{n}$. La largeur de l’intervalle décroît en $1/\sqrt{n}$, et le nombre de répétitions se choisit à partir de la précision voulue, pas au hasard.

Comparer deux systèmes

Revenons à la question de départ : la nouvelle version du script est-elle plus rapide ? On a mesuré les deux versions sur les mêmes huit fichiers de ventes, de tailles différentes (en secondes) :

Fichier	1	2	3	4	5	6	7	8
Ancienne version	5,2	3,1	8,4	2,2	6,7	4,0	7,5	3,6
Nouvelle version	4,8	3,0	7,6	2,3	6,1	3,7	6,9	3,5

Première idée, fausse : calculer un IC pour chaque version et regarder s’ils se chevauchent. On obtient $5{,}09 \pm 1{,}87$ s pour l’ancienne et $4{,}74 \pm 1{,}62$ s pour la nouvelle. Les intervalles se chevauchent largement : on serait tenté de dire « pas de différence ».

La bonne méthode : les mesures sont appariées (même fichier, deux versions). On calcule donc la différence fichier par fichier : 0,4 ; 0,1 ; 0,8 ; −0,1 ; 0,6 ; 0,3 ; 0,6 ; 0,1. Leur moyenne vaut 0,35 s et leur écart type 0,307 s. Avec $t_{0{,}975 \,;\, 7} = 2{,}365$, l’IC de la différence est $0{,}35 \pm 2{,}365 \times 0{,}307/\sqrt{8} = 0{,}35 \pm 0{,}257$, soit $[0{,}093 \, ; \, 0{,}607]$ s.

L’intervalle ne contient pas 0 : la nouvelle version est significativement plus rapide, d’environ 0,35 s par fichier. Pourquoi les deux méthodes divergent-elles ? Parce que l’essentiel de la variabilité vient de la taille des fichiers (de 2 à 8 s), pas des versions. L’appariement élimine cette variabilité commune et ne garde que l’effet de la version.

Séparément, la variabilité entre fichiers (de 2 à 8 s) noie l'effet de la version. Apparier les mesures fichier par fichier élimine cette variabilité : l'intervalle de la différence exclut 0.

Piège

Conclure « pas de différence » parce que deux intervalles de confiance se chevauchent. Des IC qui ne se chevauchent pas indiquent bien une différence, mais l’inverse est faux. Pour comparer deux systèmes, calculez l’IC de la différence (apparié si les deux systèmes ont subi les mêmes charges) : s’il contient 0, la différence n’est pas significative ; sinon, elle l’est.

En entretien

« Je ne compare jamais deux temps d’exécution isolés. Je répète les mesures après une chauffe, je donne un intervalle de confiance, et pour comparer deux versions je les passe sur les mêmes entrées et je calcule l’intervalle de confiance de la différence appariée : s’il exclut zéro, l’amélioration est réelle. »

En résumé

• On mesure pour trouver les points chauds et les goulots, régler, caractériser la charge et calibrer les modèles.
• Trois stratégies : événementielle (compter), traçage (tout enregistrer), échantillonnage (relever périodiquement, base du profilage).
• Outils : instrumentation, traçage système, temps real/user/sys, vmstat et iostat, profileurs (gprof, gcov, perf, cProfile). Toute mesure perturbe le système et a une résolution limitée.
• Une mesure est une variable aléatoire : on fait une chauffe, on répète, et on donne l’IC $\bar{x} \pm t \, s/\sqrt{n}$.
• Le nombre de répétitions pour une précision de $r$ % : $n \approx (100 z s/(r \bar{x}))^2$.
• Pour comparer deux systèmes, on calcule l’IC de la différence, apparié quand c’est possible ; le chevauchement des IC ne suffit pas à conclure.

Exercices

Exercice · Lire la commande time

facile

La commande time ./export affiche : real 12,4 s, user 3,1 s, sys 0,6 s. Que pouvez-vous en déduire sur le programme ? Quelle ressource faut-il examiner en priorité ?

Voir la solution

Le programme n’utilise le processeur que $3{,}1 + 0{,}6 = 3{,}7$ s sur 12,4 s de temps réel. Pendant les 8,7 s restantes, il attend : des entrées-sorties disque, le réseau, un verrou ou un autre processus. Optimiser le code de calcul ne ferait gagner qu’une partie des 3,7 s. Il faut examiner en priorité les entrées-sorties, par exemple avec iostat (disque) ou strace (quels appels système bloquent).

En code

Python

import time

real, user, sys_ = 12.4, 3.1, 0.6               # sortie de `time ./export` (s)
cpu = user + sys_
print(round(cpu, 1), round(real - cpu, 1), f"{cpu / real:.0%}")   # 3.7  8.7  30%

# Reproduire le symptôme : un programme qui calcule un peu puis attend une E/S
def export():
    sum(i * i for i in range(2_000_000))         # calcul (temps processeur)
    time.sleep(1.0)                              # attente simulée (disque, réseau…)

debut_reel, debut_cpu = time.perf_counter(), time.process_time()
export()
print(f"real {time.perf_counter() - debut_reel:.2f} s, "
      f"user+sys {time.process_time() - debut_cpu:.2f} s")
# real 1.09 s, user+sys 0.09 s (valeurs variables) : real >> user + sys, le programme attend

R

reel <- 12.4; user <- 3.1; sys <- 0.6           # sortie de `time ./export` (s)
cpu <- user + sys
c(cpu, reel - cpu, cpu / reel)                  # 3.7  8.7  0.30

# Reproduire le symptôme : un programme qui calcule un peu puis attend une E/S
export <- function() {
  sum(as.numeric(1:5e6)^2)                      # calcul (temps processeur)
  Sys.sleep(1)                                  # attente simulée (disque, réseau…)
}
system.time(export())
# utilisateur     système      écoulé
#         0.03        0.00        1.03   (valeurs variables : écoulé >> utilisateur + système)

Exercice · Un intervalle de confiance

moyen

Huit mesures du temps de démarrage d’un conteneur donnent (en secondes) : 1,8 ; 2,1 ; 1,9 ; 2,4 ; 2,0 ; 1,7 ; 2,2 ; 1,9.

1. Calculez l’IC à 95 % de la moyenne ($t_{0{,}975 \,;\, 7} = 2{,}365$).
2. Combien de mesures faudrait-il pour une précision de ±2 % ?

Voir la solution

1. Somme : 16,0, donc $\bar{x} = 2{,}0$ s. Écarts : −0,2 ; 0,1 ; −0,1 ; 0,4 ; 0 ; −0,3 ; 0,2 ; −0,1. Somme des carrés : 0,04 + 0,01 + 0,01 + 0,16 + 0 + 0,09 + 0,04 + 0,01 = 0,36. Écart type : $s = \sqrt{0{,}36/7} \approx 0{,}227$ s. Demi-largeur : $2{,}365 \times 0{,}227/\sqrt{8} \approx 0{,}190$ s. IC : $[1{,}81 \, ; \, 2{,}19]$ s, soit environ ±9,5 %.
2. $n \approx (100 \times 1{,}96 \times 0{,}227/(2 \times 2{,}0))^2 \approx 11{,}1^2 \approx 124$. Il faudrait environ 124 mesures, soit quinze fois plus.

En code

Python

import numpy as np
from scipy import stats

x = np.array([1.8, 2.1, 1.9, 2.4, 2.0, 1.7, 2.2, 1.9])     # démarrages (s)
n, m, s = len(x), x.mean(), x.std(ddof=1)
demi = stats.t.ppf(0.975, n - 1) * s / np.sqrt(n)
print(round(m, 2), round(s, 3), round(demi, 3))           # 2.0 0.227 0.19
print(round(m - demi, 2), round(m + demi, 2), f"±{demi / m:.1%}")   # 1.81 2.19 ±9.5%

r = 2                                                      # précision voulue (%)
n_requis = (100 * 1.96 * s / (r * m)) ** 2
print(round(n_requis, 1))                                  # 123.5, soit environ 124 mesures

R

x <- c(1.8, 2.1, 1.9, 2.4, 2.0, 1.7, 2.2, 1.9)           # démarrages (s)
n <- length(x); m <- mean(x); s <- sd(x)
demi <- qt(0.975, n - 1) * s / sqrt(n)
c(m, s, demi)                                             # 2  0.227  0.190
t.test(x)$conf.int                                        # 1.81  2.19

r <- 2                                                    # précision voulue (%)
(100 * 1.96 * s / (r * m))^2                              # 123.5, soit environ 124 mesures

Exercice · Apparié ou non ?

difficile

On compare deux moteurs de requêtes sur cinq requêtes types. Temps (en ms) du moteur A : 120, 340, 85, 510, 230. Temps du moteur B : 112, 322, 83, 489, 221.

1. En calculant un IC à 95 % pour chaque moteur séparément ($t_{0{,}975 \,;\, 4} = 2{,}776$), peut-on conclure ?
2. Faites l’analyse appariée. Que concluez-vous ?

Voir la solution

1. Moteur A : $\bar{x}_A = 257$ ms, $s_A \approx 173{,}2$ ms, demi-largeur $\approx 215{,}0$ ms. Moteur B : $\bar{x}_B = 245{,}4$ ms, $s_B \approx 165{,}8$ ms, demi-largeur $\approx 205{,}8$ ms. Les intervalles se chevauchent presque entièrement : cette méthode ne permet pas de conclure.
2. Différences A − B : 8, 18, 2, 21, 9 ms. Moyenne 11,6 ms, écart type $\approx 7{,}77$ ms, demi-largeur $2{,}776 \times 7{,}77/\sqrt{5} \approx 9{,}64$ ms. IC de la différence : $[1{,}96 \, ; \, 21{,}24]$ ms. Il ne contient pas 0 : B est significativement plus rapide, d’environ 12 ms par requête (soit 2 à 7 % selon la requête). La variabilité entre requêtes (de 85 à 510 ms) masquait cet écart dans l’analyse non appariée.

En code

Python

import numpy as np
from scipy import stats

A = np.array([120, 340, 85, 510, 230])        # moteur A (ms)
B = np.array([112, 322, 83, 489, 221])        # moteur B (ms)

def ic(x):
    """Intervalle de confiance à 95 % de la moyenne."""
    demi = stats.t.ppf(0.975, len(x) - 1) * x.std(ddof=1) / np.sqrt(len(x))
    return float(round(x.mean() - demi, 1)), float(round(x.mean() + demi, 1))

print(ic(A), ic(B))       # (42.0, 472.0) (39.5, 451.3) : chevauchement complet
print(ic(A - B))          # (2.0, 21.2) : ne contient pas 0
print(stats.ttest_rel(A, B).pvalue)           # 0.029 : test apparié significatif

R

A <- c(120, 340, 85, 510, 230)                # moteur A (ms)
B <- c(112, 322, 83, 489, 221)                # moteur B (ms)

t.test(A)$conf.int                            # 42.0  472.0
t.test(B)$conf.int                            # 39.5  451.3 : chevauchement complet
apparie <- t.test(A, B, paired = TRUE)
apparie$conf.int                              # 2.0  21.2 : ne contient pas 0
apparie$p.value                               # 0.029