Test&Set, cohérence de caches et autres bizarreries !

[Shihaya]

Salutations gurus du x86 ! J'ai un petit problème de perf intéressant pour vous !



Contexte :
Je développe actuellement un framework évenementiel pour machines multi-coeur. Classiquement ça fonctionne très bien jusqu'à 4 coeurs et puis après (8 coeurs / 16 coeurs) les perfs s'écroulent.
En investiguant sur les causes du pourquoi du comment je suis tombé sur des comportements étranges sur des Q6600 & Bi Xeon (j'ai pas encore testé sur d'autres processeurs). L'idée de base était de tester le comportement des test&set (faits via "xchgb").

Voici les résultats qu'on obtient : (chaque coeur bourinne et fait des xchgb en boucle)
- si chaque coeur fait des xchgb sur une variable différente, pas de problème : on en fait énormement et ça scale bien (~1 milliard / seconde au total avec 8 coeurs)
- si chaque coeur fait un xchgb sur la même variable les perfs sont nazes (écroulement : on en fait plus que ~18 millions/sec au total avec 8 coeurs ! (210m/s avec 4))

On s'est dit que c'était dû à la cohérence des caches qui moulinait un peu, donc on a décidé de faire un faux T&S pour se convaincre.



Le test en question est tout bête : on lance un thread par coeur (fixé sur un coeur) et chaque thread fait des T&S en boucle : (cette fois les tests sont faits sur des Q6600 donc on passe de 2 à 4 coeurs)

Code:
unsigned char faux_test_and_set(volatile unsigned char* addr) {
register unsigned char ret = *addr;
*addr = 1;
return ret;
}
... Les perfs sont effectivement nazes... (On passe de 210m/s à 17m/s de 2 à 4 coeurs )

LE PROBLEME c'est que si on fait ça :
Code:
unsigned char faux_test_and_set(volatile unsigned char* addr) {
register unsigned char ret = *addr;
(*addr)++; // Subtile modif
return ret;
}
... Là ça marche plus que bien ! (~700m/s à 2 coeurs et ~800m/s à 4).



J'ai fouillé un peu dans le code asm généré par gcc (et icc : les perfs sont identiques et le code asm très très proche) et fait quelques modifs. De base on a : (SYNTAXE AT&T !)

• version *addr = 1 : (lent)

Movb $1, value_to_tas(%rip)

• version (*addr)++ : (rapide)

Movzbl value_to_tas(%rip), %eax
Addl $1, %eax
Movb %eax, value_to_tas(%rip)


Modifs & perfs : (lent = ~20m/s, rapide = ~600/800m/s)
*1/
Movzbl value_to_tas(%rip), %eax
Xorl %eax, %eax
Movb %eax, value_to_tas(%rip)
=> C'est lent !

*2/
Movzbl value_to_tas(%rip), %eax
Andl %eax, %eax
Movb %eax, value_to_tas(%rip)
=> C'est rapide !

*3/
Movzbl value_to_tas(%rip), %eax
Incl %eax
Movb %eax, value_to_tas(%rip)
=> C'est rapide !

*4/
Movzbl value_to_tas(%rip), %eax
Xorl %eax, %eax
Nop (x 50)
Movb %eax, value_to_tas(%rip)
=> C'est rapide !


Et là je comprends plus rien... Si on regarde juste 1 & 4, on pourrait se dire qu'il faut laisser un peu de temps au cache pour qu'il soit bien efficace (algo de cohérence foireux ? Optimisation qui fonctionne mal quand on bourrine trop ?), mais pourquoi ça redevient rapide lorsqu'on met un andl/incl à la place d'un xorl ???


Bizarrement si on lance notre test de T&S avec un autre test bien intensif (un test qui fait un while(1) { malloc(); free(); } par exemple), on a de meilleures perfs que si le test T&S est lancé seul.
(Empiriquement : T&S seul : ~20m/s et T&S + processus qui fait des mallocs : ~380m/s !)


Quelqu'un a une idée du pourquoi du comment ?

[fefe]

Je regarde ca quand j'ai un peu de temps ca a l'air interressant .

Au premier abord je dirais que les machines Nehalem devraient avoir des perfs tres differentes sur ce type de tests (et nettement plus elevees).

[fefe]

Salutations gurus du x86 ! J'ai un petit problème de perf intéressant pour vous !



Contexte :
Je développe actuellement un framework évenementiel pour machines multi-coeur. Classiquement ça fonctionne très bien jusqu'à 4 coeurs et puis après (8 coeurs / 16 coeurs) les perfs s'écroulent.
En investiguant sur les causes du pourquoi du comment je suis tombé sur des comportements étranges sur des Q6600 & Bi Xeon (j'ai pas encore testé sur d'autres processeurs). L'idée de base était de tester le comportement des test&set (faits via "xchgb").

