Teil 1

Eindeutig minimiert Unveränderlichkeit die Notwendigkeit von Sperren bei der Multiprozessor-Programmierung. Beseitigt sie diese Notwendigkeit, oder gibt es Fälle, in denen Unveränderlichkeit allein nicht ausreicht? Es scheint mir, dass Sie die Verarbeitung und Kapselung des Status nur so lange aufschieben können, bis die meisten Programme tatsächlich etwas tun müssen (einen Datenspeicher aktualisieren, einen Bericht erstellen, eine Ausnahme auslösen usw.). Können solche Aktionen immer ohne Sperren ausgeführt werden? Bietet die bloße Aktion, jedes Objekt wegzuwerfen und ein neues zu erstellen, anstatt das Original zu ändern (eine grobe Sichtweise der Unveränderlichkeit), absoluten Schutz vor Konflikten zwischen Prozessen, oder gibt es Eckfälle, die noch gesperrt werden müssen?

Ich kenne viele funktionale Programmierer und Mathematiker, die gerne über "keine Nebenwirkungen" sprechen, aber in der "realen Welt" hat alles einen Nebeneffekt, auch wenn es die Zeit ist, die es dauert, eine Maschinenanweisung auszuführen. Ich interessiere mich sowohl für die theoretische / akademische Antwort als auch für die praktische / reale Antwort.

Wenn Unveränderlichkeit unter bestimmten Bedingungen oder Annahmen sicher ist, möchte ich wissen, wie genau die Grenzen der "Sicherheitszone" sind. Einige Beispiele für mögliche Grenzen:

• I / O
• Ausnahmen / Fehler
• Interaktionen mit Programmen, die in anderen Sprachen geschrieben wurden
• Interaktionen mit anderen Maschinen (physisch, virtuell oder theoretisch)

Besonderer Dank geht an @JimmaHoffa für seinen Kommentar, der diese Frage ausgelöst hat !

Teil 2

Multiprozessor-Programmierung wird häufig als Optimierungstechnik verwendet, um die Ausführung von Code zu beschleunigen. Wann ist es schneller, Sperren im Vergleich zu unveränderlichen Objekten zu verwenden?

Wann können Sie in Anbetracht der in Amdahls Gesetz festgelegten Grenzen eine bessere Gesamtleistung (mit oder ohne Berücksichtigung des Garbage Collectors) mit unveränderlichen Objekten erzielen und veränderliche Objekte sperren?

Zusammenfassung

Ich kombiniere diese beiden Fragen zu einer, um herauszufinden, wo der Begrenzungsrahmen für Unveränderlichkeit liegt, und um Threading-Probleme zu lösen.

Dies ist eine seltsam formulierte Frage, die sehr, sehr weit gefasst ist, wenn sie vollständig beantwortet wird. Ich werde mich darauf konzentrieren, einige der Details zu klären, nach denen Sie fragen.

Unveränderlichkeit ist ein Design-Kompromiss. Dies erschwert einige Vorgänge (schnelles Ändern des Zustands großer Objekte, schrittweises Erstellen von Objekten, Beibehalten des Betriebszustands usw.) zugunsten anderer Vorgänge (einfacheres Debuggen, einfacheres Überlegen des Programmverhaltens, keine Sorge, dass sich bei der Arbeit etwas unter Ihnen ändert) gleichzeitig usw.). Dies ist die letzte Frage, die uns interessiert, aber ich möchte betonen, dass es sich um ein Werkzeug handelt. Ein gutes Tool, das oft mehr Probleme löst, als es verursacht (in den meisten modernen Programmen), aber keine Wunderwaffe ... Es ändert nichts am eigentlichen Verhalten von Programmen.

Was bringt es dir? Unveränderlichkeit bringt eines mit sich: Sie können das unveränderliche Objekt frei lesen, ohne sich Gedanken darüber zu machen, dass sich sein Zustand unter Ihnen ändert (vorausgesetzt, es ist wirklich tief unveränderlich ... Ein unveränderliches Objekt mit veränderlichen Elementen ist normalerweise ein Deal Breaker). Das ist es. Sie müssen nicht mehr gleichzeitig arbeiten (über Sperren, Snapshots, Datenpartitionierung oder andere Mechanismen; der Schwerpunkt der ursprünglichen Frage liegt auf Sperren ... Falsch angesichts des Umfangs der Frage).

