L'immuabilité élimine-t-elle entièrement le besoin de verrous dans la programmation multiprocesseur?

39

Partie 1

Clairement, l'immutabilité minimise le besoin de verrous dans la programmation multiprocesseur, mais élimine-t-elle ce besoin ou existe-t-il des cas où la seule immuabilité ne suffit pas? Il me semble que vous ne pouvez différer le traitement et encapsuler que si longtemps avant que la plupart des programmes ne soient réellement obligés de faire quelque chose (mettre à jour un magasin de données, produire un rapport, renvoyer une exception, etc.). De telles actions peuvent-elles toujours se faire sans serrures? Est-ce que le simple fait de jeter chaque objet et d'en créer un autre au lieu de changer l'original (vue grossière de l'immutabilité) offre une protection absolue contre les conflits entre processus, ou existe-t-il des cas de ce type qui nécessitent encore un verrouillage?

Je sais que beaucoup de programmeurs fonctionnels et de mathématiciens aiment parler de "pas d'effets secondaires", mais dans le "monde réel", tout a un effet secondaire, même si c'est le temps nécessaire à l'exécution d'une instruction machine. Je suis intéressé à la fois par la réponse théorique / théorique et par la réponse pratique / réelle.

Si l'immuabilité est sûre, compte tenu de certaines limites ou hypothèses, je veux savoir quelles sont exactement les limites de la "zone de sécurité". Quelques exemples de limites possibles:

  • I / O
  • Exceptions / erreurs
  • Interactions avec des programmes écrits dans d'autres langues
  • Interactions avec d'autres machines (physiques, virtuelles ou théoriques)

Un merci spécial à @JimmaHoffa pour son commentaire qui a commencé cette question!

Partie 2

La programmation multiprocesseur est souvent utilisée comme technique d'optimisation pour accélérer l'exécution de certains codes. Quand est-il plus rapide d'utiliser des verrous par rapport à des objets immuables?

Compte tenu des limites énoncées dans la loi d'Amdahl, à quel moment pouvez-vous améliorer les performances globales (avec ou sans le récupérateur de mémoire) avec des objets immuables ou bloquant des objets mutables?

Sommaire

Je combine ces deux questions en une seule pour tenter de déterminer où se trouve le cadre englobant Immutability en tant que solution aux problèmes de threading.

GlenPeterson
la source
21
but everything has a side effect- Non, non. Une fonction qui accepte une valeur et renvoie une autre valeur, et ne perturbe rien en dehors de la fonction, n'a aucun effet secondaire et est donc thread-safe. Peu importe que l'ordinateur utilise de l'électricité. Nous pouvons parler des rayons cosmiques frappant aussi les cellules de la mémoire, si vous voulez, mais gardons l’argument pratique. Si vous souhaitez prendre en compte des éléments tels que la manière dont la fonction s'exécute affecte la consommation d'énergie, le problème est différent de celui de la programmation threadsafe.
Robert Harvey
5
@ RobertHarvey - Peut-être que j'utilise simplement une définition différente de l'effet secondaire et que j'aurais dû dire plutôt "effet secondaire du monde réel". Oui, les mathématiciens ont des fonctions sans effets secondaires. Le code qui s'exécute sur une machine du monde réel nécessite des ressources de la machine pour s'exécuter, qu'il mue les données ou non. La fonction de votre exemple place sa valeur de retour sur la pile dans la plupart des architectures de machine.
GlenPeterson
1
Si vous parvenez
Jimmy Hoffa
6
Aux fins de notre discussion, je suppose que vous faites référence à une machine complète de Turing qui exécute une sorte de langage de programmation bien défini, dans laquelle les détails de la mise en œuvre ne sont pas pertinents. En d’autres termes, l’utilisation de la pile n’a aucune importance, si la fonction que j’écris dans le langage de programmation de mon choix peut garantir l’immuabilité dans les limites du langage. Je ne pense pas à la pile lorsque je programme dans un langage de haut niveau, je ne devrais pas non plus le faire.
Robert Harvey
1
@ RobertHarvey spoonerism; Monades heh Et vous pouvez le comprendre dans les deux premières pages. Je le mentionne parce que, dans l’ensemble, il décrit en détail une technique permettant de traiter les effets secondaires de manière pratiquement pure. Je suis sûr que cela répondrait à la question de Glen. C’est donc un bon message de base pour tous ceux qui trouveraient cette question dans l'avenir pour une lecture ultérieure.
Jimmy Hoffa

