Journal Performances des processeurs Intel et optimisation

Posté par steckdenis (site web personnel) le 14 mai 2013 à 17:11. Licence CC By‑SA.

Étiquettes :

mai

2013

Sommaire

Présentations
- Le processeur
- Le logiciel
Quand ralentir accélère
- La programmation lockless
- Base de donnée lockless
Questions quant à l'optimisation
Notes

Bonjour,

Je préviens d'abord que ce journal aborde des sujets assez pointus et n'intéressant peut-être pas grand-monde. N'étant pas un expert en microprocesseurs et optimisation, ce journal sera très certainement incomplet et incorrect par endroits.

Je vais vous parler d'une aventure très spéciale que j'ai vécue avec mon microprocesseur, alors que je voulais améliorer un morceau de code sur lequel je travaille depuis quelques temps.

Présentations

Je ne pense pas être l'objet central de ce journal, mais pour être complet, je précise tout de même que je suis un étudiant en 2e année de « Sciences Informatiques », comme on appelle ça en Belgique (j'étudie à l'Université Libre de Bruxelles). Le logiciel que je vais décrire est une base de donnée spécifique à un de mes projets personnels, codée en C++.

Le processeur

Intel Core i5 3230M, 35 W
Double coeur avec hyper threading
2,6 Ghz de base, 3,2 Ghz turbo sur un coeur, 3,1 Ghz turbo sur les deux coeurs (mon échantillon maintient cette vitesse toute la journée, chargé à 100%, si je le lui demande)
Cache L1 : 128k (je dirais donc 32k instructions, 32k données par coeur)
Cache L2 : 512k (donc 256k par coeur)
Cache L3 : 3 Mio (partagé par les deux coeurs si je me rappelle bien)

Le tout épaulé par 6 Gio de RAM DDR3 1600 Mhz double canal dans un portable Dell Inspiron 15R Special Edition que je vous recommande d'ailleurs plus que chaudement : j'ai eu le mien à 610€ (promo saisonnière), c'est un 15 pouces avec écran mat FullHD, le processeur que je viens de décrire, et une carte graphique AMD Radeon HD 7720M qui peut s'utiliser en parallèle de la carte Intel via l'équivalent d'Optimus chez AMD qui a l'avantage d'être supporté sous Linux (mais ça consomme beaucoup et il faut chipoter).

Le logiciel

Dans le cadre d'un projet personnel qui n'est pas encore assez avancé pour que j'en parle, j'ai du développer une base de donnée répondant aux critères suivants :

Association de valeurs à des couples (objet, clé) (donc par exemple A.B = C)
Les objets, les attributs et les valeurs sont tous des entiers (donc l'exemple devient 34.128 = 21)
Ça doit être rapide, et par rapide je veux dire capable de lire plusieurs millions de valeurs par seconde (donc toute base de donnée externe, SQL ou non, est disqualifiée)
Scalable (aucun algorithme dont la complexité est non-constante en fonction du nombre d'entrées dans la base n'est accepté)

Ça fait déjà deux ans que je travaille sur le volet base de donnée, même si elle ne pèse que 314 SLOC (source lines of code), et tous ces points sont respectés. Je compte publier cette base de donnée sous licence libre quand tout le projet sera terminé, ou avant, suivant les circonstances et l'intérêt que pourrait avoir une publication à son sujet.

Quand ralentir accélère

Maintenant que toutes ces présentations sont faites, et j'espère ne pas avoir ennuyé trop de monde, je peux passer aux choses sérieuses : les timings.

Jusqu'à il y a peu, la base de donnée était parfaitement fonctionnelle, mais vraiment pensée pour aller le plus vite possible. Par exemple, elle n'était pas thread-safe : si deux threads y accédaient en écriture en même temps, tout pouvait exploser. Dans cet état, la base de donnée lisait 65536*12 = 786432 couples (objet, clé) en 3.7 millisecondes. Cela fait 213 millions de couples (objet, clé) lus par seconde. En comptant que mon processeur passera en mode turbo entre le début et la fin du benchmark, sa fréquence moyenne se situe donc entre 2,6 Ghz et 3,2 Ghz. Le nombre de cycles d'horloge par lecture est donc compris entre 15,0 et 12,2. Pendant ce temps, 12,6 Mio sont lus depuis un fichier mappé en mémoire et stocké dans un tmpfs (ça fait quand-même 3,5 Gio/s, le contrôleur RAM de mon CPU peut lire jusqu'à 25 Gio/s, et le benchmark lit les données assez séquentiellement).

Les valeurs absolues de ces nombres ne sont pas à considérer trop sérieusement, le benchmark étant assez court du fait que la base de donnée doit rester assez petite. L'important sera de voir leur évolution au fil des modifications.

Comme le projet en général aura besoin d'accéder à la base de donnée depuis plusieurs threads, il m'a un jour fallu me rendre à l'évidence que cette base de donnée doit être thread-safe. Comme la base de donnée sera beaucoup plus souvent lue que modifiée (grosso-modo, elle sera lue comme de la mémoire, d'ailleurs c'est un fichier mappé en mémoire), j'ai opté pour un Readers-Writer lock, qui permet à plusieurs lecteurs d'accéder en même temps à la base de donnée, mais qu'à un seul thread d'écriture. Quand une écriture est en cours, il faut qu'aucun lecteur ne soit en train d'accéder à la base de donnée.

En utilisant l'implémentation Posix Threads (bibliothèque pthreads) de ce lock, j'ai eu des performances vraiment mauvaises, mon benchmark prenait de l'ordre de 80 millisecondes pour se compléter. En utilisant une version personnelle de ces locks, optimisée pour mon cas d'utilisation, j'ai pu ramener ce temps à 38 millisecondes environ. Notez bien que le benchmark n'utilise qu'un seul thread ! Il mesure donc le temps perdu dans la gestion du lock alors qu'il n'y a aucune contention.

La programmation lockless

J'ai donc du trouver une autre solution, pour garder ma base de donnée rapide. L'idéal aurait été de faire se compléter le benchmark en entre 3.2 millisecondes et 38 millisecondes, les deux extrémités. J'ai donc passé deux mois à m'intéresser aux algorithmes dits Lockless (c'est assez spartiate).

Le code d'algorithmes lockless n'est pas très compliqué. On programme en fait sans utiliser ni mutex, ni condition d'arrêt, ni rien de ce genre. Un thread ne peut jamais bloquer un autre. La seule chose qu'on fait est coder comme si un seul thread exécuterait le code, tout en sachant qu'ils seront plusieurs. À chaque ligne de code, il faut donc se demander ce qui pourrait se passer si deux threads devaient l'exécuter en même temps.

Pour nous aider, les microprocesseurs x86, ainsi que d'autres sans doutes, disposent d'instructions dites « atomiques ». Par exemple, pour incrémenter une valeur, il faut lire l'ancienne valeur, lui ajouter 1, puis écrire la nouvelle valeur. Deux threads peuvent lire en même temps l'ancienne valeur, l'incrémenter en même temps (ils obtiennent tous les deux la même nouvelle valeur), et l'écrire tous les deux. Au final, la valeur n'aura été incrémentée que de 1, et non de deux. Il existe néanmoins une instruction d'incrément atomique, qui bloquera l'accès à la variable par les autres threads (ou processeurs dans ce cas-ci) tant que l'incrément n'est pas complet.

Ces instructions sont accessibles avec GCC et Clang en utilisant les fonctions de la famille __sync. Par exemple, pour incrémenter une variable atomiquement, je peux faire

int var = 0;

int incrementer()
{
    return __sync_fetch_and_add(&var, 1);  // Retourne la valeur précédente de var
}

Si var permet d'indicer un tableau, plein de threads peuvent appeler cette fonction incrementer() en même temps, et ils vont tous recevoir une case différente du tableau, dans laquelle ils pourront écrire ce qu'ils veulent.

Base de donnée lockless

J'ai donc truffé mon code de fonctions __sync. J'attire bien votre attention sur le fait que je n'ai fait que rajouter du code. J'ai changé des variable++ en __sync_fetch_and_add(&variable, 1), et j'ai rajouté des boucles (par exemple : exécuter quelque-chose, voir si un autre thread ne nous est pas passé sous le nez, et recommencer si c'est le cas).

Après avoir beaucoup réfléchi, noté, transpiré, relu et testé (quand c'était possible), j'ai finalement obtenu une base de donnée qui marche et qui ne plante pas quand on y accède depuis plusieurs threads. Ne va-t-elle jamais planter ? Je ne sais pas, la programmation lockless n'est pas supportée par des choses comme helgrind, et je n'ai pas les compétences pour prouver qu'il n'y aura jamais le moindre problème. Je me suis donc juste assuré que je pouvais laisser tourner mes tests pendant des heures sans qu'ils ne plantent.

Les performances ? Et bien, il faut 1.66 millisecondes pour compléter le benchmark, 474 millions de valeurs lues à la seconde, 6 cycles d'horloge par valeur. Là maintenant, vous comprenez ce qui m'a motivé à écrire ce journal : en rajoutant du code, des instructions lourdes, qui synchronisent les coeurs de mon CPU, j'ai drastiquement accéléré mon benchmark, alors même qu'il n'est que mono-thread et qu'il aurait donc du ralentir à cause de ces nouvelles instructions !

Questions quant à l'optimisation

Cette accélération de ma base de donnée, qui tourne maintenant deux fois plus vite, mais fait quand-même me poser des questions quant à l'optimisation logicielle. J'ai regardé le code assembleur généré par GCC 4.8, et les différences sont minimes (instructions remplacées par d'autres normalement plus lentes, ajout d'instructions). Même l'alignement de mon code est toujours le même. Aucune structure de donnée n'a changé.

Je me demande donc comment ça se fait qu'ajouter ces instructions accélère le code à ce point. Surtout que mon benchmark se porte sur la lecture de la base de donnée, c'est à dire quelque-chose auquel je n'ai quasiment pas touché, les synchronisations entre threads ne s'appliquant que quand on écrit. Donc mes modifications, au lieu de ralentir ou de laisser tel quel un code auquel je n'ai quasiment pas touché, l'ont en fait drastiquement accélérer.

Les processeurs modernes sont très complexes, d'ailleurs mon i5 a vraiment des performances époustouflantes sur certains points (j'ai indiqué plus haut que mon benchmark nécessite 13 cycles d'horloge par lecture sur ce CPU, alors qu'il en fallait 40 sur un AMD E-350 plus lent), est-il donc encore possible d'optimiser pour eux ? Si ça se trouve, ces instructions permettent au processeur de mieux gérer sa mémoire cache, ou alors on évite des latences, ou alors le processeur exécute des choses en avance (vu que le code gère maintenant tous ces cas bizarres de modifications parallèles).

Je n'en sais rien donc rien, et j'invite toute personne ayant une idée de ce qui peut se passer à laisser un commentaire. Je me demande également si les compilateurs ne pourraient pas un jour tirer parti de ces bizarreries, surtout quand on voit les gains obtenus.

Notes

Tous les tests ont été réalisés avec le gouverneur cpufreq « userspace » et la fréquence du processeur fixée à 2,6 Ghz. La documentation d'Intel indique que cette fréquence, la maximum possible, peut être augmentée vers la fréquence turbo. Cela arrive après un court délai qui semble néanmoins plus long que le temps que met le benchmark pour s'exécuter, car l'utilitaire turbostat n'indique aucun passage en fréquence turbo lors des benchmarks. J'ai également re-fait les tests avec la fréquence calée sur 2,5 Ghz, et les durées sont à peine plus longue, et toujours dans le même rapport.

Niveau précision, j'utilise gettimeofday, qui retourne des valeurs en microsecondes. Quelques tests montrent que mon ordinateur peut mesurer des temps précis de l'ordre de la milliseconde ou du dixième de milliseconde. Plusieurs itérations du benchmark sont bien entendu exécutées, et la moyenne des résultats est prise. L'écart-type n'est jamais grand, mes tests donnent par exemple 1.666 msec, 1.668 msec, 1.663 msec, 1.699 msec, 1.667 msec, etc.

Pour ceux qui se demandent à juste titre comment je peux lire une base de donnée en 10 cycles d'horloge : la base de donnée a été pensée pour que la lecture soit grosso-modo équivalente à cette ligne de C :

int get(int **db, int object, int key)
{
    return db[object][key];
}

# y'a trop peu d'infos pour t'aider.

Posté par Nicolas Boulay (site web personnel) le 14 mai 2013 à 17:24. Évalué à 10.

Il faudrait tes fameux 314 SLOC pour te répondre. De mon coté, j'aurais fait un arbre 256-aire avec un read-modify-write sur le noeud écrit pour être sans lock.

Concernant le mesure du temps, il vaut mieux utiliser l'instruction rdtsc qui rend un nombre de cycles d'horloge (bidouillé pour que cela ne voit pas trop en cas de changement de vitesse de proc car des andouilles partaient du principe que la fréquence est fixe). https://fr.wikipedia.org/wiki/RDTSC attention pour le printf, c'est un nombre 64 bits.

