SPSCQueue
Increased throughput
C++11로 작성된 단일 생산자 단일 소비자 대기 및 잠금 없는 고정 크기 대기열입니다. 이 구현은 Boost::lockfree::spsc 및 folly::ProducerConsumerQueue 보다 빠릅니다.
SPSCQueue< int > q ( 1 );
auto t = std::thread([&] {
while (!q. front ());
std::cout << *q. front () << std::endl;
q. pop ();
});
q.push( 1 );
t.join(); 전체 예제는 src/SPSCQueueExample.cpp 참조하세요.
SPSCQueue<T>(size_t capacity);
용량 capacity 사용하여 T 유형의 항목을 보유하는 SPSCqueue 를 만듭니다. 용량은 1 이상이어야 합니다.
void emplace(Args &&... args);
내부 구성을 사용하여 항목을 대기열에 넣습니다. 대기열이 가득 차면 차단됩니다.
bool try_emplace(Args &&... args);
내부 구성을 사용하여 항목을 대기열에 추가해 보십시오. 성공하면 true 반환하고 대기열이 가득 차면 false 반환합니다.
void push(const T &v);
복사 구성을 사용하여 항목을 대기열에 추가합니다. 대기열이 가득 차면 차단됩니다.
template <typename P> void push(P &&v);
이동 구성을 사용하여 항목을 대기열에 넣습니다. std::is_constructible<T, P&&>::value == true 인 경우에만 오버로드 해결에 참여합니다. 대기열이 가득 차면 차단됩니다.
bool try_push(const T &v);
복사 구성을 사용하여 항목을 대기열에 추가해 보세요. 성공하면 true 반환하고 대기열이 가득 차면 false 반환합니다.
template <typename P> bool try_push(P &&v);
이동 구성을 사용하여 항목을 대기열에 추가해 보세요. 성공하면 true 반환하고 대기열이 가득 차면 false 반환합니다. std::is_constructible<T, P&&>::value == true 인 경우에만 오버로드 해결에 참여합니다.
T *front();
큐의 앞쪽으로 포인터를 반환합니다. 큐가 비어 있으면 nullptr 반환합니다.
void pop();
대기열의 첫 번째 항목을 제거합니다. pop을 호출하기 전에 대기열이 비어 있지 않은지 확인해야 합니다. 이는 front() pop() 을 호출할 때마다 nullptr 이 아닌 값을 반환해야 함을 의미합니다. std::is_nothrow_destructible<T>::value == true 필요합니다.
size_t size();
대기열에서 사용 가능한 항목 수를 반환합니다.
bool empty();
큐가 현재 비어 있으면 true를 반환합니다.
단일 쓰기 스레드만 큐에 넣기 작업을 수행할 수 있고 단일 판독기 스레드만 큐에서 빼기 작업을 수행할 수 있습니다. 다른 사용법은 유효하지 않습니다.
표준 사용자 정의 할당자 인터페이스를 통해 사용자 정의 할당을 지원하는 것 외에도 이 라이브러리는 표준 제안 P0401R3도 지원합니다. 할당자 인터페이스에서 크기 피드백을 제공합니다. 이를 통해 할당된 공간을 낭비하지 않고 대용량 페이지를 편리하게 사용할 수 있습니다. 크기 피드백 사용은 C++17이 활성화된 경우에만 지원됩니다.
대용량 페이지를 할당하기 위한 API는 플랫폼에 따라 다르고 대용량 페이지 크기를 처리하며 NUMA 인식은 애플리케이션에 따라 다르므로 현재 라이브러리에는 대용량 페이지 할당자가 포함되어 있지 않습니다.
다음은 Linux용 거대 페이지 할당자의 예입니다.
# include < sys/mman.h >
template < typename T> struct Allocator {
using value_type = T;
struct AllocationResult {
T *ptr;
size_t count;
};
size_t roundup ( size_t n) { return (((n - 1 ) >> 21 ) + 1 ) << 21 ; }
AllocationResult allocate_at_least ( size_t n) {
size_t count = roundup ( sizeof (T) * n);
auto p = static_cast <T *>( mmap ( nullptr , count, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
- 1 , 0 ));
if (p == MAP_FAILED) {
throw std::bad_alloc ();
}
return {p, count / sizeof (T)};
}
void deallocate (T *p, size_t n) { munmap (p, roundup ( sizeof (T) * n)); }
}; Linux에서 방대한 페이지를 사용하는 방법에 대한 전체 예제는 src/SPSCQueueExampleHugepages.cpp 참조하세요.
기본 구현은 링 버퍼를 기반으로 합니다.
허위 공유로 인한 문제가 발생하지 않도록 주의를 기울였습니다. 헤드 및 테일 인덱스는 잘못된 공유 범위(캐시 라인 크기)에 맞게 정렬되고 채워집니다. 또한 슬롯 버퍼는 시작과 끝에서 잘못된 공유 범위로 채워져 인접한 할당과의 잘못된 공유를 방지합니다.
이 구현은 작성자와 판독기에서 각각 헤드 및 테일 인덱스를 로컬로 캐싱함으로써 일반적인 동시 링 버퍼보다 더 높은 처리량을 갖습니다. 캐싱은 캐시 일관성 트래픽 양을 줄여 처리량을 증가시킵니다.
이것이 어떻게 작동하는지 이해하려면 먼저 캐싱이 없는 읽기 작업을 고려하십시오. 헤드 인덱스(읽기 인덱스)를 업데이트해야 하며 따라서 캐시 라인은 배타적 상태에서 L1 캐시에 로드됩니다. 큐가 비어 있지 않아 공유 상태로 L1 캐시에 로드되었는지 확인하려면 테일(쓰기 인덱스)을 읽어야 합니다. 큐 쓰기 작업은 헤드 인덱스를 읽어야 하기 때문에 쓰기 작업에는 헤드 인덱스 캐시 라인을 다시 배타적 상태로 되돌리기 위해 일부 캐시 일관성 트래픽이 필요할 수 있습니다. 최악의 경우 모든 읽기 및 쓰기 작업에 대해 하나의 캐시 라인이 공유에서 독점으로 전환됩니다.
다음으로 꼬리 인덱스를 캐시하는 대기열 리더를 고려하세요. 캐시된 꼬리 인덱스가 대기열이 비어 있음을 나타내면 꼬리 인덱스를 캐시된 꼬리 인덱스에 로드합니다. 큐가 비어 있지 않은 경우 캐시된 테일 인덱스가 작성자의 테일 인덱스 캐시 라인의 배타적 상태를 도용하지 않고 완료될 수 있을 때까지 여러 읽기 작업이 수행됩니다. 따라서 캐시 일관성 트래픽이 줄어듭니다. 대기열 쓰기 작업에 대해서도 유사한 주장을 할 수 있습니다.
이 구현에서는 전체 대기열을 나타내기 위해 추가 대기열 슬롯을 할당하는 대신 임의의 2개 용량의 거듭제곱을 허용합니다. 추가 대기열 슬롯을 위해 스토리지를 낭비하고 싶지 않다면 다른 구현을 사용해야 합니다.
참고자료:
잠금 없는 알고리즘을 테스트하는 것은 어렵습니다. 구현을 테스트하기 위해 두 가지 접근 방식을 사용하고 있습니다.
처리량 벤치마크는 int 항목 대기열에 대한 2개 스레드 간의 처리량을 측정합니다.
지연 시간 벤치마크는 int 항목의 2개 대기열을 사용하여 통신하는 2개 스레드 간의 왕복 시간을 측정합니다.
AMD Ryzen 9 3900X 12코어 프로세서에 대한 벤치마크 결과, 2개의 스레드는 동일한 칩렛의 서로 다른 코어에서 실행됩니다.
| 대기줄 | 처리량(ops/ms) | 지연 시간 RTT(ns) |
|---|---|---|
| SPSC큐 | 362723 | 133 |
| 부스트::lockfree::spsc | 209877 | 222 |
| 어리석음::ProducerConsumerQueue | 148818 | 147 |
SPSCQueue는 다음 논문에서 인용되었습니다.
이 프로젝트는 Erik Rigtorp <[email protected]>에 의해 만들어졌습니다.