Réponses:

35

C'est une question étrangement formulée qui est vraiment très large si on y répond complètement. Je vais essayer de clarifier certains des détails dont vous parlez.

L'immuabilité est un compromis de conception. Cela rend certaines opérations plus difficiles (modification rapide de l’état dans les objets volumineux, construction d’objets fragmentés, maintien de l’état de fonctionnement, etc.) au profit d’autres (débogage plus facile, raisonnement plus aisé sur le comportement du programme, ne pas avoir à s’inquiéter des changements qui surviennent sous votre travail. en même temps, etc.). C’est cette dernière question qui nous intéresse, mais je tiens à souligner qu’il s’agit d’un outil. Un bon outil qui résout souvent plus de problèmes qu'il n'en pose (dans la plupart des programmes modernes ), mais pas une solution miracle ... Pas quelque chose qui modifie le comportement intrinsèque des programmes.

Maintenant, qu'est-ce que ça vous apporte? L’immuabilité vous donne une chose: vous pouvez lire l’objet immuable librement, sans vous soucier de son état qui change en dessous de vous (en supposant qu’il soit vraiment profondément immuable ... Avoir un objet immuable avec des membres mutables est généralement un facteur décisif). C'est ça. Cela vous évite d'avoir à gérer les accès simultanés (via des verrous, des instantanés, un partitionnement des données ou d'autres mécanismes; la question initiale est axée sur les verrous est ... incorrecte compte tenu de la portée de la question).

Il s'avère cependant que beaucoup de choses lisent des objets. IO le fait, mais IO lui-même a tendance à ne pas bien gérer les utilisations simultanées. Presque tous les traitements le font, mais d'autres objets peuvent être modifiables, ou le traitement lui-même peut utiliser un état non compatible avec la simultanéité. La copie d'un objet est un gros problème dans certaines langues, car une copie complète n'est (presque) jamais une opération atomique. C'est là que les objets immuables vous aident.

En ce qui concerne les performances, cela dépend de votre application. Les serrures sont (généralement) lourdes. D'autres mécanismes de gestion de la simultanéité sont plus rapides mais ont un impact important sur votre conception. En général , une conception hautement concurrente utilisant des objets immuables (et évitant leurs faiblesses) fonctionnera mieux qu'une conception hautement concurrente verrouillant les objets mutables. Si votre programme est légèrement concurrent, alors cela dépend et / ou n’a aucune importance.

Mais la performance ne devrait pas être votre plus grande préoccupation. L'écriture de programmes concurrents est difficile . Le débogage de programmes concurrents est difficile . Les objets immuables aident à améliorer la qualité de votre programme en éliminant les risques d'erreur lors de l'implémentation manuelle de la gestion de la simultanéité. Ils facilitent le débogage car vous n'essayez pas de suivre l'état dans un programme simultané. Ils simplifient votre conception et éliminent ainsi les bugs.

Donc, pour résumer: l’immuabilité aide mais n’éliminera pas les difficultés nécessaires pour gérer correctement la concurrence. Cette aide a tendance à être omniprésente, mais les gains les plus importants concernent la qualité plutôt que la performance. Et non, l'immuabilité ne vous exonère pas comme par magie de la gestion de la simultanéité dans votre application, désolée.

