samedi 20 décembre 2014

Impact inattendu(?) sur les performances d'un programme. Vaz'y PAPI.

  • "Faire une mesure est relativement aisé. C'est quand on a obtenu la mesure que les emm... commencent." (Moi).
  • "Et j'aimerais bien savoir quand ils finissent!" (Re-moi) 
  • "Sans compter tous les emm... annexes."  (Toujours moi)
  • "Il y a beaucoup de mérite
    Sans compter les emmerdements.
    " (Extrait de "Qu’y a-t-il…?" de Boris Vian)

Indiquons

Soit un simple morceau de code qui cherche à exprimer la puissance de calcul d'un CPU, genre nombre d'instructions / de boucles  ou ce que vous voulez par secondes. Par exemple quelque chose qui ressemblerait aux calculs faits dans la procédure do_loop  utilisée dans Linux : CPU, core, HyperThread, mesures de temps d'exécution. De manière concrète, dans cet article, on a exécuté 4000 boucles (de 100000) en 10696 millisecondes, soit un indicateur de 4000/10,696 = 373,97 FauxPlat/sec(*) pour le processeur en question.

(*) Le FauxPlat/sec est une unité de puissance de CPU créée pour les besoins de ce billet. Le FauxPlat/sec est invariable : 1 FauxPlat/sec 2 FauxPlat/sec. Il n'y a pas d’abréviation officielle pour le FauxPlat/sec. FP/sec est prohibé en tant qu’abréviation de FauxPlat/sec. 

Blindons

Une fois écrit ce code, reste à s'assurer qu'il est exécuté dans des conditions relativement stables et protégées  des perturbations provoquées par l'exécution d'autres programmes. Le but : obtenir des valeurs  identiques ou raisonnablement proches pour des machines basées sur le même CPU. Ce qui devrait permettre (conditionnel dans un monde idéal) de comparer des machines...

