Ich habe ein "Server" -Programm, das viele verknüpfte Listen im Shared Memory als Reaktion auf externe Ereignisse aktualisiert. Ich möchte, dass Client-Programme so schnell wie möglich ein Update auf einer der Listen bemerken (niedrigste Latenz). Der Server markiert den Knoten state_ einer verknüpften Liste als FILLED , sobald die Daten ausgefüllt sind und der nächste Zeiger auf eine gültige Position gesetzt wurde. Bis dahin ist seine state_ NOT_FILLED_YET . Ich verwende Speicherbarrieren, um sicherzustellen, dass Clients state_ nicht als FILLED sehen, bevor die Daten tatsächlich bereit sind (und es scheint zu funktionieren, ich sehe niemals korrupte Daten). Außerdem ist state_ flüchtig, um sicher zu sein, dass der Compiler die Überprüfung des Clients aus Schleifen nicht aufhebt.
Da der Servercode genau gleich ist, habe ich drei verschiedene Methoden entwickelt, mit denen der Client die verknüpften Listen nach Änderungen durchsuchen kann. Die Frage ist: Warum ist die 3. Methode am schnellsten?
Methode 1: Round Robin über alle verknüpften Listen ("Kanäle" genannt) kontinuierlich, um zu sehen, ob Knoten in "FILLED" geändert haben:
%Vor%Methode 1 ergab eine sehr geringe Latenz, wenn die Anzahl der Kanäle klein war. Aber als die Anzahl der Kanäle anstieg (250K +), wurde es sehr langsam, weil alle Kanäle durchlaufen wurden. Also habe ich es versucht ...
Methode 2: Geben Sie jeder verknüpften Liste eine ID. Halten Sie eine separate "Update-Liste" auf der Seite. Jedes Mal, wenn eine der verknüpften Listen aktualisiert wird, schieben Sie ihre ID auf die Update-Liste. Jetzt müssen wir nur die einzelne Update-Liste überwachen und die IDs überprüfen, die wir daraus erhalten.
%Vor%Methode 2 gab schreckliche Latenz. Während Methode 1 eine Latenz von weniger als 10us ergeben könnte, würde Methode 2 unerklärlicherweise oft 8ms Latenzzeit geben! Mit gettimeofday scheint es, dass die Änderung in update_cursor- & gt; state_ sehr langsam war, um von der Serveransicht zum Client zu propagieren (Ich bin in einer Multicore-Box, daher nehme ich an, dass die Verzögerung auf Cache zurückzuführen ist). Also habe ich einen hybriden Ansatz versucht ...
Methode 3: Behalten Sie die Update-Liste bei. Wiederholen Sie jedoch alle Kanäle kontinuierlich und überprüfen Sie innerhalb jeder Iteration, ob die Update-Liste aktualisiert wurde. Wenn ja, geh mit der darauf geschobenen Nummer. Wenn dies nicht der Fall ist, überprüfen Sie den Kanal, zu dem wir gerade iteriert haben.
%Vor%Die Latenz dieser Methode war so gut wie Methode 1, aber auf eine große Anzahl von Kanälen skaliert. Das Problem ist, ich habe keine Ahnung warum. Nur um einen Schlüssel in die Sache zu werfen: Wenn ich den 'gefunden via update' Teil auschecke, druckt er zwischen JEDER LATENCY LOG MESSAGE. Was bedeutet, dass Dinge nur auf der Update-Liste gefunden werden! Also ich verstehe nicht, wie diese Methode schneller als Methode 2 sein kann.
Der vollständige kompilierbare Code (erfordert GCC und boost-1.41), der zufällige Zeichenfolgen als Testdaten generiert, lautet: Ссылка
Update: Alle 3 Methoden sind effektiv Spinlocking, bis eine Aktualisierung auftritt. Der Unterschied besteht darin, wie lange es dauert, bis die Aktualisierung bemerkt wird. Sie all besteuern den Prozessor ständig, so dass der Geschwindigkeitsunterschied nicht erklärt wird. Ich teste auf einem 4-Core-Rechner, auf dem sonst nichts läuft, also haben Server und Client nichts zu bieten. Ich habe sogar eine Version des Codes erstellt, in der Updates eine Bedingung signalisieren und Clients auf diese Bedingung warten lassen - die Latenz der Methoden hat sich nicht verbessert.
Update2: Obwohl es 3 Methoden gibt, habe ich immer nur 1 probiert, also konkurrieren nur 1 Server und 1 Client um das Mitglied state_.
Die Antwort war schwierig herauszufinden, und um fair zu sein, wäre schwer mit den Informationen, die ich präsentierte, obwohl jemand den Quellcode tatsächlich kompilierte, vorausgesetzt, dass sie eine Chance haben würden;) Ich sagte das über Update-Liste gefunden "wurde nach jeder Latenz-Log-Nachricht gedruckt, aber das war nicht wirklich wahr - es war nur wahr, so weit ich in meinem Terminal scrollen konnte. Am Anfang wurden einige Updates gefunden, ohne die Update-Liste zu verwenden.
Das Problem ist, dass zwischen dem Zeitpunkt, zu dem ich meinen Startpunkt in der Update-Liste gesetzt habe, und meinem Startpunkt in jeder der Datenlisten ein gewisser Zeitabstand besteht, da diese Operationen Zeit brauchen. Denken Sie daran, dass die Listen die ganze Zeit wachsen. Betrachten Sie den einfachsten Fall, in dem ich zwei Datenlisten, A und B habe. Wenn ich meinen Startpunkt in der Update-Liste setze, sind es 60 Elemente, aufgrund von 30 Aktualisierungen in Liste A und 30 Aktualisierungen in Liste B. Sagen Sie sie habe abgewechselt:
%Vor%Aber dann, nachdem ich die Update-Liste dort eingestellt habe, gibt es eine Reihe von Updates für B und keine Updates für A. Dann setze ich meine Startplätze in jeder der Datenlisten. Meine Startpunkte für die Datenlisten werden sein, nachdem diese Flut von Updates, aber mein Startpunkt in der Update-Liste ist vor diesem Anstieg, also werde ich jetzt nach einer Reihe von Updates suchen ohne sie zu finden. Der obige gemischte Ansatz funktioniert am besten, da durch das Iterieren aller Elemente, wenn keine Aktualisierung gefunden werden kann, die zeitliche Lücke zwischen der Aktualisierungsliste und der Datenliste schnell geschlossen wird.
Hypothese: Methode 2 blockiert irgendwie, dass das Update vom Server geschrieben wird.
Eines der Dinge, die Sie hämmern können, ist neben den Prozessorkernen selbst Ihr kohärenter Cache. Wenn Sie einen Wert für einen gegebenen Kern lesen, muss der L1-Cache auf diesem Kern Lesezugriff auf diese Cache-Zeile erlangen, was bedeutet, dass er den Schreibzugriff auf die Zeile, die jeder andere Cache hat, ungültig machen muss. Und umgekehrt, um einen Wert zu schreiben. Das bedeutet, dass Sie die Cache-Zeile ständig zwischen einem "Schreib" -Zustand (im Cache des Server-Core) und einem "Lese" -Zustand (in den Caches aller Client-Kerne) pingen.
Die Feinheiten der Performance des x86-Caches sind mir nicht völlig vertraut, aber es scheint (zumindest in der Theorie) völlig plausibel zu sein, dass Sie drei verschiedene Threads verwenden, die diesen einen Speicherort so hart wie möglich hämmern Bei Lesezugriffsanforderungen wird in etwa ein Denial-of-Service-Angriff auf dem Server ausgelöst, der verhindert, dass er gelegentlich für einige Millisekunden in diese Cachezeile schreibt.
Sie können möglicherweise ein Experiment durchführen, um dies zu erkennen, indem Sie sich ansehen, wie lange es dauert, bis der Server den Wert tatsächlich in die Aktualisierungsliste schreibt und ob dort eine Verzögerung auftritt, die der Latenz entspricht.
Sie können auch versuchen, den Cache aus der Gleichung zu entfernen, indem Sie alles auf einem einzelnen Kern ausführen, sodass die Client- und Server-Threads die Dinge aus demselben L1-Cache herausziehen.
Ich weiß nicht, ob Sie jemals die Concurrency-Spalten von Herb Sutter gelesen haben. Sie sind ziemlich interessant, besonders wenn Sie Probleme mit dem Cache haben.
In der Tat scheint die Method2 hier besser zu sein, weil die id kleiner als die Daten im Allgemeinen bedeuten würde, dass Sie nicht zu oft zum Hauptspeicher hin und zurück fahren müssen (was zu besteuern ist).
Was jedoch tatsächlich passieren kann ist, dass Sie eine solche Cache-Zeile haben:
%Vor%Was dann eine Konkurrenz erzeugt.
Hier ist der Artikel von Herb Sutter: Erledige das falsche Teilen . Die Grundidee ist einfach, Ihre ID in der Liste künstlich aufzublasen, so dass sie eine Zeile des Caches vollständig belegt.
Sehen Sie sich die anderen Artikel der Serie an, während Sie gerade dabei sind. Vielleicht bekommst du ein paar Ideen. Es gibt einen schönen lock-free circular buffer Ich denke, das könnte für Ihre Update-Liste helfen:)
Ich habe sowohl in Methode 1 als auch in Methode 3 bemerkt, dass Sie eine Zeile haben, ACQUIRE_MEMORY_BARRIER , von der ich annehme, dass sie etwas mit Multi-Threading / Race-Bedingungen zu tun hat?
Wie auch immer, Methode 2 hat keine Betten, was den folgenden Code bedeutet ...
%Vor%wird den Prozessor hämmern. Die typische Art, diese Art von Producer / Consumer-Task auszuführen, besteht darin, eine Art Semaphor zu verwenden, um dem Leser zu signalisieren, dass sich die Update-Liste geändert hat. Eine Suche nach Producer / Consumer Multi Threading sollte Ihnen eine große Anzahl von Beispielen geben. Der Grundgedanke hierbei ist, dass der Thread in den Ruhezustand versetzt werden kann, während er auf den Status update_cursor & gt; wartet. Dies verhindert, dass dieser Thread alle CPU-Zyklen stehlen kann.
Tags und Links c++ multithreading performance shared-memory latency