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)

[koala01]

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é.

A vrai dire, à ce niveau, ce n'est pas un problème spécifique au C++, mais bien un problème lié au fonctionnement même d'un ordinateur

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 ?

Non, ce n'est pas du tout idiot comme raisonnement, car c'est en gros ce qui se passe, mais il comporte une erreur d'importance:

Tu sais, à n'en pas douter, que toutes les données que tu manipule finissent tôt ou tard par se trouver "dans la mémoire" de l'ordinateur, et que, pour que le processeur puisse y accéder, chaque donnée se trouve à une adresse qui lui est propre.

L'idée de la mise en cache, c'est de se dire que, si on accède à un instant T à l'adresse mémoire X, il y a "de très fortes chances" pour que l'accès mémoire qui se fera à l'instant T+1 se fasse à une adresse que l'on espère se trouver entre X et X+Y, où X est constant et où Y correspond au nombre de données que l'on peut mettre dans "une page de mémoire cache".

Si c'est ce qui se passe réellement, tout va très bien, mais si l'accès à la mémoire que l'on fait à T+1 nous emmène à X+Z où Z nous emmène "au delà" de ce qui a été mis en cache, la prédiction s'est vautrée et, comme tu l'as si bien dit, on observe des perte de temps en cascade :

• parce que le processeur a perdu du temps à mettre des données "inutiles" en cache à l'instant T
• parce que le processeur perd du temps à l'instant T+1 à accéder à la donnée dont il a besoin
• parce que le processeur perd encore du temps à mettre en cache les données qui se trouvent "aux alentours" de la donnée dont il a besoin

Ce qui importe, ce n'est pas la fréquence d'accès à une donnée qui produira le cache miss, mais bel et bien la "proximité" en mémoire d'une donnée par rapport à la donnée qui a été traitée "juste avant" ou qui sera traitée "juste après".

Et ca, c'est d'avantage lié à un problème de... création de la donnée, voire, de la collection dans laquelle la donnée sera placée.

Ainsi, si ta donnée contient des éléments pour lesquels tu as eu recours à l'allocation dynamique, il y a fort à parier que le simple fait de tenter d'accéder à ces éléments provoquera un cache miss

De la même manière, l'utilisation d'un tableau (comme std::vector ou std::array) nous assure que toutes les données seront contigües en mémoire ( du moins, les éléments de ces données pour lesquels on n'a pas eu recours à l'allocation dynamique de la mémoire), ce qui peut fortement limiter le risque de cache miss, à condition que l'on traite ces données "par lot".

A l'inverse, on peut partir du principe que toutes les autres collections (std::list, std::map, std::set, std::stack, ...) ont recours à l'allocation dynamique de la mémoire pour placer chacun des éléments qu'elles contiennent (bon, ce n'est pas forcément vrai, mais attends toi toujours au pire, comme cela tu ne sera jamais déçu ), ce qui de fortes chances de favoriser les cache miss.

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)

N'oublie pas que la moyenne ne veut généralement pas dire grand chose si on n'y adjoint pas l'écart-type, car la moyenne n'est jamais qu'un repère tracé "quelque part" sur ton graphique, mais, ce qui est intéressant à connaitre, c'est l'intervalle dans lequel on peut considérer que les éléments sont "dans la moyenne"

Ainsi, une moyenne haute avec un écart-type important peut indiquer que tu peux avoir des élément très lents qui seraient pourtant considérés comme "dans la moyenne", alors qu'une moyenne plus basse mais avec un "très léger écart-type" pourrait indiquer que les élément sont globalement plus rapides

[Seabirds]

A vrai dire, à ce niveau, ce n'est pas un problème spécifique au C++, mais bien un problème lié au fonctionnement même d'un ordinateur

Tu veux dire cette boîte noire magique qui permet de jouer, consulter ses mails et taper du C++ ?

N'oublie pas que la moyenne ne veut généralement pas dire grand chose si on n'y adjoint pas l'écart-type, car la moyenne n'est jamais qu'un repère tracé "quelque part" sur ton graphique, mais, ce qui est intéressant à connaitre, c'est l'intervalle dans lequel on peut considérer que les éléments sont "dans la moyenne"

Ainsi, une moyenne haute avec un écart-type important peut indiquer que tu peux avoir des élément très lents qui seraient pourtant considérés comme "dans la moyenne", alors qu'une moyenne plus basse mais avec un "très léger écart-type" pourrait indiquer que les élément sont globalement plus rapides

Merci pour le rappel ! Ce que je fais, c'est tester l'égalité des moyennes avec un test de Welch, qui intègre la dispersion dans sa comparaison. Le test fait l'hypothèse de normalité, c'est entre autres choses pour ça que j'ai voulu regarder la tête des distributions (en pratique, l'hypothèse de normalité est très vite assurée pour les grands échantillons).
Si les moyennes sont considérées comme inégales, je calcule le ratio des deux moyennes, ce qui me donne une idée de quel algo tourne le plus vite. J'ai eu un moment peur que ça soit overkill (même si ça ne mange pas de pain), mais au vu de ta réponse, je me dis que c'était (peut-être) une idée pas si mauvaise

Ce qui importe, ce n'est pas la fréquence d'accès à une donnée qui produira le cache miss, mais bel et bien la "proximité" en mémoire d'une donnée par rapport à la donnée qui a été traitée "juste avant" ou qui sera traitée "juste après".

C'est plus clair ! Merci

