Le cœur des processeur x86 récent n'est pas vraiment RISC. Les instruction CISC sont bien décodées vers des micro-instructions qui forment un jeu plus simple que celui de l'architecture de base, mais ça reste loin d'être du RISC.
Il suffit de regarder les manuel de Agner que cite pour s'en convaincre. La majorité des instructions sont décodé vers une seule micro-instruction qui en garde donc toute la complexité.
C'est surtout légalement inexact. Au départ, on a zéro droit sur un logiciel, c'est bien pour ça qu'il y a des licences libres et force tergiversations et débats chez les développeurs pour savoir laquelle mettre. On ne peut pas priver les gens de ce qu'ils n'ont jamais eu (si je suis privé de dessert, c'est bien parce qu'il était convenu au préalable que j'y avais le droit).
On peut être privé d'un droit considéré comme fondamental, ici appliqué au logiciel. Mais bon dans la situation actuelle, c'est pas vraiment considéré par fondamental par beaucoup de monde, du coup c'est beaucoup plus discutable (ça marche bien pour les convaincus quoi).
Faut pas abuser non plus. À la base c'est le développeur qui a tous les droits, au moment ou il publie le logiciel il choisit ceux qu'il donne.
J'ai des tas de morceaux de code qui trainent sur mon disque et que je n'ai jamais publiés et en dehors de moi, personne n'a de droit "fondamental" dessus. Tant que je ne le diffuse je ne te prive d'aucun droit sauf si on part sur du communisme extrême où tout est à tout le monde. Mais dans ce cas, pourquoi ne l'appliquer que au logiciel ? Est-tu d'accord pour me donner des droits sur tout ce que tu possèdes ?
Par contre, quand je publie mon code, je choisis quels droits je donne à l'utilisateur, le terme privateur n'a donc bien aucun sens ici.
Et donc je suppose que ça doit vachement te révolter que la constante 0xCAFEBABE soit utilisée pour identifié les fichier objets au format Mach-O (notamment MacOS X) ainsi que les fichier bytecode de Java ?
J'ai toutefois trouvé un peu bizarre que la gestion du retour à la ligne ne soit pas fournie comme en C++ (avec std::endl). De fait, on doit faire attention à ce léger détail et différencier les cas selon les OS à la main, ce qui est assez dommage.
En C++, std::endl n'a pas grand chose à voir avec la gestion multi-plateforme du retour à la ligne. Un simple '\n' sera traduit par le bon retour à la ligne utilisé par la plateforme.
std::endl est identique à '\n' de ce point de vue, la différence est qu'il force un flush du buffer. Donc, il ne faut l'utiliser que si ce flush est désiré. Son nom est d'ailleurs à mon avis très mal choisi et amène à des codes inutilement lents quand un codeur pensant bien faire l'utilise pour écrire un fichier de sortie par petits fragments et au final perd tout le bénéfice du buffer de sortie.
Je ne connais pas Go mais à mon avis il y a de fortes chances pour que le '\n' soit correctement géré et donc s'adapte automatiquement à la plateforme.
Je fais partis des gens qui ont eu la chance de le rencontrer de son vivant et de le remercier alors. Je n'ai pas eu l'occasion de le faire en public avant mais ça ne change rien au fait que je peut le faire maintenant.
Je profite juste de ce commentaire pour faire taire tous les grincheux qui ne manque pas de critiquer le fait qu'il n'ait pas le droit aux mêmes honneurs que Steve Jobs pour leur dire que Steve s'en fout sûrement royalement, ou tout du moins s'en foutait il y a quelques années.
Il était parfaitement conscient de ce qu'il a réaliser pour l'informatique et ne le niait pas, mais était aussi parfaitement conscient qu'il ne l'avait pas fait seul. Il parlait surtout du fait qu'il avait eu la chance d'être au bon endroit au bon moment. Dans un labo ou l'on avait su laisser quelques personne compétentes faire un truc un peu à part du boulot que l'on attendait d'eux sans leurs mettre trop de bâtons dans les roues. D'arriver au bon moment, quand l'informatique avait vraiment besoin de quelque chose tel que Unix et le C.
Il m'a dit qu'il espérait que n'importe qu'elle équipe dans les même conditions au même moment aurait fait la même chose. Je pense qu'il y a du vrai dans ce qu'il a dit même si je n'en suis pas aussi convaincu que lui.
C'était loin d'être une personne parfaite (notament il ne buvait pas assez à mon gout...) mais c'était quelqu'un de bien.
C'est en effet un problème. Mais c'est ce que l'on a de mieux actuellement. L'avantage de IEEE 754 c'est que l'on dispose d'une norme précise qui offre de bonnes garanties et qui est implémentée en hard donc qui permet de faire des calculs rapide.
Le choix qui ont été fais dans la norme n'ont pas été fais de manière arbitraire mais pour permettre de réellement faire du calcul mathématique. Il existe des représentations qui ont de meilleur propriété d'un point de vue mathématique, mais le résultat est toujours le même : elles ne sont pas vraiment utilisables.
Garantir l'associativité par exemple entraine toujours de gros problèmes lors de l'analyse de la propagation d'erreurs.
Je rêve d'une représentation des réels qui soit un vrai corps commutatif avec les mêmes garantie que l'IEEE 754 mais c'est tout simplement impossible. Actuellement au moins, l'IEEE 754 reste le meilleur compromis. Il y a quelques principes à bien garder en tête, et pour les passage critique du code, il est relativement simple de calculer l'erreur maximale que l'on obtient.
Je dirais que c'est un peu la raison d'être des compilateurs : tenir compte de la cible. Même si un travail manuel serait meilleur, il est infiniment plus long qu'une compilation.
C'est même pour cela que la libm est avant tout codée en C avec de très bonnes performances. Le passage à l'assembleur n'est fait que pour certaines architectures et que pour certaines fonctions. Réussir à faire mieux que le compilateur est même souvent très difficile.
Par contre, il n'y a pas de magie, le compilateur ne trouvera pas tout seul la bonne réduction et la bonne approximation. L'humain reste indispensable à ce niveau là. (pour l'instant en tout cas)
Concernant la précision, comme la définis-tu ? En relatif uniquement ? Avec une petit touche d'absolue pour gérer autour de zéro ?
De manière générale et pour la libm, la précision est définie par le standard IEEE754. En gros ça veux dire que tu dois renvoyer un résultat identique à ce que donnerais le calcul exact puis arrondis de manière à être représentable.
La ou c'est chiant c'est qu'il y a différent mode d'arrondis...
Dans mon cas, l'optimisation ce justifiais car mon code passait près de 46% de son temps à calculer des exp() et des log(). Le truc c'est que je n'avais pas besoin de gérer les nombres démoralisés, un seul type de NaN, pas d'infinis en entrée et surtout les valeurs d'entrée ne pouvait couvrir qu'un intervalle plus réduit.
Donc dans ce cas là, même avec une précision complète, on gagne déjà beaucoup : presque un facteur x2 sur les deux fonctions.
Pour ce qui est de la précision, une partie du code avais besoin de la précision complète, c'est elle qui garde le code FPU avec ses 80bits et qui fait le calcul en long double. Par contre, une grosse partie du code travail sur des doubles mais peut tolérer environs 3bits d'erreurs. Cette portions utilise le code SSE2 avec un polynôme tronqué qui fournis juste ce dont le code à besoin et permet en plus de profiter du SIMD. Au final les exp() et log() ne représentent plus que 6% du temps de calcul.
Par contre, avant de jouer avec ces fonctions il faut bien faire attention et bien mettre des gros warning. Dans mon cas, si tu leur donnes des valeurs qu'elles n'attendent pas, elles te renvoie du bruit. Leur utilité est donc très liée à mon programme. Dans le cas général ou tu dois respecter le standard IEEE 754 tu n'auras jamais de tels gains. Une bonne fonction exp() à un gain non-négligeable par rapport à la version FPU pour le cas général, par contre, si l'entrée ou la sortie est un NaN ou un Inf, ce n'est souvent pas le cas.
Pour les nombre dénormalisé, c'est souvent kifkif car la FPU à une pénalité de près de 200 pour ces cas là elle aussi.
Le gros problème c'est que pour trouver la manière la plus rapide de calculer une de ces fonctions il faut tenir compte à la fois de l'aspect mathématique et de l'aspect informatique.
J'ai vu un cas ou ajouter une division qui prend 40cycles permettait d'obtenir un code plus rapide car pendant que le processeur s'occupait de la division dans l'unité flottante il y avait suffisamment d'autres calculs à faire en parallèle. Au final ce code était presque trois fois plus rapide que la version plus classique avec la même précision car la réduction était triviale.
Il y a moyen de produire automatiquement différentes alternatives, mais il faut toujours regarder à la main comment chacune d'entre elles peut être implémentée pour choisir la meilleure. Quand j'ai bossé sur l'exponentielle par exemple, j'avais du code pour me produire différentes formes d'approximations sur les intervalles qui m'intéressait pour différentes précisions. Ensuite je regardait à la main comment je pouvais m'arranger pour organiser au mieux le calcul.
J'ai fais des version FPU et SSE2 à l'époque et elles utilisent des méthodes de calcul différentes. Je me penche en ce moment sur une version AVX et à priori ce sera encore différent.
Tu as plein de méthode pour calculer toutes ces fonctions et la bonne méthode dépend de beaucoup de choses. En pratique, le gros problèmes c'est toujours la précision. Les différentes méthode ne sont généralement applicable de manière raisonnable que sur un intervalle de valeurs petit, il faut donc trouver le meilleur compromis entre :
la réduction : elle doit être simple à calculer et facilement réversible sans perte de précision ;
le calcul réduit : il doit être suffisamment précis pour les besoins et rapide.
Les développement limités ont plusieurs avantages : ont peu généralement obtenir la précision que l'on veux sur n'importe quel intervalle pas trop gros et avec un peu de bol le polynôme peu ce mettre sous une forme sympa pour faire plusieurs opérations en parallèle et profiter au maximum du processeur.
Mais le sujet est vaste et des livres entiers ont étés écris dessus...
Tout d'abord les calculs sont fais avec une précision de 32bits uniquement pour les versions soft là ou la FPU va faire les calculs au moins partiellement en 80bits. Pour l'exponentielle par exemple, l'appel à f2xm1 sera fais avec 80bits de précision.
Les résultats ne sont donc valable que si tu as besoin de peu de précisions. (dans ce cas tant pis pour la FPU, elle n'avait qu'a savoir faire le calcul en 32bits...)
Les bench sont réalisés sur de très gros vecteurs puisque l'objectif est de comparer avec des versions vectorielles, l'impact des accès mémoire n'est pas négligeable et les résultats sur des appels fréquents mais plus espacés peuvent être très différents.
J'ai pris l'exemple de l'exponentielle car justement j'ai beaucoup bossé dessus et sur les différentes manières de l'approximer. Les valeurs en nombre de cycles que je donne sont les valeur réellement mesurées pour l'approximation software dans le cas ou les constantes sont dans le cache L1. Si les constantes ne sont que dans le cache L2, il y a un trou de 17 à 22 cycles en moyenne à rajouter.
Pour la version hardware, ce sont les valeurs théoriques maximum que l'on peut atteindre mais je n'ai pas trop de doute dessus. Le f2xm1 bloque vraiment les ports flottants donc il y a peu de difficultés à prédire la durée.
Pour ce qui est des loads, ils n'ont que peu d'impact lorsqu'ils se font depuis le cache L1. Le port de lecture est saturé sur le début du calcul mais il n'y a pas de cycles perdus, et il est disponible pendant l'étape finale pour charger les données des instructions qui suivent le calcul de l'exponentielle.
Si les constantes ne sont pas dans le cache L1, ça veux généralement dire que tu fais peu appel à ces fonctions et que donc une différence d'une vingtaine de cycles ne changera rien de manière globale.
Pour ce qui est de l'instruction f2xm1, c'est loin d'être la plus lente. Si on oublie fnsave et frstor qui sont un peu hors de propos mais qui culminent à plus de 150 cycles ; on trouve quand même parmi les instructions complexes :
fsin et fcos qui suivant les valeurs d'entrée prennent entre 40 et 100 cycles ;
fsincos qui prend un peu plus d'une centaine de cycles ;
fyl2x et fyl2xp1 qui prennent 80 cycles ;
fptan et fpatan qui prennent en gros 115 cycles.
Dans les fonctions complexes, il n'y a que fsqrt et fscale qui prennent moins (27 et 12 cycles respectivement). La fonction exponentielle est un peu particulière car la réduction est simple et peu se calculer très rapidement. Si on prend le calcul de tan() comme exemple, on peut être en dessous des 115 cycles en soft aussi, mais la réduction est plus complexe et donc l'exemple est moins facile à expliquer.
Ce qu'il faut bien voir c'est que d'un point de vu hardware, la FPU x87 ne fait que survivre comme elle peut et les instructions complexes sont elles bien mortes. Le seul intérêt qu'il reste au x87 c'est la précision sur 80bits, pour tout le reste il faut passer à SSE qui ne dispose pas d'instructions complexes et donc nécessite des implémentations hardware.
Les processeurs récents ont encore de très bon multiplieurs dans la FPU car ce sont les mêmes que pour le SSE mais pour les instructions complexes ça dépend vraiment des générations. Elle sont découpée en un très grand nombre de micro-instructions et leur efficacité varie beaucoup. L'idée c'est de les coder en ajoutant le moins possible de micro-instruction, donc suivant ce qui est disponibles dans le reste du processeur ça deviens très variable.
Par exemple, f2xm1 qui prend 58 cycles sur un core i7 ne prenait que 45 cycles sur un core 2 en 45nm. C'est l'avantage des versions soft, on connais leur comportement de manière beaucoup plus fiable.
Pour ce qui est de faire des calculs sur la FPU et le SSE en même temps je te le déconseille, les deux utilisent les mêmes ports pour leurs micro-instructions et les mêmes unités de calcul. Tu ne peux que perdre en performances de manière globale.
Pour tous le message suivant, je prend comme exemple un processeur intel core i7. Sur ce processeur, une multiplication flotante prend 5 cycles mais il est possible de démarrer une nouvelle multiplication à chaque cycles avec un maximum de 3 multiplication en même temps. Pour les additions et soustraction c'est la même chose mais en 3 cycles.
Pour prendre un exemple que je connais bien : la fonction exponentielle. L'exemple est un peu biaisé mais j'y reviendrais à la fin. Son calcul avec les fonctions interne repose sur l'instruction f2xm1 qui prend 58 cycles.
Sont calcul en soft ce fait par une réduction de e^x vers 2^k * e^f avec f dans l'intervalle [-0.5,0.5] :
La réduction nécessite 3 multiplications, une addition et deux soustractions. Mais, les trois multiplication peuvent être faites en parallèle. Au final la réduction ce fais en 13 cycles.
Le calcul de l'exponentielle sur l'intervalle réduit ce fait par une approximation polynomiale. La méthode basique demande un polynôme de degré 6 pour avoir la bonne précision, en pratique 9 multiplication qui ne peuvent être faites en parallèle. Mais si on passe par un polynôme en forme de Pade, on passe a 11 multiplication mais qui peuvent être faites en parallèle deux par deux. Si on rajoute les additions, on arrive à 24 cycles.
Le calcul final ce fait avec une opération logique qui peut être faite en parallèle de l'étape précédente, et une multiplication et une addition pour un coût de 6 cycles.
Si on rajoute la gestions des NaN et autres Inf, on arrive à un 47 cycles une fois bien tassé. Si on a besoin de la gestion des nombres dénormalisés, on rajoute 4 cycles au cas standard. (le cas dénormalisé prenant lui beaucoup plus de temps...)
On peut ce dire que l'économie est faible, mais ce qu'il faut voir c'est que l'instruction f2xm1 seule ne suffie pas à calculer l'exponentielle. L'exponentielle est calculée avec la formule e^x = 2^(x * log2(e)), il faut rajouter au final une audition, une soustraction et une multiplication ainsi que quelque petits détails et prendre en compte que f2xm1 bloque les port 0 1 et 5 de l'unitée de calcul et que donc on ne peut rien faire d'autre pendant 58 cycles. On arrive à 73 cycles auxquels il faut rajouter 3 cycles pour être sûr que tout ce passe bien avec les dénormalisés.
Au final la version soft est nettement gagnante. Principalement car la multiplication est très rapide et à un reciprocal throughput d'un seul cycle.
Par contre, cet exemple est biaisé : les deux fonction sin et cos sont globalement aussi rapide en hard qu'en soft mais ce sont les seules avec la fonction sincos qui calcule les deux en même temps car ce sont les seule ou la version hardware est vraiment très proche de la version software. Pour toutes les autre fonctions du même genre, il y a souvent une réduction à faire à l'aide de quelques instructions avant. Et cette réduction est nécessaire aussi bien en hard qu'en soft.
Mais la version soft conserve l'avantage de ne pas occuper tout les ports et donc de permettre de dispatcher quelques autres instruction en même temps si possible ainsi que d'être beaucoup plus portable que de l'assembleur.
Et juste pour terminer, l'instruction fsin ne prend un peu moins que 50 cycles que dans le cas ou tu veux une précision sur 32 bits. Pour une précision complète elle demande 100 cycles, il y a moyen de faire énormément de choses pendant ce temps la notament environs 30 multiplication s'il n'y a pas de dépendances trop fortes.
des fonctions comme tan/sin/cos, etc... qui peuvent être plus rapide que leur version avec du code SSE surtout si la précision importe.
En pratique c'est faux. Ces instructions sont très couteuses en cycles. Une version soft de ces fonctions bien codée est souvent plus rapide que la version hardware des processeurs.
C'est particulièrement le cas depuis que la multiplication flottante est devenue rapide. À l'époque ou la multiplication prenait plusieurs dizaine de cycles ce n'était pas le cas, mais maintenant je ne pense pas qu'il reste des processeurs ou la version hardware soit plus rapide que la version software.
La dépêche le rappel bien, les prix Ig Nobel ne récompensent pas des recherches stupides mais intrigantes et faisant sourire. Et pour que ce soit marrant elle sont en général présentées de la manière la plus drôle possible...
Mais il ne faut pas oublier de relativiser et de bien ce rendre compte qu'il y a quand même un travail serieux derrière beaucoup de ces recherches. Par exemple :
physiologie: L'aspect contagieux du bâillement chez les êtres vivants reste un mystère et l'étude présenté à été faite sur des tortue d'une espèce particulière car cette espèce est particulièrement intéressante pour tester une hypothèse car elle est insensible à la majorité des stimuli envisagés. Il est donc simple de tester l'hypothèse sans interférences.
médecine: De nombreux états physiologiques peuvent influencer la prise de décisions et la aussi l'envie de pisser est un bon sujet d'étude car il est simple à mettre en place expérimentalement et permet de poser les bases des théorie qui pourrons ensuite être validées sur d'autres états avec des protocoles plus complexes et couteux.
chimie: Le bruit comme alarme à de nombreux problèmes, une personne endormie sera réveillée brutalement et fortement désorientée ce qui en cas d'urgence peut causer des soucis, de même une foule réagi de manière chaotique à une alarme sonore. Les alarme odorantes on beaucoup moins de problème à ce niveau là mais sont moins efficace face à un public non informé. La technique mise au point à l'aide du wasabi permet d'obtenir une alarme qui fait réagir même un public non informé de manière raisonnable.
Pour les autres, je vous laisse aller regarder par vous même et faire le tri...
Sauf que entre :
- utiliser un mutex fournis par l'OS ou une opération atomique,
- espérer que le compilateur va produire le bon code et que les instructions font ce que l'on suppose,
La première solution à l'avantage de marcher et en plus d'être plus portable.
Le code en assembleur, il vaut mieux le laisser au compilateur à travers les builtin et intrinscs, dans des bibliothèques bien testées ou dans le noyeau.
Oui, tu peut avoir un thread qui est toujours bloqué mais, car il y a un mais comme toujours ;-) ce genre de mécanisme : instruction atomiques ou mémoire transactionelle, serve le plus souvent à implémenter des algorithmes de type "forward progress".
C'est-à-dire que en général ce qui t'intéresse c'est de garantir que de manière globale le système avance. Si ton thread échoue toujours ce n'est pas grave car à chaque fois qu'il échoue cela veut dire qu'un autre à réussi et donc que globalement le système à progressé.
Et si tu gère bien le truc, en général tu as de bonne garanties probabilistes sur les progres de chaque threads. Du style la probabilité d'échouer d'un thread décroit de manière quadratique avec le nombre d'échec ou ce genre de choses.
Si tu as besoin de garanties plus fortes comme dans le cas d'un système temps réél, il faut passer à d'autres méthodes. Mais le besoin en garanties plus fortes est relativement rare en comparaison des besoins satisfait par le forward progress, et surtout c'est beaucoup plus compliqué à gérer donc tu as très peu de chances de voir ça arriver dans du hardware rapidement.
Non ça ne marchera pas car chaque cœur à son propre cache et sur les processeur récent le passage par le cache L1 est obligatoire.
Par contre, si tu rajoute le prefix LOCK devant ça marche, tout simplement car cela deviens une instruction atomique, mais vu que c'est coûteux le compilo ne l'ajoute pas automatiquement partout, uniquement quand tu lui demande explicitement en utilisant les intrinsics...
Donc au final, on en reviens toujours au même point : quoi que tu fasses il y a une faille sauf si tu demande explicitement la version atomique.
En plus, ce reposer sur un comportement spécifique d'un processeur c'est plutot extrêment pourris à ça ne n'apporte qu'une chose : des emmerdes plus ou moins rapidement.
Mais ta file d'attente d'opérations doit gérer le cas ou plusieur thread veulent ajouter des deltas et donc repose sur un mutex ou des CAS...
Dans la pratique tu n'utilises pas forcément un mutex de manière explicite, pour éviter les emerdes il peut être implicite et gérer par une sous classe ou par une instruction spéciale du langage, mais ça reste beaucoup plus efficace et moins risqué que de passer par un thread supplémentaire.
Le premier message parle d'instruction atomique dont le CAS. Victor Stinner répond que l'on ne peut pas les utiliser car il y a quatre pointeurs à modifier. --> d'un point de vue instruction atomique c'est forcément du CAS ou du load-lock ici.
Je lui répond qu'en fait il n'y en a que deux, et vu que l'on parle d'instruction atomique et de modifier des pointeurs, c'est encore du CAS... je le dis même de manière explicite à la ligne du dessous.
Toutes les instructions atomiques qui permettent d'affecter un pointeur on globalement le même comportement : tu affectes la valeur s'il elle n'a pas été modifiée depuis un certains temps.
Donc pour tous les cas ou l'on utilise des instructions atomiques (ce qui est le sujet de ce thread) il n'y a besoin que de deux affectations atomiques. Si elles échoue, tu refais les deux autres affectations et tu réessayes, c'est le principe de ces instructions.
Dans le cas de la mémoire transactionelle c'est en effet différent puisqu'on garantit l'atomicité d'une transaction sans tests avec les valeurs précédentes. C'est une stratégie différente mais, même si c'est le thème du journal, ce thread à pour thème les instruction atomiques.
Non, il n'y a que deux pointeurs à modifier. Tu commence par modifier les deux pointeurs qui sont dans le nœud à ajouter, pour ceux la tu n'as besoin d'aucune protection. Ensuite, tu modifies les deux pointeurs externes.
Et certains processeur supportent le CAS sur deux valeurs, par contre en général elles doivent être contiguës en mémoire ce qui n'est pas le cas ici.
Mais que ce soit avec de la mémoire transactionnelle ou n'importe quoi d'autre, dans tous les cas, il vaut mieux mettre le minimum d'affectations dans le atomic.
Le problème des mutex n'est généralement pas leur coût au moment du lock et du unlock. A ce niveau c'est plutôt devenu très rapide sur un mutex de base. (pas de lock récursif ou autres)
Le soucis c'est plutôt que les mutex sont pessimiste, tu doit faire un lock même si il y a très peu de chances qu'il soit nécessaire.
La mémoire transactionelle est plutôt à comparer à l'instruction compare-and-swap. Tu fais tout ton calcul comme s'il n'allait pas y avoir de problèmes, et au moment de stocker le résultat, tu vérifie juste que personne n'a fait de connerie pendant ce temps.
En gros :
tu lis la valeur de départ
tu fais ton calcul
tu stocke le résultat si personne n'a modifié la valeur de départ.
Si la probabilité que de thread modifient la même zonne est très basse, en général tu n'as pas à recommencer ton calcul.
Cette stratégie permet d'éviter les mutex et donc le cout associé aux lock, et surtout permet de ce passer complètement du lock, donc tu n'empêche pas un autre thread de bosser.
C'est particulièrement efficace dans le cas ou tu as un grand vecteur de valeur qui peuvent être modifiées. Avec des mutex, soit tu as un mutex pour tout le vecteur, et donc si tu modifie une seule valeur, tu empêches les autres threads de modifier les autres valeurs, voir de les lires, soit tu as un mutex par valeur et ça deviens très couteux.
Avec la mémoire transactionnelle tu n'as plus ce problème.
Par contre il faut que le calcul ne soit pas trop lourd, réversible et atomisable. Et surtout il faut que la probabilité de conflit soit basse: c'est-à-dire être dans une situation optimiste.
C'est par exemple le cas d'une table de hashage lock-free.
Le soucis n'est pas, pour un seul programme, de savoir ou aller chercher les données. Ça on sait très bien le faire et de manière à peu près propre.
Les problèmes commencent quand tu as plusieurs versions du même programme en même temps et que chacune d'elle doit donc utiliser une version différente des données.
Si toutes les versions du programme suivent la procédure que tu indiques, elles vont toutes utiliser les même données.
Pour que chacune utilise sa propre version, tu n'as que deux solutions possibles :
1/ tu indiques, au moment de la compilation qu'elles données doivent être utilisées. Que ce soit en donnant directement le chemin des données ou le chemin de la config spécifique à cette version, ou bien en déduisant le chemin du numéro de version.
Dans les deux cas tu as le problème que le chemin est codé en dur dans le programme.
2/ tu fournis un paramètre en ligne de commande, et dans ce cas, il faut ce souvenir à chaque lancement d'une des version, quelle versions des données il faut utiliser.
Personnellement j'ai tendance à coder les deux, mais ce n'est pas vraiment satisfaisant. Si quelqu'un à une meilleure solution, je suis intéressé aussi.
Il y a pas mal de solutions toutes aussi pourries les unes que les autres...
Commencer par scanner le pwd puis /usr/shar/bipbip et donc la version git doit être lancer dans le répertoire avec ses donnée et l'autre n'importe ou ailleurs
Fournir des options DESTDIR ou PREFIX au moment du make et les utiliser pour régler des #define (classique)
Utiliser un paramètre en ligne de commande pour annuler la recherche par défaut.
Utiliser autoconf et le parametre --datadir (sûrement la pire solution...)
Ça reste un gros problème qu'à ma connaissance personne n'a résolu correctement, que ce soit sous Linux, BSD, MacOS ou Windows. Les différentes solutions ont toujours des problèmes plus ou moins graves.
Au final, je pense que la meilleure solution reste :
Si l'utilisateur donne un chemin en ligne de commande, l'utiliser ;
Sinon, (si le logiciel est en dev actif) chercher dans le répertoire courant ;
Sinon, utiliser une liste de quelques répertoires courants.
Dans la liste tu mets en premier un chemin spécifiable au moment de la compilation (soit par ./configure soit au moment du make).
C'est pour ça que je reste sur linuxfr… en plus des gros troll et de l'info pour geek, il y a aussi de temps en temps ce genre de petit trucs bien sympa qui font quand même sacrément rêver.
Le seul problème de ce journal c'est que je me dis, « si seulement j'avais les couilles de tout plaquer pendant un an et de faire comme l'op… ». Actuellement non, mais bientôt j'espère…
[^] # Re: Je maintiens qu'il y a une partie qui n'est pas terrible
Posté par beagf (site web personnel) . En réponse à la dépêche Où vont les supercalculateurs ? D’où on vient, quels sont les problèmes, où l’on va (1re partie). Évalué à 3.
Le cœur des processeur x86 récent n'est pas vraiment RISC. Les instruction CISC sont bien décodées vers des micro-instructions qui forment un jeu plus simple que celui de l'architecture de base, mais ça reste loin d'être du RISC.
Il suffit de regarder les manuel de Agner que cite pour s'en convaincre. La majorité des instructions sont décodé vers une seule micro-instruction qui en garde donc toute la complexité.
[^] # Re: dur…
Posté par beagf (site web personnel) . En réponse au journal Les mots divisent le libre. Évalué à 6.
Désolé mais tu ne proposes pas, tu imposes et tu le dis même dans ton journal.
[^] # Re: dur…
Posté par beagf (site web personnel) . En réponse au journal Les mots divisent le libre. Évalué à 3.
Faut pas abuser non plus. À la base c'est le développeur qui a tous les droits, au moment ou il publie le logiciel il choisit ceux qu'il donne.
J'ai des tas de morceaux de code qui trainent sur mon disque et que je n'ai jamais publiés et en dehors de moi, personne n'a de droit "fondamental" dessus. Tant que je ne le diffuse je ne te prive d'aucun droit sauf si on part sur du communisme extrême où tout est à tout le monde. Mais dans ce cas, pourquoi ne l'appliquer que au logiciel ? Est-tu d'accord pour me donner des droits sur tout ce que tu possèdes ?
Par contre, quand je publie mon code, je choisis quels droits je donne à l'utilisateur, le terme privateur n'a donc bien aucun sens ici.
[^] # Re: sexisme ou blague ?
Posté par beagf (site web personnel) . En réponse au journal B16B00B5 : Sexisme dans le source du Kernel. Évalué à 10.
Et donc je suppose que ça doit vachement te révolter que la constante 0xCAFEBABE soit utilisée pour identifié les fichier objets au format Mach-O (notamment MacOS X) ainsi que les fichier bytecode de Java ?
# Retours à la ligne
Posté par beagf (site web personnel) . En réponse à la dépêche Retour d'expérience sur Go. Évalué à 6.
En C++, std::endl n'a pas grand chose à voir avec la gestion multi-plateforme du retour à la ligne. Un simple '\n' sera traduit par le bon retour à la ligne utilisé par la plateforme.
std::endl est identique à '\n' de ce point de vue, la différence est qu'il force un flush du buffer. Donc, il ne faut l'utiliser que si ce flush est désiré. Son nom est d'ailleurs à mon avis très mal choisi et amène à des codes inutilement lents quand un codeur pensant bien faire l'utilise pour écrire un fichier de sortie par petits fragments et au final perd tout le bénéfice du buffer de sortie.
Je ne connais pas Go mais à mon avis il y a de fortes chances pour que le '\n' soit correctement géré et donc s'adapte automatiquement à la plateforme.
[^] # Re: Respect...
Posté par beagf (site web personnel) . En réponse à la dépêche Dennis Ritchie, un père d’UNIX, nous a quittés. Évalué à 10.
Je fais partis des gens qui ont eu la chance de le rencontrer de son vivant et de le remercier alors. Je n'ai pas eu l'occasion de le faire en public avant mais ça ne change rien au fait que je peut le faire maintenant.
Je profite juste de ce commentaire pour faire taire tous les grincheux qui ne manque pas de critiquer le fait qu'il n'ait pas le droit aux mêmes honneurs que Steve Jobs pour leur dire que Steve s'en fout sûrement royalement, ou tout du moins s'en foutait il y a quelques années.
Il était parfaitement conscient de ce qu'il a réaliser pour l'informatique et ne le niait pas, mais était aussi parfaitement conscient qu'il ne l'avait pas fait seul. Il parlait surtout du fait qu'il avait eu la chance d'être au bon endroit au bon moment. Dans un labo ou l'on avait su laisser quelques personne compétentes faire un truc un peu à part du boulot que l'on attendait d'eux sans leurs mettre trop de bâtons dans les roues. D'arriver au bon moment, quand l'informatique avait vraiment besoin de quelque chose tel que Unix et le C.
Il m'a dit qu'il espérait que n'importe qu'elle équipe dans les même conditions au même moment aurait fait la même chose. Je pense qu'il y a du vrai dans ce qu'il a dit même si je n'en suis pas aussi convaincu que lui.
C'était loin d'être une personne parfaite (notament il ne buvait pas assez à mon gout...) mais c'était quelqu'un de bien.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 3.
C'est en effet un problème. Mais c'est ce que l'on a de mieux actuellement. L'avantage de IEEE 754 c'est que l'on dispose d'une norme précise qui offre de bonnes garanties et qui est implémentée en hard donc qui permet de faire des calculs rapide.
Le choix qui ont été fais dans la norme n'ont pas été fais de manière arbitraire mais pour permettre de réellement faire du calcul mathématique. Il existe des représentations qui ont de meilleur propriété d'un point de vue mathématique, mais le résultat est toujours le même : elles ne sont pas vraiment utilisables.
Garantir l'associativité par exemple entraine toujours de gros problèmes lors de l'analyse de la propagation d'erreurs.
Je rêve d'une représentation des réels qui soit un vrai corps commutatif avec les mêmes garantie que l'IEEE 754 mais c'est tout simplement impossible. Actuellement au moins, l'IEEE 754 reste le meilleur compromis. Il y a quelques principes à bien garder en tête, et pour les passage critique du code, il est relativement simple de calculer l'erreur maximale que l'on obtient.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 3.
C'est même pour cela que la libm est avant tout codée en C avec de très bonnes performances. Le passage à l'assembleur n'est fait que pour certaines architectures et que pour certaines fonctions. Réussir à faire mieux que le compilateur est même souvent très difficile.
Par contre, il n'y a pas de magie, le compilateur ne trouvera pas tout seul la bonne réduction et la bonne approximation. L'humain reste indispensable à ce niveau là. (pour l'instant en tout cas)
De manière générale et pour la libm, la précision est définie par le standard IEEE754. En gros ça veux dire que tu dois renvoyer un résultat identique à ce que donnerais le calcul exact puis arrondis de manière à être représentable.
La ou c'est chiant c'est qu'il y a différent mode d'arrondis...
Dans mon cas, l'optimisation ce justifiais car mon code passait près de 46% de son temps à calculer des exp() et des log(). Le truc c'est que je n'avais pas besoin de gérer les nombres démoralisés, un seul type de NaN, pas d'infinis en entrée et surtout les valeurs d'entrée ne pouvait couvrir qu'un intervalle plus réduit.
Donc dans ce cas là, même avec une précision complète, on gagne déjà beaucoup : presque un facteur x2 sur les deux fonctions.
Pour ce qui est de la précision, une partie du code avais besoin de la précision complète, c'est elle qui garde le code FPU avec ses 80bits et qui fait le calcul en long double. Par contre, une grosse partie du code travail sur des doubles mais peut tolérer environs 3bits d'erreurs. Cette portions utilise le code SSE2 avec un polynôme tronqué qui fournis juste ce dont le code à besoin et permet en plus de profiter du SIMD. Au final les exp() et log() ne représentent plus que 6% du temps de calcul.
Par contre, avant de jouer avec ces fonctions il faut bien faire attention et bien mettre des gros warning. Dans mon cas, si tu leur donnes des valeurs qu'elles n'attendent pas, elles te renvoie du bruit. Leur utilité est donc très liée à mon programme. Dans le cas général ou tu dois respecter le standard IEEE 754 tu n'auras jamais de tels gains. Une bonne fonction exp() à un gain non-négligeable par rapport à la version FPU pour le cas général, par contre, si l'entrée ou la sortie est un NaN ou un Inf, ce n'est souvent pas le cas.
Pour les nombre dénormalisé, c'est souvent kifkif car la FPU à une pénalité de près de 200 pour ces cas là elle aussi.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 3.
Le gros problème c'est que pour trouver la manière la plus rapide de calculer une de ces fonctions il faut tenir compte à la fois de l'aspect mathématique et de l'aspect informatique.
J'ai vu un cas ou ajouter une division qui prend 40cycles permettait d'obtenir un code plus rapide car pendant que le processeur s'occupait de la division dans l'unité flottante il y avait suffisamment d'autres calculs à faire en parallèle. Au final ce code était presque trois fois plus rapide que la version plus classique avec la même précision car la réduction était triviale.
Il y a moyen de produire automatiquement différentes alternatives, mais il faut toujours regarder à la main comment chacune d'entre elles peut être implémentée pour choisir la meilleure. Quand j'ai bossé sur l'exponentielle par exemple, j'avais du code pour me produire différentes formes d'approximations sur les intervalles qui m'intéressait pour différentes précisions. Ensuite je regardait à la main comment je pouvais m'arranger pour organiser au mieux le calcul.
J'ai fais des version FPU et SSE2 à l'époque et elles utilisent des méthodes de calcul différentes. Je me penche en ce moment sur une version AVX et à priori ce sera encore différent.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 2.
Tu as plein de méthode pour calculer toutes ces fonctions et la bonne méthode dépend de beaucoup de choses. En pratique, le gros problèmes c'est toujours la précision. Les différentes méthode ne sont généralement applicable de manière raisonnable que sur un intervalle de valeurs petit, il faut donc trouver le meilleur compromis entre :
Les développement limités ont plusieurs avantages : ont peu généralement obtenir la précision que l'on veux sur n'importe quel intervalle pas trop gros et avec un peu de bol le polynôme peu ce mettre sous une forme sympa pour faire plusieurs opérations en parallèle et profiter au maximum du processeur.
Mais le sujet est vaste et des livres entiers ont étés écris dessus...
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 2.
Attention avec ce benchmark, il à deux problèmes.
Tout d'abord les calculs sont fais avec une précision de 32bits uniquement pour les versions soft là ou la FPU va faire les calculs au moins partiellement en 80bits. Pour l'exponentielle par exemple, l'appel à f2xm1 sera fais avec 80bits de précision.
Les résultats ne sont donc valable que si tu as besoin de peu de précisions. (dans ce cas tant pis pour la FPU, elle n'avait qu'a savoir faire le calcul en 32bits...)
Les bench sont réalisés sur de très gros vecteurs puisque l'objectif est de comparer avec des versions vectorielles, l'impact des accès mémoire n'est pas négligeable et les résultats sur des appels fréquents mais plus espacés peuvent être très différents.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 7.
J'ai pris l'exemple de l'exponentielle car justement j'ai beaucoup bossé dessus et sur les différentes manières de l'approximer. Les valeurs en nombre de cycles que je donne sont les valeur réellement mesurées pour l'approximation software dans le cas ou les constantes sont dans le cache L1. Si les constantes ne sont que dans le cache L2, il y a un trou de 17 à 22 cycles en moyenne à rajouter.
Pour la version hardware, ce sont les valeurs théoriques maximum que l'on peut atteindre mais je n'ai pas trop de doute dessus. Le f2xm1 bloque vraiment les ports flottants donc il y a peu de difficultés à prédire la durée.
Pour ce qui est des loads, ils n'ont que peu d'impact lorsqu'ils se font depuis le cache L1. Le port de lecture est saturé sur le début du calcul mais il n'y a pas de cycles perdus, et il est disponible pendant l'étape finale pour charger les données des instructions qui suivent le calcul de l'exponentielle.
Si les constantes ne sont pas dans le cache L1, ça veux généralement dire que tu fais peu appel à ces fonctions et que donc une différence d'une vingtaine de cycles ne changera rien de manière globale.
Pour ce qui est de l'instruction f2xm1, c'est loin d'être la plus lente. Si on oublie fnsave et frstor qui sont un peu hors de propos mais qui culminent à plus de 150 cycles ; on trouve quand même parmi les instructions complexes :
Dans les fonctions complexes, il n'y a que fsqrt et fscale qui prennent moins (27 et 12 cycles respectivement). La fonction exponentielle est un peu particulière car la réduction est simple et peu se calculer très rapidement. Si on prend le calcul de tan() comme exemple, on peut être en dessous des 115 cycles en soft aussi, mais la réduction est plus complexe et donc l'exemple est moins facile à expliquer.
Ce qu'il faut bien voir c'est que d'un point de vu hardware, la FPU x87 ne fait que survivre comme elle peut et les instructions complexes sont elles bien mortes. Le seul intérêt qu'il reste au x87 c'est la précision sur 80bits, pour tout le reste il faut passer à SSE qui ne dispose pas d'instructions complexes et donc nécessite des implémentations hardware.
Les processeurs récents ont encore de très bon multiplieurs dans la FPU car ce sont les mêmes que pour le SSE mais pour les instructions complexes ça dépend vraiment des générations. Elle sont découpée en un très grand nombre de micro-instructions et leur efficacité varie beaucoup. L'idée c'est de les coder en ajoutant le moins possible de micro-instruction, donc suivant ce qui est disponibles dans le reste du processeur ça deviens très variable.
Par exemple, f2xm1 qui prend 58 cycles sur un core i7 ne prenait que 45 cycles sur un core 2 en 45nm. C'est l'avantage des versions soft, on connais leur comportement de manière beaucoup plus fiable.
Pour ce qui est de faire des calculs sur la FPU et le SSE en même temps je te le déconseille, les deux utilisent les mêmes ports pour leurs micro-instructions et les mêmes unités de calcul. Tu ne peux que perdre en performances de manière globale.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 10.
Pour tous le message suivant, je prend comme exemple un processeur intel core i7. Sur ce processeur, une multiplication flotante prend 5 cycles mais il est possible de démarrer une nouvelle multiplication à chaque cycles avec un maximum de 3 multiplication en même temps. Pour les additions et soustraction c'est la même chose mais en 3 cycles.
Pour prendre un exemple que je connais bien : la fonction exponentielle. L'exemple est un peu biaisé mais j'y reviendrais à la fin. Son calcul avec les fonctions interne repose sur l'instruction f2xm1 qui prend 58 cycles.
Sont calcul en soft ce fait par une réduction de e^x vers 2^k * e^f avec f dans l'intervalle [-0.5,0.5] :
Si on rajoute la gestions des NaN et autres Inf, on arrive à un 47 cycles une fois bien tassé. Si on a besoin de la gestion des nombres dénormalisés, on rajoute 4 cycles au cas standard. (le cas dénormalisé prenant lui beaucoup plus de temps...)
On peut ce dire que l'économie est faible, mais ce qu'il faut voir c'est que l'instruction f2xm1 seule ne suffie pas à calculer l'exponentielle. L'exponentielle est calculée avec la formule e^x = 2^(x * log2(e)), il faut rajouter au final une audition, une soustraction et une multiplication ainsi que quelque petits détails et prendre en compte que f2xm1 bloque les port 0 1 et 5 de l'unitée de calcul et que donc on ne peut rien faire d'autre pendant 58 cycles. On arrive à 73 cycles auxquels il faut rajouter 3 cycles pour être sûr que tout ce passe bien avec les dénormalisés.
Au final la version soft est nettement gagnante. Principalement car la multiplication est très rapide et à un reciprocal throughput d'un seul cycle.
Par contre, cet exemple est biaisé : les deux fonction sin et cos sont globalement aussi rapide en hard qu'en soft mais ce sont les seules avec la fonction sincos qui calcule les deux en même temps car ce sont les seule ou la version hardware est vraiment très proche de la version software. Pour toutes les autre fonctions du même genre, il y a souvent une réduction à faire à l'aide de quelques instructions avant. Et cette réduction est nécessaire aussi bien en hard qu'en soft.
Mais la version soft conserve l'avantage de ne pas occuper tout les ports et donc de permettre de dispatcher quelques autres instruction en même temps si possible ainsi que d'être beaucoup plus portable que de l'assembleur.
Et juste pour terminer, l'instruction fsin ne prend un peu moins que 50 cycles que dans le cas ou tu veux une précision sur 32 bits. Pour une précision complète elle demande 100 cycles, il y a moyen de faire énormément de choses pendant ce temps la notament environs 30 multiplication s'il n'y a pas de dépendances trop fortes.
[^] # Re: À propos de SSE et AVX
Posté par beagf (site web personnel) . En réponse à la dépêche Intel Sandy Bridge et Linux : état des lieux. Évalué à 5.
En pratique c'est faux. Ces instructions sont très couteuses en cycles. Une version soft de ces fonctions bien codée est souvent plus rapide que la version hardware des processeurs.
C'est particulièrement le cas depuis que la multiplication flottante est devenue rapide. À l'époque ou la multiplication prenait plusieurs dizaine de cycles ce n'était pas le cas, mais maintenant je ne pense pas qu'il reste des processeurs ou la version hardware soit plus rapide que la version software.
# Relativisons un peu
Posté par beagf (site web personnel) . En réponse à la dépêche Prix Ig Nobel 2011. Évalué à 10.
La dépêche le rappel bien, les prix Ig Nobel ne récompensent pas des recherches stupides mais intrigantes et faisant sourire. Et pour que ce soit marrant elle sont en général présentées de la manière la plus drôle possible...
Mais il ne faut pas oublier de relativiser et de bien ce rendre compte qu'il y a quand même un travail serieux derrière beaucoup de ces recherches. Par exemple :
Pour les autres, je vous laisse aller regarder par vous même et faire le tri...
[^] # Re: Recouvrement
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 2.
Sauf que entre :
- utiliser un mutex fournis par l'OS ou une opération atomique,
- espérer que le compilateur va produire le bon code et que les instructions font ce que l'on suppose,
La première solution à l'avantage de marcher et en plus d'être plus portable.
Le code en assembleur, il vaut mieux le laisser au compilateur à travers les builtin et intrinscs, dans des bibliothèques bien testées ou dans le noyeau.
[^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 2.
Oui, tu peut avoir un thread qui est toujours bloqué mais, car il y a un mais comme toujours ;-) ce genre de mécanisme : instruction atomiques ou mémoire transactionelle, serve le plus souvent à implémenter des algorithmes de type "forward progress".
C'est-à-dire que en général ce qui t'intéresse c'est de garantir que de manière globale le système avance. Si ton thread échoue toujours ce n'est pas grave car à chaque fois qu'il échoue cela veut dire qu'un autre à réussi et donc que globalement le système à progressé.
Et si tu gère bien le truc, en général tu as de bonne garanties probabilistes sur les progres de chaque threads. Du style la probabilité d'échouer d'un thread décroit de manière quadratique avec le nombre d'échec ou ce genre de choses.
Si tu as besoin de garanties plus fortes comme dans le cas d'un système temps réél, il faut passer à d'autres méthodes. Mais le besoin en garanties plus fortes est relativement rare en comparaison des besoins satisfait par le forward progress, et surtout c'est beaucoup plus compliqué à gérer donc tu as très peu de chances de voir ça arriver dans du hardware rapidement.
[^] # Re: Recouvrement
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 4.
Non ça ne marchera pas car chaque cœur à son propre cache et sur les processeur récent le passage par le cache L1 est obligatoire.
Par contre, si tu rajoute le prefix LOCK devant ça marche, tout simplement car cela deviens une instruction atomique, mais vu que c'est coûteux le compilo ne l'ajoute pas automatiquement partout, uniquement quand tu lui demande explicitement en utilisant les intrinsics...
Donc au final, on en reviens toujours au même point : quoi que tu fasses il y a une faille sauf si tu demande explicitement la version atomique.
En plus, ce reposer sur un comportement spécifique d'un processeur c'est plutot extrêment pourris à ça ne n'apporte qu'une chose : des emmerdes plus ou moins rapidement.
[^] # Re: Recouvrement
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 2.
Mais ta file d'attente d'opérations doit gérer le cas ou plusieur thread veulent ajouter des deltas et donc repose sur un mutex ou des CAS...
Dans la pratique tu n'utilises pas forcément un mutex de manière explicite, pour éviter les emerdes il peut être implicite et gérer par une sous classe ou par une instruction spéciale du langage, mais ça reste beaucoup plus efficace et moins risqué que de passer par un thread supplémentaire.
[^] # Re: Instructions atomiques
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 3.
Si, on parlait du CAS : moi surtout en fait...
Le premier message parle d'instruction atomique dont le CAS. Victor Stinner répond que l'on ne peut pas les utiliser car il y a quatre pointeurs à modifier. --> d'un point de vue instruction atomique c'est forcément du CAS ou du load-lock ici.
Je lui répond qu'en fait il n'y en a que deux, et vu que l'on parle d'instruction atomique et de modifier des pointeurs, c'est encore du CAS... je le dis même de manière explicite à la ligne du dessous.
Toutes les instructions atomiques qui permettent d'affecter un pointeur on globalement le même comportement : tu affectes la valeur s'il elle n'a pas été modifiée depuis un certains temps.
Donc pour tous les cas ou l'on utilise des instructions atomiques (ce qui est le sujet de ce thread) il n'y a besoin que de deux affectations atomiques. Si elles échoue, tu refais les deux autres affectations et tu réessayes, c'est le principe de ces instructions.
Dans le cas de la mémoire transactionelle c'est en effet différent puisqu'on garantit l'atomicité d'une transaction sans tests avec les valeurs précédentes. C'est une stratégie différente mais, même si c'est le thème du journal, ce thread à pour thème les instruction atomiques.
[^] # Re: Instructions atomiques
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 4.
Non, il n'y a que deux pointeurs à modifier. Tu commence par modifier les deux pointeurs qui sont dans le nœud à ajouter, pour ceux la tu n'as besoin d'aucune protection. Ensuite, tu modifies les deux pointeurs externes.
Et certains processeur supportent le CAS sur deux valeurs, par contre en général elles doivent être contiguës en mémoire ce qui n'est pas le cas ici.
Mais que ce soit avec de la mémoire transactionnelle ou n'importe quoi d'autre, dans tous les cas, il vaut mieux mettre le minimum d'affectations dans le atomic.
[^] # Re: Méthode coûteuse
Posté par beagf (site web personnel) . En réponse à la dépêche IBM lance la mémoire transactionnelle dans le matériel. Évalué à 9.
Le problème des mutex n'est généralement pas leur coût au moment du lock et du unlock. A ce niveau c'est plutôt devenu très rapide sur un mutex de base. (pas de lock récursif ou autres)
Le soucis c'est plutôt que les mutex sont pessimiste, tu doit faire un lock même si il y a très peu de chances qu'il soit nécessaire.
La mémoire transactionelle est plutôt à comparer à l'instruction compare-and-swap. Tu fais tout ton calcul comme s'il n'allait pas y avoir de problèmes, et au moment de stocker le résultat, tu vérifie juste que personne n'a fait de connerie pendant ce temps.
En gros :
Si la probabilité que de thread modifient la même zonne est très basse, en général tu n'as pas à recommencer ton calcul.
Cette stratégie permet d'éviter les mutex et donc le cout associé aux lock, et surtout permet de ce passer complètement du lock, donc tu n'empêche pas un autre thread de bosser.
C'est particulièrement efficace dans le cas ou tu as un grand vecteur de valeur qui peuvent être modifiées. Avec des mutex, soit tu as un mutex pour tout le vecteur, et donc si tu modifie une seule valeur, tu empêches les autres threads de modifier les autres valeurs, voir de les lires, soit tu as un mutex par valeur et ça deviens très couteux.
Avec la mémoire transactionnelle tu n'as plus ce problème.
Par contre il faut que le calcul ne soit pas trop lourd, réversible et atomisable. Et surtout il faut que la probabilité de conflit soit basse: c'est-à-dire être dans une situation optimiste.
C'est par exemple le cas d'une table de hashage lock-free.
[^] # Re: fichier de configuration ?
Posté par beagf (site web personnel) . En réponse au message Savoir où chercher les données utilisées après un make install. Évalué à 3.
Le soucis n'est pas, pour un seul programme, de savoir ou aller chercher les données. Ça on sait très bien le faire et de manière à peu près propre.
Les problèmes commencent quand tu as plusieurs versions du même programme en même temps et que chacune d'elle doit donc utiliser une version différente des données.
Si toutes les versions du programme suivent la procédure que tu indiques, elles vont toutes utiliser les même données.
Pour que chacune utilise sa propre version, tu n'as que deux solutions possibles :
1/ tu indiques, au moment de la compilation qu'elles données doivent être utilisées. Que ce soit en donnant directement le chemin des données ou le chemin de la config spécifique à cette version, ou bien en déduisant le chemin du numéro de version.
Dans les deux cas tu as le problème que le chemin est codé en dur dans le programme.
2/ tu fournis un paramètre en ligne de commande, et dans ce cas, il faut ce souvenir à chaque lancement d'une des version, quelle versions des données il faut utiliser.
Personnellement j'ai tendance à coder les deux, mais ce n'est pas vraiment satisfaisant. Si quelqu'un à une meilleure solution, je suis intéressé aussi.
[^] # Re: fichier de configuration ?
Posté par beagf (site web personnel) . En réponse au message Savoir où chercher les données utilisées après un make install. Évalué à 5. Dernière modification le 04 septembre 2011 à 13:48.
Il y a pas mal de solutions toutes aussi pourries les unes que les autres...
Ça reste un gros problème qu'à ma connaissance personne n'a résolu correctement, que ce soit sous Linux, BSD, MacOS ou Windows. Les différentes solutions ont toujours des problèmes plus ou moins graves.
Au final, je pense que la meilleure solution reste :
Dans la liste tu mets en premier un chemin spécifiable au moment de la compilation (soit par ./configure soit au moment du make).
[^] # Re: J'aime <3
Posté par beagf (site web personnel) . En réponse au journal photos libre d'Antarctique. Évalué à 8.
C'est clair que ça fais du bien.
C'est pour ça que je reste sur linuxfr… en plus des gros troll et de l'info pour geek, il y a aussi de temps en temps ce genre de petit trucs bien sympa qui font quand même sacrément rêver.
Le seul problème de ce journal c'est que je me dis, « si seulement j'avais les couilles de tout plaquer pendant un an et de faire comme l'op… ». Actuellement non, mais bientôt j'espère…