Telastyn
la source
+1 Cela a du sens, mais pourriez-vous donner un exemple de l'endroit où, dans un langage profondément immuable, vous devez toujours vous inquiéter de la gestion correcte de la simultanéité? Vous dites que vous le faites, mais un tel scénario ne me semble pas clair
Jimmy Hoffa
@ JimmyHoffa Dans un langage immuable, vous avez toujours besoin de mettre à jour l'état entre les threads. Les deux langages les plus immuables que je connaisse (Clojure et Haskell) fournissent un type de référence (atomes et Mvars) qui permet d'envoyer l'état modifié entre les threads. La sémantique de leurs types ref évite certains types d’erreur de concurrence, mais d’autres sont toujours possibles.
Stonemetal
@stonemetal intéressant, au cours de mes 4 mois avec Haskell, je n'avais même pas entendu parler de Mvars, j'avais toujours entendu utiliser STM pour la communication simultanée avec l'état qui se comporte davantage comme le message de Erlang en passant, me semble-t-il. Bien que l'exemple parfait d'immutabilité ne résolve pas les problèmes concurrents que je puisse imaginer est la mise à jour d'une interface utilisateur, si vous avez 2 threads qui tentent de mettre à jour une interface utilisateur avec différentes versions de données, l'un d'entre eux peut être plus récent et doit par conséquent obtenir la deuxième mise à jour. condition de course où vous devez garantir le séquençage d'une manière ou d'une autre .. Pensée intéressante .. Merci pour les détails
Jimmy Hoffa
1
@jimmyhoffa - L'exemple le plus courant est IO. Même si la langue est immuable, votre base de données / site web / fichier ne l’est pas. Un autre est votre carte typique / réduire. L'immuabilité signifie que l'agrégation de la carte est plus infaillible, mais vous devez tout de même gérer la coordination une fois que toute la carte est réalisée en parallèle.
Telastyn
1
@JimmyHoffa: MVars sont une primitive de concurrence d' accès modifiable de bas niveau (techniquement, une référence immuable à un emplacement de stockage modifiable), pas très différente de ce que vous verriez dans d'autres langues; les impasses et les conditions de course sont très possibles. STM est une abstraction de concurrence de haut niveau pour une mémoire partagée modifiable sans verrouillage (très différente de la transmission de message) qui permet des transactions composables sans possibilité d'impasses ou de conditions de concurrence. Les données immuables sont simplement thread-safe, rien d’autre à dire à ce sujet.
CA McCann
13

Une fonction qui accepte une valeur et renvoie une autre valeur, et ne perturbe rien en dehors de la fonction, n'a aucun effet secondaire et est donc thread-safe. Si vous souhaitez prendre en compte des éléments tels que la manière dont la fonction s'exécute affecte la consommation d'énergie, le problème est différent.

Je suppose que vous faites référence à une machine complète de Turing qui exécute une sorte de langage de programmation bien défini, où les détails de mise en œuvre ne sont pas pertinents. En d’autres termes, l’utilisation de la pile n’a aucune importance, si la fonction que j’écris dans le langage de programmation de mon choix peut garantir l’immuabilité dans les limites du langage. Je ne pense pas à la pile lorsque je programme dans un langage de haut niveau, je ne devrais pas non plus le faire.

Pour illustrer comment cela fonctionne, je vais vous proposer quelques exemples simples en C #. Pour que ces exemples soient vrais, nous devons faire quelques hypothèses. Premièrement, le compilateur respecte la spécification C # sans erreur et deuxièmement, il génère les programmes corrects.

Supposons que je souhaite une fonction simple qui accepte une collection de chaînes et renvoie une chaîne qui est une concaténation de toutes les chaînes de la collection, séparées par des virgules. Une implémentation simple et naïve en C # pourrait ressembler à ceci:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Cet exemple est immuable, à première vue. Comment je sais ça? Parce que l' stringobjet est immuable. Cependant, la mise en œuvre n'est pas idéale. Étant donné qu’il resultest immuable, un nouvel objet chaîne doit être créé à chaque fois dans la boucle, en remplacement de l’objet original pointé resultvers. Cela peut affecter négativement la vitesse et faire pression sur le ramasse-miettes, car il doit nettoyer toutes ces chaînes supplémentaires.

Maintenant, disons que je fais ceci:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Notez que je l' ai remplacé string resultpar un objet mutable, StringBuilder. C'est beaucoup plus rapide que le premier exemple, car une nouvelle chaîne n'est pas créée à chaque fois dans la boucle. Au lieu de cela, l'objet StringBuilder ajoute simplement les caractères de chaque chaîne à une collection de caractères et affiche le tout à la fin.

Cette fonction est-elle immuable, même si StringBuilder est modifiable?

Oui, ça l'est. Pourquoi? Parce que chaque fois que cette fonction est appelée, un nouveau StringBuilder est créé, uniquement pour cet appel. Nous avons donc maintenant une fonction pure compatible avec les threads, mais contenant des composants mutables.

