Discussion :

[Seabirds]

Bonjour à toutes et à tous

J'ai fait un benchmark pour comparer deux politiques pour un algorithme : "identity" et "truncate" (y'en a à qui ça évoquera quelque chose )
J'ai utilisé std::chrono::high_resolution_clock pour mesurer le temps mis par chaque stratégie.
J'ai ré-échantillonné 10000 fois le temps d'exécution pour chaque stratégie.

Comme je benchmark pour différents jeux de variables d'entrée des algos, j'ai commencé par regarder seulement les moyennes des temps d'exécution. Mais après coup j'ai quand même voulu jeter un coup d'oeil aux distributions sous-jacentes.

Bizarrement, il y a souvent des distributions bi-modales qui apparaissent, et ça me plaît pas trop. Par exemple, sur la figure suivante, la stratégie rose va être sur-pénalisée si on ne compare les stratégies que sur le critère de la moyenne (traits verticaux).


Je ne sais pas trop d'où ces artefacts peuvent venir (pour un même jeu de variables d'entrée de l'algorithme ils peuvent ou pas apparaître, mais certains paramétrages ont l'air d'être plus susceptibles à ce genre d'incidents).

J'ai lu par ailleurs qu'on est censé benchmarker dans des conditions "optimales" (pas de programmes de fond, pas de GUI ... ). Evidemment, ce n'est pas ce que j'ai fait, pensez-vous. Pensez-vous que le problème puisse venir de là ?

Si ça vient de là, est-ce qu'il vaut mieux prendre le temps de se placer dans ces conditions optimales (Ubuntu sans GUI ? seriously ? ) ou bien peut on s'intéresser plutôt au temps CPU (même si j'avais lu qu'il vaut généralement mieux utiliser le temps système, le programme n'est pas multithreadé donc j'imagine qu'on ne prend pas beaucoup de risques ? ).

Est-il de coutume de s'encombrer de ce genre de considérations (ou j'en fais trop ) ?

merci à vous

[ternel]

Le problème, ce n'est pas tellement de mesurer dans les conditions idéales, mais dans des conditions similaires entre les cas.
C'est à dire qu'il faut pouvoir obtenir la même gêne venant de l'environnement.

La seule solution, c'est effectivement un système le plus vide possible.
Tu devrais te trouver en bonne condition si:

• tu fermes ta session utilisateur graphique,
• tu passes sur une session en ligne de commande,
• tu déconnectes le réseau,
• tu t'assures de n'avoir aucun autre utilisateur actif sur le système,
• tu attends un peu que tous les programmes de début de session se calment,

Fais aussi attention à ne comparer que des choses très similaires. Un comparatif où tout change entre les comparés ne permet pas de dire quoi que ce soit.
Entre truncate et identity, je ne vois pas la raison pour laquelle "bi-modale" apparait comme moyen de distinguer des résultats.

[Seabirds]

Merci de ta réponse !

Tu devrais te trouver en bonne condition si:

• tu fermes ta session utilisateur graphique,
• tu passes sur une session en ligne de commande,
• tu déconnectes le réseau,
• tu t'assures de n'avoir aucun autre utilisateur actif sur le système,
• tu attends un peu que tous les programmes de début de session se calment,

Ok je vais aller voir comment on fait tout ça !

Fais aussi attention à ne comparer que des choses très similaires. Un comparatif où tout change entre les comparés ne permet pas de dire quoi que ce soit.

Yep, normalement, c'est le cas. Quand on regarde la figure, il n'y a qu'un seul truc qui a changé pour passer d'une distribution à l'autre, tout le reste étant égal par ailleurs.

Entre truncate et identity, je ne vois pas la raison pour laquelle "bi-modale" apparait comme moyen de distinguer des résultats.

Heu j'ai pas compris ce que tu dis Je souhaite comparer truncate et identity en comparant la moyenne de leur distribution, et le fait que la distribution de identity soit bimodale colle mal avec l'intuition qu'on se fait de la moyenne, du coup j'ai bien envie de virer le petit pic de valeurs vers 1000 ns

[ternel]

Ca y est, j'ai pigé le "bimodale": ca veut juste dire, il y a 2 tas de données.

A priori, non, il ne faut pas le négliger, il faut comprendre pourquoi il apparaît.
Tu ne fais pas une publication, tu veux analyser.

Tu disposes d'un constat, demandes toi pourquoi celui-ci et pas un autre.

[koala01]

Salut,

A vrai dire, j'irais même encore plus loin : outre le pic de valeurs au alentours de 10000 ns, tu as aussi un pic (quoi que bien moins visible) entre 2500 et 5000 ns.

Ces valeurs sont, de toutes évidences, bien au delà de l'écart-type (l'écart par rapport à "la norme constatée" qui correspond à des "valeur anormalement élevées" ou "anormalement basses", en fonction du coté où elles apparaissent).

Ce que tu devrais faire, c'est surtout essayer de comprendre pourquoi ces valeurs apparaissent : qu'est ce qui fait que "certaines valeurs" nécessitent de deux à quatre fois plus longtemps pour être traitées que ce que l'on peut observer pour la grande majorité des données

