Est-ce que quelqu'un sait s'il est possible de faire une programmation sans verrouillage à Haskell? Je suis intéressé à la fois dans la question de savoir si les primitives de bas niveau appropriés sont disponibles et (s'ils sont) sur toutes les informations sur ce qui fonctionne en termes d'utilisation de ceux-ci pour créer des systèmes à plus grande échelle dans le contexte fonctionnel pur. (Je n'ai jamais fait de programmation sans verrouillage dans un contexte fonctionnel pur auparavant.) Par exemple, comme je le comprends, les canaux Control.ContCurrent.chan sont construits sur des Mvars, qui (comme je comprends les choses) utilisent des serrures-- -coulez-vous en principe construire des versions de la primitive Chan qui sont libres de verrouillage en interne? Combien de gain de performance pourrait espérer obtenir?
Je devrais aussi dire que je connais l'existence de TVArs, mais ne comprend pas comprendre leur mise en œuvre interne --- J'ai été donnée pour comprendre qu'ils sont surtout libres, Mais je ne sais pas si elles sont entièrement libérées. Toutes les informations sur la mise en œuvre interne des TVArs seraient également utiles!
( Ce fil offre une discussion, mais je me demande s'il y a quelque chose plus à jour / plus complet.)
3 Réponses :
regarder dans STM , spécifiquement son type TCHAN.
Merci - - Je connaissais la STM (voir Edition ci-dessus) mais je ne savais pas tant de savoir comment il est mis en œuvre en interne. Est-ce que c'est libre? Surtout verrouillé gratuitement? De plus, sont des primitives sans verrouillage inférieures exposées?
@ circulaire-ruine Je suis à peu près sûr que STM est sans verrouillage, mais si ce n'est pas le meilleur que vous allez obtenir.
OK très bien! Bien que je sois toujours intéressé si quelqu'un a des informations plus détaillées (ou peut indiquer de telles ...)
STM est optimiste, mais pas complètement libre que je me souvienne.
J'accepterais également que la STM n'est pas libérée. Cela vous permet de penser dans un manoir sans serrure, mais c'est plus d'abstraction sur quelque chose qui doit presque certainement utiliser le verrouillage quelque part.
Non seulement un verrouillage d'utilisation MVAR, il est une abstraction de verrouillage. Et, à mesure que je me souviens, les primitives de STM individuelles sont optimistes, mais il existe des serrures utilisées dans divers endroits de la mise en œuvre de la STM. Rappelez-vous simplement la rime pratique: "S'il est possible de bloquer, méfiez-vous des serrures".
Pour une programmation sans verrouillage réelle Vous souhaitez utiliser directement iOREFS, ainsi que Mais cette implémentation a subi des modifications, je pense, comme décrit dans Simon Marlow's Haskell Midisors Discussion "Planification de l'évaluation paresseuse sur Multicore": http://hakell.org/haskellwiki/hakellimplementasershop/2010 . Les diapositives sont malheureusement hors ligne, mais la vidéo devrait toujours fonctionner. atomicmodifyioref .
Mon impression était que, si quelque chose, STM a tendance à échouer à l'autre extrême - avec une avance élevée et sans verrouillage, l'optimisme sans bornes entraîne des transactions invalidant gaiement à gauche et à droite jusqu'à ce que personne ne puisse rien faire.
Droit! Je suis d'accord, les mvars sont simplement des serrures simplement; La question était libellée de manière non optimale. Je conviens que je veux utiliser iOREFS et modification atomique. Mais atomicmodifyioref n'est-ce que la seule primitive sans verrouillage que vous souhaiteriez peut-être de manière critique, on peut vouloir un comparer-et-définit! primitif qui modifie un ioref uniquement si Sa valeur actuelle est toujours ce que vous attendiez qu'il soit ...
De plus: le mécanisme de trou noir est-il implémenté à l'aide de serrures? (Dans GHC.)
Ouais, pas de comparaison et d'échange aussi loin que je sache. Mais la sémantique de Thunk Delay devrait suffire à vous donner tout ce dont vous avez besoin WIHT atomicmodifyioref . Bien entendu, l'inconvénient est que vous payez, en échange, la surcharge typique du facteur constant d'une orduite paresseuse collectée.
@C. A. McCann Je ne sais pas à propos de la STM, mais je me souviens de l'hérolithy conçu des algorithmes qui garantissent des progrès dans son livre "Art of Multicore Programming"; Je serais surpris de ne pas avoir d'influence STM.
Il n'y a pas besoin de comparer et d'échanger avec atomicmodifyioref, tout ce que vous avez à faire est dans la fonction que vous utilisez pour effectuer la modification, vous comparez à ce que vous voulez que ce soit, et si c'est le cas, le swap, si ce n'est pas t, laissez la valeur d'origine là-bas. Vous pouvez faire ce que vous voulez à l'intérieur de votre fonction, peu importe la complexité, car tout ce que AtomicModifyIOoref est placé à l'intérieur du calcul, qui peut être évalué à l'avenir par des threads qui en ont besoin. Voir ma réponse à la question et aux diapositives référencées pour plus de détails.
@ Axman6, @sclv. Je vois comment cela fonctionne, mais j'ai une inquiétude: le mécanisme "trou noir" est-il implémenté à l'aide de serrures? Si c'est le cas, votre solution sera (il me semble-t-il), vous devez vous retrouver à l'aide des verrous implicites à l'intérieur des trous noirs. Donc, pour que cela soit une solution de «verrouillage libre», nous devons connaître les trous noirs sont sans verrouillage. (Contrajoliais, si les BHS ne sont pas libres de verrouillage, écrivez le code libres de verrouillage, vous devez évaluer à WHNF --- ou probablement même nf --- avant le atomicmodifyioref et vous suggère toujours que vous vous suggérez besoin d'une primitive comparative / set.)
@ circulaire-ruine voir mes références ci-dessus RE BHS.
@ C.A.MCCANN La mise en œuvre de la STM est garantie de progresser. Une transaction spécifique peut être bloquée, pas simultanément les transactions toutes les transactions. Quelqu'un doit faire des progrès.
La programmation libre de verrouillage est triviale à Haskell. Le moyen le plus simple d'avoir un élément de données partagé à modifier par de nombreux threads est de commencer avec n'importe quel type de haskell normal (liste, carte, peut-être, tout ce dont vous avez besoin) et la place dans une iOREF. Une fois que vous avez fait cela, vous avez la possibilité d'utiliser atomicmodifyioref pour effectuer des modifications en place, qui sont garanties à prendre à peu près au pas de temps. La raison pour laquelle cela fonctionne est qu'un pointeur à La pensée qui éventuellement évaluera finalement le résultat à l'intérieur de l'iOREF est stockée et chaque fois qu'un fil se lit de l'iOREF, ils obtiennent le Thunk et évaluent autant de la structure que nécessaire. Étant donné que toutes les threads pouvaient lire ce même thunk, il ne sera évalué qu'une seule fois (et s'il est évalué plus d'une fois, il est garanti de toujours se retrouver avec le même résultat, de sorte que les évaluations simultanées sont correctes). Je crois que c'est correct, je suis heureux d'être corrigé. Le message de prise à la maison est que ce type d'abstraction n'est facilement mis en œuvre que dans une langue pure, où la valeur des choses ne change jamais (Sauf bien sûr où ils le font, avec des types comme ioref, Mvars et les types STM). La copie sur la nature écrite des structures de données de Haskell signifie que les structures modifiées peuvent partager de nombreuses données avec la structure d'origine, tout en attribuant tout ce qui est nouveau à la structure. Je ne pense pas que j'ai fait Un très bon expliquant comment cela fonctionne, mais je reviendrai demain et clarifier ma réponse. Pour plus d'informations, voir les diapositives pour la conversation Programmation multicore à Haskell par Simon Marlow de Microsoft Research (et l'un des principaux implémentaux de GHC).