Es stellt sich jedoch heraus, dass viele Dinge Objekte lesen. IO funktioniert, aber IO selbst kann die gleichzeitige Verwendung selbst nicht gut verarbeiten. Fast alle Verarbeitungen sind möglich, andere Objekte sind jedoch möglicherweise veränderlich, oder die Verarbeitung selbst verwendet möglicherweise einen Status, der nicht für die gleichzeitige Verwendung geeignet ist. Das Kopieren eines Objekts ist in einigen Sprachen eine große versteckte Schwierigkeit, da eine vollständige Kopie (fast) nie eine atomare Operation ist. Hier helfen Ihnen unveränderliche Objekte.

Die Leistung hängt von Ihrer App ab. Schlösser sind (normalerweise) schwer. Andere Verwaltungsmechanismen für die gleichzeitige Verwendung sind schneller, wirken sich jedoch stark auf Ihr Design aus. Im Allgemeinen ist ein Entwurf mit hoher Gleichzeitigkeit, der unveränderliche Objekte verwendet (und deren Schwächen vermeidet), leistungsfähiger als ein Entwurf mit hoher Gleichzeitigkeit, der veränderbare Objekte sperrt. Wenn Ihr Programm leicht parallel läuft, hängt es davon ab und / oder spielt keine Rolle.

Die Leistung sollte jedoch nicht Ihr Hauptanliegen sein. Das Schreiben von gleichzeitigen Programmen ist schwierig . Das Debuggen gleichzeitig ablaufender Programme ist schwierig . Unveränderliche Objekte verbessern die Qualität Ihres Programms, indem sie die Möglichkeit von Fehlern bei der manuellen Implementierung der Parallelitätsverwaltung beseitigen. Sie erleichtern das Debuggen, da Sie nicht versuchen, den Status in einem gleichzeitigen Programm zu verfolgen. Sie vereinfachen Ihr Design und beseitigen dort Fehler.

Zusammenfassend lässt sich sagen: Unveränderlichkeit hilft, beseitigt jedoch nicht die Herausforderungen, die für einen ordnungsgemäßen Umgang mit der Parallelität erforderlich sind. Diese Hilfe ist in der Regel allgegenwärtig, aber die größten Gewinne werden eher aus der Qualitätsperspektive als aus der Leistung erzielt. Und nein, Unveränderlichkeit entschuldigt Sie nicht auf magische Weise von der Verwaltung der Parallelität in Ihrer App, sorry.

Eine Funktion, die einen bestimmten Wert akzeptiert und einen anderen Wert zurückgibt und nichts außerhalb der Funktion stört, hat keine Nebenwirkungen und ist daher threadsicher. Wenn Sie überlegen möchten, wie sich die Funktionsausführung auf den Stromverbrauch auswirkt, ist dies ein anderes Problem.

Ich gehe davon aus, dass Sie sich auf eine Turing-complete-Maschine beziehen, die eine bestimmte Programmiersprache ausführt, bei der die Implementierungsdetails irrelevant sind. Mit anderen Worten, es sollte keine Rolle spielen, was der Stack tut, wenn die Funktion, die ich in der Programmiersprache meiner Wahl schreibe, Unveränderlichkeit innerhalb der Grenzen der Sprache garantieren kann. Ich denke nicht an den Stack, wenn ich in einer höheren Sprache programmiere, und ich sollte auch nicht müssen.

Um zu veranschaulichen, wie dies funktioniert, werde ich einige einfache Beispiele in C # anbieten. Damit diese Beispiele zutreffen, müssen wir einige Annahmen treffen. Erstens, dass der Compiler die C # -Spezifikation fehlerfrei befolgt und zweitens, dass er korrekte Programme erstellt.

Angenommen, ich möchte eine einfache Funktion, die eine Zeichenfolgensammlung akzeptiert und eine Zeichenfolge zurückgibt, die eine Verkettung aller Zeichenfolgen in der Sammlung ist, die durch Kommas getrennt sind. Eine einfache, naive Implementierung in C # könnte folgendermaßen aussehen:

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;
} 