Voici les résultats qu'on obtient : (chaque coeur bourinne et fait des xchgb en boucle)
- si chaque coeur fait des xchgb sur une variable différente, pas de problème : on en fait énormement et ça scale bien (~1 milliard / seconde au total avec 8 coeurs)
- si chaque coeur fait un xchgb sur la même variable les perfs sont nazes (écroulement : on en fait plus que ~18 millions/sec au total avec 8 coeurs ! (210m/s avec 4))

On s'est dit que c'était dû à la cohérence des caches qui moulinait un peu, donc on a décidé de faire un faux T&S pour se convaincre.



Quelqu'un a une idée du pourquoi du comment ?

Je vais m'y mettre progressivement il y a beaucoup d infos dans ton post.
Pour commencer je vais partir du principe que tu as (ou vas) lire des details sur le protocole de coherence des caches MESI: http://en.wikipedia.org/wiki/MESI_protocol , et le chapitre consacre a la coherence memoire dans l'excellent Hennesy-Patterson sur L'architecture des ordinateurs http://www.eyrolles.com/Informatique...-9782711787005 (un livre a avoir a mon avis).

Tout d'abord pourquoi est ce que ca va plus vite quand tu le fais sur des variables differentes ? La coherence des caches est geree par ligne de cache (64 octets dans ton cas), donc tout ce qui est present sur la meme ligne de cache est essentiellement traite comme une seule donnee du point de vue de la coherence des caches. Si je veux pouvoir en ecrire un bout il faut que je sois proprietaire de toute la ligne.

Donc si chaque core fait des tests and set sur des lignes de caches differentes qui sont chacune dans son cache de premier niveau et qu'il est le proprietaire exclusif de ces lignes, tout va se passer tres vite etant donne qu'il n'y aura aucun message echange entre les cores.
Si tu emploies des variables differentes mais te debrouille pour les coller dans la meme ligne de cache (addresses contigues) tu vas avoir le meme comportement que si tu employais une seule variable.

Ensuite, pourquoi les perfs changent de maniere dramatique quand je passe de 2 a 4 cores et de 4 a 8 cores et plus et fait le test and set sur la meme variable.
Si tu as 2 cores de type core2 ils partagent le meme cache de second niveau et peuvent communiquer entre eux par cet intermediaire. La latence d'un message qui permet par exemple de devenir le proprietaire d'une ligne de cache parce qu'on l'a demande va etre du meme ordre de grandeur qu'un aller retour vers le cache L2.
Si tu as 4 cores de type core 2 tu vas devoir passer par un FSB interne au chip pour communiquer entre les 2 paires de cores, ca va prendre beaucoup plus de temps.
Si tu passes a un dual socket ou quad socket tu as besoin d'aller encore plus loin la latence augmente encore une fois (et ce de beaucoup vu que tu sors du chip).

Le test and set est une operation atomique qui ne doit pas etre interrompue par d'autres operations, donc tu dois attendre que toutes les conditions soient reunies pour pouvoilr l'executer (en particulier avoir la permission de faire le set donc etre le proprietaire de la ligne de cache). Si cette dite ligne de cache est la propriete d'un autre coeur sur un autre socket il va falloir que tu attendes qu'il ait fini son traitement, puis qu'il te transmette la ligne de cache modifiee si elle l'a ete ou le droit de la modifier si tu avais une copie qui est toujours valable. Plus c'est loin, plus ca prend de temps.

Pour moi ca explique la raison pour laquelle le debit de test&set que tu observes s'effondre sur les plateformes multi-socket. La latence pour obtenir les droits d'executer cette instruction est enorme devant le cout de l'instruction elle meme.

Sur le Phenom ou Nehalem, tu as 4 coeurs qui partagent le meme cache sur un chip donc les communications y sont plus rapides qu a travers un FSB meme on die. Quand tu vas sur les autres sockets sur ces plateformes tu n'as pas besoin de passer par un FSB (qui est charge parce que tout le monde passe son temps a envoyer des messages sur le meme), tu vas passer par un lien point a point qui a une latence plus faible.

Il me semble avoir vu qq part que Nehalem avait fait des ameliorations supplementaires pour ce type d'operations mais je n'ai pas encore eu le temps de creuser.

[Møgluglu]

La cohérence de caches n'explique quand même pas ça :

Et là je comprends plus rien... Si on regarde juste 1 & 4, on pourrait se dire qu'il faut laisser un peu de temps au cache pour qu'il soit bien efficace (algo de cohérence foireux ? Optimisation qui fonctionne mal quand on bourrine trop ?), mais pourquoi ça redevient rapide lorsqu'on met un andl/incl à la place d'un xorl ???

