Esiste una coda pronta per la produzione o un’implementazione hash in C ++

Ho cercato un po ‘su google per una coda senza blocco in C ++. Ho trovato un po ‘di codice e alcune prove – ma nulla che sia stato in grado di compilare. Un hash lock-free sarebbe anche il benvenuto.

SOMMARIO: Finora non ho una risposta positiva. Non esiste una libreria “pronta per la produzione” e incredibilmente nessuna delle librerie esistenti è conforms all’API dei contenitori STL.

A partire da 1.53, boost fornisce una serie di strutture di dati senza blocco , incluse code, stack e code singolo produttore / singolo consumatore (ad es. Ring buffer).

Il punto di partenza sarebbe uno degli articoli DDJ di Herb Sutter sia per un singolo produttore che per il consumatore o per uno multiplo . Il codice che dà (in-line a partire dalla seconda pagina di ogni articolo) usa il tipo di template atomico in stile C ++ 0x; che puoi imitare usando la libreria di interprocessi Boost.

Il codice boost è sepolto nelle profondità della libreria interprocess, ma avendo letto il file di intestazione appropriato (atomic.hpp) le implementazioni per le necessarie operazioni di confronto e scambio sui sistemi con cui ho familiarità con l’aspetto del suono.

La follia di Facebook sembra avere strutture dati libere da lock basate su C ++ 11 :

  • ProducerConsumerQueue con documenti e codice di esempio qui .

  • AtomicHashMap con documenti e codice di esempio qui

Oserei dire che questi sono attualmente utilizzati in produzione, quindi credo che potrebbero essere tranquillamente utilizzati in altri progetti.

Saluti!

Sì!

Ho scritto una coda senza blocco . Ha caratteristiche ™:

  • Completamente senza attese (nessun loop CAS)
  • Super veloce (oltre cento milioni di operazioni di accodamento / annullamento al secondo)
  • Utilizza la semantica del movimento C ++ 11
  • Cresce quando necessario (ma solo se lo vuoi)
  • Blocca la gestione della memoria per gli elementi (utilizzando blocchi contigui preassegnati)
  • Stand-alone (due intestazioni più una licenza e readme)
  • Compilare sotto MSVC2010 +, Intel ICC 13 e GCC 4.7.2 (e dovrebbe funzionare con qualsiasi compilatore C ++ 11 completamente compatibile)

È disponibile su GitHub sotto la licenza BSD semplificata (non esitare a farlo!).

Avvertenze:

  • Solo per architettura single-producer single-producer (cioè due thread)
  • Testato approfonditamente su x86 (-64), e dovrebbe funzionare su ARM, PowerPC e altre CPU in cui numeri interi allineati nativi e carichi e depositi puntatori sono naturalmente atomici, ma non sono stati testati sul campo su CPU non x86 (se qualcuno ha uno per testarlo fammi sapere)
  • Nessuna idea in caso di violazione di brevetti (uso a proprio rischio, ecc.). Si noti che l’ho progettato e implementato da zero.

C’è una tale biblioteca, ma è in C.

Il wrapping su C ++ dovrebbe essere semplice.

http://www.liblfds.org

Dopo aver controllato la maggior parte delle risposte date, posso solo indicare:

La risposta è NO .

Non esiste una cosa giusta che possa essere utilizzata immediatamente.

boost.lockfree è un tentativo di creare implementazioni c ++ di stack lockfree e classi fifo.

repository git pubblico

La cosa più vicina di cui sono a conoscenza sono le liste collegate singolarmente a Windows Interlocked . Certo, è solo per Windows.

Se disponi di una coda di più produttori / singoli consumatori / FIFO, puoi facilmente creare un LockFree usando SLIST o un banale stack LIFO gratuito Lock. Quello che fai è avere un secondo stack “privato” per il consumatore (che può essere fatto anche come SLIST per semplicità o qualsiasi altro modello di stack che scegli). Il consumatore apre gli oggetti dallo stack privato. Ogni volta che il LIFO privato viene espulso, esegui una risciacquo invece di escludere la SLIST concorrente condivisa (afferrando l’intera catena SLIST) e poi apri l’elenco Flush in ordine spingendo gli oggetti nello stack privato.

Funziona per singolo produttore / singolo consumatore e per produttore multiplo / consumatore singolo.

Tuttavia, non funziona per i casi con più consumatori (con produttori singoli o produttori multipli).

