Gibt es eine produktionsbereite, wartungsfreie Warteschlange oder Hash-Implementierung in C ++? [Geschlossen]

79

Ich habe ziemlich viel nach einer Warteschlange ohne Sperren in C ++ gegoogelt. Ich habe Code und einige Versuche gefunden - aber nichts, was ich kompilieren konnte. Ein sperrfreier Hash wäre ebenfalls willkommen.

ZUSAMMENFASSUNG: Bisher habe ich keine positive Antwort. Es gibt keine "produktionsbereite" Bibliothek, und erstaunlicherweise entspricht keine der vorhandenen Bibliotheken der API von STL-Containern.

ROTE WEICHE ADAIR
quelle
4
Visual Studio 2010 enthält eine sperrfreie Warteschlange in <concurrent_queue.h>
Rick
1
Und es gibt eine Hash_Map und eine ungeordnete_Map unter Code.msdn.com/concrtextras
Rick
2
Beachten Sie, dass der Begriff "sperrenfrei" seltsamerweise nicht unbedingt bedeutet, dass keine Sperren vorhanden sind. Eine Definition finden Sie unter en.wikipedia.org/wiki/Non-blocking_algorithm .
Kristopher Johnson
7
Wow, eine Frage, wie man ein allgemeines, aber schwieriges Problem in der Multithread-Programmierung löst, das mehrere Lösungen hat, viel Diskussion hervorruft und eine Menge positive Stimmen verdient ... 9 Jahre später schließen Sie es als Off-Topic. Vielen Dank für Ihren Beitrag zu StackOverflow, NathanOliver, Sir E_net4, dem weisen Downvoter, Jean-François Fabre, Machavity und gre_gor / s
muusbolla
1
Ich würde sagen, dass die Leute, die die Frage geschlossen haben, sie wahrscheinlich nicht verstehen.
Derf Skren

Antworten:

40

Ab 1.53 bietet Boost eine Reihe sperrenfreier Datenstrukturen , einschließlich Warteschlangen, Stacks und Warteschlangen für einzelne Produzenten / einzelne Konsumenten (dh Ringpuffer).

Nova
quelle
boost :: lockfree :: queue funktioniert nur mit POD-Typen und ist in den meisten Fällen nicht sehr nützlich. Ich bin sicher, wenn es eine Möglichkeit gegeben hätte, eine flexiblere Struktur bereitzustellen, hätte Boost sie eingeführt.
Rahman
1
@rahman wo ist das problem damit? Wenn Sie etwas anderes weitergeben möchten, insbesondere Objekte mit undurchsichtigen, möglicherweise blockierenden Nebenwirkungen, haben Sie den gesamten Zweck des sperrenfreien Designs nicht verstanden.
Ichthyo
Warum Boost eine sperrfreie Warteschlange und einen Stapel bietet, beide basierend auf einer verknüpften Liste. Aber sie bieten keine sperrenfreie verknüpfte Liste?
Deqing
25

Ausgangspunkt wäre entweder der DDJ-Artikel von Herb Sutter für einen einzelnen Produzenten und Verbraucher oder mehrere . Der von ihm angegebene Code (inline ab der zweiten Seite jedes Artikels) verwendet den atomaren <T> -Vorlagentyp im C ++ 0x-Stil. die Sie mithilfe der Boost-Interprozessbibliothek imitieren können.

Der Boost-Code ist in den Tiefen der Interprozessbibliothek vergraben, aber nachdem ich die entsprechende Header-Datei (atomic.hpp) durchgelesen habe, sind die Implementierungen für die erforderlichen Vergleichs- und Austauschvorgänge auf den Systemen, mit denen ich vertraut bin, gut.