Au risque d'avoir l'air ridicule, je me lance.
Dites-moi si je raconte trop de conneries...

L'idiome "xor eax, eax" doit être suffisamment courant pour que le hard sache que le résultat (=0) ne dépend pas de la valeur précédente de eax, du coup il peut renommer eax, exécuter le xor en même temps que le load, voire même commencer le store avant que le load ne termine.

Dans tous les autres cas, il y a une dépendance entre le load et le store (2, 3) ou bien il s'écoule suffisamment de temps (4) entre les deux pour que le load termine, et pour une raison quelconque ça fait moins de bagarre pour le contrôle de la ligne de cache concernée?

Edit:
Le load copie la donnée dans le L1 de coeur à partir du L2 ou d'un autre L1 (snoop).
Dans les cas 2, 3 et 4 la donnée qui vient d'arriver en L1 est dans l'état Shared quand le store est fait, il a "juste" à invalider les copies des autres cores.
Dans le cas 1, l'entrée du cache est toujours invalide au moment du write, c'est plus compliqué et ça change tout?...

[fefe]

La cohérence de caches n'explique quand même pas ça :

Tout a fait, je repondais par petits bouts (et quotais l'objet de ma reponse).

L'idiome "xor eax, eax" doit être suffisamment courant pour que le hard sache que le résultat (=0) ne dépend pas de la valeur précédente de eax, du coup il peut renommer eax, exécuter le xor en même temps que le load, voire même commencer le store avant que le load ne termine.

L'idiome est reconnu dans le renamer dans mes souvenirs c'est une instruction "zero cycles d'execution".

[fefe]

Essaye avec (*addr)+=16; // Subtile modif - incrementer d'au moins une ligne de cache.

Et compare avec les 2 autres versions.

Je reflechis a la version 4 (la seule explication qui me vienne a l'esprit est que tu resouts un probleme de speculation en forcant le CPU a attendre avec tes nops mais je n'ai pas d'explication qui me satisfasse pour l'instant), mais le comportement des 3 premieres semble parfaitement raisonable.

[lordmagnum]

Q6600 => FSB1066 = 8.5 Go/s, déjà que c'est du MCM donc si on passe en plus à du MP normal que les perfs s'écroulent.

[newbie06]

Oui mais là on parle de 20M de transactions / sec on est très en-dessous de la bande passante que tu donnes

[Tramb]

Effectivement l'interlocking est plein de pièges au niveau perf (quand déjà t'arrives à faire marcher le bouzin pour faire des structures non triviales).
Le problème c'est que quand tu développes des algorithmes lockfree en général tu es déjà bien content que ça marche, et de ton gain sur les structures de locking de ton OS.
Séparer tes variables atomiques sur des lignes de caches différentes peut donner des gains intéressants... Ou pas en pratique si tu augmentes trop la footprint mémoire de ton code
Mais (tarte à la crême évidente mais tellement vrai), moins tu fais de synchro et mieux tu te portes
Ca peut être intéressant d'avoir des caches en TLS que tu synchronises moins souvent (regarde les implémentations de hoard et nedmalloc, c'est du code dispo librement qui scale bien)

[newbie06]

Warning : je n'y connais pas grand-chose en MT...

Le problème c'est que quand tu développes des algorithmes lockfree en général tu es déjà bien content que ça marche, et de ton gain sur les structures de locking de ton OS.
Séparer tes variables atomiques sur des lignes de caches différentes peut donner des gains intéressants... Ou pas en pratique si tu augmentes trop la footprint mémoire de ton code

L'idée n'est-elle pas de coller des données partagées à côté de tes variables atomiques pour réduire la fragmentation ? Lors de la transaction cohérente de la ligne de cache, tu vas aussi récupérer des data utiles.

[Tramb]

Warning : je n'y connais pas grand-chose en MT...

L'idée n'est-elle pas de coller des données partagées à côté de tes variables atomiques pour réduire la fragmentation ? Lors de la transaction cohérente de la ligne de cache, tu vas aussi récupérer des data utiles.

Yep mais par exemple c'est pas forcément astucieux de poolallouer globalement des structures contenant une variable atomique et une deuxième métadonnée, si c'est pour que deux threads différents bossent sur la même ligne de cache sur deux objets conceptuellement indépendants.

[newbie06]

Faut vraiment que je m'y mette à tout ça... Ca tombe bien j'ai enfin un vrai CPU ; plus que 5h30 avant la fin du DL de FC10

[Shihaya]

Tramb : effectivement, séparer les locks sur une ligne de cache est une idée intéressante. (On a déjà eu quelques "blagues" qui pourraient ressembler à ce problème de données privées / publiques mélangées sur une ligne de cache : en alignant des structures, on a eu un écroulement des perfs (~ -50% !))