Dieses Beispiel ist auf den ersten Blick unveränderlich. Woher weiß ich das? Weil das stringObjekt unveränderlich ist. Die Implementierung ist jedoch nicht ideal. Da resultunveränderlich ist, muss jedes Mal durch die Schleife ein neues Zeichenfolgenobjekt erstellt werden, das das ursprüngliche Objekt ersetzt, auf das resultverwiesen wird. Dies kann sich negativ auf die Geschwindigkeit auswirken und Druck auf den Abfallsammler ausüben, da alle diese zusätzlichen Zeichenfolgen entfernt werden müssen.

Angenommen, ich mache Folgendes:

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();
} 

Beachten Sie, dass ich durch string resultein veränderliches Objekt ersetzt habe StringBuilder. Dies ist viel schneller als im ersten Beispiel, da nicht jedes Mal eine neue Zeichenfolge durch die Schleife erstellt wird. Stattdessen fügt das StringBuilder-Objekt die Zeichen aus jeder Zeichenfolge zu einer Sammlung von Zeichen hinzu und gibt das Ganze am Ende aus.

Ist diese Funktion unveränderlich, obwohl StringBuilder veränderlich ist?

Ja ist es. Warum? Da bei jedem Aufruf dieser Funktion ein neuer StringBuilder nur für diesen Aufruf erstellt wird. Jetzt haben wir also eine reine Funktion, die threadsicher ist, aber veränderbare Komponenten enthält.

Aber was ist, wenn ich das tue?

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();
    } 
}

Ist diese Methode threadsicher? Nein, das ist es nicht. Warum? Weil die Klasse jetzt den Status hält, von dem meine Methode abhängt. In der Methode ist jetzt eine Racebedingung vorhanden: Ein Thread kann ändern IsFirst, aber ein anderer Thread kann den ersten ausführen Append(). In diesem Fall habe ich jetzt ein Komma am Anfang meiner Zeichenfolge, das nicht vorhanden sein soll.

Warum könnte ich es so machen wollen? Nun, ich möchte vielleicht, dass die Threads die Strings resultunabhängig von der Reihenfolge oder in der Reihenfolge, in der die Threads eingehen, in meinen akkumulieren . Vielleicht ist es ein Logger, wer weiß?

Wie auch immer, lockum das Problem zu beheben, habe ich eine Aussage über die Innereien der Methode gemacht.

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();
        }
    } 
}

Jetzt ist es wieder threadsicher.

Die einzige Möglichkeit, dass meine unveränderlichen Methoden möglicherweise nicht threadsicher sind, besteht darin, dass die Methode einen Teil ihrer Implementierung verliert. Könnte das passieren? Nicht, wenn der Compiler korrekt ist und das Programm korrekt ist. Brauche ich jemals Sperren für solche Methoden? Nein.

Ein Beispiel dafür, wie die Implementierung in einem Parallelitätsszenario möglicherweise durchgesickert sein kann, finden Sie hier .

Ich bin mir nicht sicher, ob ich Ihre Fragen verstanden habe.

IMHO ist die Antwort ja. Wenn alle Ihre Objekte unveränderlich sind, benötigen Sie keine Sperren. Wenn Sie jedoch einen Status beibehalten müssen (z. B. eine Datenbank implementieren oder die Ergebnisse aus mehreren Threads zusammenfassen müssen), müssen Sie Mutability und daher auch Locks verwenden. Unveränderlichkeit macht Sperren überflüssig, aber normalerweise können Sie es sich nicht leisten, vollständig unveränderliche Anwendungen zu haben.

Antwort auf Teil 2 - Schlösser sollten immer langsamer sein als keine Schlösser.

Das Einkapseln einer Reihe verwandter Zustände in eine einzelne veränderbare Referenz auf ein unveränderliches Objekt kann es ermöglichen, dass viele Arten von Zustandsänderungen mithilfe des folgenden Musters gesperrt werden:

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