Dans la mesure où la durée du calcul est relativement courte (~11 sec dans l'article cité), on peut se permettre d'exécuter ce calcul en utilisant une classe d'ordonnancement temps-réel (SCHED_FIFO) avec une priorité maximum. Pour limiter encore davantage les perturbations, l'utilisation de l'affinité processeur (sched_setaffinity) évitera de compter des coûts de migration CPU. Et comme les processeurs modernes sont de grands taquins et qu'ils ont la capacité de faire varier leur fréquence, on va aussi fixer la fréquence du processeur au maximum. (Euh, là, les bidouilles sont à découvrir vous-mêmes, à moins qu'elles ne soient livrées dans un billet ultérieur).

Ratons (pas laveurs)

Hmmm. Comme dit précédemment, la loi de Murphy indique que forcément non... Dans les faits, si vous pouvez (faire) réaliser ce type de calcul sur des centaines de machines, les variations relevées sur des machines de CPU identiques vont être surprenantes... de 1 à 3. Gloups. Pas systématique, la grosse majorité des résultats va varier dans une fourchette de disons 0 à 30%. Mais la masse de mesures joue contre vous et vous avez donc un nombre de mesures pour lesquellesvous ne savez pas justifier les variations.  Il peut arriver, expérience vécue*, qu'il faille changer la carte mère pour obtenir des résultats homogènes avec des CPUs identiques..

* euh? y'a des expériences pas vécues?

Piqué au vif soyons

Vous reprenez donc votre programme, et sur vos (quelques, car vous, vous n'avez pas accès à des centaines) machines, tentez de perturber ce calcul.
  • Essai n°1: Ajout d'une charge CPU importante sur le même processeur. Résultat : variation de 10% du nombre de FauxPlat/sec.
Regardez bien, ma sœur ;
Est-ce assez ? dites-moi ; n'y suis-je point encore? - Nenni. 
  • Essai n°2 : Ajout d'une charge CPU importante  faisant de nombreux accès mémoire pour perturber le cache L1. Résultat : variation de 20 % du nombre de FauxPlat/sec.
- M'y voici donc ?
- Point du tout.
  • Essai n° 3 : Ajout d'une charge CPU importante s'exécutant au même niveau de priorité temps-réel que le calcul de l'indicateur. Le calcul étant fait sur la mesure du temps CPU et non du temps mural... cela ne change rien, par ailleurs, il est relativement facile de prouver que cette situation ne semble pas être rencontrée sur vos machines de production...
M'y voilà ?
- Vous n'en approchez point.
Merci Mr Jean de La Fontaine.
  • Essai n°4 : Certes vous avez fixé la fréquence du processeur au maximum. Mais qui vous assure que cette fréquence n'est pas modifiée par un autre programme pendant vos exercices?  D'accord. Quand on fait varier la fréquence du simple au double, le nombre de FauxPlat/sec varie aussi du simple au double... Mmm Il y a là encore peu de chance que ce soit ce qui se passe sur vos machines de production...

10 wagons euh, divaguons

Fatigué, harassé, vous en êtes là et même un peu las de vos vaines et ridicules tentatives. Quand vous découvrez au hasard d'une errance webique la publication suivante (dont la lecture vous est vivement recommandée) : 

Producing Wrong Data Without Doing Anything Obviously Wrong!
Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, Peter F. Sweeney
ASLPOS09 

où il est exposé et démontré que des mesures de performances peuvent être sérieusement altérées par des éléments n'ayant rien à voir ni avec la choucroute ni avec le yaourt. Il est dit qu'un programme aussi simple que ceci :

static int i = 0, j = 0, k = 0;
int main() {
    int g = 0, inc = 1;
    for (; g < 65536; g++) {

        i += inc;
        j += inc;
        k += inc;
    }
    return 0;
}

peut voir ses temps d'exécution  sérieusement modifiés selon... la taille des variables d'environnement du programme. Le graphique suivant extrait de l'article montre une variation du nombre de cycles nécessaires pour la boucle en fonction de la taille des variables d'environnement passées au programme. On voit très nettement, que dans un certain nombre de cas le nombre de cycles nécessaire est de 30% supérieur au cas "normal". Et dans un cas extrême il est de 300% supérieur au cas normal...

L'article décrit aussi des effets de bord extrêmement hilarants (de la Baltique) de l'ordre dans lequel les .o sont passés fournis lors de l'édition de liens sur les performances.

Reproduisons

L'expérience (la vôtre, donc la mienne en l’occurrence. Vous me suivez? Expérience donc tout aussi vécue que la précédente, même si ici, on ne se réfère pas à une expérience précise mais à l'Expérience que l'on pourrait définir comme le cumul de toutes les expériences vécues.)  L'expérience, donc, vous a rendu méfiant. Et vous voilà donc parti sur la piste de la répétition d'une expérience. Eh, oh. C'est un article scientifique... Qu'est-ce qui pourrait.. .

Les mesures ont été faites à l'aide de la bibliothèque PAPI (Performance Application Programming Interface) pour calculer le nombre de cycles utilisés pour la boucle...
  • téléchargement,
  • ./configure
  • make 
  • make install
Allons-y.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "papi.h"

#define NUM_EVENTS 1
long long values[NUM_EVENTS];
unsigned int events[NUM_EVENTS]={PAPI_TOT_CYC};
 

static int i = 0, j = 0, k = 0;

int main() {
    int g = 0, inc = 1;

    int retval;

    if((retval = PAPI_start_counters((int*)events, NUM_EVENTS)) 
        < PAPI_OK) {
         printf("argh %s\n", PAPI_strerror(retval));
         exit(1);
    }

    for (; g < 65536; g++) {

        i += inc;
        j += inc;
        k += inc;
    }

  
    if((retval = PAPI_stop_counters(values, NUM_EVENTS))
        < PAPI_OK) {
        printf("argh %s\n", PAPI_strerror(retval));
        exit(1);
    }

    printf("%lld\n", values[0]);

    PAPI_shutdown();

    return 0;
}

Vous (re)prenez des précautions élémentaires :
  • sur votre machine avec 24 processeurs, qui ne font pas grand chose, vous choisissez un processeur reculé au fin fond d'un core de la deuxième socket. Et vous jouez de l'affinité (taskset) pour être sûr que vous ne laisserez pas ce programme s'exécuter ailleurs.
  • Vous utilisez  aussi chrt pour vous donner une priorité bien méritée.
  • Si vous êtes vraiment parano, vous y allez même d'un coup de numactl, pour être certain que la mémoire va être allouée pas trop loin de votre processeur. (Note pour plus tard : faudra regarder ça de plus près ces trucs de NUMA.)
Et vous vous lancez dans un script qui
  • élimine toutes les variables d'environnement,
  • lance  100 fois votre programme avec comme seule variable d'environnement
  • A=
  • puis avec A=a
  • puis avec A=aa
  • etc jusqu'à 8192 ajouts.
Et vous calculez la moyenne des 100 exécutions faites pour chaque valeur de la variable d'environnement. Jusqu'à...

Un café sirotons

Bon, il faut plus d'un café... Chaque essai étant réalisé 100 fois pour chacune des 8192 tailles d'environnement, le résultat est disponible environ 1H45 après le lancement du script.


Déception! 

Le comportement décrit dans l'article  ne semble pas se reproduire. Certes, quelques mesures gigotent autour des 500 000 cycles, mais la moyenne étant à 490 000 cycles... nous sommes loin des 30 % de variations constatés dans l'article. Et pas aberration en vue à 300 %.

Persévérons

Oui, enfin... Au chat, notre langue donnons! Un échange avec un des auteurs de l'article conduit sur la piste de ASLR! Oui "Adresse Space Layout Randomization" décrit par DjiBee. La tentative précédente a été effectuée sur un système dans lequel ce mécanisme était activé.

Désactivons ASLR.


fa# echo 0 >/proc/sys/kernel/randomize_va_space
fa#

Et ré-essayons. Un autre café, et 1H45 plus tard:


C'est encore très différent du comportement observé dans l'article initial. Mais malgré tout, vous observez ici des variations entre 14% et 30 % par rapport à la moyenne. 

Zoomons

Si vous zoomez sur le premier pic, vous obtenez :


Et sur le deuxième pic :


Les 2 pics se ressemblent : 16 points chacun. Le delta entre les 2 n'est pas exactement  de 4096...Mais de 4093... Un peu décevant... Mais, tolérant soyons.

L'observation semble être répétable. Si vous avez quelques paquets de 1H45 à perdre, investir, gaspiller, il semble bien que vous obteniez sensiblement les mêmes résultats.

Ailleurs voir allons

Les essais précédents ont été faits sur une machine à base de processeurs Xeon E5-2420 en utilisant un compilateur GCC 4.4.6.
Donc, vous trouvez une autre machine, merci YuRug, avec 40 cores, donc 80 CPU. Et 1H45 plus tard, vous obtenez une variation entre le point minimum et maximum d'environ 2%...
"Rien ne t'affole." (Téléphone).

Vous vous apprêtez à relancer le test en désactivant l'ASLR... Vous pouvez vous avez le droit.

Capitulons

Oui, mais non... le système vous injurie. En disant que echo 0 dans randomize_va_space, là ça va pas le faire. uh ?Un coup de Google Est Ton Ami, et rien. Abandonné en rase campagne. Bon. Faudrait plonger  dans les sources du noyau.

Mais. C'est Décembre sérieusement avancé, comme un camembert. Faut aller remplir la hotte de PAPI (tiens?) Noël. Sans compter que vous avez un tas de 68 copies qui vous attend...

Alors... 

Concluons

Ah, ben. Pas trop avancé, là. Faudrait vraiment refaire cette expérience sur d'autres processeurs. Les impacts entre environnements et performance semblent bien possible. Si dans les lecteurs de ce billet il y a des amateurs qui veulent partager leurs résultats, la porte est grande ouverte! 

Est-ce que ça explique les variations de FauxPlat/sec  recherchées initialement ? Murphy traînant toujours dans les parages, j'ai du mal à y croire... 
  
"Il y a beaucoup de mérite
Sans compter qu’il y a des emmerdements."
(Boris Vian)

 

7 commentaires:

  1. C'est un foutu problème auquel je n'ai jamais osé m'attaquer, mais dont je pense qu'i est important à creuser. La problématique de la mesure est trop souvent ignorée, il y a des choses à aller chercher du côté des physiciens etc autres scientifiques expérimentaux...

    RépondreSupprimer
  2. C'est en partie abordé dans l'article référencé. Les gains de performance entre -O2 et -O3 lots de la compilation, sont souvent plus petits que les variations induites par les 2 facteurs extérieurs (environnement et ordre des objets au link). Sachant qu'il y a probablement d'autres facteurs possibles, évidemment. Ils font référence plutôt aux biologistes qui doivent tenter d'analyser des données à partir de petits échantillons, de manière à éviter de se lancer dans des campagnes de tests longues et fastidieuses.

    RépondreSupprimer
  3. J'ai pas lu le papier référencé, si j'ai un peu de temps je le fais cette problématique est très intéressante. Je m'étais posé la même question sur l'ordre du link, il n'y a pas longtemps, je me disais que cela devait avoir un impact sur les caches... De mémoire, les compilos HP avait une option de compilation permettant de recompiler du code à l'aide de traces d'exécution; je crois qu'ils faisaient des analyses de fréquences d'appels, du graphe d'appel etc pour rapprocher les différentes fonctions entre elles de sorte à éviter les cache-miss (entre autres).

    RépondreSupprimer
  4. Il y a ce papier "STABILIZER: Statistically Sound Performance Evaluation" (http://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf) qui décrit un outil qui permet d'éliminer les variations dues aux environnement et ordre de link. Initialement c'est avec ça que je voulais jouer. Mais mon incapacité à reproduire sérieusement les hypothèses de variabilité m'a fait rabattre mon caquet. Mais je vais m'y remettre (j'ai déjà ma carte du club très peu sélectif des Yakafoc).

    Côté HP, j'avais regardé HP Dynamo, quand je faisais une classification des machines virtuelles. (http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html). Ça fait le boulot d'optimisation globale qu'un compilo qui est limité à un .o ne peut pas faire. En fait, les mécanismes de "dynamic binary translation" (http://en.wikipedia.org/wiki/Binary_translation#Dynamic_binary_translation) font tous plus ou moins ça: réorganiser le code, supprimer les branchements inutiles et meilleur suivi de registres... Cf VMware sur 32 bits: A
    "Comparison of Software and Hardware Techniques for x86 Virtualization" (http://www.vmware.com/pdf/asplos235_adams.pdf.)

    Du coup, comprendre l'impact temporel d'un changement d'algorithme devient encore plus compliqué. Mais c'est peut-être un débat (bientôt?) dépassé?

    RépondreSupprimer
  5. Les commentaires sont de trop haut niveau ici! Je vais niveler : Le lien "laveur" de "ratons (pas laveur)" est cassé !

    RépondreSupprimer
    Réponses
    1. Oups. Apparemment la cible du lien a disparu. C'est rétabli vers les indispensables Frères Jacques ! https://www.youtube.com/watch?v=qVB4pxGB8jQ

      Et je suis très heureux que tu te donnes la peine de suivre mes stupides liens ! Merci Matthieu !
      Du coup, ça va m'inciter à continuer ! Tant pis pour vous, toi !

      Supprimer
  6. L'impact temporel sur les agorithmes...Oui, aussi une vieille réflexion (mais primitive) de mon côté; de laquelle il me reste le sentiment que décidément la complexité algorithmique ne dit pas grand chose au quotidien; rien que l'impact du système, de se caches, etc ne donne pas grand-chose de prévisible ou plutôt de très utile pour prédire avec une exactitude suffisante...

    RépondreSupprimer