Steve Gilham
quelle
1
Steve, ich interessiere mich auch für die atomaren Implementierungen von Boost, aber sie scheinen im Detail von Interprocess zu liegen / und sind nicht dokumentiert. Sind sie trotzdem sicher zu benutzen? Vielen Dank!
Kim Gräsman
Ich kenne die Artikel von Herb Sutter sehr gut - wo haben Sie die Quellen gefunden? Sie werden weder von DDJ noch auf seiner Website veröffentlicht (oder bin ich vielleicht blind?).
RED SOFT ADAIR
1
Der Code ist in den Artikeln enthalten, die auf den jeweiligen zweiten Seiten beginnen.
Steve Gilham
3
Wenn Sie wirklich sperrenfreien Code für mehrere Priducer oder Konsumenten wünschen, bin ich raus. Sutters Warteschlangenbeispiel für mehrere Produzenten ist nicht sperrenfrei - es gibt eine Sperre zum Serialisieren von Produzenten und eine Sperre zum Serialisieren von Verbrauchern. Wenn Sie einen finden können, würde mich das auch interessieren.
Steve Gilham
1
Es gibt eine boost :: lockfree Projekt tim.klingt.org/git?p=boost_lockfree.git ; das kannst du dir ansehen. Eines seiner Ziele ist es, eine Nicht-Details-Version von Atomprimitiven bereitzustellen.
Sstock
17

Ja!

Ich habe eine sperrenfreie Warteschlange geschrieben . Es hat Features ™:

  • Völlig wartungsfrei (keine CAS-Schleifen)
  • Superschnell (über hundert Millionen Enqueue / Dequeue-Vorgänge pro Sekunde)
  • Verwendet die C ++ 11-Verschiebungssemantik
  • Wächst nach Bedarf (aber nur, wenn Sie es möchten)
  • Führt eine sperrfreie Speicherverwaltung für die Elemente durch (unter Verwendung vorab zugewiesener zusammenhängender Blöcke)
  • Standalone (zwei Header plus Lizenz und Readme)
  • Kompiliert unter MSVC2010 +, Intel ICC 13 und GCC 4.7.2 (und sollte unter jedem C ++ 11-kompatiblen Compiler funktionieren)

Es ist auf GitHub unter der vereinfachten BSD-Lizenz verfügbar (zögern Sie nicht!).

Vorsichtsmaßnahmen:

  • Nur für Single-Producer-Single-Consumer-Architektur (dh zwei Threads)
  • Gründlich getestet auf x86 (-64) und sollte auf ARM, PowerPC und anderen CPUs funktionieren, bei denen ausgerichtete Ganzzahlen und Zeigerladevorgänge und -speicher von Natur aus atomar sind, aber nicht auf Nicht-x86-CPUs getestet wurden (falls jemand dies getan hat) eine, um es zu testen, lass es mich wissen)
  • Keine Ahnung, ob Patente verletzt werden (Verwendung auf eigenes Risiko usw.). Beachten Sie, dass ich es selbst von Grund auf neu entworfen und implementiert habe.