"La première sécurité est la liberté"
- [^] # Re: y'a trop peu d'infos pour t'aider.
  
  Posté par ckyl le 14 mai 2013 à 17:48. Évalué à 10.
  
  Il faudrait tes fameux 314 SLOC pour te répondre.
  
  Idem. Trop de blabla et de moussage, pas assez de code.
  - [^] # Re: y'a trop peu d'infos pour t'aider.
    
    Posté par steckdenis (site web personnel) le 14 mai 2013 à 21:17. Évalué à 2.
    
    Je suis tout à fait d'accord.
    
    Le problème est que je viens de rendre cette base de donnée thread-safe, donc utilisable. J'ai encore corrigé un bug juste avant de poster ce journal. Je n'ai donc pas encore vraiment eu le temps de réfléchir à la distribution de cette base de donnée.
    
    L'idéal serait d'en faire profiter tout le monde avec une licence BSD (la plupart de mes projets sont en GPL, mais pour les composants bas-niveaux, j'aime la BSD, mais c'est une autre affaire). Néanmoins, j'aimerais d'abord avoir quelques retour quant à l'intérêt qu'auraient quelques explications supplémentaires quant aux algorithmes et structures de données utilisées. Ça peut peut-être paraître bête, mais c'est quand-même deux ans de réflexion, donc soit je suis particulièrement lent, soit ça vaut la peine que j'explique bien comment tout fonctionne.
    
    Je comptais donc publier un « papier » au sujet de cette base de donnée. Par papier, j'entends un PDF disponible quelque-part et bien fait, ce serait je trouve un bon exercice sachant que je veux m'orienter vers une carrière de chercheur. Après, si quelqu'un veut réellement le publier au sens propre du terme, pas de problème, mais ce n'est pas le but.
    
    En attendant plus de retours sur cet éventuel papier, et pendant les prochains jours, je préfère être plutôt trop prudent que trop peu. C'est en effet un monde que je ne connais pas, et j'invite d'ailleurs toute personne renseignée sur le monde de la recherche, si elle le désire, à me ou nous faire part de ce qu'elle connaît du domaine et des bonnes pratiques qui s'y appliquent.
    - [^] # Re: y'a trop peu d'infos pour t'aider.
      
      Posté par ckyl le 14 mai 2013 à 21:31. Évalué à 2.
      
      Quel intérêt donc hormis t'écouter parler ? Si tu n'as rien ou ne veut rien montrer, il suffit de ne rien dire.
      
      Poser des questions sur des micro-optimisations (soit dit au passage très certainement inutiles par ce que sur une workload réelle ce sont les caches miss qui vont rapidement te couter cher et le reste qui ne suivra pas) sans publier du code concret, le bench et la méthodologie c'est prendre son temps. Soit tu montres ton code, soit tu sors des exemples auto-contenus. Mais sans ca, c'est un peu pisser dans un violon.
      - [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par steckdenis (site web personnel) le 14 mai 2013 à 21:56. Évalué à 2.
        
        J'ai posté le journal au cas où quelqu'un aurait eu une réponse indépendante de l'implémentation exacte du code, par exemple « les instructions atomiques indiquent au processeur ce que tu veux faire, et donc il ne se trompe pas dans ses prédictions ». D'ailleurs, ce genre de truc serait bien possible, car Intel cite dans sa documentation sur PAUSE, une instruction qui ne fait rien :
        
        Improves the performance of spin-wait loops. When executing a “spin-wait loop,” processors will suffer a severe
        performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE
        instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint
        to avoid the memory order violation in most situations, which greatly improves processor performance. For this
        reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.
        
        L'emphase est de moi. Certaines instructions qui semblent donc ralentir le code peuvent l'accélérer.
        
        Maintenant, je me rend bien compte que le problème peut être beaucoup plus proche de mon code que ce que je pensais (le but du journal était grosso-modo de dire « un machin qui prenait 3 ms en prend maintenant 1,6 alors que j'ai ajouté des instructions atomiques »). D'ailleurs, en corrigeant un bug, j'ai modifié une ligne de code qui n'est jamais exécutée par mon benchmark (ni dans la partie écriture, ni dans la lecture), et il a accéléré.
        
        Si ça se trouve, c'est donc simplement une histoire d'alignement de code, qui entre peut-être en conflit de ligne de cache avec mes données. Si mon benchmark passe son temps à accéder à un certain endroit de la base de donnée, en vidant la ligne de cache qui contenait justement les instructions pour effectuer cet accès, alors il est lent. Peut-être qu'ajouter ces instructions a simplement décalé une partie de code ou un accès au donnée, et le conflit n'a plus lieu.
        
        En tous cas, ce serait chouette que ce genre de phénomène soit documenté pour qu'un compilateur puisse choisir où il place ses fonctions pour qu'elles ne soient pas évincées du cache.
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par Gof (site web personnel) le 14 mai 2013 à 23:19. Évalué à 4.
        
        Donne nous les sources d'un vrai benchmark répétable. Sans ça j'ai du mal à te croire, les instruction atomique sont beaucoup plus lente que les instructions non atomiques.
        Es-tu sur que le code est exactmenent le même et que tu n'as pas changé la signification ?
        Les options de compile sont elles bien les même (avec les optimisations activées) ?
        
        P.S.: Ce n'est pas __sync_* qu'il faut utiliser, mais std::atomic
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par MrLapinot (site web personnel) le 15 mai 2013 à 11:32. Évalué à 4.
        
        Sauf qu'une boucle spin-wait, ça n'a de sens que quand tu utilises plusieurs processeurs. Mais effectivement, on pourrait imaginer que le l'algorithme de prédiction des branches tire parti de ces instructions (même si je ne vois pas vraiment comment).
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par Gof (site web personnel) le 15 mai 2013 à 12:39. Évalué à 4.
        
        Le spin-wait a très rarement « du sens ». (en userspace sous linux)
- [^] # Re: y'a trop peu d'infos pour t'aider.
  
  Posté par grim7reaper le 14 mai 2013 à 18:06. Évalué à 7. Dernière modification le 14 mai 2013 à 18:07.
  Mouais, vaut quand même mieux éviter RDTSC sur du multicore si on veut un truc fiable.
  This use of RDTSC for timing suffers from these fundamental issues:
  - Discontinuous values. Using RDTSC directly assumes that the thread is always running on the same processor. Multiprocessor and dual-core systems do not guarantee synchronization of their cycle counters between cores. This is exacerbated when combined with modern power management technologies that idle and restore various cores at different times, which results in the cores typically being out of synchronization. For an application, this generally results in glitches or in potential crashes as the thread jumps between the processors and gets timing values that result in large deltas, negative deltas, or halted timing.
  - Availability of dedicated hardware. RDTSC locks the timing information that the application requests to the processor's cycle counter. For many years this was the best way to get high-precision timing information, but newer motherboards are now including dedicated timing devices which provide high-resolution timing information without the drawbacks of RDTSC.
  - Variability of the CPU's frequency. The assumption is often made that the frequency of the CPU is fixed for the life of the program. However, with modern power management technologies, this is an incorrect assumption. While initially limited to laptop computers and other mobile devices, technology that changes the frequency of the CPU is in use in many high-end desktop PCs; disabling its function to maintain a consistent frequency is generally not acceptable to users.
  Source.
  
  De même, le coup du gettimeofday je ne suis pas sûr qu’il soit très multicore proof (à vérifier).
  Je partirais plus sur un coup de clock_gettime(CLOCKMONOTONIC_RAW)_
  
  Et encore…
  
  If the CPUs in an SMP system have different clock sources then there is no way to maintain a correlation between the timer registers since each CPU will run at a slightly different frequency. If that is the case then clock_getcpuclockid(0) will return ENOENT to signify this condition. The two clocks will then only be useful if it can be ensured that a process stays on a certain CPU.
  
  The processors in an SMP system do not start all at exactly the same time and therefore the timer registers are typically running at an offset. Some architectures include code that attempts to limit these offsets on bootup. However, the code cannot guarantee to accurately tune the offsets. Glibc contains no provisions to deal with these offsets (unlike the Linux Kernel). Typically these offsets are small and therefore the effects may be negligible in most cases.
  
  Source: page de man de clock_gettime
  
  Au final, faudrait peut-être partir sur HPET pour avoir un timing cohérent (à vérifier).
  
  À part ça, je plussoie les deux commentaires précédents.
  - [^] # Re: y'a trop peu d'infos pour t'aider.
    
    Posté par lasher le 14 mai 2013 à 19:49. Évalué à 3.
    
    clock_gettime() est la bonne fonction à appeler en effet. Avec l'option CLOCK_REALTIME si je me souviens bien.
    
    En pratique sur un mono-socket multi-cœur comme décrit pas steckdenis, RDTSC reste OK.
    
    Une autre façon de mesurer (avec rdtsc ou clock_gettime ou gettimeofday …) est simplement d'enrober le programme dans un thread que tu forces à s'exécuter sur un cœur donné, et lui laisser le soin d'appeler le reste du programme. Ensuite, tu peux utiliser des trucs genre pthread_barrier_* ou autres machins faits maison pour garantir que tous les threads sont synchronisés puis reprendre la mesure depuis le threads « launcher ».
    - [^] # Re: y'a trop peu d'infos pour t'aider.
      
      Posté par ckyl le 14 mai 2013 à 20:26. Évalué à 2.
      
      clock_gettime() est la bonne fonction à appeler en effet. Avec l'option CLOCK_REALTIME si je me souviens bien.
      
      La seule différente entre clock_gettime(CLOCK_REALTIME) et gettimeofday c'est la perte de précision entre le timespec qui est en nsec et le timeval qui est en msec et fais un: tv->tv_usec /= 1000;
      
      Faut faire pas mal gaffe en descendant à ces précisions car ca devient difficile de mesurer quelque chose.
      
      Le coup du taskset est en effet une bonne idée pour les benchs mais aussi pour dispatcher manuellement le code métier. Le scheduler reste mauvais sur l'affinité, et c'est pas rare de gratter 10-30% de perf la dessus plutôt que laisser les threads se balader…
      - [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par barmic le 14 mai 2013 à 23:49. Évalué à 4.
        
        Faut faire pas mal gaffe en descendant à ces précisions car ca devient difficile de mesurer quelque chose.
        
        À mon humble avis descendre sur des temps aussi bas c'est du bullshit. Les variations deviennent trop importantes, etc.
        
        Déjà que le benchmark ne semble pas particulièrement révélateur (aucune écriture, pas de concurrence), il faudrait à mon humble avis augmenter les volumes pour obtenir des résultat plus fiables.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par ckyl le 14 mai 2013 à 23:57. Évalué à 6.
        
        Déjà que le benchmark ne semble pas particulièrement révélateur
        
        Bha c'est un truc à la steckdenis… Ca n'empêche pas d'avoir des échanges intéressant et en ne cherchant par trop le pourquoi du comment de la question originale ;)
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par lasher le 15 mai 2013 à 01:37. Évalué à 8.
        
        Tu as tort. Utiliser rdtsc est parfaitement logique surtout si ton bench prend peu de temps (après tout, les risques de modification de fréquence sont bien moindres). Ça n'empêche pas qu'il faut une certain stabilité. Généralement lorsque je fais des micro-benchmarks, j'utilise un truc du genre:
        
        for ( outer = 0; outer < MAX_OUTER; ++outer) { FLUSH_CACHES(); #if OBSERVE_IN_CACHE_BEHAVIOR run_kernel(); // warm up caches #endif uint64_t exec_time = read_rdtsc(); for (inner = 0; inner < MAX_INNER; ++inner) { run_kernel(); } exec_times[outer] = (double) (read_rdtsc() - exec_time) / MAX_INNER; } /* ... */ /* exec_times[] contient un « histogramme » des différentes exécutions */ REMOVE_OUTLIERS(exec_times,MAX_OUTER); // supprime les temps les plus courts et les plus longs en fonction de lubies statistiques COMPUTE_MEAN(exec_times, MAX_OUTER); // arithmétique, harmonique, etc., en fonction des besoins
        
        Note que MAX_INNER/MAX_OUTER peuvent être extrêmement petits dans le cas de microbenchmarks, surtout si l'environnement de benchmarking permet de fixer un thread sur un cœur donné : on évite les variations dues à l'ordonnanceur qui est moins con qu'avant, mais qui va quand même réordonnancer certains threads pour les remettre sur le même cœur juste après… mais avec des caches et TLB qui ont eu droit à des entrées évincées.
        
        Maintenant ce que j'appelle « micro-benchmarks », ce sont vraiment de minuscules benchs, où je teste un sous-système de mon micro-processeur. Genre je veux tester la latence réelle de mon cache L3 partagé : je vais faire tourner 4 threads en parallèle sur mon core i7, un par cœur. Ensuite je vais m'assurer que chaque thread copie un mot de 64 bits dans un registre, puis copie le (i+8×k)è mot dans le même registre à l'itération suivante, etc. J'ai besoin de faire i+8×k car les prefetchers des archis x86 ont tendance à rapatrier la ligne de cache adjacente lors d'un défaut de cache. Du coup il faut précharger au moins tous les 16 mots. L'autre problème étant que, au moins pour les micro-archis Intel, il existe un « stride préfetcher » (« préchargeur de distance » ? je ne sais pas comment traduire). Il détecte tout seul comme un grand si la distance entre deux mots mémoire est fixe. Si c'est le cas, il va précharger les mots mémoire suivants sans qu'on lui demande quoi que ce soit (dans la limite d'une page mémoire, donc pas au-delà de 4096 octets). Du coup il faut faire son sioux, et précharger un mot aléatoire dans la ligne de cache « suivante ».
        
        Soupir…
        
        Désolé pour le HS complet. J'ai pas pu m'empêcher. :)
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par barmic le 15 mai 2013 à 09:00. Évalué à 1.
        
        Note que MAX_INNER/MAX_OUTER peuvent être extrêmement petits dans le cas de microbenchmarks […]
        
        Tu rate tous les éventuels effets qui apparaissent lors de la charge notamment lorsque celle-ci est prolongée. Ça permet éventuellement (mais faut prendre des pincettes) de comparer de très courts algorithmes (quand on arrive pas à en évaluer la complexité), mais c'est tout. Tu n'a aucune idée des performances réelles de quoi que ce soit. Parce que dans la vrai vie (en prod) l’ordonnanceur sera là pour te les briser, la CPU agira en fonction de sa configuration (changement des différentes fréquences), etc.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par barmic le 15 mai 2013 à 09:07. Évalué à 2.
        
        Ça permet éventuellement (mais faut prendre des pincettes) de comparer de très courts algorithmes (quand on arrive pas à en évaluer la complexité) […]
        
        Du coup les valeurs on s'en fout un peu, ce sont des indices qui n'ont pas de sens hors de comparaison.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 09:36. Évalué à 3.
        
        Il ne faut pas faire des boucles pour augmenter les chiffres. Sur tout les benchs que j'ai fait, j'ai observé un ramp-up des performances, entre la 1er, la deuxième et la 3ième exécution d'un même code. La meilleur façon de faire de mon point de vue est de tracer des courbes, tu imprimes le temps d’exécution de chaque itération, ainsi tu peux comparer en repérant les anomalies et les patterns (très amusant à faire sur un malloc par exemple, ou on repère facilement 3 branches de code).
        
        "La première sécurité est la liberté"
- [^] # Re: y'a trop peu d'infos pour t'aider.
  
  Posté par Narishma Jahar le 14 mai 2013 à 18:16. Évalué à 4.
  
  Concernant le mesure du temps, il vaut mieux utiliser l'instruction rdtsc qui rend un nombre de cycles d'horloge (bidouillé pour que cela ne voit pas trop en cas de changement de vitesse de proc car des andouilles partaient du principe que la fréquence est fixe).
  
  A moins que ton processeur n'ait qu'un seul coeur, un seul thread, une fréquence fixe et qu'il ne soit pas capable d'entrer en veille, je dirais qu'il vaut mieux éviter cette instruction à tout prix vu le nombre de façons différentes qu'elle a de donner des résultats erronés.
  - [^] # Re: y'a trop peu d'infos pour t'aider.
    
    Posté par Troy McClure (site web personnel) le 14 mai 2013 à 22:21. Évalué à 2.
    
    Bof a l'usage moi je la trouve très fiable, et beaucoup moins couteuse que tous les appels a clock_gettime ou QueryPerformanceCounter et cie qui ont vite fait de plomber les perfs. Dans mon expérience le seul cas où ça a semblé faire de la merde à uné époque c'était sur certains athlons x2, et sur ces machines le QueryPerformanceCounter souffrait du meme bug (perte de synchro des compteurs entre les coeurs, je crois que maintenant tous les os font le necessaire pour que ça n'arrive plus).
    - [^] # Re: y'a trop peu d'infos pour t'aider.
      
      Posté par lasher le 15 mai 2013 à 01:42. Évalué à 5.
      
      Mon expérience sur du multicœur un peu massif (AMD Bulldozer/Interlagos 48 cœurs en mémoire partagée, NUMA, 4×12 cœurs) est contraire à la tienne. Tant qu'il n'y avait pas de frequency scaling et un FSB (sur archi Intel Core 2/Core 2 Quad), tout allait bien en utilisant la bonne version de rdtsc. Le moment où tu as de la variation dynamique de tension et de fréquence, avec en plus plusieurs processeurs reliés entre eux par un réseau d'interconnexion souvent un peu douteux, j'ai appris à mes dépends que rdtsc passait à la trappe (j'ai eu plusieurs fois droit à des comportements très étranges où je me trouvait au final avec un temps négatif, malgré mes précautions …).
  - [^] # Re: y'a trop peu d'infos pour t'aider.
    
    Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 14:00. Évalué à 4.
    
    C'est un "free running counter" par cpu. Cela veut dire que si on change de cpu, il peut y a voir un shift. Intel pour les crétins qu'il l'utilise comme horloge fixe l'a sorti du domaine de fréquence variable, pour le coller à une horloge fixe : donc cela ne correspond plus vraiment à un nombre de cycle et plus à du temps à l'échelle de l'instruction.
    
    Dans le cas de mesure courte, il y a peu de chance que l'os foute le bordel dans la mesure. C'est 2 instructions super légères.
    
    En général, je colle des résultats dans un tableau, que je print ensuite pour faire une jolie courbe dans un tableur. C'est facile de voir les valeurs "à la con", les pattern, les extrêmes. Faire une boucle pour atteindre un pas de temps mesurable pour les autres fonctions te donnes une sorte de borne supérieurs du code, car les caches sont "archi chauds". Cela te donne peu d'info sur la vitesse réelle dans ton code, ni la vitesse minimum.
    
    "La première sécurité est la liberté"
- [^] # Re: y'a trop peu d'infos pour t'aider.
  
  Posté par ckyl le 14 mai 2013 à 18:39. Évalué à 4. Dernière modification le 14 mai 2013 à 18:42.
  
  Concernant le mesure du temps, il vaut mieux utiliser l'instruction rdtsc qui rend un nombre de cycles d'horloge
  
  Il y a une raison particulière part rapport à un gettimeofday moderne qui s'occupe de gérer tout le bordel TSC/HPET pour pas cher avec une résolution exportée assez correcte ? On peut arriver aux limites de la résolution si on veut mesurer quelque chose d'extrêmement précis, mais là à priori il suffit de faire durer le bench le temps qu'il faut.
  - [^] # Re: y'a trop peu d'infos pour t'aider.
    
    Posté par grim7reaper le 14 mai 2013 à 18:49. Évalué à 1.
    
    Suffit de lire le man :
    
    The time returned by gettimeofday(2) is affected by discontinuous jumps in the system time (e.g., if the system administrator manually changes the system time). If you need a monotonically increasing clock, see clock_gettime(2).
    - [^] # Re: y'a trop peu d'infos pour t'aider.
      
      Posté par ckyl le 14 mai 2013 à 19:01. Évalué à 4. Dernière modification le 14 mai 2013 à 19:03.
      
      Le point que tu donnes on s'en balance dans un cas comme ca. On est en train de faire des benchs à vie courte !
      
      Maintenant si tu regardes le code qui est exécuté pour gettimeofday, ou clock_gettime, je ne vois des masses que je pourrais faire mieux en écrivant mon propre code sauf besoin extrêment spécifique qui mérite qu'on prenne le risque de faire n'importe quoi. Maintenant puisque tu insistes sur le monotonic, si je compare do_monotonic avec do_realtime je ne vois pas en quoi ca change quoi que ce soit pour notre problème actuel. La différence c'est juste un offset appliqué par update_vsyscall quand les valeurs de base de vsyscall_gtod_data sont mises à jour.
      
      Rappelons que ces fonctions sont mappées dans la page vdso par le kernel dans l'espace utilisateur de chaque process et donc que le coût d'appel à ces syscall à exactement le même qu'a une fonction userspace normale.
      
      Je peux me tromper, je ne suis qu'un oeil naïf. Mais en réfléchissant au problème et à l'implémentation actuelle je ne vois pas de raison d'aller voir ailleurs.
      - [^] # Re: y'a trop peu d'infos pour t'aider.
        
        Posté par lasher le 11 juin 2013 à 15:38. Évalué à 2.
        
        Perso j'utilise/utilisais rdtsc parce que ca me permet d'avoir un nombre de cycles plutot qu'un nombre de nanosecondes. C'est important, car j'etais reellement au cycle pres, et que certains effets dus aux latences/debits memoire peuvent influer sur la performance finale (par ex: un processeur a 1GHz avec un bus a "1333MHz", la latence pour acceder a la memoire sera minime, alors que pour le meme bus memoire avec un proc. a 3GHz, les latences auront triple).
- [^] # Re: y'a trop peu d'infos pour t'aider.
  
  Posté par khivapia le 14 mai 2013 à 18:55. Évalué à 2.
  
  Concernant le mesure du temps
  Le mieux est sans conteste la fonction omp_get_wtime() (précis, efficace). Par contre il faut un compilateur qui supporte OpenMP.
# Magnifique

Posté par bubar🦥 (Mastodon) le 14 mai 2013 à 18:07. Évalué à 10. Dernière modification le 14 mai 2013 à 18:08.

Merci pour journal, ça faisait longtemps qu'on n'avait pas eu le plaisir de te lire, SteckDenis ;
Parce que c'est toujours abordable, compréhensible et intéressant pour tous ;
Et là, tes «aventures avec ton micro-processeur» tombent à pic pour la prochaine dépêche sur le prochain noyau :-)
Bref, passionnant :-) (au plaisir de lire des commentaires + instructifs que celui-ci, maintenant)
# En pire hic

Posté par fcartegnie le 14 mai 2013 à 18:11. Évalué à -9.

je n'ai pas les compétences pour prouver qu'il n'y aura jamais le moindre problème. Je me suis donc juste assuré que je pouvais laisser tourner mes tests pendant des heures sans qu'ils ne plantent.

Tu devrais proposer ta méthode pour démontrer certaines conjonctures mathématiques alors…
# Ai-je bien compris ?

Posté par Guillaum (site web personnel) le 14 mai 2013 à 19:29. Évalué à 10.

En fait, si j'ai bien compris, tu compares un code pas thread-safe à un code thread-safe et tu en conclue que le thread-safe va plus vite alors qu'il est en théorie plus lourd (i.e.: instruction atomiques).

Hum… Et il se passe quoi si dans ta boucle pas thread-safe qui compte le nombre d'essais tu saute un increment ? Et bien le pas thread-safe va faire un tour de boucle de plus, donc il sera plus lent (mais bon, c'est bugé).

Donc soit j'ai raté une étape, soit ton bench n'a pas de sens ?

Ce qu'il faudrait que tu fasses c'est mesurer le temps en sinle core avec la version pas thread safe et mesurer le temps en multi-core avec la version thread safe, tu auras ainsi une idée du cout de la synchronisation.

ou

Faire une version thread-safe lourde et comparer avec la thread safe légère.

Note que les instructions atomique sont optimistes (au contraire des instructions lourdes genre verrous et autre qui sont pessimistes). Cela signifie que tes instructions atomiques supposent que les choses se passent bien (et coûtent du temps quand les choses se passent mal).
Alors qu'un verrou fait l'inverse. Quand cela se passe bien, il coûte du temps, quand cela se passe mal, il coûte le même temps.

En gros, si tu as beaucoup d'accès partagés sur une variable, cela peu valoir le coup de mettre un vrai mutex. Si dans l'autre main tu as peu d'accès partagés, un atomique est génial (en utilisant au maximum les atomiqueInc/Dec contrairement au CompareAndSwap qui sont plus lent).

Dernièrement, je n'ai pas accès à ton code, mais il peut être intéressant de regarder sur quelles lignes de cache sont les données partagées. En effet, si elles sont sur des lignes identiques, un atomique sur un ligne va faire échouer toutes les variables atomiques de la ligne. Cela peut donc valoir le coup de mettre cela sur des lignes différentes.

tl;dr; Le benchmark me semble pourri par définition, il compare du code buggé a du code non bugé (ou j'ai raté une étape)
- [^] # Re: Ai-je bien compris ?
  
  Posté par lasher le 14 mai 2013 à 20:52. Évalué à 10.
  Je suis d'accord en ce que la méthodologie me semble peu rigoureuse. Mais en même temps, on peut sans doute faire en sorte de l'améliorer ! :-)
  
  Ta suggestion de faire tout tourner sur un seul cœur les deux versions est à mon avis excellente : même s'il y a une race condition, les effets de bords ne seront pas réellement « visibles » dans le cas non thread-safe.
  
  Les instructions atomiques sont certes plus lentes que des instructions normales, mais elles ont aussi quelques avantages/propriétés. Je vais en citer quelques uns:
  1. Une instruction atomique sur x86 actuel (donc Core i5) effectue les opérations suivantes : load-modify-write. Pendant que ceci s'opère, le processeur verrouille la ligne contenant le mot à modifier, et souvent aussi le bus mémoire du cœur qui effectue la modification: le mot est chargé dans un registre, modifié/comparé en utilisant une des UAL du cœur qui a effectué l'op atomique, puis stocké à nouveau en mémoire.
  2. Au sein d'un même processeur multi-cœur, lorsqu'on utilise une instruction atomique, seule la ligne de cache qui contient la donnée accédée est verrouillée. Ce qui est important avec ce constat, c'est que le cache lui-même n'est pas complètement verrouillé, et aussi qu'il n'y a pas « d'écriture retour » (write-back) vers la DRAM automatiquement après exécution d'une instruction atomique. Bref, il y a bien sérialisation des écritures/lectures sur une ligne de cache donnée, mais pas sur le bloc/niveau de cache complet (ce qui se faisait à une époque, le bus étant complètement verrouillé pour ce niveau de cache tant que l'op atomique avait lieu).
  3. Si jamais tu n'utilises pas d'instruction atomique pour accéder à un mot partagé par plusieurs threads, et que ce mot n'est pas « isolé » tout seul sur sa ligne de cache, tu risques de provoquer un phénomène de faux partage (false sharing), c'est-à-dire que le mot est modifié et du coup indique que la ligne entière est modifiée. Si par hasard d'autres données étaient utilisées en lecture ou écriture par un autre thread sur un autre cœur (en L2 par ex), la ligne devient marquée invalide alors qu'en fait c'était pas le cas. Je ne sais pas si c'est ce qui se passe, mais il arrive qu'en induisant des délais supplémentaire, une opération « lisse » les effets de contention sur un certain composant mémoire (je ne sais pas si je suis clair).
  Dans tous les cas, comme on te le faisait remarquer plus haut, si tu ne fournis pas ton code, on ne peut que spéculer.
- [^] # Re: Ai-je bien compris ?
  
  Posté par steckdenis (site web personnel) le 14 mai 2013 à 21:04. Évalué à 3.
  Bonjour,
  
  En fait, le programme qui fait le benchmark n'utilise qu'un thread. La version pas thread-safe de la base de donnée, donc sans les instructions atomiques, s'exécute correctement car un seul thread accède à la base de donnée. La version thread-safe de la base de donnée est aussi utilisée par ce même unique thread.
  
  C'est comme si je comparais ces deux fonctions :
```
void thread_safe(int *ptr)
{
    __sync_fetch_and_add(ptr, 1);
}

void not_thread_safe(int *ptr)
{
    *ptr += 1;
}

#define BENCHMARK_TYPE SAFE

void benchmark()
{
    volatile int var = 0;

    for (unsigned int i=0; i<BENCHMARK_ITERATIONS; ++i)
    {
#if BENCHMARK_TYPE == SAGE
        thread_safe(&var);
#else
        not_thread_safe(&var);
#endif
    }

    assert(var == BENCHMARK_ITERATIONS);
}
```
  Le benchmark ne teste donc pas la validité de l'implémentation (c'est testé par des tests unitaires dédiés), mais seulement sa rapidité, en mono-thread. Cela permet donc d'évaluer l'overhead des instructions atomiques, qui est ici négatif, ce qui est surprenant.
  
  Après, c'est vrai que la base de donnée non thread-safe est « buguée » si on veut l'utiliser en mode thread-safe, mais elle reste parfaitement utilisable par un programme qui aurait une base de donnée propre par thread, ou qui serait mono-thread, ou qui protégerait lui-même les accès par un mutex.
  
  Pour ce qui est des lignes de cache, toutes les opérations atomiques portent sur des adresses mémoires différentes (il n'y a pas de lock global, tout est de grain fin). Les objets stockés dans la base de donnée font 16 octets, il y en a donc 4 par ligne de cache de 64 octets. C'est en effet un problème quand on accède à des objets proches l'un de l'autre, je verrai avec le temps si cela pose problème et si je dois ajouter des zéros à la fin de mes objets pour qu'ils fassent 64 octets et soient alignés avec le cache.
  - [^] # Re: Ai-je bien compris ?
    
    Posté par ribwund le 14 mai 2013 à 21:23. Évalué à 2. Dernière modification le 14 mai 2013 à 21:23.
    
    Si c'est ça ton benchmark je sais pas ce que ça vaut (dejà volatile je sais pas ce qu'il fait la, je pense pas que ça force l'ecriture en mémoire). Faudrait regarder l'assembleur mais y'a des chances qui le compilo optimise très aggressivement , fasse de l'inlining et enleve les acces memoires.
    - [^] # Re: Ai-je bien compris ?
      
      Posté par steckdenis (site web personnel) le 14 mai 2013 à 21:46. Évalué à -1.
      J'ai regardé le code assembleur et ma méthode Database::get est bien présente dans le fichier objet, et appelée le bon nombre de fois (callgrind confirme). Le benchmark ne portant que sur la lecture de la base de donnée, la seule chose qui peut arriver est que la base de donnée tienne dans le cache du processeur. Des parties peuvent être contenues dans ce cache (qui fait 3 Mio), mais pas tout, la base de donnée fait 12 Mio.
      
      Entre la version non thread-safe et la version thread-safe, le seul code qui change au niveau de la lecture de la base de donnée (testée dans le benchmark) est l'ajout de ceci :
      
      void PerThreadAccess::enterDatabase() { while (true) { _db_accessed = true; store_fence(); if (_db_access_allowed) { break; } else { // Waiting for the db to be accessible is a very long operation // (the database file has to be remapped, pagefaults may occur, etc) // Don't spin, but yield the processor to an useful thread _db_accessed = false; store_fence(); while (!_db_access_allowed) sched_yield(); } } } void PerThreadAccess::leaveDatabase() { _db_accessed = false; }
      
      Ces deux méthodes sont appelées juste avant et juste après la lecture. store_fence() est une méthode inline qui exécute l'instruction assembleur sfence, qui garanti qu'aucune lecture après cette instruction (donc de la base de donnée, et surtout de _db_access_allowed) n'aura lieu avant que l'écriture de _db_accessed soit visible par tous les autres coeurs de la machine. Le code assembleur contient bien toutes les instructions nécessaires, donc l'inlining, bien qu'agressif (c'est pour ça qu'on utilise un compilateur, surtout que j'ai tout compilé en LTO), n'a pas modifié le comportement du programme.
      
      Ce bout de code vient du fait que dans de très rares cas, tous les accès à la base de donnée doivent être suspendus (aussi bien en lecture qu'en écriture). En effet, quand la base de donnée devient trop petite pour ce qu'on veut y stocker, il faut agrandir le fichier, et le re-mapper. Re-mapper le fichier va très probablement invalider tous les pointeurs vers ce fichier mappé, et donc aucun accès ne peut être en cours.
      
      L'algorithme est donc :
      
      Placer les _db_access_allowed de tous les threads à false, les threads évitent dès lors de commencer un accès
      
      Boucler et faire un sched_yield tant que tous les threads n'ont pas placé leur _db_accessed à false, donc tant qu'ils accèdent à la base de donnée
      
      Agrandir et re-mapper le fichier
      
      Placer tous les _db_access_allowed à true, les threads peuvent reprendre leur activité
      
      L'utilisation de sched_yield n'est peut-être pas la plus élégante, et je n'ai pas encore suffisamment testé la base de donnée en condition réelle pour voir si ça accélère ou ralentit les choses par rapport à une busyloop. Sous Linux, il y a aussi les futex qui pourraient être utilisés pour endormir les threads tant que leur flag _db_access_allowed n'est pas à true, je regarderai de ce côté-là quand j'en aurai l'occasion (même si idéalement, déjà que pas mal de code est spécifique à x86, j'aimerais éviter de trop tomber dans le Linux-only).
      
      Pour info, l'écriture en base de donnée (première phase du benchmark) est plus normale : il fallait avant 16 ms pour écrire toutes les clés, il en faut maintenant 46. L'écriture a donc été fortement impactée, mais ce n'est pas grave car cette base de donnée passe son temps à être lue (ce serait grave d'avoir un programme qui génère 250 Mio de données par seconde, en tous cas pour ce que je fais).
      - [^] # Re: Ai-je bien compris ?
        
        Posté par rewind (Mastodon) le 14 mai 2013 à 23:01. Évalué à 7.
        
        Make it work. Make it right. Make it fast.
        
        J'ai un peu l'impression que tu commences par la fin.
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 15 mai 2013 à 09:36. Évalué à 2.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 10:34. Évalué à 4.
        
        En général, le "make it work" implique le bon algorithme et la bonne architecture. Le "make it fast" sous-entend une transformation du code source uniquement pour aller plus vite, il reste peu de marge, et cela rend le code source difficile à lire.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 10:36. Évalué à 1.
        
        En effet.
        
        Dans mon cas, ce qui m'a motivé à me passer du readers-writer lock a été quand je me suis rendu compte que dans un autre benchmark, la base de donnée comptait pour 50% du temps, alors que ce benchmark fait également plein d'autres choses.
        
        Cet autre benchmark, multithreadé, est passé de 280 ms à 126 ms entre la version rwlocks et lockless, ces deux chiffres comprenant également le temps de démarrage du benchmark, de parsing d'un fichier d'entrée et du lancement de threads (c'est une mesure donnée par time).
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 10:56. Évalué à 2.
        
        ta base de donnée, c'est 2 chiffres de 32 bits qui pointent vers un seul chiffre de 32 bits ou est-ce n chiffres de 32 bits vers un seul de 32 bits ?
        
        Quelle est sa taille ? Genre 100 mo ? 10 Go ? 1 To ?
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 11:49. Évalué à 1.
        
        Ce sont exactement 2 nombres de 32 bits qui pointent vers un seul de 32 bits.
        
        La taille de la base de ce test était très petite, quelques kilo-octets. La particularité de ma base de donnée est qu'elle ne contient pas réellement des « données » mais des directives. On peut la voir comme une grosse matrice N*M => K qui peut servir de machine à état. Avec peu de données, il est donc possible de faire beaucoup de choses s'il y a beaucoup de transitions d'état.
        
        Je ne pense pas qu'elle sera fortement limitée par le débit mémoire ou disque, car ce sont énormément de petites lectures qui y sont effectuées, comme un processeur qui lit ses instructions, qui peuvent très bien lui faire faire des boucles. Par contre, la latence du cache, de la mémoire, le readahead de l'OS, tout cela va entrer en jeu. En comptant large, 32 octets par triplet (objet, clé, valeur), je peux stocker 256 millions de ces couples sur 8 Gio. Le stockage est sparse, les triplets non-utilisés ne sont pas stockés.
        
        Le test dont je parle est un test qui consiste qui consiste à faire effectuer 100 000 transitions d'état simple à ma machine à état. Chaque transition est lue depuis la base de donnée (certains à répétition, sinon la base de donnée serait immense et surtout pas optimisée).
        
        En écrivant ce test, je pensais mettre en évidence toute la machinerie de gestion des états, qui est très complexe et assez lourde (il y a des méthodes virtuelles à appeler, des constructeurs et destructeurs à invoquer, de la mémoire à allouer et libérer (mais pas trop), etc). En lançant ce test dans valgrind et en analysant les résultats avec kcachegrind, j'ai constaté que la base de donnée représentait néanmoins 50% du temps processeur, alors que son code est comparativement très simple par rapport au reste.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 12:02. Évalué à 5.
        
        J'ai du mal à suivre. Est-ce une vrai base de donné avec sauvegarde sur disque des écritures de façon protégé ? Parce que niveau perf, il y a une différence énorme entre une grosse structure de donné en mémoire, et des données sauvé sur disque. Il y a aussi une grosse différence de performance si chaque écriture doit être pris en compte immédiatement ou non.
        
        Ton bench de qq Ko n'a strictement aucun sens, la base tient dans le cache L1 d'un processeur ! Les perfs peuvent tomber drastiquement si la base ne tient pas en cache L2 ou L3, voir ne tient pas dans la RAM.
        
        "32 octets par triplet (objet, clé, valeur)"
        
        C'est quoi cet objet ? Tu ne parles que d'une matrice[i][j]-> k, i,j,k étant entier.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 12:44. Évalué à 1.
        
        La base de donnée est un fichier mappé en mémoire, il n'y a pas de fsync explicite dans le code, l'OS écrit quand il le veut ou quand la mémoire et unmappée. Je conviens que ce n'est pas très sécurisé et que ça ne peut pas être utilisé dans certains environnements, mais l'avantage de la base de donnée lockless est qu'en cas de crash, comme les opérations sont atomiques à tous les niveaux, la base de donnée ne sera jamais corrompue (si quelques pages n'ont pas été écrites sur le disque, ça ne fait rien, la machine à état reprendra exactement là où elle en était au moment de la dernière écriture).
        
        Pour la terminologie, j'avoue ne pas avoir été clair. La base de donnée associe bien un entier à un couple d'entiers, de la forme (i, j) -> k. Ces nombres, pour ne pas simplement être appelés « nombres », portent les noms suivants :
        
        i : l'objet
        
        j : la clé
        
        k : la valeur
        
        Cette nomenclature permet maintenant de représenter la base de donnée comme une suite de changements d'états quand des objets réagissent à des messages. Si j'envoie le message M à l'objet O, je vais aller regarder la valeur du tuple (O, M), notée O.M, dans la base de donnée. J'obtiens une valeur V.
        
        Maintenant, suivant ce que je voulais faire au départ, je vais encore accéder ma base de donnée. Par exemple, V peut être un objet auquel je veux forwarder le message, auquel cas je vais maintenant me positionner sur la valeur V.M . Cette valeur peut également avoir une signification spécifique, comme afficher le message dans la console, etc.
        
        Ce que je fais avec les valeurs des tuples dépend de l'objet : j'ai un tableau qui associe pour chaque valeur de l'objet une classe C++ que j'instancie à chaque fois que l'objet est rencontré. Cette classe contient des méthodes virtuelles permettant de continuer le traitement. C'est cette gestion des classes C++ qui devait normalement être lourd et masquer les délais introduits par la base de donnée.
        
        Le fait que chaque objet fasse 32 octets vient du fait qu'il y a des pointeurs dans l'histoire (pour ne pas devoir stocker une matrice objets*messages sur le disque) ainsi que quelques flags.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 15 mai 2013 à 12:54. Évalué à 8. Dernière modification le 15 mai 2013 à 12:55.
        
        Donc si on arrête d'utiliser pleins de mots pour ne rien dire. Ton machin c'est une matrice bi-dimensionnelle dont les valeurs sont des entiers…
        
        Aller encore un effort et tu vas réussir à expliquer les deux contraintes que tu as dessus !
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 13:04. Évalué à 7.
        
        roooh, te rappelles-tu comment tu étais à son age ? (ce que tu pensais des plus vieux sur les forums :)
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 15 mai 2013 à 13:14. Évalué à 6. Dernière modification le 15 mai 2013 à 13:14.
        
        Ouai et le genre de réponse que je fais m'a fait réfléchir. Je m'en était pris des plus violentes et les "plus vieux", je dirais plus compétents qu'importe l'âge, avaient raison ;)
        
        Le plus important dans l'informatique c'est de comprendre son problème et d'être capable de l'expliquer non ? Ca sert à rien de patauger dans la technique, les benchmarks, les optimisations si on n'est pas capable d'exprimer clairement les entrées, l'objectif et les contraintes de ce qu'on manipule. Ca lève un drapeau qu'on est en train de faire n'importe quoi.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 13:16. Évalué à 5.
        
        C'est totalement vrai, mais il y a aussi une bonne dose de mauvaise communication de sa part.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 15 mai 2013 à 13:31. Évalué à 5.
        
        C'est exactement ce que je dis.
        
        Si tu n'arrives pas à communiquer avec les autres c'est que tu n'es pas capable toi même de découper ton gros-machin en problèmes bien identifiés aux frontières claires. Si tu es un habitué à son ancienne prose, qui ne diffère pas de celle-ci, je pense sincèrement que faire ce genre de reflexion lui apportera plus qu'une quelconque réponse techniques.
        
        Quand je lui dis "arrête le blabla et montre le code" c'est dans le même état d'esprit. Tu dois faire la même démarche pour trouver tes problèmes que pour l'expliquer aux autres. Identifie ce que tu veux mesurer/optimiser/comprendre. Isole le code, défini clairement les paramètres. Mets en place des métriques cohérentes et réfléchi aux façons de les valider. Si tu ne peux pas me sortir le code que je demande, alors c'est que le boulot n'est pas fait et que tu pédales beaucoup mais n'avance pas d'un poil.
        
        À chaque fois qu'il parle d'un bench ou d'une implem tu sens la connerie arriver à 100km et ça fait souvent mouche. En le forçant à s'exprimer clairement il ne peut qu'avancer.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ahuillet (site web personnel) le 15 mai 2013 à 17:12. Évalué à 3.
        
        Si tu n'arrives pas à communiquer avec les autres c'est que tu n'es pas capable toi même de découper ton gros-machin en problèmes bien identifiés aux frontières claires
        
        De manière générale, je dirais même que si tu n'arrives pas à expliquer quelque chose clairement, c'est que tu ne l'as pas compris.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 17:15. Évalué à 8.
        
        Et une fois tu as expliqué clairement un problème, tu trouves la solution. J'adore aller ennuyer un collègue avec un problème, je fais mon monologue, puis je trouve la solution tout seul :)
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par oinkoink_daotter le 15 mai 2013 à 17:41. Évalué à 5.
        
        Je crois me rappeler d'une moule< qui appelait ça "le débuggage au canard" : tu prends un canard en plastique et tu lui dis ligne par ligne ce que fait le code buggué. Et paf tu trouves pourquoi.
        
        Mais ça remonte, à pfiouh….
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par CrEv (site web personnel) le 15 mai 2013 à 17:51. Évalué à 4.
        
        Cadeau : Méthode du canard en plastique
        
        \_o<
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Spyhawk le 15 mai 2013 à 17:52. Évalué à 3.
        
        PAN!
        
        (pardon)
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par oinkoink_daotter le 15 mai 2013 à 18:41. Évalué à 2.
        
        *click* *click*. Rahhh zut, enrayé.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par oinkoink_daotter le 15 mai 2013 à 18:46. Évalué à 1.
        
        Je me demande si c'est un IDE dans lequel est affiché le code dans l'image de l'article wikipedia.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Spyhawk le 15 mai 2013 à 17:52. Évalué à 3.
        
        Effectivement, c'est la méthode du Rubber duck debugging issue du Pragmatic Programmer publié à la fin des années 90.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 13:15. Évalué à 3.
        
        Je ne sais pas trop comment tu gères les données "à effacer", qui est le problème des structures en softupdate. Tu as une sorte de garbage collector ?
        
        J'imagine qu'en écriture, tu alloues de la mémoire dans ton fichier pour y mettre ton triplet, puis l'écrit, puis tu modifies un pointeur de l'ancienne vers la nouvelle valeur ? Comment tu récupères la mémoire du triplet précédent, sur une liste de blocs libres ?
        
        Il doit exister un paquet de littérature sur la manière la plus efficace d'implémenter une sparse-matrix (matrice à trous).
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 14:15. Évalué à 1.
        
        Pour rentrer un peu dans les détails, j'ai deux listes de blocs libres :
        
        Quand on efface un bloc dans la base de donnée, il est placé dans la liste de blocs discarded. À ce point, rien ne dit qu'un lecteur n'est pas encore en train d'y accéder
        
        Quand on doit allouer un bloc dans la base de donnée, il est pris depuis la liste des blocs available, disjointe des blocs discarded.
        
        S'il n'y a plus de blocs dans la liste available, un nouveau bloc est alloué atomiquement dans le fichier (le fichier grandit de 512K en 512K, alors que les blocs sont bien plus petits)
        
        Si le fichier est trop court, le flag _db_access_allowed dont j'ai parlé dans un de mes commentaires est mis à 0 pour tous les threads, puis on attend que tous les threads aient cessé d'accéder à la base de donnée (leur variable _db_accessed doit valoir 0).
        
        Maintenant que plus aucun thread n'accède à la base de donnée, il y a deux cas possibles : soit la liste des blocs discarded contient des blocs, auquel cas on swappe simplement les pointeurs de tête de liste de available et discarded (on sait que plus aucun thread ne lit discarded, donc on peut la réutiliser), soit cette liste est vide, auquel cas 512K de zéros sont écrits dans le fichier, qui est ensuite remappé avec mremap.
        
        On re-tente l'allocation, la liste available contient normalement des blocs. Normalement l'allocation réussira maintenant, mais on ne sait jamais, peut-être qu'on a été préempté pendant plusieurs minutes et que les 512K qu'on vient de rajouter au fichier ont déjà été consommés. Ce n'est pas grave, on va juste recommencer tout ce qui est swap des listes et agrandissement du fichier
        
        Le fichier de la base de donnée n'est jamais réduit. Un bloc ici est une unité d'espace utilisée par la base de donnée. Chaque objet (donc chaque premier entier d'un couple (i, j)) est lié à un bloc, et ce bloc contient une liste de couples (clé, valeur). Un bloc doit être supprimé quand il devient trop petit pour l'ensemble des (clé, valeur) qu'on veut y placer (il faut donc en allouer un nouveau, plus grand), ou quand on veut supprimer un objet.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par reno le 15 mai 2013 à 13:57. Évalué à 3.
        
        la base de donnée ne sera jamais corrompue
        
        Si tu écris dans un object sur une page A et ensuite dans un autre sur une page B, il est tout à fait possible que B soit sur le disque mais pas A, ça n'est pas une corruption de BDD pour toi?
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Matthieu Moy (site web personnel) le 15 mai 2013 à 15:00. Évalué à 0.
        
        Tout à fait. Avec un peu de chance, le disque sera monté avec une option genre data=ordered et ça n'arrivera pas, mais c'est difficile de le garantir …
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 15:03. Évalué à 2.
        
        tu peux t'en sortir, si il s'agit d'un pointeur dans B et des données dans A.
        
        Le pointeur B peut être invalide (en dehors du fichier tel que vu actuellement), ou B pointe vers une vielle donné : si le nom est présent, on peut détecter l'erreur.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par riba le 15 mai 2013 à 23:58. Évalué à 8.
        
        Le noyau synchronize le mmap sur disque dans l'ordre qu'il veut, sa méthode est foireuse de base. Il faut qu'il duplique toute ses opérations d'écriture séquentiellement dans un fichier à côté (+crc), aka un "journal", et fasse des msync(SYNC) régulier de son mmap + fsync/close de son journal, et après il peut continuer. C’est une DB RAM-only, ça a été codé en plein de version dans quasiment toutes les industries & start-up du monde. Il existe plein de variantes pour gérer la transition (le… commit). Dès qu'il aura de la pression mémoire (dirty_ratio toussa), il va commencer à voir tout ça. Jusqu’ici il n'a mesuré que le débit de sa RAM (dans le meilleur des cas). Il va aussi voir que MADV_NOSYNC n'est disponible que sous BSD (donc devoir faire finalement un MAP_ANONYMOUS et gérer les I/O lui-même).
        
        Bref, une base ACID en 200 lignes de code, threadsafe avec les latences/débits annoncés, c'est pas le bon jour.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 09:32. Évalué à 1.
        
        acid est rarement nécessaire comme le montre le succès du no-sql.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par khivapia le 15 mai 2013 à 11:21. Évalué à 2.
        
        Tu es sûr que le résultat obtenu est le bon ? (comparaison des deux fichiers obtenus par exemple) ? Y compris en stress-testant la gestion des threads ? (ajouter beaucoup plus de threads que de cœurs de calcul, ajouter des programmes qui ne font rien genre cat /dev/zero > /dev/null, baisser la priorité de ton programme…)
      - [^] # Re: Ai-je bien compris ?
        
        Posté par ribwund le 15 mai 2013 à 00:54. Évalué à 3.
        
        Un conseil, deja remplace les bool par des variables avec accès atomique: http://en.cppreference.com/w/cpp/atomic/atomic
      - [^] # Re: Ai-je bien compris ?
        
        Posté par Gof (site web personnel) le 15 mai 2013 à 09:49. Évalué à 7.
        
        while (!_db_access_allowed)
        sched_yield();
        
        Aaa. Évites ça.
        
        Ceci est un spin-lock, qui comme son nom l'indique est un type de lock. Donc si tu croyais que ton algo est lock-free, eh bien il ne l'est pas.
        
        Le spin lock ne devrais jammais être utilisé en user-space. C'est le pire de tous. Car les autres locks sont bien plus économe pour le CPU (consomaion d'énergie) ou sont plus favorable pour les autres processus.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 10:41. Évalué à 1.
        
        C'est proche d'un spinlock mais le sched_yield() permet à tous les autres threads de la machine d'être ordonnancés avant que ce thread ne le soit à nouveau (si le scheduler utilisé est CFS, qui ordonnance il me semble les threads en round-robin, sauf ceux en temps-réel).
        
        Idéalement, j'aurais aimé utiliser une wait-condition, mais on ne peut pas s'en servir sans mutex. C'est pour cela que j'aimerais regarder du coté des futex : quand _db_access_allowed est à false, un appel à futex est fait pour que le noyaux ne donne plus de temps CPU au thread courant. Le noyau réveillera lui-même le thread quand _db_access_allowed vaudra à nouveau true.
        
        Néanmoins, j'ai lu à pas mal d'endroits que les futex sont très difficiles à utiliser correctement, donc pour le moment, je préfère me concentrer sur d'autres choses.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par MrLapinot (site web personnel) le 15 mai 2013 à 11:45. Évalué à 4.
        
        C'est proche d'un spinlock mais le sched_yield() permet à tous les autres threads de la machine d'être ordonnancés avant que ce thread ne le soit à nouveau (si le scheduler utilisé est CFS, qui ordonnance il me semble les threads en round-robin, sauf ceux en temps-réel).
        
        NON !
        
        Je l'ai appris à mes dépends. Ceci était vrai avant le CFS. Depuis le CFS, sched_yield() ne fait plus du tout ce que tu attends en mode mono-processeur ; par contre, il est plus efficace pour synchroniser des threads quand tu as plusieurs processeurs. Pendant quelques temps, il y a eu un sysctl pour garder l'ancien comportement (noyau 2.6.23) : /proc/sys/kernel/sched_compat_yield notamment parce que la JVM en dépendait. Voir http://kerneltrap.org/Linux/CFS_and_sched_yield
        
        Ce sysctl a été retiré plus tard (noyau 2.6.38). Maintenant, il ne faut absolument pas compter dessus. Il faut utiliser les futex pour faire des spinlocks (mais ça ne marche qu'en multi-processeur par principe), ou un ordonnancement temps-réel et demander le scheduler SCHED_RR grâce à sched_setscheduler(2) (mais on retrouve les contraintes du temps-réel).
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par steckdenis (site web personnel) le 15 mai 2013 à 12:29. Évalué à 1.
        
        C'est en effet très intéressant !
        
        J'ai fait sur ma machine le test décrit sur kerneltap. Un mail en haut du thread donne un petit programme appelé "task2", qui affiche en continu le temps qu'il faut pour exécuter une boucle vide de 100 millions d'itérations.
        
        Le programme "task1" est donné par le code suivant :
        
        #include <sched.h> int main() { while (1) { sched_yield(); // Version 1 asm("pause"); // Version 2, instruction PAUSE conseillée par Intel pour les busyloops ; // Version 3, On ne fait rien } }
        
        Seulement une des trois lignes est décommentée à la fois, pour avoir trois versions du programme. les deux programmes sont compilés en -O0, sinon GCC est trop intelligent et élimine les boucles vides. Les résultats sont les suivants (plus c'est petit, plus c'est rapide) :
        
        Quand task2 tourne seul sur un coeur, aucune autre tâche en parallèle : 505851 plus ou moins des poussières, je vais considérer le nombre 50
        
        Quand task2 tourne seul sur un coeur, avec sched_yield sur un autre : 52
        
        Quand task2 tourne seul sur un coeur, avec pause sur un autre : 51
        
        Quand task2 tourne seul sur un coeur, avec la boucle vide sur un autre : 51
        
        Quand task2 tourne sur le même coeur que sched_yield : 76 (alors qu'idéalement, on aurait voulu 50 ou 51, l'autre tâche yield le processeur)
        
        Quand task2 tourne sur le même coeur que pause : 150
        
        Quand task2 tourne sur le même coeur que la boucle vide : 88
        
        Le choix des coeur est fait avec taskset -c X commande, avec X égal à 0 ou 2, sachant que mon processeur dispose de l'hyper threading, et que les coeurs 0 et 1 sont en fait deux threads du même coeur physique. J'ai découvert ça en lançant task1 et task2 sur les coeurs 0 et 1, et les deux étaient ralenties. La fréquence de mon processeur a été fixée à 1200 Mhz pour tous les coeurs (fréquence basse car je suis sur batterie et j'aimerais éviter de consommer 35 W).
        
        Si j'essaie de tirer des conclusions, je dirais que sched_yield induit un léger ralentissement inter-coeurs (résultat 2), sans doutes parce que le scheduler doit agir, ou que les caches sont vidés. Par contre, sched_yield semble sur ma machine (Linux 3.8.8 d'openSUSE 12.3, x86_64) la solution la plus rapide pour quand deux threads partagent le même coeur. De manière surprenante, PAUSE introduit un énorme ralentissement quand les deux tâches sont sur le même coeur !
        
        J'ai en tous cas l'après-midi devant moi pour m'intéresser aux futex.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Gof (site web personnel) le 15 mai 2013 à 12:53. Évalué à 3.
        
        C'est pour ça que les spin-lock sont à éviter. Même en utilisant des pause ou des sched_yield, tu gaspilles des cycles à attendre, alors que un autre processus pourait les utilisé, ou qu'il pourait ne pas être utilisé du tout et consomer moin d'énnergie.
        Un lock sera beaucoup plus simple
        
        Le plus simple c'est d'utiliser std::mutex. Mais il est vrai que tu aura un petit overhead comparé à utiliser des futex directement (genre un appel de fonction).
  - [^] # Re: Ai-je bien compris ?
    
    Posté par Guillaum (site web personnel) le 15 mai 2013 à 00:03. Évalué à 10.
    Le benchmark ne teste donc pas la validité de l'implémentation (c'est testé par des tests unitaires dédiés), mais seulement sa rapidité, en mono-thread. Cela permet donc d'évaluer l'overhead des instructions atomiques, qui est ici négatif, ce qui est surprenant.
    
    Déjà ton code est faux. var est volatile et tu le passes en tant que non volatile dans les deux fonctions. GCC emet un warning et ce n'est pas pour rien, cela n'a pas de sens, ce bench n'a pas de sens.
    
    Et en supprimant le volatile ?
    
    Je m'explique, le qualifier volatile en c/c++ n'est utile que pour des mappings hardware (genre device mapppé, ou interruption, …), mais il ne change RIEN pour l'atomicité des opérations, mais il empêche le compilateur d'optimiser certains traitements.
    
    Hors le atomic est une opération hardware spécifique du CPU (Je ne sais pas comment elle fonctionne, mais il y a des chances que ton CPU soit capable en un unique cycle de faire le get/l'incrementation/le set).
    
    A ce moment, le compilateur va simplement remplacer ton __sync par l'appel à l'instruction du CPU qui va bien.
    
    De l'autre coté, le compilateur va être forcé de générer le code pour récupérer la valeur, l’incrémenter et la remettre en mémoire.
    
    En gros, vire volatile et regarde ce qui ce passe. Volatile n'est pas nécessaire ni suffisant pour faire des opération thread-safe et se contente simplement d’empêcher des optimisation du compilateur ou du CPU.
    
    On va creuser un peu. les fonctions thread_safe et not_thread_safe en -Os donnent:
    
    thread_safe:
    lock addl $1, (%rdi)
    ret
    not_thread_safe:
    addl $1, (%rdi)
    ret
    
    Bon, rien de magique. Maintenant la boucle, bon là c'est marrant, mais la boucle genere moins d'assembleur en unsafe que en safe (globalement GCC se rend compte que c'est une boucle, l'inline, se rend compte que tu fais N fois l'incrementation et remplace tout par une unique incrementation de N, contrairement à la version /safe/ qui force la boucle et l'appel de N fois la primitive atomique.) Bref, tant que on a pas ton code complet, cela n'a pas de sens.
    
    Bon, par contre si on met volatile AUSSI sur les prototypes des fonctions:
```
void thread_safe(volatile int *ptr)
{
    __sync_fetch_and_add(ptr, 1);
}

void not_thread_safe(volatile int *ptr)
{
    *ptr += 1;
}

#define BENCHMARK_ITERATIONS 10

int benchmark(const int c)
{
    volatile int var = 0;

    for (unsigned int i=0; i<c; ++i)
    {
       not_thread_safe(&var);
    }

    return var;
}
```
    (J'ai un peu changé la fonction benchmark pour que GCC ne puisse pas inliner la boucle aussi facilement qu'avant)
    Là cela devient drole, car le code (en O3) du milieu de la boucle en unsafe est donc:
```
.L7:                                # debut de boucle
    movl    -4(%rsp), %edx          # Fetch memoire (à cause du volatile)
    addl    $1, %eax                # compteur de boucle++
    addl    $1, %edx                # valeur++
    cmpl    %edi, %eax              # test de boucle
    movl    %edx, -4(%rsp)          # store memoire (à cause du volatile)
    jne .L7                         # Jump en fonction du test de boucle
```
    Contre en safe:
```
.L7:                                # debut de boucle
    lock addl   $1, -4(%rsp)        # Incrementation atomique (note le lock)
    addl    $1, %eax                # compteur de boucle
    cmpl    %edi, %eax              # comparaison
    jne .L7                         # Jump en fonction du test de boucle
```
    Donc la raison ici c'est que le volatile force le fetch/store alors que l'atomique ne fait rien… Test sans le volatile.
    - [^] # Re: Ai-je bien compris ?
      
      Posté par Guillaum (site web personnel) le 15 mai 2013 à 00:05. Évalué à 6.
      
      Hors le atomic est une opération hardware spécifique du CPU (Je ne sais pas comment elle fonctionne, mais il y a des chances que ton CPU soit capable en un unique cycle de faire le get/l'incrementation/le set).
      
      Lire: unique instruction, et moinsser moi ;)
    - [^] # Re: Ai-je bien compris ?
      
      Posté par steckdenis (site web personnel) le 15 mai 2013 à 10:55. Évalué à 1.
      
      Bonjour,
      
      Je me suis en effet trompé dans le volatile, ce n'est pas var qui doit l'être (les instructions atomiques se chargent de tout), c'est i. Rendre la variable d'itération volatile est un petit hack dont j'ai besoin pour m'assurer que le compilateur ne déroulera ni n'optimisera la boucle. En effet, le benchmark teste la lecture depuis la base de donnée, et ce chemin de code ne contient aucune instruction atomique (seulement le sfence comme instruction bizarre). Sans le volatile, GCC déroule la boucle, inline les appels à la base de donnée, voit que c'est de la lecture seule et finalement supprime toute la boucle sauf sa dernière itération !
      
      En mode non-benchmark, il y a bien sûr des assertions (ou plutôt des fail_if() pour ceux qui connaissent Check) sur les valeurs renvoyées par la base de donnée, mais elles n'y sont pas en mode benchmark car le but est vraiment juste de mesurer le temps que Database::get prend pour s'exécuter, en conditions parfaites.
    - [^] # Re: Ai-je bien compris ?
      
      Posté par Matthieu Moy (site web personnel) le 15 mai 2013 à 12:13. Évalué à 2.
      
      Pour les détails, lire : « Why the "volatile" type class should not be used »
      https://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt
    - [^] # Re: Ai-je bien compris ?
      
      Posté par neologix le 15 mai 2013 à 17:38. Évalué à 3.
      
      Je m'explique, le qualifier volatile en c/c++ n'est utile que pour des mappings hardware (genre device mapppé, ou interruption, …), mais il ne change RIEN pour l'atomicité des opérations, mais il empêche le compilateur d'optimiser certains traitements.
      
      Pour l'atomicité non, mais comme tu l'as dit, ça force le compilateur à faire des fetch/store, et ça peut être utile dans un contexte multi-threadé.
      
      Il y a par exemple cette macro utilisée pas mal dans le kernel:
      #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
      
      cf https://lwn.net/Articles/508991/
      
      Ca ne garantit pas que tu liras la valeur la plus récente écrite (pas de memfence contrairement au volatile de java), mais tu la liras éventuellement.
      Aussi, ça garantit que la variable ne sera lue qu'une fois (sinon le compilo pourrait la dégager des registres et la relire plus tard).
      
      Et ça c'est utile. Idem pour les écritures.
      
      Après, il est vrai que dans 99% des cas, un volatile dans un code multi-threadé est mauvais signe (d'où le fameux poste de Linus "volatile considered harmful"), mais utilisé à bon escient, si ça t'évite une memfence ou une instruction atomique, ça peut être un gain non négligeable.
      - [^] # Re: Ai-je bien compris ?
        
        Posté par Guillaum (site web personnel) le 15 mai 2013 à 22:30. Évalué à 2.
        
        Ce qui me fait toujours peur c'est que j'ai commencé a me renseigner sur volatile et autre suite à une question existentielle, si j'ai une boucle, genre
        
        running = 1;
        while(running)
        {
        // fait quelque chose, mais ne touche pas à running
        }
        
        Ici il semblerait que mon compilateur soit en droit de de remplacer cela par une boucle infinie, d'où le besoin de volatile.
        
        En faisant quelques tests, il semblerait que le compilateur (ici gcc en O3) prenne cette liberté seulement si running n'est pas utilisé autre part dans le code. Si jamais il est fait référence à la variable running avant la boucle pour un appel de fonction ou autre, GCC génère tout de même le read, même sans volatile.
        
        Ainsi je me demande donc. Est-ce une limitation de GCC/CLANG qui n'essaye pas d'optimiser dans ce cas ? Est-ce voulu pour protéger le codeur d'une erreur grossière de code ou y a il une raison bien spécifiée qui fait que dans ce cas le compilateur n'a pas le droit de protéger ?
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Matthieu Moy (site web personnel) le 15 mai 2013 à 22:36. Évalué à 1.
        
        Ton volatile ne servira pas à grand chose : rien ne garanti que la lecture ne se fera pas dans un cache ou un write buffer pas flushé. cf. le lien "volatile considered harmfull" que j'ai posté dans un autre commentaire.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Guillaum (site web personnel) le 15 mai 2013 à 23:03. Évalué à 2.
        
        Je suis d'accord, mais si on est pas à la seconde près, le cache sera un jour mis à jour et cela va fonctionner.
        
        Ma question c'est plutôt, est-ce que cela marche tout seul (i.e.: sans volatile et avec potentiellement autant de latence que le cache/write buffer peut prendre) ? Est-ce que je suis garanti que GCC ne me fera pas une boucle infinie. En fait je torture mon code depuis un bout de temps et je suis incapable de générer du code ou gcc/clang remplace cela par une boucle infinie.
        
        Ma question est plus poussé, c'est "Est ce que le fait que GCC/Clang ne remplace pas cela par une boucle infinie est un comportement documenté/standard/… et si oui pourquoi ?".
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 23:54. Évalué à 2.
        
        volatile est un mot clef pour dire que la donnée mémoire déclarée ensuite, à le contenu qui bouge tout seul. C'est la base pour accéder à des registres hardware.
        
        Dans le cas contraire, un compilo considère que seul le programme C en cours de compilation peut y toucher, d'où la génération possible de boucle infinie, de lecture unique puis un usage de registre.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Guillaum (site web personnel) le 16 mai 2013 à 00:21. Évalué à 2.
        
        Merci, je sais, c'est ce que j'ai expliqué plus tôt (au début du thread auquel je m'auto repond.). C'est assez enervant quand on essaye d'avoir une discussion un peu plus avancé de se faire répondre ce que l'on a préalablement expliqué plus tôt. (Un peu comme sur le chan irc d'ubuntu, et depuis peu d'arch linux… Quand tu as un soucis, les seuls aides que tu obtient te conseil des trucs que tu as déjà testé ;)
        
        Mon problème c'est que je n'ai jamais réussi à générer un bout de code tel que:
        
        while(variable){}
        
        avec variable modifiée à l’extérieur et que cela génère une boucle infinie. Automatiquement GCC et Clang me régénérait des fetch pour mettre à jour tout cela. Donc je voulais savoir si j'étais dans un cas bien défini ou pas.
        
        Mais c'est bon, j'ai trouvé un exemple tout con qui marche bien. Stop en -O0 et boucle infinie au dela.
        
        // g++ -std=c++11 -Wall -Wextra -lpthread fichier.cpp #include <thread> #include <iostream> #include <unistd.h> int f; void thread1() { while(!f); } int main() { f = 0; std::thread t1(thread1); // give t1 some time to run sleep(1); f = 1; t1.join(); }
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Gof (site web personnel) le 16 mai 2013 à 01:31. Évalué à 2.
        
        Ton programme est en effet une « undefined behaviour » d'après le standard. Je cite:
        
        [C++11] §1.10 21
        The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior.
        
        !f et f = 1 sont dans différent thread, sont deux opérations non atomic, conflictuelles et il n'y a pas de « happens before » selon les définitions données dans la même section.
        Le compilateur est donc libre de faire ce qu'il veut.
        
        Si f était de type std::atomic<int> alors ce serait bon.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par neologix le 16 mai 2013 à 00:34. Évalué à 3.
        
        Ma question est plus poussé, c'est "Est ce que le fait que GCC/Clang ne remplace pas cela par une boucle infinie est un comportement documenté/standard/… et si oui pourquoi ?".
        
        Non, ce n'est pas standard, mais c'est plutôt une limite de l'optimisation faite par GCC.
        
        Si ta variable n'est pas volatile, le compilateur peut tout à fait hoister la lecture.
        
        Le problème c'est que si tu as une variable globale - notamment non statique - et que dans ta boucle tu fais:
        
        variable = 0;
        
        while (variable) {
        foo(autre_variable);
        …
        }
        
        et que GCC ne peut pas prouver que foo(autre_variable) ne modifie pas variable, il va forcer un reload.
        
        Par contre si tu appelles une fonction pure, il y a des chances que GCC ne fasse pas le reload.
        
        Si jamais il est fait référence à la variable running avant la boucle pour un appel de fonction ou autre, GCC génère tout de même le read, même sans volatile.
        
        Essaie d'appeler une fonction static.
        
        Ton volatile ne servira pas à grand chose : rien ne garanti que la lecture ne se fera pas dans un cache ou un write buffer pas flushé. cf. le lien "volatile considered harmfull" que j'ai posté dans un autre commentaire.
        
        En pratique dans ce genre de boucle tu souvent toujours des syscalls/instructions qui vont provoquer une memfence (du genre un mutex ou opération atomique sur une autre variable). Sinon, en l'absence de telles instructions, en effet dans un cas simple comme au dessus ça ne suffit pas à le garantir.
        Mais en pratique dès qu'un thread fait un appel système, context switch ou est schedulé sur un autre core, c'est équivalent à une memory barrier.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 23:51. Évalué à 2.
        
        La mémoire de PC est cohérente de partout normalement. Une fois une données écrite quelques part, elle est visible par tous de la même façon. Il y a logiquement un mécanisme de synchronisation qui détecte ce genre de cas.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par neologix le 16 mai 2013 à 07:01. Évalué à 2.
        
        Non, à cause des store buffers et invalidate queues, il y a besoin de memory barriers:
        http://en.wikipedia.org/wiki/Memory_barrier
        
        Ou mieux la référence :
        https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Matthieu Moy (site web personnel) le 16 mai 2013 à 09:08. Évalué à 1.
        
        La mémoire de PC est cohérente de partout normalement.
        
        Ça dépends de ce que tu appelles « cohérente ». Si c'est sequential consistency, alors non, ce n'est pas le cas.
        
        Une fois une données écrite quelques part, elle est visible par tous de la même façon.
        
        Non, même le modèle mémoire x86 ne garantie pas ça. Quand tu fais une écriture, elle passe d'abord par un write buffer, et celui qui a écrit peut relire la nouvelle valeur alors qu'elle n'est pas écrite partout. Par contre, c'est du TSO (total store order), donc les écritures sont vues dans le même ordre par tout le monde, ce qui est déjà une propriété assez forte par rapport à d'autres architectures (et qui permet souvent, mais pas toujours, de se passer d'opérations atomiques pour des lectures/écritures d'entiers). Tu peux regarder ce que GCC génère pour les opérations atomiques de C++11 pour t'en convaincre (de mémoire, toutes sauf le memory_order_seq_cst génèrent des movl).
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 16 mai 2013 à 09:27. Évalué à 2.
        
        Non, même le modèle mémoire x86 ne garantie pas ça. […] ce qui est déjà une propriété assez forte par rapport à d'autres architectures
        
        Et c'est là que tu te dis que pour 99% du code que tu écris tu es content d'utiliser un langage qui défini un memory model.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 16 mai 2013 à 16:24. Évalué à 2.
        
        Tu veux dire comme Java ? Parce que le premier modèle est cassé, et que le second (qui date de 2005) permet des trucs qui en pratique autorisent de briser la causalité.
        
        Pour C++-11, ils ne se sont pas trop trop foulés : le principe-même d'un modèle mémoire c'est de définir la sémantique des "conflits" de lecture-écriture (data race). En disant "toute data race est un UB", en gros les gens de C-11 et C++-11 disent simplement "si tu as une data race, tout peut arriver, même que le compilo génère du code pour t'acheter 20000 big macs via le net en utilisant ta carte de crédit".
        
        Le problème, c'est qu'il existe quelques (rares) cas ou les data races sont correctement contrôlées, i.e. on sait qu'il existe un conflit lecture/écriture sur une adresse mémoire, mais on sait évaluer l'amplitude de l'erreur, ou bien on n'a pas besoin de la toute dernière valeur de la variable, la n-k^eme valeur est OK aussi. C'est le cas dans les solveurs à relaxation chaotique par exemple. Avec C++, il est impossible de garantir quoi que ce soit, parce que le compilateur, pour des raisons d'optimisation, va peut-être mettre une valeur arbitraire a l'adresse de la variable ciblée.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 16 mai 2013 à 17:34. Évalué à 3.
        
        Tu veux dire comme Java ?
        
        Oui
        
        Parce que le premier modèle est cassé, et que le second (qui date de 2005) permet des trucs qui en pratique autorisent de briser la causalité.
        
        Tu as des resources sur le deuxième voir si il y a des choses que je ne connais pas ?
        
        Il y a bien deux besoins qui existent. Le premier c'est pouvoir aller chercher la perf sur des problèmes très spécifiques ou y'a une poignée de mec qui vont pas faire de conneries et qui ecrivent des softs pour une plateforme donnée figée dans le marbre. Le deuxième c'est le reste du monde.
        
        En pratique, ca permet à la majorité des programmeurs pas trop cons, de raisonner sur du code concurrent et d'écrire des programmes qui marchent et qui marchera encore quand tu changeras de proco.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 16 mai 2013 à 17:43. Évalué à 2.
        
        Il y a des références dans cette présentation :
        http://www.capsl.udel.edu/courses/eleg652/2012/slides/05_sm.pdf
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 16 mai 2013 à 17:52. Évalué à 2.
        
        J'en profite pour rajouter une autre référence (mêmes auteurs) :
        Verification of Causality Requirements in Java is Undecidable. C'est quand même ballot. :-)
        
        Un de mes collègue a aussi pu montrer un exemple de code multithreadé qui peut être « optimisé » en respectant les règles du modèle mémoire de Java, et qui malgré tout provoquera une exécution non conforme aux souhaits du programmeur.
        
        Enfin, juste pour que nous soyons d'accord : je suis d'accord avec toi sur le fond : quand un langage intègre un modèle mémoire, c'est beaucoup mieux, et ça autorise la création de programmes concurrents dont le comportement est prévisible. Encore faut-il que le modèle en question soit correct/implémentable. Même un environnement tel qu'OpenMP qui est d'une certaine manière plus simple que le modèle mémoire de Java est extrêmement complexe à prouver en tant que modèle mémoire.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par ckyl le 16 mai 2013 à 18:01. Évalué à 2.
        
        Un de mes collègue a aussi pu montrer un exemple de code multithreadé qui peut être « optimisé » en respectant les règles du modèle mémoire de Java, et qui malgré tout provoquera une exécution non conforme aux souhaits du programmeur.
        
        Ca m'intéresse si tu l'as sous le coude.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 24 mai 2013 à 00:11. Évalué à 2.
        
        J'ai pas, mais il a enfin réussi à récupérer un visa, donc il est de retour. Je lui demanderai. :)
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 09:36. Évalué à 2.
        
        Tu veux dire que le mécanisme de cohérence mémoire n'entre pas en compte lorsque la donnée est en write buffer, mais pas encore en cache. Donc, pris en compte par le cpu ayant écrit mais pas les autres ? J'avais lu qu'il relachait sans cesse la cohérence mémoire, et l'itanium allait assez loin, mais je ne pensais pas à ce point-là.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par neologix le 16 mai 2013 à 10:25. Évalué à 2.
        
        Donc, pris en compte par le cpu ayant écrit mais pas les autres ?
        
        Et oui, d'où l'utilité des barrières.
        
        J'avais lu qu'il relachait sans cesse la cohérence mémoire, et l'itanium allait assez loin, mais je ne pensais pas à ce point-là.
        
        La performance est à ce prix.
        
        Pour vraiment s'amuser, il y a l'architecture alpha, qui peut réordonner les "dependant reads". Donc en gros, quand tu parcours une liste chaînée, tu peux récupérer une valeur non initialisée dans ton noeud: il faut une read barrier même pour lire une iste chainée ;-)
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 10:29. Évalué à 2. Dernière modification le 16 mai 2013 à 10:29.
        
        A l'époque où j'avais lu sur le sujet, il y avait les Cray qui avait un mode non-coherent (nc). C'était le seul moyen d'avoir toute la puissance disponible. Les codeurs s'arrachaient tellement les cheveux, qu'ils ont renoncer à ce genre de mode dans les machines suivantes. J'imagine que cela devait ressembler à un gros GPU mais avec des vecteurs de plusieurs centaines de flottant.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 16 mai 2013 à 16:31. Évalué à 2.
        
        Bah, le modèle SPARC v9 (RMO, Relaxed Memory Order) propose différents types de barrières mémoire: celles qui stoppent tout tant que toutes les opérations en cours ne sont pas terminées; celles qui permettent d’exécuter des loads spéculativement; celles qui permettent d'exécuter des loads et des d’exécuter stores spéculativement (tant que les dépendances de données sont respectées); et même d'émettre des loads spéculativement malgré la présence d'une dépendance de contrôle.
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par lasher le 16 mai 2013 à 16:14. Évalué à 2.
        
        Bon, "Sequential consistency" ça va beaucoup plus loin que "cohérent".
        
        <pedantic>
        Sequential consistency (SC—"Constance séquentielle" ?) garantit que tous les threads d'une machine a mémoire partagée voient les lectures et écritures mémoire dans un ordre identique. En pratique le matériel n'a pas a garantir que l'ordre des opérations est strictement identique, mais il doit apparaître comme si. Donc si j'ai 2 threads, dont l'un des deux au moins écrit dans une variable v, lorsque T0 écrit, alors T1 doit voir la séquence des valeurs de v changer au "même" moment. Les deux threads doivent donc s'accorder sur une séquence unique des valeurs successives de v.
        
        La cohérence ("Cache consistency" ou "Coherence") relaxe fortement SC. Désormais, l'ordre des opérations se fait adresse mémoire par adresse mémoire. Ainsi, si j'ai 2 threads (T0,T1) et deux variables, x et y, Je me fiche de savoir si T1 et T2 voient les écritures de x et y de façon totalement identique en tant que "paire" d'adresses mémoire , tant que les accès individuels a x sont tous vus dans le même ordre par tous les threads, et que les accès a y idem.
        </pedantic>
        
        [^] # Re: Ai-je bien compris ?
        
        Posté par Tonton Th (Mastodon) le 17 mai 2013 à 00:44. Évalué à 2.
        
        Ton volatile ne servira pas à grand chose
        
        C'est triste ton avis sur les coincoins.
# Linux perf

Posté par JoeltheLion (site web personnel) le 14 mai 2013 à 21:40. Évalué à 9.

Est-ce que tu as utilisé un outil utilisant les compteurs matériels de ton cpu pour étudier les performances de ton programme? Un outil comme linux perf (https://perf.wiki.kernel.org/index.php/Tutorial) est tout simplement irremplaçable pour ce genre de travail.
- [^] # Re: Linux perf
  
  Posté par steckdenis (site web personnel) le 14 mai 2013 à 22:18. Évalué à 1.
  
  J'avais déjà regardé du côté de cet outil, mais jamais de près. Et bien, c'est vraiment très pratique !
  
  Par contre, serais-ce possible d'invoquer perf depuis le code source du benchmark, ou seulement sur une partie du programme ? En effet, en utilisant "perf stat ./benchmark", les statistiques de tout le benchmark (y compris les entrées/sorties console, la création de la base de donnée, le mapping des fichiers) sont agrégées en un seul report, alors que j'aimerais n'avoir que la partie qui concerne la lecture de la base de donnée.
  - [^] # Re: Linux perf
    
    Posté par JoeltheLion (site web personnel) le 14 mai 2013 à 22:44. Évalué à 5.
    
    Essaie perf record/report, et viens m'en dire des nouvelles :-D
- [^] # Re: Linux perf
  
  Posté par lasher le 15 mai 2013 à 01:12. Évalué à 10.
  
  Bon alors, dans le principe je suis d'accord. En pratique, comme dirait mon ancien directeur de thèse, « il y a peut-être 20 ou 30 personnes dans le monde qui savent réellement quels compteurs utiliser et ce qu'ils font (et ceux qui existent mais qui ne compte pas ce qu'on croit) ».
  
  J'ai fait de l'analyse de performance pendant très longtemps. J'ai mis grosso modo un an à me retrouver avec un tout petit sous ensemble de compteurs qui comptent ce qu'il faut et dont je suis certain de ce qu'ils comptent. Et ce savoir est déjà dépassé : de Core 2/Core Quad on est passé à Nehalem, puis à Sandy Bridge… Ben mon savoir sur Nehalem était déjà à moitié faux (en plus du fait que certains compteurs avaient été renommés, et donc il fallait de nouveau tester ce qu'ils comptaient pour de vrai), et depuis les Sandy/Ivy Bridge, ben il y a peut-être 3 compteurs dont je suis sûr. :-)
  
  Ceci étant dit, j'ai pas fait d'analyse de perf depuis un bail, mais mon directeur (avec qui j'ai causé y'a quelques jours) me disait que comparé aux autres outils existants (HPCToolKit, PAPI, PerfMon), Linuxperf est définitivement le plus fiable, au moins sur x86/Intel (à l'époque j'avais été regarder comment PAPI comptait certains événements dont j'avais besoin, et j'ai remarqué qu'ils prenaient le mauvais compteur… J'ai arrêté d'utiliser PAPI).
  - [^] # Re: Linux perf
    
    Posté par JoeltheLion (site web personnel) le 15 mai 2013 à 09:22. Évalué à 2.
    
    Merci pour ce commentaire très intéressant! Mes quelques expériences avec perf m'ont effectivement montré qu'il faut prendre les résultats avec quelques pincettes, mais j'avais plus tendance à attribuer ça à mon manque d'expérience qu'à la complexité des compteurs.
    
    Par curiosité, dans quel domaine est-ce que tu travailles maintenant? Ca m'intéresserait de savoirs quels domaines recrutent des gens comme toi.
    - [^] # Re: Linux perf
      
      Posté par lasher le 15 mai 2013 à 16:38. Évalué à 4.
      
      L’expérience joue un énorme rôle aussi. Faire la course aux cache misses (par exemple) n'est pas toujours payante car on sous-estime d'autres facteurs qui pourraient jouer sur la (non-)performance d'une application.
      
      Pour répondre a ta deuxième question, je fais de la recherche dans une fac aux USA, mais pas en analyse/mesure de performance. Je fais dans les modèles d’exécution pour machines parallèles (c'est a dire : modèle de concurrence, modèle mémoire, et modèle de synchronisation). On implémente tout ça dans un runtime (que j’espère pouvoir libérer très bientôt).
  - [^] # Re: Linux perf
    
    Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 09:47. Évalué à 2.
    
    Il y a un peu plus de 30 personnes qui font des cpu dans le monde :)
    
    "La première sécurité est la liberté"
    - [^] # Re: Linux perf
      
      Posté par lasher le 15 mai 2013 à 16:08. Évalué à 2.
      
      Il fallait comprendre : "30 personnes par type de processeur". :)
      - [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 15 mai 2013 à 16:26. Évalué à 3.
        
        :)
        
        Les téchniques disponibles par processeurs, ne sont pas pléthoriques. Je ne connais pas ton équipe, mais toutes les universitaires que j'ai vu bosser dans le domaine des compilateurs avaient une vision très vague de la façon de fonctionner d'un cpu.
        
        Genre cela peut les défriser quand on leur dit :
        - que plus d'instructions peut permettre d'aller plus vite que moins
        - que l'instruction la plus lente est souvent un load
        - que le temps d'accès à la mémoire, n'est absolument pas uniforme, avec un rapport environ de 100 entre le plus lent et le plus rapide.
        - qu'une multiplication est une instruction très rapide de nos jours, mais pas du tout une division
        
        "La première sécurité est la liberté"
        
        [^] # Re: Linux perf
        
        Posté par lasher le 15 mai 2013 à 16:43. Évalué à 2.
        
        L’équipe dont je faisais partie se spécialise dans la création d'outils pour la mesure et l'analyse de performance. Ce sont loin d’être des manches. Tout ce dont tu parles, nous le savons bien. ;-) J'ai passé une soirée de rêve avec mon directeur à l’époque à utiliser gdb et essayer de comprendre ce qui se passait avec la MKL (multiplication de matrices) sur Itanium 2.
        
        [^] # Re: Linux perf
        
        Posté par Ontologia (site web personnel) le 16 mai 2013 à 10:39. Évalué à 2.
        
        mdr, je vois de qui tu parles :-)
        A sa décharges, ça fait pas longtemps que la multiplication est rapide : en 2003, c'était pas encore le cas.
        
        Mais si on veut vraiment contrôler son code, la solution n'est-elle pas de faire des prefetch à la main ?
        
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 10:55. Évalué à 2.
        
        oula non. La meilleur distance de prefetch dépend de l'architecture. A la limite, le preload est mieux : tu coupes ta boucle en 3, pour qu'en simultané tu ais la lecture des données n+1, le traitement des données n, et l'écriture des données n-1. Si le parcours suit un pattern pas trop complexe, les prefetch automatiques pourront s'en sortir.
        
        "La première sécurité est la liberté"
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 16 mai 2013 à 11:45. Évalué à 2.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 11:54. Évalué à 2.
        
        Je l'avais lu à une époque :) dans mon souvenir, il y avait 3 pdf. Concernant les perfs pour le codage en C, AMD avait sorti quelques choses de très lisible.
        
        Sans doute ce truc : http://support.amd.com/us/Processor_TechDocs/22007.pdf
        
        "La première sécurité est la liberté"
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 16 mai 2013 à 12:01. Évalué à 2.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 12:17. Évalué à 4.
        
        Il faudrait que je le relise, mais quand il était sorti, il y avait des trucs qui m'avait fait tiquer, (mais j'ai oublié quoi :).
        
        Il faut connaitre aussi un peu le genre de truc que sortent les compilo C, surtout avec la vectorisation automatique, en changeant un peu son code, le compilo peut faire plus de chose.
        
        De plus, laisser faire le compilo marche bien pour les monstres comme les Intel core. Mais pour des trucs plus simple comme les PPC 603 (et donc les ARM des smartphone), tu te prends tous les problèmes des CPU les plus simple : prédiction de branchement statique, pas de prédiction de saut dynamique (vtable), très peu de write buffer (donc mélanger lecture et écriture est pénalisant), l'alignement mémoire est primordial, etc…
        
        La doc d'AMD parle d'assembleur mais aussi de code C.
        
        Par exemple, un code que l'on trouve dans le kernel linux, n'est pas intuitif :
        
        for (i=0;i<N;tab+=4,i+=4){
        tab[0] = tab[0] + n…
        tab[1] = tab[1] + n…
        tab[2] = tab[2] + n…
        tab[3] = tab[3] + n…
        }
        C'est plus rapide car l'indexation d'un tableau par une constante, génère une seul instruction contrairement à "tab[i]" qui nécessite une addition.
        
        Le cout d’usage des pointeurs est souvent négligé. Tous les codes utilisant des "str->foo" passe très souvent par la mémoire, plutôt que par un registre.
        
        "La première sécurité est la liberté"
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 16 mai 2013 à 14:14. Évalué à 3. Dernière modification le 16 mai 2013 à 14:15.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 16 mai 2013 à 15:15. Évalué à 2.
        
        "le add supprimé c'est 1 cycle"
        
        Le add représente bien plus d'un cycle, car il y a une dépendance read-after-write. C'est évidement une amélioration du loop unrolling, mais bon, c'est la base, même gcc le fait tout seul (ou presque).
        
        "via un, à la louche, load R16, PTR [R15 + CST]."
        
        C'est bien ce que je reproche, il passe par la mémoire au lieu d'utiliser un registre (en cas de réutilisation du str->foo bien sûr). Cela doit être dû à la gestion des alias mémoire par le compilo C (2 pointeurs du même type dans le même scope et tout passe par la mémoire, car l'un peu aliaser l'autre).
        
        D'ailleurs, cela me rappelle aussi une personne qui pensait que parce que la donné se trouvait dans les write buffer, cela n'était pas la peine d'essayer de passer par un registre. Pourtant, la bande passante, même entre un registre, et un write buffer n'a rien à avoir. Il y a souvent qu'un ou 2 bus (1read/ 1write) pour gérer la mémoire, or un x86 gère 5 instructions à la volé soit 10 read et 5 write. Et encore, il n'est pas question du surcout de la mémoire à cause de la gestion de la pagination et de sa cohérence (lecture retardé juste après un write pour vérifier que l'on ne relit pas la même donné).
        
        "La première sécurité est la liberté"
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 16 mai 2013 à 21:29. Évalué à 2. Dernière modification le 16 mai 2013 à 21:30.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 17 mai 2013 à 08:59. Évalué à 1.
        
        r1 = addr + r0 r2 = [r1]
        
        La dépendance est sur r1. Avec un immédiat tu as : r2 = [r1+imm]
        
        // après c'est de la manip de registre
        
        C'est souvent complexe à faire en C malheureusement, il faut que cela soit explicit. "restrict" n'est pas encore utilisé partout. J'ai surtout l'impression que c'est utilisé dans gcc, mais c'est encore loin d'avoir atteint les compilo pour l'embarqué.
        
        "La première sécurité est la liberté"
        
        [^] # Re: Linux perf
        
        Posté par grim7reaper le 17 mai 2013 à 09:08. Évalué à 1.
        
        Ça dépends des constructeurs je suppose.
        J’avais bossé sur une carte de traitement vidéo, de Texas, et le compilo’ le supportait sans problème.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 17 mai 2013 à 09:20. Évalué à 1.
        
        Sans doute. Mais il faut aussi faire attention au restrict, cela doit pouvoir introduire des bugs subtiles, si on veut utiliser un autre pointeur pour se balader à l'intérieur d'un tableau par exemple.
        
        "La première sécurité est la liberté"
        
        [^] # Commentaire supprimé
        
        Posté par Anonyme le 17 mai 2013 à 10:19. Évalué à 3.
        
        Ce commentaire a été supprimé par l’équipe de modération.
        
        [^] # Re: Linux perf
        
        Posté par Nicolas Boulay (site web personnel) le 17 mai 2013 à 11:36. Évalué à 1.
        
        "Dans 99% des cas. Sans pointeur, tu auras très très souvent :"
        
        Non, dans 80% des cas, il s'agit d'un paramètre de ta fonction, qui est dans un registre.
        
        "(C'est généralement juste l'affaire d'un changement de paramètre et c'est tout)…"
        
        bah non :)
        Les compilo sont souvent uniquement à la génération d'avant.
        
        "La première sécurité est la liberté"
# Pas thread safe

Posté par pyknite le 14 mai 2013 à 22:25. Évalué à -1.

En fait, si j'ai bien compris ce que tu fais, tu utilises des instructions atomiques (fetch and add, compare and swap, test and set,… Je crois que j'en ai oublié une ou deux encore).
C'est "normal" que cela aille beaucoup plus vite. Ces instructions nécessitent, comme l'indique le "atomique", qu'un seul coup d'horloge pour être exécutée (et surtout j'imagine que tu fais de l'attente active dans tes algos, alors qu'en général avec des mutex&co on fait de l'attente passive (ce qui n' aucun intérêt lorsque l'on utilise des instructions atomiques)).

Par contre, quand tu dis que t'as version des lecteurs-redacteurs (avec priorité aux lecteurs) est thread-safe depuis que tu utilises ces instructions, j'en doute un peu. Les algorithmes utilisant des instructions atomiques sont ~~relativement~~ très compliqués (et encore plus à débogguer… Je pense à tout ceux qui on ont fait et qui on ont chié avec des ABA un peu partout ;) ). Je te conseille de lire de la docs à leur sujet (d'ailleurs si ça t'intéresse, je peux demander à un de mes profs de l'année passée si il veut bien me filer son cours en pdf à ce sujet).

En plus, généralement, ce genre d'algorithmes sont orientés "lock-free structures", c'est une autre façon de penser que lorsque tu codes avec la librairie pthread…

Je te laisse un peu chercher ;) Une petite piste, regarde du coté des "non blocking algorithm" et des "loch-free structure".

(My 2 cents… J'espère ne pas avoir dit trop de conneries, mes souvenirs à propos de ce types d'algorithmes sont un peu rouillé ;) )
- [^] # Re: Pas thread safe
  
  Posté par Troy McClure (site web personnel) le 14 mai 2013 à 23:22. Évalué à 4.
  
  Ces instructions nécessitent, comme l'indique le "atomique", qu'un seul coup d'horloge pour être exécutée
  
  Ca prend plus d'un cycle d'horloge. Dans mon souvenir c'est de l'ordre de 100 cycles pour une instruction atomique quand un lock de mutex (sans contention) en prend 300
  - [^] # Re: Pas thread safe
    
    Posté par pyknite le 14 mai 2013 à 23:38. Évalué à 1.
    
    Euh oui, en effet, je me suis mal exprimé…
    Ce que je voulais dire, c'est quand on fait un fetch and add, par exemple, le pipeline du proc "est à nous", on ne peut pas se faire "préempter" pendant une instruction de ce type, on est donc sûr et certain que cette instruction à été effectuée sans que la valeur que l'on modifie n'ai été modifiée par un autre thread.
# Suggestion

Posté par bobbysixkiller le 15 mai 2013 à 00:22. Évalué à 2.

Serait-il possible que ces instructions différentes/supplémentaires aient une influence sensible sur l'efficacité de la prédiction de branchement du processeur?
Plus de détail sur le sujet: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/
Un autre outil utile: http://valgrind.org/docs/manual/cg-manual.html
# On oublie le plus important !!!

Posté par oinkoink_daotter le 15 mai 2013 à 15:39. Évalué à 5.

Nan mésérieu, allo quoi !

(j'étudie à l'Université Libre de Bruxelles)

C'est quelle licence ?
# C'est bien beau tout ça mais...

Posté par Spack le 16 mai 2013 à 15:11. Évalué à 8.

…on voudrait bien connaître la fin de l'histoire. Il y a plein de fils intéressant mais comme le principal témoin fait obstruction et cache ~~le code~~ les preuves, impossible de savoir qui est le coupable.

Va t-on enfin savoir qui a tiré sur M. Benchmark ?
# Idée

Posté par MCMic (site web personnel) le 30 mai 2013 à 18:34. Évalué à 2.

Peut-être qu'avec la version qui utilise des opérations atomiques, le cœur n'est pas partagé pareil avec les autres processus (puisqu'il ne peut pas être partagé durant l'opération atomique) et que du coup ton programme accapare plus de cycles que la version normale (qui elle se fait bouffer des cycles par ton WM, ton browser, ton terminal, … plus régulièrement).

En gros, tu obtiens ce que tu obtiendrais en exécutant la première version avec un nice négatif devant.

Après, c'est peut-être pas du tout ça et pas du tout possible, mais c'est ce qui m'est venu à l'esprit en lisant cette histoire.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.