Mais si je faisais ça?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Cette méthode est-elle thread-safe? Non ce n'est pas. Pourquoi? Parce que la classe détient maintenant l’état dont dépend ma méthode. Une condition de concurrence critique est maintenant présente dans la méthode: un thread peut être modifié IsFirst, mais un autre peut effectuer le premier Append(). Dans ce cas, j'ai une virgule au début de ma chaîne qui n'est pas supposée s'y trouver.

Pourquoi pourrais-je vouloir le faire comme ça? Eh bien, je souhaiterais peut-être que les threads accumulent les chaînes dans mon resultordre ou dans l'ordre d'arrivée des threads. Peut-être que c'est un enregistreur, qui sait?

Quoi qu'il en soit, pour résoudre ce problème, j'ai mis une lockdéclaration autour des entrailles de la méthode.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Maintenant, il est à nouveau thread-safe.

La seule façon pour mes méthodes immuables de ne pas être thread-safe est que si la méthode perd en quelque sorte une partie de son implémentation. Cela pourrait-il arriver? Pas si le compilateur est correct et le programme est correct. Aurai-je besoin de verrous sur de telles méthodes? Non.

Pour voir un exemple de fuite possible dans une implémentation dans un scénario d'accès simultané, voir ici .

Robert Harvey
la source
2
Sauf erreur de ma part, parce que a Listest mutable, dans la première fonction que vous avez déclarée «pure», un autre thread pourrait supprimer tous les éléments de la liste ou en ajouter un nombre supplémentaire pendant qu'il est dans la boucle foreach. Pas sûr de savoir comment cela jouerait avec l’ IEnumeratorêtre while(iter.MoveNext())éduqué, mais à moins que le ne IEnumeratorsoit immuable (douteux), cela menacerait de brouiller la boucle foreach.
Jimmy Hoffa
Certes, vous devez supposer que la collection n’est jamais écrite pendant que les threads la lisent. Ce serait une hypothèse valable, si chaque thread appelant la méthode construit sa propre liste.
Robert Harvey
Je ne pense pas que vous puissiez l'appeler «pur» lorsqu'il contient cet objet mutable qu'il utilise par référence. S'il a reçu un IEnumerable, vous pouvez peut- être faire cette réclamation, car vous ne pouvez pas ajouter ou supprimer des éléments d'un IEnumerable, mais il peut s'agir d'un tableau ou d'une liste remise sous le nom IEnumerable, de sorte que le contrat IEnumerable ne garantit aucun formulaire. de pureté. La vraie technique pour rendre cette fonction pure serait l'immuabilité avec la méthode de copie par copie. C # ne le fait pas. Vous devez donc copier la liste correctement lorsque la fonction la reçoit. mais la seule façon de le faire est avec une foreach dessus ...
Jimmy Hoffa
1
@ JimmyHoffa: Bon sang, vous m'avez obsédé par ce problème de la poule et de l'œuf! Si vous voyez une solution n'importe où, faites le moi savoir.
Robert Harvey
1
Je viens tout juste de trouver cette réponse et c’est l’une des meilleures explications sur le sujet que j’ai rencontré. Les exemples sont très concis et facilitent vraiment la tâche. Merci!
Stephen Byrne
4

Je ne suis pas sûr d'avoir compris vos questions.

IMHO la réponse est oui. Si tous vos objets sont immuables, vous n'avez besoin d'aucun verrou. Mais si vous devez conserver un état (par exemple, vous implémentez une base de données ou vous devez agréger les résultats de plusieurs threads), vous devez utiliser la mutabilité et par conséquent les verrous. L'immuabilité élimine le besoin de verrous, mais vous ne pouvez généralement pas vous permettre d'avoir des applications complètement immuables.

Réponse à la partie 2 - les verrous devraient toujours être plus lents que pas de verrous.

Maros
la source
3
La deuxième partie demande "Quel est le compromis de performance entre serrures et structures immuables?" Elle mérite probablement sa propre question, si elle est même susceptible de réponse.
Robert Harvey
4