Cameron
quelle
2
Klingt sehr gut, aber es werden mehrere Hersteller und / oder mehrere Verbraucher benötigt, um echtes Multithreading zu nutzen.
RED SOFT ADAIR
2
@RED: Abhängig von der Anwendung. Single-Produzent / Konsument war alles, was ich brauchte, also ist es alles, was ich gebaut habe ;-)
Cameron
@ Cameron: Tolles Zeug! Haben Sie Ihre Warteschlange mit der Torheit ProducerConsumerQueue von Facebook verglichen ? Ich habe es mit Ihrem Benchmark-Code gemacht und es scheint sowohl Ihren RWQ als auch den SPSC von Dmitry dramatisch zu übertreffen. Ich bin unter OS X 10.8.3 mit einem 3,06 GHz Core 2 Duo (T9900) und habe den Code mit Clang mit -O3 kompiliert. Ich habe dies getan, weil ich derzeit eine Warteschlange für einen einzelnen Produzenten / einen einzelnen Konsumenten für eines meiner Projekte suche und Ihre als Kandidaten angesehen habe :)
André Neves
@ André: Ich habe gerade nachgesehen :-) Facebooks Torheit ist etwas schneller als meine, wenn ich mich aus einer leeren Warteschlange in die Warteschlange stelle, und etwas langsamer, wenn ich mich aus einer nicht leeren Warteschlange in einem einzelnen Thread in die Warteschlange stelle. Alle anderen Vorgänge haben fast genau die gleiche Geschwindigkeit (dies war mit g ++ -O3 auf einer VM). Welche Größe verwenden Sie für die Torheitswarteschlange? (Ich habe MAX verwendet.) Mine und Dmitry wachsen beide nach Bedarf, während die Torheit behoben ist - und natürlich ist die schnellste Warteschlangenoperation, wenn kein Platz vorhanden ist und sie einfach fehlschlägt. Wenn man sich den Code ansieht, scheint Torheit die gleichen Ideen wie ich zu verwenden, aber ohne Größenanpassung.
Cameron
@ André: Oh, noch etwas, das ich vergessen habe zu erwähnen - mit meinem Benchmark-Code führt der Benchmark "Raw Empty Remove" bei weitem die meisten Iterationen durch (da es so einfach ist, dass mehr erforderlich ist, um ein messbares Ergebnis zu erzielen), was tendenziell der Fall ist die endgültigen "durchschnittlichen Ops / s" -Zahlen überproportional zu beeinflussen. Die Multiplikatoren (und Flat-Timing-Werte) sind im Allgemeinen nützlicher. Wie auch immer, bei diesen Geschwindigkeiten werden alle diese Warteschlangen ziemlich schnell genug sein, wenn sie tatsächlich für etwas Fleischigeres als meine albernen synthetischen Benchmarks verwendet werden ;-)
Cameron
15

Facebooks Folly scheint sperrfreie Datenstrukturen zu haben, die auf C ++ 11 basieren <atomic>:

Ich würde es wagen zu sagen, dass diese derzeit in der Produktion verwendet werden, also denke ich, dass sie sicher in anderen Projekten verwendet werden könnten.

Prost!

André Neves
quelle
Sie haben auch eine MPMC-Warteschlange. dass sie behaupten, ist "optional blockieren". Es scheint nicht Teil ihrer regulären Dokumentation zu sein, unsicher, ob die Verwendung empfohlen wird.
Rusty Shackleford
10

Nachdem ich die meisten der gegebenen Antworten überprüft habe, kann ich nur sagen:

Die Antwort lautet NEIN .

Es gibt kein solches Recht, das sofort verwendet werden könnte.

ROTE WEICHE ADAIR
quelle
4
100% richtig. Mit Hilfe der Newsgroup comp.programming.threads bin ich zum gleichen Ergebnis gekommen. Ein Grund dafür ist, dass der Bereich der sperrenfreien Datenstrukturen ein Patentminenfeld ist. Selbst kommerzielle Bibliotheken wie Intel vermeiden dies.
Lothar
Dies ist C, nicht C ++. Bitte lesen Sie die Fragen, bevor Sie abstimmen.
RED SOFT ADAIR
Entschuldigung. Ich stelle fest, dass SO meine Abstimmung nicht rückgängig machen lässt, da die Abstimmung zu alt ist. Ich denke, die SO-Entwickler müssen mehr tun - sie scheinen immer mehr nicht hilfreiche Verhaltensweisen hinzuzufügen.
3
Warum diese Antwort so viele positive Stimmen bekommt. Die Frage kann leicht bearbeitet werden. Oder das könnte in einem Kommentar stehen.
Benutzer
6

Das nächste, was mir bekannt ist, sind Windows Interlocked Singly Linked Lists . Natürlich ist es nur Windows.

