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.

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.

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 .

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.

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.

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.