atomic_queue
1.0.0
C ++ 14 Multiple-Produzent-Multiple-Consumer -lockfreie Warteschlangen basierend auf kreisförmiger Puffer und std::atomic .
Entworfen mit einem Ziel, um die Latenz zwischen einem Faden zu minimieren, das ein Element in eine Warteschlange drückt, und einen anderen Faden, der es aus der Warteschlange steckt.
Es wurde unter Linux entwickelt, getestet und bewertet, sollte jedoch alle C ++ 14 -Plattformen unterstützen, die std::atomic implementieren. Als mit Windows kompatibel gemeldet, aber die von GitHub gehosteten kontinuierlichen Integrationen sind derzeit nur für die X86_64-Plattform auf Ubuntu-20.04 und Ubuntu-22.04 eingerichtet. Ziehen Sie Anfragen zur Erweiterung der kontinuierlichen Integrationen auf andere Architekturen und/oder Plattformen, die willkommen sind.
Bei der Minimierung der Latenz ist ein gutes Design nicht, wenn nichts mehr zu erweitern ist, sondern wenn nichts mehr zu entfernen ist, wie diese Warteschlangen beispielhaft darstellen.
Minimierung der Latenz maximiert den Durchsatz natürlich. Niedriger Latenz ist in idealem mathematischer und praktischer technischer Sinne hoch throUhput. Niedrige Latenz ist mit Verzögerungen und/oder Chargen nicht kompatibel, die die globale Zeitreihenfolge der originalen (Hardware-) Zeitreihenfolge der Ereignisse zerstören, die durch verschiedene Threads in eine Warteschlange gedrängt wurden. Die Maximierung des Durchsatzes kann dagegen auf Kosten der Latenz erfolgen, indem mehrere Updates verzögert und angegriffen werden.
Das Hauptdesignprinzip, den diese Warteschlangen folgen, ist der Minimalismus , der zu Designentscheidungen wie folgt:
push / pop eine Kopie/Verschiebung erstellen, ohne Referenz/Zeiger auf Elemente in der Warteschlange zu erhalten.Die Auswirkungen jeder dieser kleinen Designentscheidungen selbst sind kaum messbar, aber ihre Gesamtwirkung ist viel größer als eine einfache Summe der Auswirkungen der Bestandteile, auch bekannt als Super-Scalar-Verbund oder Synergie. Die Synergie, die sich aus der Kombination mehrerer dieser kleinen Designentscheidungen zusammengetan hat, ermöglicht es CPUs, die am wenigsten behinderten Spitzenkapazitäten durchzuführen.
Diese Designoptionen sind auch Einschränkungen:
Ultra-Law-Latency-Anwendungen brauchen genau das und nichts weiter. Der Minimalismus zahlt sich aus, sehen Sie die Durchsatz- und Latenz -Benchmarks.
Einige andere gut etablierte und beliebte thread-sichere Behälter werden in den Benchmarks als Referenz verwendet:
std::mutex - ein Ringpuffer mit fester Größe mit std::mutex .pthread_spinlock - ein Ring -Buffer mit fester Größe mit pthread_spinlock_t .boost::lockfree::spsc_queue -Eine Wartezeitfreiheit mit einem Produzenten-Konsumenten-Warteschlangen aus der Boost-Bibliothek.boost::lockfree::queue -Eine lock-freie Multiple-Produzent-Multiple-Consumer-Warteschlange aus der Boost-Bibliothek.moodycamel::ConcurrentQueue -Eine lockfreie Multipler-Produzent-Multiple-Konsumenten-Warteschlange im nicht blockierenden Modus. Diese Warteschlange wurde entwickelt, um den Durchsatz auf Kosten der Latenz zu maximieren und die globale Zeitreihenfolge der Elemente zu vermeiden, die durch verschiedene Threads in eine Warteschlange gedrängt wurden. Es entspricht nicht anderen Warteschlangen, die hier in dieser Hinsicht bewertet sind.moodycamel::ReaderWriterQueue -Eine lockfreie einzelne Produzent-Konsumer-Warteschlange, die im nicht blockierenden Modus verwendet wird.xenium::michael_scott_queue -Eine von Michael und Scott vorgeschlagene Warteschlange mit mehreren Produzierern-Multi-Consumer-Warteschlangen (diese Warteschlange ähnelt boost::lockfree::queue , das auch auf demselben Vorschlag basiert).xenium::ramalhete_queue -Eine von Ramalhete und Correia vorgeschlagene Warteschlange mit mehreren Produzenten-Multi-Konsumenten.xenium::vyukov_bounded_queue -Eine begrenzte Multi-Produzent-Multi-Konsumenten-Warteschlange basierend auf der von Vyukov vorgeschlagenen Version.tbb::spin_mutex - Ein Ring -Puffer mit fester Größe mit tbb::spin_mutex aus Intel -Threading -Bausteinen.tbb::concurrent_bounded_queue - gleichnamige Warteschlange im Nicht -Blocking -Modus aus Intel -Threading -Bausteinen verwendet.Die bereitgestellten Container sind nur Klassenvorlagen aus Header, es ist kein Gebäude/Installieren erforderlich.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include das Verzeichnis (verwenden Sie den vollständigen Pfad) in die inklusiven Pfade Ihres Build -Systems.#include <atomic_queue/atomic_queue.h> In Ihrer C ++ - Quelle. vcpkg install atomic-queue
Folgen Sie dem offiziellen Tutorial zum Konsum von Conan -Paketen. Details für diese Bibliothek sind in Conancenter verfügbar.
Die bereitgestellten Container sind nur Header-Klassenvorlagen, für die nur #include <atomic_queue/atomic_queue.h> erforderlich ist. Es ist kein Gebäude/Installieren erforderlich.
Gebäude ist erforderlich, um die Tests und Benchmarks durchzuführen.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
Für den Benchmark muss auch die Intel TBB -Bibliothek verfügbar sein. Es wird davon ausgegangen, dass es in /usr/local/include und /usr/local/lib installiert ist. Wenn es an anderer Stelle installiert ist, möchten Sie möglicherweise cppflags.tbb und ldlibs.tbb in Makefile ändern.
AtomicQueue - ein Ring -Puffer mit fester Größe für Atomelemente.OptimistAtomicQueue -Ein schnellerer Ring-Puffer mit fester Größe für atomare Elemente, die sich im leeren oder vollständigen Wagen beschäftigt. Es ist AtomicQueue mit push / pop anstelle von try_push / try_pop .AtomicQueue2 -Ein Ring-Puffer mit fester Größe für nichtatomare Elemente.OptimistAtomicQueue2 -Ein schnellerer Ring-Puffer mit fester Größe für nichtatomare Elemente, die im leeren oder vollständigen Wagen beschäftigt sind. Es ist AtomicQueue2 , das mit push / pop anstelle von try_push / try_pop verwendet wird. Diese Behälter haben entsprechende AtomicQueueB , OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 -Versionen, bei denen die Puffergröße als Argument für den Konstruktor angegeben wird.
Der vollständige geordnete Modus wird unterstützt. In diesem Modus empfangen Verbraucher Nachrichten in derselben FIFO -Reihenfolge, in denen die Nachrichten veröffentlicht wurden. Dieser Modus wird für push und pop -Funktionen unterstützt, aber nicht für die try_ -Versionen. Auf Intel X86 hat der vollständig geordnete Modus ab 2019 0 Kosten.
Der einzelne Produzent-Single-Consumer-Modus wird unterstützt. In diesem Modus sind keine teuren Atom-Read-Modify-Write-CPU-Anweisungen erforderlich, nur die billigsten Atomlasten und -speicher. Dies verbessert den Warteschlangendurchsatz erheblich.
Die Elementtypen nur für Bewegung werden vollständig unterstützt. Zum Beispiel wäre eine Warteschlange von std::unique_ptr<T> Elemente AtomicQueue2B<std::unique_ptr<T>> oder AtomicQueue2<std::unique_ptr<T>, CAPACITY> .
Die Warteschlangenklassenvorlagen bieten die folgenden Mitgliedsfunktionen:
try_push - findet ein Element an das Ende der Warteschlange an. Gibt false zurück, wenn die Warteschlange voll ist.try_pop - entfernt ein Element von der Vorderseite der Warteschlange. Gibt false zurück, wenn die Warteschlange leer ist.push (Optimist) - Fügt ein Element zum Ende der Warteschlange hinzu. Beschäftigt wartet, wenn die Warteschlange voll ist. Schneller als try_push , wenn die Warteschlange nicht voll ist. Optionales FIFO -Produzent anstehen und insgesamt Reihenfolge.pop (Optimist) - entfernt ein Element von der Vorderseite der Warteschlange. Beschäftigt wartet, wenn die Warteschlange leer ist. Schneller als try_pop , wenn die Warteschlange nicht leer ist. Optionale FIFO -Verbraucherwarteschlange und Gesamtreihenfolge.was_size - Gibt die Anzahl der nicht ausgezeichneten Elemente während des Anrufs zurück. Der Staat hat sich möglicherweise bis zum Zeitpunkt des Rückgabewerts geändert.was_empty - Gibt true zurück, wenn der Container während des Anrufs leer war. Der Staat hat sich möglicherweise bis zum Zeitpunkt des Rückgabewerts geändert.was_full - Rücksetzt true , wenn der Container während des Anrufs voll war. Der Staat hat sich möglicherweise bis zum Zeitpunkt des Rückgabewerts geändert.capacity - Gibt die maximale Anzahl von Elementen zurück, die die Warteschlange möglicherweise halten kann. Atomische Elemente sind diese, für die std::atomic<T>{T{}}.is_lock_free() true zurückkehrt, und wenn C ++ 17 Funktionen verfügbar sind, bewertet std::atomic<T>::is_always_lock_free zu true zur Kompilierungszeit. Mit anderen Worten, die CPU kann solche Elemente atomar nativ laden, speichern und vergleichen und austauschen. Auf x86-64 sind solche Elemente alle C ++-Standard-Arithmetik- und Zeigertypen.
Die Warteschlangen für Atomelemente behalten sich einen Wert vor, um als leerer Elementmarker zu dienen NIL Der Standardwert beträgt 0 . NIL -Wert darf nicht in eine Warteschlange gestellt werden, und es gibt eine assert in push -Funktionen, um das im Debug -Modus -Build vor diesem zu schützen. Wenn Sie NIL -Element in eine Warteschlange im Release -Modus drücken, erstellt er zu undefiniertem Verhalten wie Deadlocks und/oder verlorene Warteschlangenelemente.
Beachten Sie, dass Optimismus eher die Wahl eines Warteschlangenmodifizierungsbetriebskontrollflusss als eines Warteschlangenentyps ist. Ein optimistischer push ist am schnellsten, wenn die Warteschlange die meiste Zeit nicht voll ist, ein optimistischer pop - wenn die Warteschlange die meiste Zeit nicht leer ist. Optimistisch und nicht so können Operationen ohne Einschränkungen gemischt werden. Die OptimistAtomicQueue in den Benchmarks verwenden nur optimistischen push und pop .
Siehe Beispiel.cc für ein Nutzungsbeispiel.
push und try_push -Operationen synchronisieren Sie mit einem nachfolgenden pop oder try_pop std::memory_order Vorgang desselben Warteschlangenobjekts. Bedeutet, dass:
push / try_push nachgeordnet, was eine memory_order::release -Operation ist. Gleiche Speicherreihenfolge wie die von std::mutex::unlock .pop / try_pop memory_order::acquire angeordnet. Gleiche Speicherreihenfolge wie die von std::mutex::lock .push / try_push eines Elements in eine Warteschlange, werden im Verbraucher-Thread sichtbar, das dieses bestimmte Element pop / try_pop . Die verfügbaren Warteschlangen hier verwenden ein Ring-Puffer-Array zum Speichern von Elementen. Die Kapazität der Warteschlange ist zur Kompilierungszeit oder zur Bauzeit festgelegt.
In einer Produktion Multiple-Produzent-Multiple-Consumer-Szenario sollte die Ring-Puffer-Kapazität auf die maximal erwartete Warteschlangengröße eingestellt werden. Wenn der Ring-Puffer voll wird, bedeutet dies, dass die Verbraucher die Elemente nicht schnell genug konsumieren können. Eine Lösung dafür ist alles:
push and pop -Anrufe entstehen immer einige teure CPU-Zyklen, um die Integrität des Warteschlangenzustands in atomarer/konsistenter/isolierter Weise in Bezug auf andere Fäden aufrechtzuerhalten, und diese Kosten erhöhen mit zunehmendem Anstoß von Warteschlangen die sehr linear. Die Herstellungsgrabung mehrerer kleiner Elemente oder Elemente, die aus einem Ereignis in eine Warteschlangennachricht resultieren, ist häufig eine vernünftige Lösung.Die Verwendung einer Ring-Buffer-Array-Größe von 2 ermöglicht einige wichtige Optimierungen:
% SIZE in den Ring-Buffer-Array-Index zugeordnet. Der Rest-Binärbetreiber % generiert normalerweise eine Division CPU-Anweisung, die nicht billig ist, aber die Verwendung einer Größe der 2-Größe, die der Restbetreiber in einen billigen Binär- and CPU-Anweisungen und so schnell ist, wie es nur geht.N Produzenten zusammen mit M Verbrauchern, die im schlimmsten Fall mit nachfolgenden Elementen in derselben Ring-Buffer-Cache-Linie konkurrieren, ist es nur ein Produzent, der mit einem Verbraucher konkurriert (pedantisch, wenn die Anzahl der CPUs nicht größer ist als die Anzahl der Elemente, die in eine Cache-Linie passen). Diese Optimierung skaliert besser mit der Anzahl der Hersteller und Verbraucher und der Elementgröße. Mit einer geringen Anzahl von Produzenten und Verbrauchern (bis zu 2 davon in diesen Benchmarks) kann diese Optimierung einen besseren Durchsatz bringen (aber eine höhere Varianz zwischen den Läufen). Die Container verwenden unsigned Typ für Größe und interne Indizes. Auf der x86-64-Plattform ist unsigned Plattform 32-Bit breit, während size_t 64-Bit breit ist. 64-Bit-Anweisungen verwenden ein zusätzliches Byte-Anweisungspräfix, was zu einem geringfügigeren Druck auf den CPU-Befehlscache und das Front-End führt. Daher werden 32-Bit- unsigned Indizes verwendet, um die Leistung zu maximieren. Dadurch begrenzt die Warteschlangengröße auf 4.294.967.295 Elemente, was für viele Anwendungen eine angemessene Hartgrenze zu sein scheint.
Während die Atomwarteschlangen mit beliebigen beweglichen Elementtypen (einschließlich std::unique_ptr ) verwendet werden können, sollten die Warteschlangenelemente für den besten Durchsatz und die beste Latenz billig sein, um zu kopieren und frei zu kopieren (z. B. unsigned oder T* ), sodass push und pop am schnellsten abgeschlossen sind.
Konzeptionell führt ein push oder pop -Operation zwei Atomschritte aus:
head inkrementieren, Verbraucher, die tail inkrementieren. Auf jeden Slot wird nur von einem Produzenten und einem Verbraucherfäden zugegriffen.NIL zu sein, und die Verbraucherbelastung von einem Schlitz ändert seinen Zustand in NIL . Der Schlitz ist ein Spinlock für seinen einzigen Produzenten und ein Verbraucherfäden. Diese Warteschlangen gehen davon aus, dass ein Thread, push oder pop durchführt, Schritt 1 abschließen und dann vor Abschluss von Schritt 2 vorbezahlt wird.
Ein Algorithmus ist lockerfrei, wenn ein systemweiter Fortschritt garantiert wird. Diese Warteschlangen garantieren den systemweiten Fortschritt der folgenden Eigenschaften:
push ist unabhängig von einem vorhergehenden push . Ein unvollständiger (vorbefragter) push eines Produzentenfadens beeinflusst push eines anderen Fadens nicht.pop ist unabhängig von einem vorhergehenden pop . Ein unvollständiger (vorbefragter) pop von einem Verbraucher -Thread beeinflusst pop eines anderen Threads nicht.push aus einem Produzenten -Thread betrifft nur einen Verbraucherfaden, der ein Element aus diesem bestimmten Warteschlitzschlitz pop . Alle anderen Threads pop S sind nicht betroffen.pop von einem Verbraucher-Thread betrifft nur einen Produzentenfaden, der ein Element in diesen bestimmten Warteschlitz push , während er erwartet, dass er vor langer Zeit verzehrt wurde. In dem eher unwahrscheinlichen Szenario, das die Produzenten um den gesamten Ring-Puffer gewickelt haben, hat dieser Verbraucher seinen pop nicht abgeschlossen. Alle anderen Threads push S und pop S unberührt. Die Vorstellung von Linux-Task Scheduler-Thread ist etwas, was kein Benutzer-Raum-Prozess beeinflussen oder entkommen sollte, da jede böswillige Anwendung dies ausnutzt.
Dennoch gibt es einige Dinge, die man tun kann, um die Präsentation der geschäftskritischen Anwendungs -Threads zu minimieren:
SCHED_FIFO Planungsklasse für Ihre Threads, z. B. chrt --fifo 50 <app> . Ein Thread oder SCHED_FIFO SCHED_FIFO .SCHED_OTHER mit seinen dynamisch angepassten Prioritäten besiegt den Zweck der Verwendung dieser Warteschlangen.SCHED_FIFO -Echtzeit-Threads gedrosselt werden.taskset platziert werden. Die Leute schlagen oft vor, mit einem nachfolgenden Anruf bei std::this_thread::yield() / sched_yield / pthread_yield ein begrenztes Beschränken vorzulegen. sched_yield ist jedoch ein falsches Tool für das Sperren, da es nicht dem OS -Kernel mitteilt, worauf der Thread wartet, sodass der OS -Thread -Scheduler den aufrufenden Thread niemals zum richtigen Zeitpunkt planen kann, wenn sich der gemeinsame Status geändert hat (es sei denn, es gibt keine anderen Threads, die auf diesem CPU -Kern ausgeführt werden können, so dass sich der Caller -Lebenslauf sofort befragt). Weitere Informationen finden Sie in den Notizenabschnitt in man sched_yield und einem Linux -Kernel -Thread über sched_yield und Spinlocks.
In Linux gibt es mutex-Typ PTHREAD_MUTEX_ADAPTIVE_NP , das einen gesperrten Mutex für eine Reihe von Iterationen beschäftigt und dann ein Blockierungssymbol in den Kernel zum Enttäuschung des wartenden Threads macht. In den Benchmarks war es der schlimmste Darsteller, und ich konnte keinen Weg finden, um es besser zu machen, und das ist der Grund, warum es nicht in den Benchmarks enthalten ist.
Auf Intel CPUs kann man die 4 Debug -Steuerregister verwenden, um den Spinlock -Speicherbereich für Schreibzugriff zu überwachen und mithilfe von select (und seinen Freunden) oder sigwait darauf zu warten (siehe perf_event_open und uapi/linux/hw_breakpoint.h für weitere Details). Ein Spinlock -Kellner könnte sich mit select oder sigwait aussetzen, bis der Spinlock -Zustand aktualisiert wurde. Aber es gibt nur 4 dieser Register, so dass eine solche Lösung nicht skalieren würde.
Anzeigendurchsatz- und Latenz -Benchmarks -Diagramme.
Es gibt ein paar OS -Verhaltensweisen, die das Benchmarking komplizieren:
SCHED_FIFO Priorität 50 verwendet wird, um die Zeitablauf der Zeitplanerzeit zu deaktivieren und die Threads durch Prozesse/Threads mit niedrigerer Priorität nicht vorsichtig zu gestalten.benchmarks zu minimieren, wird mindestens 33 Mal ausgeführt. Die Benchmark -Diagramme zeigen Durchschnittswerte. Der Diagramm -Tooltip zeigt auch die Standardabweichung, die minimalen und maximalen Werte an. Benchmark-Leistung von Single-Producer-Single-Consumer-Warteschlangen boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue und diese Warteschlangen in Single-Producer-Single-Consumer-Modus sollten identisch sein, da sie genau denselben Algorithmus implementieren, der genau dieselben Atomlast- und Speicheranweisungen verwendet. boost::lockfree::spsc_queue Implementation Benchmarked zu diesem Zeitpunkt hatte keine Optimierungen für die Minimierung von L1D -Cache -Konkurrenz, Fehlverpotktion oder Pipeline -Ständen aus subtileren Problemen, die nur im generierten Assemblercode bemerkenswert sind.
Ich habe nur Zugriff auf ein paar X86-64-Maschinen. Wenn Sie Zugriff auf verschiedene Hardware haben, können Sie die Ausgabedatei mit scripts/run-benchmarks.sh senden und ich werde Ihre Ergebnisse in die Benchmarks-Seite einbeziehen.
Wenn riesige Seiten verfügbar sind, verwenden die Benchmarks 1x1GB oder 16 x 2 MB riesige Seiten für die Warteschlangen, um die TLB -Fehlschläge zu minimieren. Um riesige Seiten zu aktivieren, tun Sie einen von:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
Alternativ möchten Sie möglicherweise transparente Riesige in Ihrem System ermöglichen und einen riesigen Allocator wie TCMALLOC verwenden.
Standardmäßig drosselt Linux Scheduler Echtzeit-Threads, 100% der CPU zu konsumieren, und das ist nachteilig für das Benchmarking. Vollständige Details finden Sie in der Echtzeit-Gruppenplanung. Um Echtzeit-Thread zu deaktivieren, tun Sie:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
N Produzentenfäden drücken eine 4-Byte-Ganzzahl in die gleiche Warteschlange, n Verbraucher-Threads stecken die Ganzzahlen aus der Warteschlange. Alle Produzenten veröffentlicht insgesamt 1.000.000 Nachrichten. Die Gesamtzeit zum Senden und Empfangen aller Nachrichten wird gemessen. Der Benchmark wird von 1 Produzent und 1 Verbraucher bis hin zu (total-number-of-cpus / 2) Produzenten / Verbrauchern betrieben, um die Skalierbarkeit verschiedener Warteschlangen zu messen.
Ein Thread veröffentlicht eine Ganzzahl zu einem anderen Thread durch eine Warteschlange und wartet auf eine Antwort einer anderen Warteschlange (insgesamt 2 Warteschlangen). Die Benchmarks messen die Gesamtzeit von 100.000 Pingspongs, die besten von 10 Läufen. Die Streitmacht ist hier minimal (1-Produzent-1-Verbraucher, 1 Element in der Warteschlange), um die niedrigste Latenz zu erreichen und zu messen. Meldet die durchschnittliche Hin- und Rückfahrt.
Beiträge sind mehr als willkommen. .editorconfig und .clang-format können verwendet werden, um automatisch die Code-Formatierung anzupassen.
Einige Bücher zum Thema Multi-Thread-Programmierung fanden ich ziemlich lehrreich:
Copyright (C) 2019 Maxim Egorushkin. MIT -Lizenz. Siehe die vollständige Lizenz in der Dateilizenz.