Nemanja Trifunovic
quelle
Wow - das scheint es zu sein. Ich werde etwas Zeit brauchen, um es zu überprüfen (ich kann es derzeit nicht tun), aber ich werde zu Ihnen zurückkehren.
RED SOFT ADAIR
Interlocked Singly Linked List ist ein wunderbares Werkzeug, aber leider kein FIFO.
ali_bahoo
Es ist keine richtige Liste, wie ich mich erinnere. Sie können die Verknüpfung beliebiger Elemente nicht aufheben. Sie können nur die gesamte Liste löschen. Vielleicht ist es seitdem weitergegangen ...
5

Wenn Sie eine Warteschlange / ein FIFO mit mehreren Produzenten / Einzelkonsumenten haben, können Sie mit SLIST oder einem trivialen Lock Free LIFO-Stack ganz einfach ein LockFree erstellen. Sie haben einen zweiten "privaten" Stapel für den Verbraucher (der der Einfachheit halber auch als SLIST oder für jedes andere von Ihnen ausgewählte Stapelmodell verwendet werden kann). Der Verbraucher nimmt Artikel vom privaten Stapel. Immer wenn das private LIFO überfordert ist, führen Sie einen Flush durch, anstatt die gemeinsam genutzte gleichzeitige SLIST (Popup der gesamten SLIST-Kette) zu entfernen und dann die Flushed-Liste der Reihe nach zu durchsuchen, um Elemente auf den privaten Stapel zu verschieben.

Das funktioniert für Einzelproduzenten / Einzelverbraucher und für Mehrfachproduzenten / Einzelverbraucher.

Es funktioniert jedoch nicht für Fälle mit mehreren Verbrauchern (entweder mit Einzelproduzenten oder mit mehreren Produzenten).

Was Hash-Tabellen angeht, sind sie auch ein idealer Kandidat für "Striping", bei dem der Hash nur in Segmente mit einer Sperre pro Segment des Caches unterteilt wird. So macht es die Java Concurrent Library (mit 32 Streifen). Wenn Sie über eine leichte Lese- / Schreibsperre verfügen, kann gleichzeitig auf die Hash-Tabelle zugegriffen werden, um sie gleichzeitig zu lesen. Sie werden nur dann blockiert, wenn auf umstrittenen Streifen geschrieben wird (und möglicherweise, wenn Sie die Hash-Tabelle vergrößern möchten).

Wenn Sie Ihre eigenen würfeln, stellen Sie sicher, dass Sie Ihre Sperren mit den Hash-Einträgen verschachteln, anstatt alle Ihre Sperren in einem Array nebeneinander zu platzieren, damit die Wahrscheinlichkeit einer falschen Freigabe geringer ist.

Adisak
quelle
Danke für deine Antwort. Ich suche eine "produktionsbereite" Lösung / Vorlage in C ++. Ich möchte nicht meine eigenen rollen. Kennen Sie eine solche Implementierung?
RED SOFT ADAIR
4

Ich komme vielleicht etwas spät.

Das Fehlen von Lösungen (bei der Frage wurde gestellt) ist hauptsächlich auf ein wichtiges Problem in C ++ (vor C ++ 0x / 11) zurückzuführen: C ++ hat (hat) kein gleichzeitiges Speichermodell.

Mit std :: atomic können Sie jetzt Probleme mit der Speicherreihenfolge steuern und ordnungsgemäße Vergleichs- und Austauschvorgänge ausführen. Ich habe mir eine Implementierung der sperrenfreien Warteschlange (PODC96) von Micheal & Scott unter Verwendung von C ++ 11 und der Gefahrenzeiger von Micheal (IEEE TPDS 2004) geschrieben, um frühzeitige freie und ABA-Probleme zu vermeiden. Es funktioniert gut, aber es ist eine schnelle und schmutzige Implementierung und ich bin mit den tatsächlichen Leistungen nicht zufrieden. Code ist auf bitbucket verfügbar: LockFreeExperiment

