informatique (MP2I/MPI) · Chapitre 6 · Application directe du cours
Le coût de l'abstraction, mesuré
Types et structures de données abstraites · niveau 2
Énoncé
Le chapitre affirme qu'une abstraction n'est pas gratuite. La mesurer : comparer incrémentations d'un champ, faites directement, puis à travers une fonction définie dans un autre fichier.
Corrigé
/* compteur.h */
typedef struct { long v; } compteur;
void compteur_incr(compteur* c);
/* compteur.c -- UNITE DE COMPILATION SEPAREE */
void compteur_incr(compteur* c) { c->v = c->v + 1; }
gcc -O0 : acces direct 0,21 s par la fonction 0,38 s (x 1,8)
gcc -O2 : acces direct 0,000 s par la fonction 0,32 sLe premier résultat est celui qu'on attendait : sans optimisation, l'appel de fonction fait presque doubler le temps. C'est le coût de l'appel lui-même — empiler l'argument, sauter, revenir.
Le second est bien plus instructif. À -O2, la boucle directe disparaît : le compilateur prouve qu'elle équivaut à une seule affectation c.v = 300000000 et la remplace. La boucle qui passe par la fonction, elle, reste — parce que la fonction est dans une autre unité de compilation et que le compilateur, qui ne voit pas son corps, ne peut rien prouver.
Voilà donc le vrai coût de l'abstraction, et ce n'est pas l'appel : c'est la frontière qu'elle pose devant l'optimiseur. L'opacité qui empêche l'utilisateur de lire un champ empêche aussi le compilateur de raisonner à travers.
Ce qu'il ne faut surtout pas en conclure. Sur un compteur, seconde pour opérations, c'est une nanoseconde par opération : dérisoire devant la moindre erreur d'ordre de grandeur dans le choix d'une structure. Le chapitre le dit bien : le bon réflexe n'est pas « ne jamais abstraire », c'est « abstraire ce qui a plusieurs réalisations plausibles, ou ce dont l'invariant est fragile ». Et le dernier problème de ce chapitre montre ce qu'un mauvais choix de structure coûte : un facteur , pas .