Inoltre, per quanto riguarda le tabelle hash, sono un candidato ideale per lo “striping” che sta semplicemente dividendo l’hash in segmenti con un blocco per segmenti della cache. Questo è il modo in cui la libreria concorrente Java lo fa (usando 32 strisce). Se si dispone di un blocco lettore-scrittore leggero, è ansible accedere contemporaneamente alla tabella hash per le letture simultanee e si bloccherà solo quando si verificano scritture su strisce contestate (e possibilmente se si consente di aumentare la tabella hash).

Se esegui il rollover, assicurati di interlacciare i blocchi con le voci di hash piuttosto che mettere tutti i blocchi in un array uno accanto all’altro in modo da avere meno probabilità di avere una condivisione errata.

E poi Intel Threading Building Blocks è arrivato. E per un po ‘, è stato bello.

PS: stai cercando concurrent_queue e concurrent_hash_map

Potrei venire un po ‘in ritardo su questo.

L’assenza di soluzioni (alla domanda è stata posta) sono principalmente dovute a un importante problema in C ++ (prima di C ++ 0x / 11): C ++ non ha (ha) alcun modello di memoria concorrente.

Ora, usando std :: atomic, è ansible controllare i problemi di ordinamento della memoria e disporre di adeguate operazioni di confronto e scambio. Mi sono occupato dell’implementazione della coda senza blocco di Micheal & Scott (PODC96) usando C ++ 11 e Micheal’s Hazard Pointers (IEEE TPDS 2004) per evitare problemi precoci gratuiti e ABA. Funziona bene ma è un’implementazione rapida e sporca e non sono soddisfatto delle prestazioni effettive. Il codice è disponibile su bitbucket: LockFreeExperiment

È anche ansible implementare la coda senza lock senza indicatori di pericolo usando parole doppie CAS (ma le versioni a 64 bit saranno possibili solo su x86-64 usando cmpxchg16b), ho un post sul blog (con codice non testato per la coda) qui : Implementazione di confronto e scambio di parole doppie generiche per x86 / x86-64 (blog LSE).

Il mio benchmark mi mostra che la coda double-locked (anche in Micheal & Scott 1996 paper) è performante così come quella lock-free (non ho raggiunto abbastanza contese in modo che le strutture dati bloccate abbiano problemi di prestazioni, ma la mia panchina è troppo leggera per ora) e la coda simultanea da Intel TBB sembra ancora migliore (due volte più veloce) per un numero relativamente piccolo (a seconda del sistema operativo, in FreeBSD 9, il limite più basso che ho trovato finora, questo numero è 8 thread su un i7 con 4 ht-core, e quindi 8 CPU logiche) di thread e hanno un comportamento molto strano (tempo di esecuzione del mio semplice benchmark spostato da secondi a ore!)

Un altro limite alle code senza blocco seguendo lo stile STL: avere iteratori su una coda senza blocco non ha senso.

Per quanto ne so, non esiste ancora nulla di pubblicamente disponibile. Un problema che un implementatore deve risolvere è che è necessario un allocatore di memoria senza blocco, che esiste, anche se non riesco a trovare il collegamento in questo momento.

Quanto segue è tratto dall’articolo di Herb Sutter su Coda concurrent lock gratuita http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . Ho apportato alcune modifiche come il riordino del compilatore. Uno ha bisogno di GCC v4.4 + per compilare questo codice.

 #include  #include  using namespace std; //compile with g++ setting -std=c++0x #define CACHE_LINE_SIZE 64 template  struct LowLockQueue { private: struct Node { Node( T* val ) : value(val), next(nullptr) { } T* value; atomic next; char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic)]; }; char pad0[CACHE_LINE_SIZE]; // for one consumer at a time Node* first; char pad1[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among consumers atomic consumerLock; char pad2[CACHE_LINE_SIZE - sizeof(atomic)]; // for one producer at a time Node* last; char pad3[CACHE_LINE_SIZE - sizeof(Node*)]; // shared among producers atomic producerLock; char pad4[CACHE_LINE_SIZE - sizeof(atomic)]; 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 Q; Q.Produce(2); Q.Produce(6); int a; Q.Consume(a); cout<< a << endl; Q.Consume(a); cout<< a << endl; return 0; } 

Ho trovato un’altra soluzione scritta in c:

http://www.ddj.com/hpc-high-performance-computing/219500200

Ho scritto questo a un certo punto probabilmente nel 2010, sono sicuro con l’aiuto di riferimenti diversi. È il singolo consumatore multiproduttore.

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