Quel est le degré d'atomicité des thunks de GHC ?

Question

Comment GHC gère-t-il les thunks qui sont accédés par plusieurs threads (soit les threads explicites, soit les threads internes qui évaluent les sparks) ? Peut-il arriver que plusieurs threads évaluent le même thunk, dupliquant ainsi le travail ? Ou, si les thunks sont synchronisés, comment, pour que les performances n'en souffrent pas ?

Answer 1

Desde le billet de blog @Lambdageek lié, le Commentaire du CGH et le Guide de l'utilisateur de GHC J'ai rassemblé les éléments suivants :

GHC essaie d'empêcher la réévaluation des thunks, mais parce qu'un véritable verrouillage entre les threads est coûteux, et que les thunks sont généralement purs et donc inoffensifs à réévaluer, il le fait normalement d'une manière bâclée, avec un petit la possibilité de dupliquer le travail de toute façon.

La méthode qu'il utilise pour éviter le travail consiste à remplacer les thunks par un trou noir un marqueur spécial qui indique aux autres fils (ou parfois, au fil lui-même ; c'est ainsi que l'on appelle les " fils ". <<loop>> détection se produit) que le thunk est en cours d'évaluation.

Dans ces conditions, il existe au moins trois options :

• Par défaut, il utilise le "lazy blackholing", où cette opération n'est effectuée qu'avant que le thread ne soit sur le point de s'arrêter. Il "parcourt" ensuite sa pile et crée de "vrais" blackholes pour les nouveaux thunks, en utilisant le verrouillage pour s'assurer que chaque thunk n'est blackholé que par un seul thread, et en interrompant sa propre évaluation s'il découvre qu'un autre thread a déjà blackholé un thunk. Cette méthode est plus économique car elle n'a pas besoin de prendre en compte les thunks dont le temps d'évaluation est si court qu'il s'insère complètement entre deux pauses.

• Avec le -feager-blackholing-flag En revanche, les trous noirs sont créés dès qu'un thunk commence à être évalué. Le guide de l'utilisateur recommande cette méthode si vous utilisez beaucoup de parallélisme. Cependant, comme le verrouillage de chaque thunk serait trop coûteux, ces blackholes sont moins chers et ne sont pas synchronisés avec les autres threads (bien que les autres threads puissent toujours les voir s'il n'y a pas de condition de course). Ce n'est que lorsque le thread s'arrête que ces trous noirs deviennent de "vrais" trous noirs.

• Un troisième cas, sur lequel portait particulièrement le billet de blog, est utilisé pour des fonctions spéciales telles que unsafePerformIO pour lequel c'est nuisible pour évaluer un thunk plus d'une fois. Dans ce cas, le thread utilise un "vrai" trou noir avec un verrouillage réel, mais le crée immédiatement, en insérant une pause artificielle du thread avant l'évaluation réelle.

Answer 2

Pour résumer l'article dont le lien figure dans les commentaires : les thunks dans GHC ne sont pas strictement atomiques entre plusieurs threads : il est possible dans une condition de course pour plusieurs threads d'évaluer le même thunk, en dupliquant le travail. Mais, ce n'est pas un gros problème en pratique car :

1. La pureté garantie signifie qu'il n'est jamais important qu'un thunk soit évalué deux fois, en termes de sémantique du programme. unsafePerformIO est un cas où cela pourrait être un problème, mais il s'avère que unsafePerformIO prend soin d'éviter de ré-exécuter la même action IO.

2. Étant donné que toutes les valeurs sont des thunks, la plupart des thunks s'avèrent être assez petits, de sorte que la duplication occasionnelle du travail pour en forcer un n'est pas un gros problème en termes de vitesse du programme. Vous pourriez imaginer que la duplication est coûteuse, par exemple, last [1,2..10000000] parce que tout ce calcul est coûteux. Mais bien sûr, le thunk le plus extérieur se résout simplement en un autre thunk, quelque chose comme :

   case [1,2..10000000] of 
     [x] -> x
     (_:xs) -> last xs
     [] -> error "empty list"

   et si deux threads dupliquent le travail pour transformer l'appel à last en une utilisation de case c'est assez bon marché dans le grand schéma des choses.

Answer 3

Oui, parfois le même thunk peut être évalué par plusieurs threads. Le runtime de GHC essaie de minimiser la probabilité de travail dupliqué, donc en pratique c'est rare. Veuillez consulter "Haskell sur un multiprocesseur à mémoire partagée" pour les détails de bas niveau, principalement la section "Lock-free thunk evaluation". (Je recommande ce document à tous les développeurs professionnels de Haskell).