Existe-t-il une implémentation en C++ d'une file d'attente ou d'un hachage sans verrou, prête à être produite ?

Question

J'ai pas mal cherché sur Google une file d'attente sans verrou en C++. J'ai trouvé du code et quelques essais - mais rien que je puisse compiler. Un hash sans verrou serait également le bienvenu.

RÉSUMÉ : Jusqu'à présent, je n'ai pas de réponse positive. Il n'y a pas de bibliothèque "prête pour la production", et étonnamment aucune des bibliothèques existantes n'est conforme à l'API des conteneurs STL.

Answer 1

Et puis Blocs de construction Intel Threading est venu. Et pendant un certain temps, c'était bien.

PS : vous cherchez concurrent_queue et concurrent_hash_map

Answer 2

J'espère que cela vous aidera :
Bibliothèque STXXL
TSTL - Thread Safe Template Library (Bibliothèque de modèles sécurisés)

Answer 3

À ma connaissance, rien de tel n'est encore accessible au public. Un problème que l'implémenteur doit résoudre est que vous avez besoin d'un allocateur de mémoire sans verrou, qui existe, bien que je ne parvienne pas à trouver le lien pour l'instant.

Answer 4

Ce qui suit est extrait de l'article de Herb Sutter sur les files d'attente concurrentes sans verrou. http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . J'ai fait quelques changements comme la réorganisation du compilateur. Il faut GCC v4.4+ pour compiler ce code.

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

Answer 5

J'ai trouvé une autre solution écrite en c :

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