Car ce n'est qu'en sachant quelles données nous font passer dans ces cas extrêmes que tu pourras définir si ce sont, oui ou non, des cas qui nécessitent d'être pris en compte.

Typiquement, je verrais deux situation possibles:

Soit tu travailles peut-etre avec un très petit jeu de données, et les pics que l'on rencontre sont ceux qui correspondent à "la première utilisation" de ces données, les utilisations suivantes utilisant d'une manière ou d'une autre la "mise en cache" effectuée lors de cette première utilisation.

Contrairement à ce que tu crois, le gros du benchmark fonctionnerait alors sur des "données existantes" dans "l'ordre attendu" et ton benchmark ne vaudrait alors rien, car, pour qu'il soit valide, il faudrait que les données soient systématiquement créées dans leur ordre initial; les "artéfacts" rencontrés représentant en définitive... les valeurs réelles auxquelles tu dois t'attendre.

Soit il se fait que "certaines données" s'avèrent être moins "cache friendly" que le reste. Tu n'ignores sans doute pas que, s'il est possible d'avoir de la mémoire permettant un accès très rapide, mais en petite quantité, s'il est possible de disposer d'une très grande quantité de mémoire, mais permettant un accès "plus lent", il en revanche impossible de disposer "d'une grande quantité de mémoire permettant un accès rapide".

C'est la raison pour laquelle le processeur "fait un pari" à chaque fois qu'il doit charger une donnée qui se trouve en mémoire : il parie sur le fait que la donnée "qui devra être chargée après" se trouve... tout près de la donnée à laquelle il doit accéder maintenant.

Du coup, au lieu de charger exactement la donnée dont il a besoin à un instant T, il va charger l'ensemble des X bytes qui "entourent" cette données, et va les placer dans ce que l'on appelle "la mémoire cache" qui est une (toute) petite quantité de mémoire à accès (très) rapide.

S'il gagne son pari, et, surtout, s'il le gagne "plusieurs fois d’affilée", il peut gagner énormément de temps, car la somme du temps nécessaire à charger toutes ces données en cache + celle de tous les temps nécessaires aux accès au données qui se trouvent dans le cache s'avère souvent être inférieure au temps qu'il aurait fallu pour accéder aux même donnée depuis la "grande quantité de mémoire plus lente".

Par contre, s'il perd son pari, il aura en définitive perdu son temps à remplir la mémoire cache. Quand cela arrive, on parle de "cache miss" (erreur de cache), et les performances ont tendance à s'effondrer.

Tout cela pour dire "qu'il se peut" que les artéfacts constatés correspondent à des données qui occasionnent d'avantage de cache misses, et qu'il faudrait "idéalement" essayer d'investiguer afin de savoir pourquoi ces caches misses supplémentaires surviennent.

Cela te permettra déjà de déterminer si "ca vaut la peine" d'essayer de résoudre ce "problème" en te permettant de déterminer si ... c'est vraiment un problème, ou si c'est une situation "suffisamment rare" que pour pouvoir ne pas y prêter attention

Et cela te permettra également de te faire une idée du "comment" résoudre le problème si tu décide d'essayer de le faire

[Seabirds]

Donc même faire un benchmark c'est pas si facile ! N'y a-t-il donc aucun secret du C++ qui ne s'arrache de haute lutte ?

Merci pour vos réponses qui mènent déjà la moitié de la bataille

J'avais pensé à ces problèmes de cache, je suis heureux de constater que tu évoques la même possibilité.

Une partie de l'algorithme consiste à échantillonner aléatoirement dans une distribution. Petite précision : les "valeurs" du support de loi sont des objets plus ou moins gros (des vecteurs d'entiers de taille inférieure à 30).

Les parties du support de loi qui ont une probabilité importante de tirage vont être souvent mis en cache, n'est ce pas ? Ce qui ferait que ça tourne très vite quand ces valeurs très probables sont échantillonnées "plusieurs fois de suite", mais qu'il y a un coût (le cache miss ?) si une autre valeur de plus basse probabilité et absente du cache est échantillonnée ? Le processeur va perdre du temps à aller chercher cette valeur de faible proba dans la "grosse mémoire à accès lent" (premier coût en temps), il va la stocker dans le cache (deuxième perte de temps) en faisant le pari qu'on va la lui redemander bientôt, sauf qu'en général il va se louper, puisqu'il a peu de chance de retirer la même. Donc troisième perte de temps quand il va falloir retourner chercher la valeur de plus grande proba.
C'est idiot comme raisonnement ?

Notez que comme vous le faisiez remarquer, je ne devrais idéalement pas passer trop de temps à comprendre les détails fins de ce qui se passe au niveau du processeur dans ces algos. Mon intérêt de base est d'avoir un indicateur potable pour répondre à la question "est-ce que l'algo A tourne en moyenne plus vite que l'algo B ?".
Je suis évidemment tout à fait intéressé par me pencher sur les détails si ça me permet de répondre à cette question (qui est sûrement plus complexe qu'elle n'en a l'air)