Wenn zwei Threads gleichzeitig versuchen, eine Aktualisierung someObject.statedurchzuführen, lesen beide Objekte den alten Status und bestimmen, wie der neue Status ohne die Änderungen des jeweils anderen aussehen würde. Der erste Thread, der CompareExchange ausführt, speichert den Status, den er für den nächsten hält. Der zweite Thread stellt fest, dass der Status nicht mehr mit dem zuvor gelesenen übereinstimmt, und berechnet daher den richtigen nächsten Status des Systems neu, wobei die Änderungen des ersten Threads wirksam werden.

Dieses Muster hat den Vorteil, dass ein Thread, der weggelegt wird, den Fortschritt anderer Threads nicht blockieren kann. Es hat den weiteren Vorteil, dass selbst bei heftigen Konflikten einige Threads immer Fortschritte machen. Es hat jedoch den Nachteil, dass bei Konflikten viele Threads viel Zeit mit der Arbeit verbringen, die sie am Ende verwerfen. Wenn beispielsweise 30 Threads auf separaten CPUs versuchen, ein Objekt gleichzeitig zu ändern, ist der erste Versuch erfolgreich, einer für den zweiten, einer für den dritten usw., sodass jeder Thread im Durchschnitt etwa 15 Versuche ausführt um seine Daten zu aktualisieren. Die Verwendung einer "Advisory" -Sperre kann die Situation erheblich verbessern: Bevor ein Thread versucht, ein Update durchzuführen, sollte überprüft werden, ob ein "Contention" -Kennzeichen gesetzt ist. Wenn ja, Es sollte eine Sperre erhalten, bevor das Update durchgeführt wird. Wenn ein Thread einige erfolglose Aktualisierungsversuche unternimmt, sollte er das Konfliktflag setzen. Wenn ein Thread, der versucht, die Sperre zu erlangen, feststellt, dass niemand anderes gewartet hat, sollte er das Konkurrenz-Flag löschen. Beachten Sie, dass das Schloss hier nicht für die "Richtigkeit" erforderlich ist; Code würde auch ohne korrekt funktionieren. Der Zweck der Sperre besteht darin, den Zeitcodeaufwand für Vorgänge zu minimieren, bei denen ein Erfolg unwahrscheinlich ist.

Du beginnst mit

Offensichtlich minimiert Unveränderlichkeit die Notwendigkeit von Sperren bei der Multiprozessor-Programmierung

Falsch. Sie müssen die Dokumentation für jede Klasse, die Sie verwenden, sorgfältig lesen. Beispielsweise ist const std :: string in C ++ nicht threadsicher. Unveränderliche Objekte können einen internen Status haben, der sich beim Zugriff ändert.

Aber Sie sehen das von einem völlig falschen Standpunkt aus. Es spielt keine Rolle, ob ein Objekt unveränderlich ist oder nicht, es kommt darauf an, ob Sie es ändern. Was Sie sagen, ist, als würden Sie sagen: "Wenn Sie niemals eine Fahrprüfung ablegen, können Sie niemals Ihren Führerschein für betrunkenes Fahren verlieren." Richtig, aber es fehlt der Punkt.

Im Beispielcode hat jemand eine Funktion mit dem Namen "ConcatenateWithCommas" geschrieben: Wenn die Eingabe veränderbar wäre und Sie eine Sperre verwendet hätten, was würden Sie gewinnen? Wenn eine andere Person versucht, die Liste zu ändern, während Sie versuchen, die Zeichenfolgen zu verketten, kann eine Sperre verhindern, dass Sie abstürzen. Sie wissen jedoch immer noch nicht, ob Sie die Zeichenfolgen verketten, bevor oder nachdem der andere Thread sie geändert hat. Ihr Ergebnis ist also eher unbrauchbar. Sie haben ein Problem, das nicht mit dem Sperren zusammenhängt und nicht mit dem Sperren behoben werden kann. Wenn Sie jedoch unveränderliche Objekte verwenden und der andere Thread das gesamte Objekt durch ein neues ersetzt, verwenden Sie das alte Objekt und nicht das neue Objekt, sodass Ihr Ergebnis unbrauchbar ist. Über diese Probleme muss man sich auf einer tatsächlichen funktionalen Ebene Gedanken machen.