Sind Vergleiche mit == atomar?

icarus2

Hi

Ich bin gerade dabei eine lockfreie Queue (als linked list) zu implementieren. Ich habe nun gerade die Methode Enqueue( T val ) geschrieben und frage mich, ob sie korrekt ist.

Sie sieht wie folgt aus:

public void Enqueue(T val)
        {
            Node newNode = new Node(val);

            while (true)
            {
                Node localTail = _tail;
                Node localTailNext = localTail.Next;

                if (localTail == _tail) // Vergleich atomar?
                {
                    if (localTailNext == null) // Vergleich atomar?
                        if (Interlocked.CompareExchange(ref localTail.Next, newNode, localTailNext) == localTailNext)
                            return;
                        else
                            Interlocked.CompareExchange(ref _tail, localTailNext, localTail);
                }
            }
        }

_tail zeigt nicht zwingend auf das hinterste Element in der Queue.

Meine Frage wäre nun, ob die Vergleiche (siehe Kommentar) atomar sind? Ich denke schon, bin mir aber nicht zu 100% sicher.

*Edit
Oder muss ich Interlocked.ReferenceEquals(...) verwenden?

Gegenfrage:
Wozu sind die Vergleiche gut?

Nach jeder if-Abfrage kann ein nebenläufiger Thread schon wieder reingepfuschst haben. Deshalb stellst Du die Threadsicherheit mit der Interlocked-Klasse sicher.

Also, wozu die Vergleiche? Ist das ein verkapptes Double-Checked-Locking?

Da fällt mir noch auf, dass
if (localTailNext == null)
in jedem Fall threadsicher ist. Du vergleichst ja nur eine lokale Variable mit null.

Der Zweck von if (localTail == _tail) bleibt offen.

Und noch etwas:

Bei einem Monitor.Pulse kannst Du mit 100ns Verzögerung rechnen. So als Faustregel auf modernen PCs. Ein Monitor.Wait verbrät logischweise die Zeit des locks, falls notwendig. Aber es gibt imho auch ein TryWait um noch etwas Performance rauszukitzeln.

Ein Interlocked verbraucht etwa 50ns. Also "nur" die Hälfte. Dafür benötigst Du die Schleife und bist bei massiver Parallelität deutlich schlechter dran.

Ich würde auf lockfreies Threading verzichten und auf Monitor setzen. Das korrekt zu implementieren ist schwierig genug, aber es gibt gute Pattern. Bei lockfreiem Threading blickt doch kein Schwein mehr durch. Schau Dir mal ein paar Beispiele in "C# in a Nutshell" an (das Threading-Kapitel ist frei verfügbar) was da alles schief gehen kann, v.a. bei optimierter Übersetzung. Volatile und MemoryBarrier lassen Grüßen

Nur so am Rande

icarus2

Hi

Erstmal danke für die Antwort(en)

Eins vornhinweg: Es ist die Aufgabe die Queue lockfrei zu implementieren, heisst ich darf keine Monitore und solches Zeug verwenden.

Ich erstelle zuerst lokale Verweise, um diese Überprüfen zu können. Dann schaue ich, ob es Änderungen gegeben hat über das Interlocked. Das macht man so wenn man Interlocked verwendet.

Ich würde sagen, dass ich gerade bei hoher Parallelität mit meiner Implementierung sicher besser dran bin, als mit Monitoren. Wenn ich die Aufgabe fertig gelöst habe, muss ich die Performance mit einer nicht lockfreien Queue vergleichen. Wenn ich soweit bin, werde ich dann mal die Laufzeiten posten.

Es ist natürlich klar, dass lockfreie Queues aufwändiger sind. Aber gerade bei hoher Parallelität sollte aus meiner Sicht die Performance besser sein (kann mich aber teuschen, das sieht man dann beim Vergleich).

Ich habe gerade etwas weitergelesen im Buch "The Art of Multiprocessor Programming" und habe festgestellt, dass dort genau die gleiche Implementierung für eine lockfreie Queue drin ist. Die Sprace ist halt einfach Java. Von daher müsste die Implementierung korrekt sein.

Noch eine Frage an dich:
Wiso denkst du, dass es mit Monitoren schneller geht? In den meisten Fällen sollten diese doch langsamer sein, oder etwa nicht?

hustbaer

Ist _tail volatile?

icarus2 schrieb:

