C ++에 프로덕션 준비 잠금이없는 큐 또는 해시 구현이 있습니까?

C ++에 프로덕션 준비 잠금이없는 큐 또는 해시 구현이 있습니까?

---

나는 C ++에서 잠금없는 큐를 위해 꽤 많이 인터넷 검색을 해왔다. 몇 가지 코드와 시험판을 찾았지만 컴파일 할 수있는 것은 없습니다. 잠금없는 해시도 환영합니다.

요약 : 지금까지는 긍정적 인 대답이 없습니다. "프로덕션 준비"라이브러리가 없으며 놀랍게도 기존 라이브러리 중 STL 컨테이너의 API를 준수하는 라이브러리가 없습니다.

---

1.53부터 boost는 대기열, 스택 및 단일 생산자 / 단일 소비자 대기열 (즉, 링 버퍼)을 포함한 잠금없는 데이터 구조 세트를 제공합니다 .

---

시작점은 단일 생산자와 소비자를 위한 Herb Sutter의 DDJ 기사 또는 여러 기사 중 하나 입니다 . 그가 제공하는 코드 (각 기사의 두 번째 페이지에서 시작하는 인라인)는 C ++ 0x 스타일 atomic <T> 템플릿 유형을 사용합니다. Boost 프로세스 간 라이브러리를 사용하여 모방 할 수 있습니다.

부스트 코드는 프로세스 간 라이브러리의 깊숙한 곳에 숨겨져 있지만 적절한 헤더 파일 (atomic.hpp)을 통해 필자가 익숙한 시스템에서 필요한 비교 및 ​​스왑 작업에 대한 구현을 읽었습니다.

---

Facebook의 Folly 는 C ++ 11에 기반한 잠금없는 데이터 구조를 가지고있는 것 같습니다 <atomic>.

• 문서 및 예제 코드가있는 ProducerConsumerQueue 여기 .

• 문서 및 예제 코드가있는 AtomicHashMap 여기

현재 프로덕션에서 사용되고 있으므로 다른 프로젝트에서도 안전하게 사용할 수 있다고 감히 말할 수 있습니다.

건배!

---

예!

나는 잠금없는 큐를 썼다 . Features ™가 있습니다.

• 완전히 대기하지 않음 (CAS 루프 없음)
• 초고속 (초당 1 억 건 이상의 대기열 삽입 / 대기열 제거 작업)
• C ++ 11 이동 의미 체계 사용
• 필요에 따라 증가 (원하는 경우에만)
• 요소에 대한 잠금없는 메모리 관리를 수행합니다 (사전 할당 된 연속 블록 사용).
• 독립형 (헤더 2 개, 라이센스 및 추가 정보 1 개)
• MSVC2010 +, Intel ICC 13 및 GCC 4.7.2에서 컴파일 (그리고 C ++ 11 완전 호환 컴파일러에서 작동해야 함)

그건 GitHub의에서 사용할 수 단순화 된 BSD 라이선스에 따라 (그것을 포크 주시기 바랍니다!).

주의 사항 :

• 단일 생산자 단일 소비자 아키텍처 (예 : 두 개의 스레드) 에만 해당
• x86 (-64)에서 철저히 테스트되었으며 정렬 된 기본 크기 정수와 포인터로드 및 저장이 자연스럽게 원자 적이지만 x86이 아닌 CPU에서 필드 테스트를 거치지 않은 ARM, PowerPC 및 기타 CPU에서 작동해야합니다. 테스트 할 사람은 알려주세요)
• 특허가 침해되었는지 여부는 알 수 없습니다 (자신의 책임하에 사용 등). 내가 처음부터 직접 디자인하고 구현했습니다.

---

그런 라이브러리가 있지만 C에 있습니다.

C ++로 래핑하는 것은 간단해야합니다.

http://www.liblfds.org

---

주어진 답변의 대부분을 확인한 후 다음과 같이 말할 수 있습니다.

대답은 아니오 입니다.

상자에서 바로 사용할 수있는 권리는 없습니다.

---

boost.lockfree는 lockfree 스택 및 fifo 클래스의 C ++ 구현을 생성하려는 시도입니다.

공용 git 저장소

---

내가 아는 가장 가까운 것은 Windows Interlocked Singly Linked Lists 입니다. 물론 Windows 전용입니다.

---

여러 생산자 / 단일 소비자 대기열 / FIFO가있는 경우 SLIST 또는 간단한 Lock Free LIFO 스택을 사용하여 하나의 LockFree를 쉽게 만들 수 있습니다. 소비자를위한 두 번째 "개인"스택이 있습니다 (단순성을 위해 SLIST 또는 선택한 다른 스택 모델로 수행 할 수도 있음). 소비자는 개인 스택에서 항목을 꺼냅니다. 개인 LIFO가 노출 될 때마다 공유 된 동시 SLIST (전체 SLIST 체인 확보)를 팝하는 대신 Flush를 수행 한 다음 항목을 개인 스택으로 푸시하는 순서대로 Flushed 목록을 살펴 봅니다.