Reste à savoir si ce test de benchmark reproduit ce qui se passerait dans la situation "réelle"

• Dans le test, le programme effectue 10000 échantillonnages dans la même distribution les uns directement à la suite de l'autre. Du coup j'imagine qu'il profite largement des optimisation de la mise en cache.
• Dans le cas "réel", il fera beaucoup moins d'échantillonnages, pas forcément dans les mêmes distributions, et il y aura d'autres bouts de code exécutés entre deux échantillonnages. J'imagine que dans ce cas là il est assez probable que le cache ait été vidé n'est-ce pas

Du coup là je me dis que j'aimerais forcer un cache miss à apparaître à chaque itération de test. Il y a un moyen plus élégant que créer des énormes vecteurs vides pour saturer le cache

[ternel]

Ne te préoccupe pas d'un éventuel unique cache miss si ton processus prend au moins quelques millisecondes. (s'il est vraiment unique)
Les cache miss importants à surveiller sont ceux survenant pendant le calcul. Pas celui au tout début (que tu ne pourras pas éliminer).

Une stratégie peut être d'ignorer les premières mesures, qu'il faut considérer comme des tours de chauffe (warm up).
Mais il faut les mesurer tout de même (pour que tout se passe comme si c'était de vraies mesures), tu les retireras des résultats montrés.

A noter, valgrind dispose d'un mode dédié aux défauts de cache. Comme il est ralenti beaucoup le programme, exécute le sur un petit nombre d'itérations.

[Seabirds]

Les cache miss importants à surveiller sont ceux survenant pendant le calcul. Pas celui au tout début (que tu ne pourras pas éliminer).

Je ne suis pas sur d'avoir compris de quel "calcul" tu parles

[ternel]

le "calcul" est le processus dont tu veux effectivement mesurer la durée.

[koala01]

Je ne suis pas sur d'avoir compris de quel "calcul" tu parles

En fait, lorsque tu "remplis" ta collection, avant de commencer à utiliser les données qu'elle contient, tu ne peux pour ainsi dire pas éviter certains cache misses (*). Il faut juste savoir que ces cache misses surviennent par la nature même de l'action que tu entreprends sur ta collection.

Mais, a priori, ta logique devrait essayer de fonctionner selon un ordre précis à savoir

1. on crée toutes les données dont on a besoin (par exemple, par "désérialisation" de celles-ci), que nous devrons manipuler et
2. on manipule toutes ces données
3. on retourne en (2) aussi souvent que nécessaire, mais on ne retourne jamais en (1)

Une logique aussi simple que celle-ci permet de ne perdre "qu'une bonne fois pour toutes tout le temps nécessaire" à la création des données , quitte à ce que le chargement des données prenne "assez longtemps pour que l'utilisateur le ressente": le temps perdu à créer les données étant en définitive (largement ) récupéré par le temps que nous passerons à les utiliser.

Maintenant, il arrive que cette logique "aussi simple" ne soit purement pas possible à mettre en place, peut-être parce qu'une partie des données que l'on manipule seront créées suite à des calculs effectués sur "un jeu restreint" de données. Mais bon, là aussi, on peut considérer le temps nécessaire à la création de telles données comme "incompressible", du moins, une fois que la manipulation qui permet de les créer a été optimisée

(*)Il est, cependant, aussi possible d'éviter les caches misses lors de la création des données si l'on envisage de manipuler des tableaux de données contigües.

En effet, l'une des situations avec lesquelles on perd le plus de temps lorsqu'on remplit un tableau de type std::vector, c'est lorsque la fonction push_back (ou emplace_back... ou similaires) doit augmenter la capacité du (**) tableau afin de pouvoir y ajouter le nouvel élément. Et c'est normal : il y a "toute une mécanique" derrière ces fonctions qui font que :

1. le tableau va faire un appel système pour obtenir "plus d'espace"
2. le tableau va transférer les éléments contenu de l'espace "d'origine" vers "le nouvel esppace" obtenu au travers de l'appel système
3. le tableau va veiller à utiliser le "nouvel espace" obtenu
4. le tableau va faire un appel système pour libérer l'espace d'origine

Cette logique prend énormément de temps; et elle en prend a priori d'autant plus que le nombre d'éléments est élevé.

Par chance, la classe std::vector propose la fonction reserve() qui permet, tout comme l'un des constructeur de la classe, de définir de manière plus ou moins arbitraire la "capacité de base" du tableau, et donc, de limiter ne nombre de fois où le tableau devra augmenter sa capacité.

Aussi, si l'on est -- par exemple -- en mesure de déterminer qu'un tableau devra presque systématiquement contenir "au minimum 1 000 000 000 d'éléments", nous pouvons lui forcer la main pour qu'il réserve directement un espace suffisant en mémoire que pour pouvoir contenir... nos 1 000 000 000 d'éléments et donc, éviter toutes les augmentations de capacités "intermédiaires".

(**) note que ce problème n'en devient réellement un que... lorsque le tableau est destiné à contenir un (très) grand nombre d'éléments... En dessous d'un millier, voire, de plusieurs millions d'éléments, il y a peu de risque que le temps nécessaire à l'augmentation de la capacité soit réellement perceptible

[Seabirds]

Remerciement bien tardif pour cette super réponse !

Ma logique fonctionne comme ça, pour autant que je puisse en juger !

Merci encore pour vos réponses, le sujet me semble résolu pour l'instant (j'entends par là qu'il a une faible priorité comparées à d'autres questions ).