Es ist auch möglich, eine sperrenfreie Warteschlange ohne Gefahrenzeiger mit Doppelwort-CAS zu implementieren (64-Bit-Versionen sind jedoch nur auf x86-64 mit cmpxchg16b möglich). Ich habe hier einen Blog-Beitrag darüber (mit nicht getestetem Code für die Warteschlange) : Implementierung eines generischen Doppelwortvergleichs und -austauschs für x86 / x86-64 (LSE-Blog.)

Mein eigener Benchmark zeigt mir, dass die doppelt gesperrte Warteschlange (ebenfalls in Micheal & Scott 1996) genauso gut funktioniert wie die sperrenfreie (ich habe nicht genügend Konflikte erreicht, sodass gesperrte Datenstrukturen Leistungsprobleme aufweisen, aber meine Bank ist zu leicht für jetzt) ​​und die gleichzeitige Warteschlange von Intels TBB scheint für eine relativ kleine Anzahl noch besser (zweimal schneller) zu sein (je nach Betriebssystem unter FreeBSD 9, der niedrigsten Grenze, die ich bisher gefunden habe, beträgt diese Anzahl 8 Threads auf einer i7 mit 4 ht-Core und damit 8 logischen CPUs) von Threads und sehr seltsamem Verhalten (Ausführungszeit meines einfachen Benchmarks von Sekunden auf Stunden verschieben!)

Eine weitere Einschränkung bei Warteschlangen ohne Sperren, die dem STL-Stil folgen: Iteratoren in Warteschlangen ohne Sperren zu haben, hat keinen Sinn.

Marwan Burelle
quelle
3

Und dann kamen Intel Threading Building Blocks . Und eine Zeit lang war es gut.

PS: Sie suchen nach concurrent_queue und concurrent_hash_map

Edouard A.
quelle
6
Diese sind nicht sperrenfrei. Siehe software.intel.com/en-us/forums/intel-threading-building-blocks/…
RED SOFT ADAIR
1
Ich weiß, im strengen Sinne von Lock-Free, aber ich dachte trotzdem, es könnte dem OP bei seinem Problem helfen, da das Lock-Free-Ding nur ein Implementierungsdetail ist. Ich dachte, er suche nach Sammlungen, die bei gleichzeitigem Zugriff gut funktionieren.
Edouard A.
Lock-free-Ding ist nicht nur ein Implementierungsdetail. Es ist ein ganz anderes Tier.
Arunmoezhi
1

Nach meinem besten Wissen gibt es so etwas noch nicht öffentlich. Ein Problem, das ein Implementierer lösen muss, ist, dass Sie einen sperrfreien Speicherzuweiser benötigen, der vorhanden ist, obwohl ich den Link derzeit nicht zu finden scheint.

Tobias
quelle
Für mich macht es keinen Sinn, warum ein Speicherzuweiser verfügbar ist. Verwenden Sie einfach Datenstrukturen mit intrinsischen Zeigern (Sie kennen den guten alten Weg, bis Sie verrückt nach Containern wurden und Ihre Fähigkeiten verloren haben, um sogar einfache Hashtables zu implementieren).
Lothar
1

Das Folgende stammt aus dem Artikel von Herb Sutter über die Warteschlange ohne gleichzeitige Sperre http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . Ich habe einige Änderungen vorgenommen, z. B. das Neuordnen von Compilern. Man benötigt GCC v4.4 +, um diesen Code zu kompilieren.

#include <atomic>
#include <iostream>
using namespace std;

//compile with g++ setting -std=c++0x

#define CACHE_LINE_SIZE 64

template <typename T>
struct LowLockQueue {
private:
    struct Node {
    Node( T* val ) : value(val), next(nullptr) { }
    T* value;
    atomic<Node*> next;
    char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };
    char pad0[CACHE_LINE_SIZE];

// for one consumer at a time
    Node* first;