On a également déjà testé quelques malloc optimisés pour multicoeurs et ça a pas changé grand-chose aux perfs (bizarrement). (Mais je connaissais pas nedmalloc, je testerai pour voir...)



Fefe : Merci pour les supers explications.

Notre idée de faire un T&S sur des variables privées / partagées c'était pour vérifier que le problème venait bien de la cohérence des caches et pas de l'instruction "lock;" (elle rend effectivement l'exécution plus lente mais scale bien). Mais je vais effectivement me pencher sur le Hennesy-Patterson : un peu de lecture sur la cohérence de cache ne peut pas me faire de mal.


Au niveau des instructions : j'avais juste donné celles qui me semblaient pertinentes mais j'avais fait d'autres tests (je recopie ça de mémoire, je vérifierai tout ça lundi) :


Movzbl value_to_tas(%rip), %eax
Addl $10, %eax // 10, pas 16 !
Movb %eax, value_to_tas(%rip)
=> c'est rapide
(Je ferai des vrais comparaisons Lundi, j'ai pas les chiffres réels en tête)


* Un movl au lieu du xorl :
Movzbl value_to_tas(%rip), %eax
movl $0, %eax
Movb %eax, value_to_tas(%rip)
=> C'est lent
(Ca confirme l'hypothèse de Møgluglu sur la non dépendance du load et du store qui foutrait les perfs en l'air ! Je vais tenter de faire d'autres tests là dessus !)

[Tramb]

Ah oui, aussi, est-ce que tu fais bien des YieldProcessor (ou autre suivant platforme/toolchain ) dans tes spinlocks?

Au fait fefe le grand gourou, on doit remercier Intel de ne pas nous forcer à mettre des memory barriers explicites sous peine de bugs imbitables ou les maudire de la perte de perf potentielle?

[Shihaya]

Ah oui, aussi, est-ce que tu fais bien des YieldProcessor (ou autre suivant platforme/toolchain ) dans tes spinlocks?

On a 1 thread / coeur (chaque coeur fait tourner une boucle de traitement d'évènements - non bloquants - et tente, si il n'a rien à faire, de voler du travail aux autres coeurs). Pas besoin de yield processor dans ce cas là, si ?
(On a dû le faire dans certains OS qui ne font pas de scheduling pour laisser la main à d'autres "process", mais pas besoin de ça sous Linux, right ? )

[newbie06]

Au fait fefe le grand gourou, on doit remercier Intel de ne pas nous forcer à mettre des memory barriers explicites sous peine de bugs imbitables ou les maudire de la perte de perf potentielle?

Moi je parie que ce sont les designers hard de chez Intel qui doivent maudire leurs prédécesseurs d'avoir laissé faire ça

[Tramb]

Ca doit pouvoir baisser la charge sur le bus même dans ce cas là.
En plus sur un vrai OS, y'a sans doute pas mal de processes et de threads qui sont schedulés sur ces même coeurs en plus de ton appli.
Si tes tâches ne sont pas microscopiques, tu ne devrais pas voir de hit de perf dû à l'augmentation de la latence pour récupérer une nouvelle tâche je pense (à mesurer )
En revanche tu seras plus amical avec le reste du système :hippie:

Je suis interessé par le résultat d'ailleurs

[fefe]

Bon le probleme est que la on rentre dans les details d'implementation des locks dont la documentation n'est pas publiee. De maniere generale le probleme vient du fait qu'il faut que l'operation soit atomique pour le software alors qu'elle est implementee par une serie d'instructions par le hardware (qui n'est plus CISC du tout, donc execute uniquement des instructions "simples"). Le fait de le casser en operations simples permet aussi de l'accelerer mais quand on ajoute de la speculation on s'expose a des fonctionnements bien sur moins predictibles.

Un lien vers un article: http://pages.cs.wisc.edu/~rajwar/papers/micro01.pdf
qui devrait permettre de comprendre pourquoi on peut observer certaines variations... Et propose une solution pour les resoudre.

De maniere generale la recommendation de Tramb est la bonne, si tu veux plus de performances, met moins de synchros. L'effet de bord est que le hard ne cherchera pas a devenir meilleur sur ces problemes vu que suffisament rare, et donc conduit au statu quo. L'avantage est que au final tres peu de problemes ne sont solvables qu'avec des synchro tres frequentes.

Sinon j'insiste, si la perf de ton appli est importante sur ce genre de synchros essaye Nehalem .

Sinon le poids de la "Legacy" est tres lourd dans le hard x86, mais je ne crois pas apprendre grand chose a grand monde .