Noch eine Frage an dich:
Wiso denkst du, dass es mit Monitoren schneller geht? In den meisten Fällen sollten diese doch langsamer sein, oder etwa nicht?

Tue ich nicht. Locking ist i.d.R. langsamer.
Ich sah es nur aus sich von "produktivem" Code. Und da muss man abwägen zwischen Verständnis/Wartbarkeit und Performance. Und lockfreier Code ist meist kaum zu verstehen.

Um trotzdem noch einmal das Argument aufzugreifen:
Wenn deine Schleife bei massiver Parallelität mehrfach die Interlocked-Methoden aufruft, bist du imho nicht besser dran als mit äußeren Lock- oder Monitor-Konstrukten.

icarus2

hustbaer schrieb:

Ist _tail volatile?

Nein, _tail ist nicht volatile.

icarus2

whosucks schrieb:

icarus2 schrieb:

Noch eine Frage an dich:
Wiso denkst du, dass es mit Monitoren schneller geht? In den meisten Fällen sollten diese doch langsamer sein, oder etwa nicht?

Tue ich nicht. Locking ist i.d.R. langsamer.
Ich sah es nur aus sich von "produktivem" Code. Und da muss man abwägen zwischen Verständnis/Wartbarkeit und Performance. Und lockfreier Code ist meist kaum zu verstehen.

Um trotzdem noch einmal das Argument aufzugreifen:
Wenn deine Schleife bei massiver Parallelität mehrfach die Interlocked-Methoden aufruft, bist du imho nicht besser dran als mit äußeren Lock- oder Monitor-Konstrukten.

Achso, ok. Ja ich werde es dann mal testen.

PS:
Sry für DP

hustbaer

icarus2 schrieb:

hustbaer schrieb:

Ist _tail volatile?

Nein, _tail ist nicht volatile.

Dann mag der Vergleich zwar vielleicht atomar sein, aber ohne volatile ist nicht garantiert dass überhaupt was gelesen wird - der Vergleich könnte einfach wegoptimiert werden.

icarus2 schrieb:

Aber gerade bei hoher Parallelität sollte aus meiner Sicht die Performance besser sein

Gerade bei hoher Parallelität wird Deine Implementierung problematisch werden. Nehmen wir mal zur Vereinfachung an wir haben genau einen Prozessor-Core und wir reden von 50 Threads die gleichzeitig versuchen eine Node einzuhängen.

In diesem Scenario wird es genau einen Thread geben der den Enqueue sofort schafft, für alle anderen wird (zwangsläufig) deine erste if-Bedingung false sein und diese durchlaufen eine weitere Runde der while(true).

Im zweiten Durchlauf schafft es dann ein zweiter Thread sein Enqueue zu machen, alle übrigen 48 Threads durchlaufen ein weiteres mal while(true)

Strickt man dieses Muster weiter folgt daraus:

Abhängig von der Laufzeit von Node.Next() und der Anzahl gleichzeitig laufender Enqueue() wird sich die Rechenlast auf der Machine erhöhen da Du ein aktive-wait implementiert hast.

Durch die if-Bedingung in der while(true) hast du eine Serialisierung geschaffen, weil immer nur genau ein Thread gleichzeitig diese Bedingung erfüllen kann. damit greift Amdahl's Law (Performancegewinn durch Parallelisierung wird durch den Seriellen Anteil des Systems bestimmt)

Hier ist die Überlegung ob ein Monitor-Ansatz schneller ist also durchaus gerechtfertigt, weil die Abwägen mußt: 49 Threads die aktiv Pollen gegen 49 Threads die im Wait-Status sind, also keine Rechenzeit kosten bis sie durch MOnitor geweckt werden. Dabei darft Du nicht ausser Acht lassen das aktives Pollen ja auch zu entsprechend vielen Kontext-Switches führt, was für sich allein betrachtet zu einem Performance-Problem ausarten kann.

icarus2 schrieb:

Ich habe gerade etwas weitergelesen im Buch "The Art of Multiprocessor Programming" und habe festgestellt, dass dort genau die gleiche Implementierung für eine lockfreie Queue drin ist. Die Sprace ist halt einfach Java. Von daher müsste die Implementierung korrekt sein.

Das heisst nichts. Es gibt auch schlechte Beispiele, falsche Aussagen und fehlerhafte Bücher