이는 단일 생산자 / 단일 소비자 및 다중 생산자 / 단일 소비자에게 적합합니다.

그러나 다중 소비자 사례 (단일 생산자 또는 다중 생산자 모두)에서는 작동하지 않습니다.

또한 해시 테이블에 관한 한 해시를 캐시의 세그먼트 당 잠금이있는 세그먼트로 나누는 "스트라이핑"에 이상적인 후보입니다. 이것이 Java 동시 라이브러리가 수행하는 방법입니다 (32 스트라이프 사용). 경량 리더-라이터 잠금이있는 경우 동시 읽기를 위해 해시 테이블에 동시에 액세스 할 수 있으며 경합 된 스트라이프에서 쓰기가 발생하는 경우에만 중단됩니다 (해시 테이블을 늘릴 수있는 경우).

직접 롤링하는 경우 모든 잠금을 서로 나란히 배열에 배치하는 대신 해시 항목으로 잠금을 인터리브하여 잘못된 공유가 발생할 가능성을 줄이십시오.

---

이것에 대해 조금 늦게 올 수 있습니다.

솔루션의 부재 (질문에서)는 주로 C ++ (C ++ 0x / 11 이전)의 중요한 문제 때문입니다. C ++에는 동시 메모리 모델이 없습니다.

이제 std :: atomic을 사용하여 메모리 순서 문제를 제어하고 적절한 비교 및 ​​교체 작업을 수행 할 수 있습니다. 저는 초기 무료 및 ABA 문제를 피하기 위해 C ++ 11 및 Micheal의 위험 포인터 (IEEE TPDS 2004)를 사용하여 Micheal & Scott의 잠금없는 대기열 (PODC96) 구현을 직접 작성했습니다. 잘 작동하지만 빠르고 더러운 구현이며 실제 성능에 만족하지 않습니다. bitbucket에서 코드를 사용할 수 있습니다. LockFreeExperiment

이중 단어 CAS를 사용하여 위험 포인터없이 잠금없는 대기열을 구현할 수도 있습니다 (하지만 64 비트 버전은 cmpxchg16b를 사용하여 x86-64에서만 가능합니다), 여기에 대한 블로그 게시물 (대기열에 대한 테스트되지 않은 코드 포함)이 있습니다. : x86 / x86-64에 대한 일반적인 두 단어 비교 및 ​​교체 구현 (LSE 블로그)

내 벤치 마크는 이중 잠금 대기열 (또한 Micheal & Scott 1996 논문에서도)이 잠금없는 대기열만큼 성능을 ​​발휘한다는 것을 보여줍니다 (잠긴 데이터 구조에 성능 문제가있을만큼 충분한 경합에 도달하지 않았지만 내 벤치는 너무 가볍습니다. 지금) Intel의 TBB의 동시 대기열은 비교적 적은 수 (운영 체제에 따라 지금까지 찾은 가장 낮은 경계인 FreeBSD 9에서 2 배 빠름)가 훨씬 더 좋아 보입니다 (2 배 빠름). 4 ht-core, 따라서 8 개의 논리 CPU가있는 i7) 스레드와 매우 이상한 동작이 있습니다 (내 간단한 벤치 마크의 실행 시간이 몇 초에서 몇 시간으로 이동합니다!).

STL 스타일을 따르는 잠금없는 큐에 대한 또 다른 제한 : 잠금없는 큐에 반복자를 갖는 것은 감각이 없습니다.

---

그리고 인텔 스레딩 빌딩 블록 이 나왔습니다. 그리고 한동안 좋았습니다.

추신 : 당신은 concurrent_queue 및 concurrent_hash_map을 찾고 있습니다.

---

내가 아는 한, 아직 공개적으로 사용할 수있는 그러한 것은 없습니다. 구현자가 해결해야 할 한 가지 문제는 현재 링크를 찾을 수없는 것 같지만 존재하는 잠금없는 메모리 할당자가 필요하다는 것입니다.

---

다음은 Concurrent lock free Queue http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 에 대한 Herb Sutter의 기사입니다 . 컴파일러 재정렬과 같은 몇 가지 변경 사항을 적용했습니다. 이 코드를 컴파일하려면 GCC v4.4 이상이 필요합니다.

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

---

c로 작성된 또 다른 해결책을 찾았습니다.

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

---

I wrote this at some point probably back in 2010, I'm sure with help from different references. It Multi-Producer Single Consumer.

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
    }

};

참고URL : https://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c