    char pad1[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among consumers
    atomic<bool> consumerLock;

    char pad2[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

// for one producer at a time
    Node* last;

    char pad3[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among producers
    atomic<bool> producerLock;

    char pad4[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

public:
    LowLockQueue() {
    first = last = new Node( nullptr );
    producerLock = consumerLock = false;
    }
    ~LowLockQueue() {
    while( first != nullptr ) {      // release the list
        Node* tmp = first;
        first = tmp->next;
        delete tmp->value;       // no-op if null
        delete tmp;
    }
    }

    void Produce( const T& t ) {
    Node* tmp = new Node( new T(t) );
    asm volatile("" ::: "memory");                            // prevent compiler reordering
    while( producerLock.exchange(true) )
        { }   // acquire exclusivity
    last->next = tmp;         // publish to consumers
    last = tmp;             // swing last forward
    producerLock = false;       // release exclusivity
    }

    bool Consume( T& result ) {
    while( consumerLock.exchange(true) )
        { }    // acquire exclusivity
    Node* theFirst = first;
    Node* theNext = first-> next;
    if( theNext != nullptr ) {   // if queue is nonempty
        T* val = theNext->value;    // take it out
        asm volatile("" ::: "memory");                            // prevent compiler reordering
        theNext->value = nullptr;  // of the Node
        first = theNext;          // swing first forward
        consumerLock = false;             // release exclusivity
        result = *val;    // now copy it back
        delete val;       // clean up the value
        delete theFirst;      // and the old dummy
        return true;      // and report success
    }
    consumerLock = false;   // release exclusivity
    return false;                  // report queue was empty
    }
};

int main(int argc, char* argv[])
{
    //Instead of this Mambo Jambo one can use pthreads in Linux to test comprehensively
LowLockQueue<int> Q;
Q.Produce(2);
Q.Produce(6);

int a;
Q.Consume(a);
cout<< a << endl;
Q.Consume(a);
cout<< a << endl;

return 0;
}
enthusiastisch
quelle
4
Dies ist nicht sperrenfrei. Sicher, es wird keine vom Betriebssystem bereitgestellte Sperre verwendet, aber die Art und Weise, wie es sich (zum Beispiel) auf "atomic <bool> consumerLock" dreht, ist definitiv ein Sperrverhalten. Wenn ein Thread abstürzt, während er eine dieser Sperren hält, kann keine Arbeit mehr ausgeführt werden. Sogar Herb selbst sagt es (ich denke auf Seite 4 dieses Artikels).
James Caccese
0

Ich habe das wahrscheinlich 2010 geschrieben, ich bin mir sicher, mit Hilfe verschiedener Referenzen. Es Multi-Produzent Einzelverbraucher.

template <typename T>
class MPSCLockFreeQueue 
{
private:
    struct Node 
    {
        Node( T val ) : value(val), next(NULL) { }
        T value;
        Node* next;
    };
    Node * Head;               
    __declspec(align(4)) Node * InsertionPoint;  //__declspec(align(4)) forces 32bit alignment this must be changed for 64bit when appropriate.

public:
    MPSCLockFreeQueue() 
    {
        InsertionPoint = new Node( T() );
        Head = InsertionPoint;
    }
    ~MPSCLockFreeQueue() 
    {
        // release the list
        T result;
        while( Consume(result) ) 
        {   
            //The list should be cleaned up before the destructor is called as there is no way to know whether or not to delete the value.
            //So we just do our best.
        }
    }

    void Produce( const T& t ) 
    {
        Node * node = new Node(t);
        Node * oldInsertionPoint = (Node *) InterLockedxChange((volatile void **)&InsertionPoint,node);
        oldInsertionPoint->next = node;
    }

    bool Consume( T& result ) 
    {
        if (Head->next)
        {
            Node * oldHead = Head;
            Head = Head->next;
            delete oldHead;
            result = Head->value;
            return true;
        }       
        return false;               // else report empty
    }

};
lockiges Haargenie
quelle