SPSCQueue
Increased throughput
Antrean ukuran tetap bebas tunggu dan bebas kunci produsen tunggal yang ditulis dalam C++11. Implementasi ini lebih cepat daripada boost::lockfree::spsc dan 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(); Lihat src/SPSCQueueExample.cpp untuk contoh lengkapnya.
SPSCQueue<T>(size_t capacity);
Buat SPSCqueue yang menampung item tipe T dengan capacity capacity . Kapasitas harus minimal 1.
void emplace(Args &&... args);
Enqueue item menggunakan konstruksi inplace. Blokir jika antrian penuh.
bool try_emplace(Args &&... args);
Cobalah untuk memasukkan item ke dalam antrean menggunakan konstruksi inplace. Mengembalikan true jika berhasil dan false jika antrian penuh.
void push(const T &v);
Enqueue item menggunakan konstruksi salinan. Blokir jika antrian penuh.
template <typename P> void push(P &&v);
Enqueuekan item menggunakan konstruksi pemindahan. Berpartisipasi dalam resolusi kelebihan beban hanya jika std::is_constructible<T, P&&>::value == true . Blokir jika antrian penuh.
bool try_push(const T &v);
Cobalah untuk memasukkan item ke dalam antrean menggunakan konstruksi salinan. Mengembalikan true jika berhasil dan false jika antrian penuh.
template <typename P> bool try_push(P &&v);
Cobalah untuk memasukkan item ke dalam antrean menggunakan konstruksi gerakan. Mengembalikan true jika berhasil dan false jika antrian penuh. Berpartisipasi dalam resolusi kelebihan beban hanya jika std::is_constructible<T, P&&>::value == true .
T *front();
Kembalikan penunjuk ke depan antrian. Mengembalikan nullptr jika antrian kosong.
void pop();
Dequeue item pertama dari antrian. Anda harus memastikan bahwa antrian tidak kosong sebelum memanggil pop. Ini berarti front() harus mengembalikan non- nullptr sebelum setiap panggilan ke pop() . Membutuhkan std::is_nothrow_destructible<T>::value == true .
size_t size();
Mengembalikan jumlah item yang tersedia dalam antrian.
bool empty();
Kembalikan nilai true jika antrian saat ini kosong.
Hanya satu thread penulis yang dapat melakukan operasi enqueue dan hanya satu thread pembaca yang dapat melakukan operasi dequeue. Penggunaan lainnya tidak valid.
Selain mendukung alokasi khusus melalui antarmuka pengalokasi khusus standar, perpustakaan ini juga mendukung proposal standar P0401R3 Memberikan umpan balik ukuran di antarmuka Pengalokasi. Hal ini memungkinkan penggunaan halaman besar dengan nyaman tanpa membuang ruang yang dialokasikan. Penggunaan umpan balik ukuran hanya didukung ketika C++17 diaktifkan.
Perpustakaan saat ini tidak menyertakan pengalokasi halaman yang besar karena API untuk mengalokasikan halaman yang besar bergantung pada platform dan penanganan ukuran halaman yang besar serta kesadaran NUMA bersifat spesifik untuk aplikasi.
Di bawah ini adalah contoh pengalokasi halaman besar untuk 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)); }
}; Lihat src/SPSCQueueExampleHugepages.cpp untuk contoh lengkap tentang cara menggunakan halaman besar di Linux.
Implementasi yang mendasarinya didasarkan pada buffer cincin.
Kehati-hatian telah diambil untuk memastikan untuk menghindari masalah apa pun dengan pembagian yang salah. Indeks kepala dan ekor diselaraskan dan diisi dengan rentang berbagi yang salah (ukuran garis cache). Selain itu, buffer slot dilengkapi dengan rentang pembagian palsu di awal dan akhir, hal ini mencegah pembagian palsu dengan alokasi yang berdekatan.
Implementasi ini memiliki throughput yang lebih tinggi daripada buffer cincin serentak pada umumnya dengan menyimpan indeks kepala dan ekor secara lokal di masing-masing penulis dan pembaca. Caching meningkatkan throughput dengan mengurangi jumlah lalu lintas koherensi cache.
Untuk memahami cara kerjanya, pertama-tama pertimbangkan operasi baca tanpa adanya caching: indeks kepala (indeks baca) perlu diperbarui dan dengan demikian baris cache dimuat ke dalam cache L1 dalam keadaan eksklusif. Ekor (indeks tulis) perlu dibaca untuk memeriksa bahwa antrian tidak kosong dan dengan demikian dimuat ke dalam cache L1 dalam keadaan bersama. Karena operasi penulisan antrean perlu membaca indeks kepala, kemungkinan besar operasi penulisan memerlukan beberapa lalu lintas koherensi cache untuk mengembalikan baris cache indeks kepala ke keadaan eksklusif. Dalam kasus terburuk akan ada satu transisi baris cache dari bersama ke eksklusif untuk setiap operasi baca dan tulis.
Selanjutnya pertimbangkan pembaca antrian yang menyimpan indeks ekor dalam cache: jika indeks ekor yang di-cache menunjukkan bahwa antrian kosong, maka muat indeks ekor ke dalam indeks ekor yang di-cache. Jika antrean tidak kosong, beberapa operasi baca hingga indeks ekor yang di-cache dapat diselesaikan tanpa mencuri status eksklusif baris cache indeks ekor penulis. Oleh karena itu, lalu lintas koherensi cache berkurang. Argumen analog dapat dibuat untuk operasi penulisan antrian.
Implementasi ini memungkinkan non-daya secara sewenang-wenang pada dua kapasitas, sebagai gantinya mengalokasikan slot antrian tambahan untuk menunjukkan antrian penuh. Jika Anda tidak ingin menyia-nyiakan penyimpanan untuk slot antrian tambahan, Anda harus menggunakan implementasi yang berbeda.
Referensi:
Menguji algoritma bebas kunci itu sulit. Saya menggunakan dua pendekatan untuk menguji implementasinya:
Tolok ukur throughput mengukur throughput antara 2 thread untuk antrian item int .
Tolok ukur latensi mengukur waktu bolak-balik antara 2 thread yang berkomunikasi menggunakan 2 antrian item int .
Hasil benchmark untuk Prosesor AMD Ryzen 9 3900X 12-Core, 2 thread berjalan pada core berbeda pada chiplet yang sama:
| Antre | Throughput (operasi/ms) | Latensi RTT (ns) |
|---|---|---|
| SPSCQueue | 362723 | 133 |
| peningkatan::lockfree::spsc | 209877 | 222 |
| kebodohan::ProducerConsumerQueue | 148818 | 147 |
SPSCQueue telah dikutip oleh makalah berikut:
Proyek ini dibuat oleh Erik Rigtorp <[email protected]>.