En encapsulant un groupe d’états apparentés dans une seule référence modifiable vers un objet immuable, de nombreux types de modifications d’états peuvent être effectués sans verrouillage à l’aide du modèle:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Si deux threads tentent tous deux de se mettre à jour someObject.statesimultanément, les deux objets liront l'ancien état et détermineront ce que serait le nouvel état sans les modifications apportées. Le premier thread qui exécutera CompareExchange stockera ce qu'il pense que l'état suivant devrait être. Le deuxième thread trouvera que l'état ne correspond plus à ce qu'il avait lu précédemment et recalculera donc l'état approprié suivant du système avec les modifications du premier thread prises en compte.

Ce modèle présente l’avantage qu’un thread qui se fait détourner ne peut bloquer la progression d’autres threads. Il présente l’avantage supplémentaire que, même en cas de forte controverse, certains fils progresseront toujours. Toutefois, il existe un inconvénient: en cas de conflit, de nombreux threads passent beaucoup de temps à effectuer un travail qu'ils finiront par rejeter. Par exemple, si 30 threads sur des processeurs distincts tentent tous de modifier un objet simultanément, celui-ci réussira à sa première tentative, un à son second, un à son troisième, etc., de sorte que chaque thread aboutit en moyenne à environ 15 tentatives. mettre à jour ses données. L'utilisation d'un verrou "consultatif" peut considérablement améliorer les choses: avant qu'un thread ne tente une mise à jour, il convient de vérifier si un indicateur de "contention" est activé. Si c'est le cas, il devrait acquérir un verrou avant de faire la mise à jour. Si un thread effectue quelques tentatives infructueuses de mise à jour, il doit définir le drapeau de contention. Si un thread qui tente d'acquérir le verrou trouve qu'il n'y avait personne d'autre en attente, il devrait effacer l'indicateur de conflit. Notez que le verrou ici n'est pas requis pour "exactitude"; le code fonctionnerait correctement même sans cela. L'objectif du verrouillage est de minimiser le temps passé par le code à effectuer des opérations qui risquent de ne pas aboutir.

supercat
la source
4

Vous commencez avec

Clairement, l'immutabilité minimise le besoin de verrous dans la programmation multiprocesseur

Faux. Vous devez lire attentivement la documentation de chaque classe que vous utilisez. Par exemple, const std :: string en C ++ n'est pas thread-safe. Les objets immuables peuvent avoir un état interne qui change lors de leur accès.

Mais vous regardez cela d'un point de vue totalement faux. Peu importe si un objet est immuable ou non, ce qui compte, c'est de le changer. Ce que vous dites, c'est comme dire "si vous ne passez jamais un examen de conduite, vous ne pourrez jamais perdre votre permis de conduire pour conduite avec facultés affaiblies". Vrai, mais manque plutôt le point.

Maintenant, dans l'exemple de code, quelqu'un a écrit avec une fonction nommée "ConcatenateWithCommas": Si l'entrée était modifiable et que vous utilisiez un verrou, que gagneriez-vous? Si quelqu'un d'autre tente de modifier la liste pendant que vous essayez de concaténer les chaînes, un verrou peut vous empêcher de planter. Mais vous ne savez toujours pas si vous concaténez les chaînes avant ou après que l'autre thread les ait modifiées. Donc, votre résultat est plutôt inutile. Vous avez un problème qui n'est pas lié au verrouillage et qui ne peut pas être résolu avec le verrouillage. Mais ensuite, si vous utilisez des objets immuables et que l'autre thread remplace l'objet entier par un nouvel objet, vous utilisez l'ancien objet et non le nouvel objet. Votre résultat est donc inutile. Vous devez penser à ces problèmes au niveau fonctionnel réel.

gnasher729
la source
2
const std::stringest un mauvais exemple et un peu d'un hareng rouge. Les chaînes C ++ sont mutables et constne peuvent en aucun cas garantir l’immuabilité. Tout ce que cela fait, c'est que seules les constfonctions peuvent être appelées. Cependant, ces fonctions peuvent toujours modifier l'état interne et constpeuvent être rejetées. Enfin, il y a le même problème que n'importe quel autre langage: le fait que ma référence constne signifie pas que votre référence l'est aussi. Non, une structure de données vraiment immuable devrait être utilisée.