Performances du code orienté ADT sur une seule affectation sur les CPU modernes

32

Travailler dans des données immuables avec des assignations uniques a évidemment pour effet de demander plus de mémoire, car on crée constamment de nouvelles valeurs (bien que les compilateurs sous la couverture fassent des astuces avec des pointeurs pour en faire un problème).

Mais j'ai entendu à quelques reprises maintenant que les pertes de performances étaient compensées par les gains apportés à la manière dont le processeur (son contrôleur de mémoire en particulier) peut tirer parti du fait que la mémoire n'est pas mutée (autant).

J'espérais que quelqu'un pourrait nous expliquer comment cela est vrai (ou si ce n'est pas le cas?).

Dans un commentaire sur un autre article, il a été mentionné que les types de données abstraits (ADT) avaient à voir avec cela, ce qui m'a rendu encore plus curieux. Comment les ADT affectent-ils spécifiquement la manière dont le processeur gère la mémoire? Ceci est cependant un aparté, principalement comment la pureté du langage affecte nécessairement les performances du processeur et de ses caches, etc.

Jimmy Hoffa
la source
2
cela est surtout utile en multithreading, où un lecteur peut capturer un instantané de manière atomique en sachant qu'il ne sera pas muté tant qu'il le lira
phénomène du cliquet
@ ratchetfreak Je comprends cela du point de vue de la programmation que votre code obtienne davantage de garanties de sécurité, mais ma curiosité porte sur le contrôleur de mémoire de la CPU et sur la façon dont ce comportement est important (ou non) car j'ai entendu des revendications clandestines une poignée de fois qui a dit que c'était plus efficace pour le contrôleur de mémoire, et je ne connais pas assez les détails de bas niveau pour dire si ou comment cela pourrait être vrai.
Jimmy Hoffa
Même si c'était vrai, je ne penserais pas que moins de modification de la mémoire est le meilleur argument de vente de l'immutabilité. La mémoire est là pour être modifiée, après tout, et les processeurs et les gestionnaires de mémoire se sont bien débrouillés au fil des ans.
Rein Henrichs
1
J'aimerais également souligner que l'efficacité de la mémoire ne doit pas nécessairement dépendre des optimisations du compilateur lors de l'utilisation de structures immuables. Dans cet exemple , le let a = [1,2,3] in let b = 0:a in (a, b, (-1):c)partage réduit les besoins en mémoire, mais dépend de la définition (:)et []et non le compilateur. Je pense? Pas sûr de celui-ci.

Réponses:

28

La CPU (son contrôleur de mémoire en particulier) peut tirer parti du fait que la mémoire n'est pas mutée

L' avantage est, ce fait permet d' économiser compilateur d'utiliser membar instructions lorsque les données sont accessibles.

Une barrière de mémoire, également connue sous le nom de membre, instruction de barrière de mémoire ou clôture, est un type d'instruction de barrière qui oblige une unité centrale de traitement ou un compilateur à appliquer une contrainte d'ordre aux opérations de mémoire émises avant et après l'instruction de barrière. Cela signifie généralement que certaines opérations sont garanties avant la barrière et d’autres après.

Les barrières de mémoire sont nécessaires car la plupart des processeurs modernes utilisent des optimisations de performances pouvant entraîner une exécution dans le désordre. Cette réorganisation des opérations de mémoire (charges et magasins) passe normalement inaperçue au sein d'un seul thread d'exécution, mais peut entraîner un comportement imprévisible dans les programmes et les pilotes de périphériques concurrents, à moins d'être soigneusement contrôlée ...


Vous voyez, lorsque les données sont accédées à partir de différents threads, sur un processeur multicœur, la procédure est la suivante: différents threads s'exécutent sur des cœurs différents, chacun utilisant son propre cache (local par rapport à son cœur) - une copie d'un cache global.

Si les données sont modifiables et que le programmeur a besoin d’être cohérentes entre les différents threads, des mesures doivent être prises pour garantir la cohérence. Pour le programmeur, cela signifie qu’il faut utiliser des constructions de synchronisation lorsqu’il accède (par exemple, en lecture) aux données d’un thread particulier.

Pour le compilateur, la construction de synchronisation dans le code signifie qu'il doit insérer une instruction membar afin de s'assurer que les modifications apportées à la copie des données sur l'un des cœurs sont correctement propagées ("publié"), afin de garantir que les caches des autres cœurs avoir la même copie (à jour).

Pour simplifier un peu, voir la note ci - dessous , voici ce qui se passe sur un processeur multicœur pour les membres:

  1. Tous les cœurs arrêtent le traitement - pour éviter d'écrire accidentellement dans le cache.
  2. Toutes les mises à jour apportées aux caches locaux sont réécrites dans une sauvegarde globale - afin de garantir que le cache global contient les données les plus récentes. Cela prend du temps.
  3. Les données mises à jour sont réécrites du cache global vers les emplacements locaux - afin de garantir que les caches locaux contiennent les données les plus récentes. Cela prend du temps.
  4. Tous les cœurs reprennent l'exécution.

Vous voyez, tous les cœurs ne font rien pendant la copie des données entre les caches globaux et locaux . Cela est nécessaire pour garantir que les données mutables sont correctement synchronisées (thread-safe). S'il y a 4 cœurs, les 4 s'arrêtent et attendent pendant la synchronisation des caches. S'il y en a 8, les 8 s'arrêtent. S'il y a 16 ... eh bien, vous avez 15 cœurs qui ne font rien exactement en attendant les tâches nécessaires à l'une de ces tâches.

Voyons maintenant ce qui se passe lorsque les données sont immuables. Peu importe le fil qui y accède, il est garanti que ce sera la même chose. Pour les programmeurs, cela signifie qu'il n'est pas nécessaire d'insérer des constructions de synchronisation lorsqu'ils accèdent à des données (en lecture) dans un thread particulier.

Pour le compilateur, cela signifie qu'il n'est pas nécessaire d'insérer une instruction membre .

Par conséquent, l'accès aux données n'a pas besoin d'arrêter les cœurs et d'attendre que les données soient écrites entre les caches globaux et locaux. C'est un avantage du fait que la mémoire n'est pas mutée .


Remarquez l' explication quelque peu simplificatrice ci-dessus qui supprime certains effets négatifs plus complexes de la mutabilité des données, par exemple sur le traitement en pipeline . Afin de garantir les commandes requises, le processeur doit invalider les pilotes affectés par les modifications de données, ce qui constitue un autre inconvénient en termes de performances. Si cela est mis en œuvre par une invalidation simple (et donc fiable :) de tous les pipelines, l’effet négatif est encore amplifié.

moucheron
la source