atomic_queue
1.0.0
C ++ 14 Antrian bebas-multiple-consumer-consumer- consumer berdasarkan buffer bundar dan std::atomic .
Dirancang dengan tujuan untuk meminimalkan latensi antara satu utas mendorong elemen ke dalam antrian dan utas lain yang muncul dari antrian.
Ini telah dikembangkan, diuji dan dibandingkan di Linux, tetapi harus mendukung platform C ++ 14 yang menerapkan std::atomic . Dilaporkan kompatibel dengan Windows, tetapi integrasi kontinu yang diselenggarakan oleh GitHub saat ini hanya diatur untuk platform X86_64 di Ubuntu-20.04 dan Ubuntu-22.04. Tarik permintaan untuk memperluas integrasi berkelanjutan untuk dijalankan pada arsitektur lain dan/atau platform dipersilakan.
Ketika meminimalkan latensi, desain yang baik bukan saat tidak ada yang tersisa untuk ditambahkan, melainkan ketika tidak ada yang tersisa untuk dihapus, seperti yang dicontohkan oleh antrian ini.
Meminimalkan latensi secara alami memaksimalkan throughput. Latensi rendah timbal balik adalah throuhput tinggi, dalam indera teknik matematika dan praktis yang ideal. Latensi rendah tidak kompatibel dengan penundaan dan/atau batching, yang menghancurkan urutan waktu global (perangkat keras) peristiwa yang didorong ke dalam satu antrian oleh utas yang berbeda. Memaksimalkan throughput, di sisi lain, dapat dilakukan dengan biaya latensi dengan menunda dan batching beberapa pembaruan.
Prinsip desain utama antrian ini diikuti adalah minimalis , yang menghasilkan pilihan desain seperti:
push / pop , tidak ada referensi/pointer ke elemen dalam antrian dapat diperoleh.Dampak dari masing-masing pilihan desain kecil ini sendiri hampir tidak dapat diukur, tetapi dampak totalnya jauh lebih besar daripada jumlah sederhana dari dampak konstituen, alias peracikan super-skalar atau sinergi. Sinergi yang muncul dari menggabungkan beberapa pilihan desain kecil ini bersama -sama adalah apa yang memungkinkan CPU untuk tampil pada kapasitas puncaknya yang paling tidak terhambat.
Pilihan desain ini juga merupakan batasan:
Aplikasi ultra-rendah-latensi hanya membutuhkan hal itu dan tidak lebih. Minimalis terbayar, lihat tolok ukur throughput dan latensi.
Beberapa wadah yang aman dan aman dan populer lainnya digunakan untuk referensi dalam tolok ukur:
std::mutex - buffer cincin ukuran tetap dengan std::mutex .pthread_spinlock - buffer cincin ukuran tetap dengan pthread_spinlock_t .boost::lockfree::spsc_queue -Antrian konsumen-produser-single-consumer bebas menunggu dari Boost Library.boost::lockfree::queue -Antrian Multiple-Producer-Producer-Consumer dari Boost Library.moodycamel::ConcurrentQueue -antrian multi-produser-produser-konsumen yang digunakan dalam mode non-blocking. Antrian ini dirancang untuk memaksimalkan throughput dengan mengorbankan latensi dan menghindari urutan waktu global elemen yang didorong ke dalam satu antrian oleh utas yang berbeda. Ini tidak setara dengan antrian lain yang dibandingkan di sini dalam hal ini.moodycamel::ReaderWriterQueue -Antrian konsumen produser tunggal-produser tunggal yang digunakan dalam mode non-blocking.xenium::michael_scott_queue -Antrian multi-produser-multi-konsumen yang diusulkan oleh Michael dan Scott (antrian ini mirip dengan boost::lockfree::queue yang juga didasarkan pada proposal yang sama).xenium::ramalhete_queue -Antrian multi-produser-multi-konsumen yang diusulkan oleh Ramalhete dan Correia.xenium::vyukov_bounded_queue -antrian multi-produser-multi-konsumen yang dibatasi berdasarkan versi yang diusulkan oleh Vyukov.tbb::spin_mutex - buffer cincin ukuran tetap terkunci dengan tbb::spin_mutex dari blok bangunan threading intel.tbb::concurrent_bounded_queue - antrian eponymous digunakan dalam mode non -blocking dari blok bangunan threading intel.Wadah yang disediakan adalah templat kelas header saja, tidak diperlukan bangunan/pemasangan.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include direktori (gunakan jalur lengkap) ke jalur termasuk sistem build Anda.#include <atomic_queue/atomic_queue.h> di sumber C ++ Anda. vcpkg install atomic-queue
Ikuti tutorial resmi tentang cara mengkonsumsi paket Conan. Detail khusus untuk perpustakaan ini tersedia di Conancenter.
Wadah yang disediakan adalah templat kelas hanya header yang hanya membutuhkan #include <atomic_queue/atomic_queue.h> , tidak diperlukan bangunan/pemasangan.
Bangunan diperlukan untuk menjalankan tes dan tolok ukur.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
Benchmark juga membutuhkan perpustakaan Intel TBB untuk tersedia. Diasumsikan bahwa itu dipasang di /usr/local/include dan /usr/local/lib . Jika diinstal di tempat lain, Anda mungkin ingin memodifikasi cppflags.tbb dan ldlibs.tbb di Makefile .
AtomicQueue - Puffer cincin ukuran tetap untuk elemen atom.OptimistAtomicQueue -Buffer cincin ukuran tetap yang lebih cepat untuk elemen atom yang menunggu sibuk saat kosong atau penuh. Ini adalah AtomicQueue yang digunakan dengan push / pop alih -alih try_push / try_pop .AtomicQueue2 -Puffer cincin ukuran tetap untuk elemen non-atom.OptimistAtomicQueue2 -buffer cincin ukuran tetap yang lebih cepat untuk elemen non-atom yang menunggu sibuk saat kosong atau penuh. Ini adalah AtomicQueue2 yang digunakan dengan push / pop alih -alih try_push / try_pop . Wadah -wadah ini memiliki AtomicQueueB yang sesuai, OptimistAtomicQueueB , AtomicQueueB2 , OptimistAtomicQueueB2 versi di mana ukuran buffer ditentukan sebagai argumen untuk konstruktor.
Mode yang benar -benar dipesan didukung. Dalam mode ini konsumen menerima pesan dalam urutan FIFO yang sama, pesan telah diposting. Mode ini didukung untuk fungsi push dan pop , tetapi untuk bukan versi try_ . Pada Intel X86 mode yang benar -benar dipesan memiliki 0 biaya, pada 2019.
Mode konsumen-single-consumer tunggal didukung. Dalam mode ini, tidak ada instruksi CPU baca-modifikasi atom yang mahal diperlukan, hanya muatan dan toko atom termurah. Itu meningkatkan throughput antrian secara signifikan.
Jenis elemen antrian bergerak saja sepenuhnya didukung. Misalnya, antrian elemen std::unique_ptr<T> akan menjadi AtomicQueue2B<std::unique_ptr<T>> atau AtomicQueue2<std::unique_ptr<T>, CAPACITY> .
Templat kelas antrian menyediakan fungsi anggota berikut:
try_push - Tambahkan elemen ke akhir antrian. Mengembalikan false saat antrian penuh.try_pop - menghapus elemen dari bagian depan antrian. Mengembalikan false saat antrian kosong.push (Optimist) - Tambahkan elemen ke akhir antrian. Sibuk menunggu saat antrian penuh. Lebih cepat dari try_push saat antrian tidak penuh. Produser FIFO opsional antrian dan pesanan total.pop (Optimist) - Menghapus elemen dari bagian depan antrian. Sibuk menunggu saat antrian kosong. Lebih cepat dari try_pop saat antrian tidak kosong. Antrian konsumen FIFO opsional dan pesanan total.was_size - Mengembalikan jumlah elemen yang tidak dikonsumsi selama panggilan. Negara mungkin telah berubah pada saat nilai pengembalian diperiksa.was_empty - mengembalikan true jika wadah kosong selama panggilan. Negara mungkin telah berubah pada saat nilai pengembalian diperiksa.was_full - kembali true jika wadah penuh selama panggilan. Negara mungkin telah berubah pada saat nilai pengembalian diperiksa.capacity - Mengembalikan jumlah elemen maksimum yang mungkin dimiliki antrian. Elemen atom adalah mereka, yang std::atomic<T>{T{}}.is_lock_free() Mengembalikan true , dan, ketika fitur C ++ 17 tersedia, std::atomic<T>::is_always_lock_free mengevaluasi waktu kompilasi yang true . Dengan kata lain, CPU dapat memuat, menyimpan, dan membandingkan dan mengukir elemen-elemen tersebut secara atom secara asli. Pada x86-64 elemen tersebut adalah semua tipe aritmatika dan pointer standar C ++.
Antrian untuk elemen atom memesan satu nilai untuk berfungsi sebagai penanda elemen kosong NIL , nilai defaultnya adalah 0 . Nilai NIL tidak boleh didorong ke dalam antrian dan ada pernyataan assert dalam fungsi push untuk menjaga terhadap hal itu dalam mode debug. Mendorong elemen NIL ke dalam antrian dalam mode rilis membangun hasil dalam perilaku yang tidak ditentukan, seperti kebuntuan dan/atau elemen antrian yang hilang.
Perhatikan bahwa optimisme adalah pilihan aliran kontrol operasi modifikasi antrian, bukan tipe antrian. push optimis adalah tercepat ketika antrian tidak penuh sebagian besar waktu, pop optimis - ketika antrian tidak kosong sebagian besar waktu. Operasi optimis dan tidak sehingga dapat dicampur tanpa batasan. OptimistAtomicQueue s dalam tolok ukur hanya menggunakan push dan pop optimis .
Lihat contoh.cc untuk contoh penggunaan.
push dan try_push Operasi Sinkronisasi dengan (sebagaimana didefinisikan dalam std::memory_order ) dengan operasi pop atau try_pop berikutnya dari objek antrian yang sama. Artinya:
push / try_push , yang merupakan operasi memory_order::release . Urutan memori yang sama seperti std::mutex::unlock .pop / try_pop , yang merupakan memory_order::acquire operasi. Urutan memori yang sama seperti std::mutex::lock .push / try_push dari suatu elemen menjadi antrian menjadi terlihat di utas konsumen yang pop / try_pop elemen tertentu. Antrian yang tersedia di sini menggunakan array ring-buffer untuk menyimpan elemen. Kapasitas antrian ditetapkan pada waktu kompilasi atau waktu konstruksi.
Dalam skenario multi-produser multiple-konsumen, kapasitas ring-buffer harus diatur ke ukuran antrian maksimum yang diharapkan. Ketika ring-buffer menjadi penuh, itu berarti bahwa konsumen tidak dapat mengkonsumsi elemen dengan cukup cepat. Perbaikan untuk itu adalah salah satu dari:
push dan pop selalu menimbulkan beberapa siklus CPU yang mahal untuk mempertahankan integritas keadaan antrian secara atom/konsisten/terisolasi sehubungan dengan utas lain dan biaya ini meningkat super-linier seiring pertengkaran antrian. Produser batching beberapa elemen atau elemen kecil yang dihasilkan dari satu peristiwa menjadi satu pesan antrian seringkali merupakan solusi yang masuk akal.Menggunakan ukuran array power-of-2 ring-buffer memungkinkan beberapa optimasi penting:
% SIZE operator biner sisanya. Operator biner yang tersisa % biasanya menghasilkan instruksi CPU divisi yang tidak murah, tetapi menggunakan ukuran power-of-2 yang beralih yang sisanya operator menjadi satu instruksi biner and CPU murah dan itu secepat yang didapat.N produsen bersama dengan konsumen M yang bersaing pada elemen-elemen berikutnya dalam garis cache ring-buffer yang sama dalam kasus terburuk, itu hanya satu produsen yang bersaing dengan satu konsumen (secara pedan, ketika jumlah CPU tidak lebih besar dari jumlah elemen yang dapat sesuai dengan satu garis cache). Optimalisasi ini berskala lebih baik dengan jumlah produsen dan konsumen, dan ukuran elemen. Dengan jumlah produsen dan konsumen yang rendah (hingga sekitar 2 dari masing -masing dalam tolok ukur ini) yang menonaktifkan optimasi ini dapat menghasilkan throughput yang lebih baik (tetapi varian yang lebih tinggi di seluruh berjalan). Wadah menggunakan jenis unsigned untuk ukuran dan indeks internal. Pada platform X86-64 unsigned adalah lebar 32-bit, sedangkan size_t lebar 64-bit. Instruksi 64-bit menggunakan awalan instruksi byte tambahan yang menghasilkan sedikit lebih banyak tekanan pada cache instruksi CPU dan front-end. Oleh karena itu, indeks unsigned 32-bit digunakan untuk memaksimalkan kinerja. Itu membatasi ukuran antrian menjadi 4.294.967.295 elemen, yang tampaknya menjadi batas keras yang masuk akal untuk banyak aplikasi.
Sementara antrian atom dapat digunakan dengan jenis elemen yang dapat dipindahkan (termasuk std::unique_ptr ), untuk throughput dan latensi terbaik elemen antrian harus murah untuk disalin dan bebas kunci (misalnya unsigned atau T* ), sehingga operasi push dan pop lengkap tercepat.
Secara konseptual , operasi push atau pop melakukan dua langkah atom:
head , konsumen bertambahnya indeks tail . Setiap slot diakses oleh satu produsen dan satu utas konsumen saja.NIL , pemuatan konsumen dari slot mengubah keadaan menjadi NIL . Slot adalah spinlock untuk satu produsen dan satu utas konsumen. Antrian ini mengantisipasi bahwa utas yang melakukan push atau pop dapat menyelesaikan langkah 1 dan kemudian didahului sebelum menyelesaikan langkah 2.
Suatu algoritma bebas kunci jika ada kemajuan sistem yang dijamin. Kemajuan Seluruh Sistem Jaminan Antrian ini oleh Properti berikut:
push tidak tergantung pada push sebelumnya. push yang tidak lengkap (lebih baik) oleh satu utas produser tidak mempengaruhi push utas lainnya.pop tidak tergantung pada pop sebelumnya. pop yang tidak lengkap (lebih dini) oleh satu utas konsumen tidak mempengaruhi pop dari utas lainnya.push yang tidak lengkap (lebih baik) dari satu utas produsen hanya mempengaruhi satu utas konsumen yang pop elemen dari slot antrian khusus ini. Semua utas lainnya pop tidak terpengaruh.pop yang tidak lengkap (yang didahului) dari satu utas konsumen hanya mempengaruhi satu utas produsen push elemen ke dalam slot antrian khusus ini sambil mengharapkannya telah dikonsumsi sejak lama, dalam skenario yang agak tidak mungkin yang telah dibungkus oleh produsen seluruh ring-buffer sementara konsumen ini belum menyelesaikan pop -nya. Semua utas lainnya push S dan pop S tidak terpengaruh. Preemption Thread Penjadwal Tugas Linux adalah sesuatu yang tidak boleh dipengaruhi oleh proses ruang pengguna atau melarikan diri, jika tidak semua/setiap aplikasi jahat akan mengeksploitasi itu.
Namun, ada beberapa hal yang dapat dilakukan untuk meminimalkan preemption utas aplikasi kritis misi seseorang:
SCHED_FIFO waktu-nyata untuk utas Anda, misalnya chrt --fifo 50 <app> . Prioritas yang lebih tinggi SCHED_FIFO Utas atau penangan interupsi kernel masih dapat mendahului utas SCHED_FIFO Anda.SCHED_OTHER dengan prioritas yang disesuaikan secara dinamis mengalahkan tujuan menggunakan antrian ini.SCHED_FIFO dari dicekik.taskset . Orang-orang sering mengusulkan membatasi menunggu sibuk dengan panggilan berikutnya ke std::this_thread::yield() / sched_yield / pthread_yield . Namun, sched_yield adalah alat yang salah untuk mengunci karena tidak berkomunikasi dengan kernel OS apa yang ditunggu -tunggu oleh utas, sehingga penjadwal utas OS tidak pernah dapat menjadwalkan utas panggilan untuk dilanjutkan pada waktu yang tepat ketika status bersama telah berubah (kecuali tidak ada utas lain yang dapat berjalan pada inti CPU ini, sehingga penelepon kembali segera). Lihat bagian Catatan di man sched_yield dan utas kernel Linux tentang sched_yield dan SPINLOCKS untuk detail lebih lanjut.
Di Linux, ada mutex tipe PTHREAD_MUTEX_ADAPTIVE_NP yang sibuk-waits mutex terkunci untuk sejumlah iterasi dan kemudian membuat pemblokiran syscall ke dalam kernel untuk deschedule utas menunggu. Dalam tolok ukur itu adalah pemain terburuk dan saya tidak dapat menemukan cara untuk membuatnya berkinerja lebih baik, dan itulah alasannya tidak termasuk dalam tolok ukur.
Pada Intel CPU, seseorang dapat menggunakan register kontrol Debug untuk memantau wilayah memori spinlock untuk akses menulis dan menunggu menggunakannya select (dan teman -temannya) atau sigwait (lihat perf_event_open dan uapi/linux/hw_breakpoint.h untuk lebih jelasnya). Seorang pelayan spinlock dapat menangguhkan dirinya dengan select atau sigwait sampai status spinlock telah diperbarui. Tetapi hanya ada 4 dari register ini, sehingga solusi seperti itu tidak akan skala.
Lihat grafik throughput dan latensi tolok ukur.
Ada beberapa perilaku OS yang menyulitkan pembandingan:
SCHED_FIFO real-time 50 digunakan untuk menonaktifkan waktu penjadwal kuantum kuantum dan membuat utas tidak dapat diselesaikan oleh proses/utas prioritas yang lebih rendah.benchmarks yang dapat dieksekusi dijalankan setidaknya 33 kali. Bagan tolok ukur menampilkan nilai rata -rata. Bagan Tooltip juga menampilkan nilai deviasi standar, minimum dan maksimum. Kinerja benchmark antrian produser-single-konsumen boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue dan antrian ini dalam mode konsumen-single-produser tunggal harus identik karena mereka menerapkan algoritma yang sama persis dengan menggunakan instruksi atom yang sama dan instruksi yang sama. boost::lockfree::spsc_queue Implementasi yang dibandingkan pada waktu itu tidak memiliki optimisasi untuk meminimalkan pertengkaran cache L1D, kesalahan prediksi cabang dingin atau kios pipa dari masalah yang lebih halus yang hanya dapat diperhatikan dalam kode perakitan yang dihasilkan.
Saya hanya memiliki akses ke beberapa mesin x86-64. Jika Anda memiliki akses ke perangkat keras yang berbeda, jangan ragu untuk mengirimkan file output scripts/run-benchmarks.sh dan saya akan memasukkan hasil Anda ke halaman tolok ukur.
Ketika halaman besar tersedia, tolok ukur menggunakan 1x1gb atau 16x2mb halaman besar untuk antrian untuk meminimalkan kesalahan TLB. Untuk memungkinkan halaman besar melakukan salah satu dari:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
Atau, Anda mungkin ingin mengaktifkan HugEpage transparan dalam sistem Anda dan menggunakan pengalokasi yang sadar HugePage, seperti TCMALLOC.
Secara default, penjadwal Linux mencekik utas waktu-nyata dari mengkonsumsi 100% CPU dan itu merugikan pembandingan. Detail lengkap dapat ditemukan dalam penjadwalan grup real-time. Untuk menonaktifkan thread throttling real-time do:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
N Thread produser mendorong bilangan bulat 4-byte ke dalam satu antrian yang sama, n Thread konsumen meletuskan bilangan bulat dari antrian. Semua produsen memposting total 1.000.000 pesan. Total waktu untuk mengirim dan menerima semua pesan diukur. Benchmark dijalankan untuk dari 1 produsen dan 1 konsumen hingga (total-number-of-cpus / 2) produsen / konsumen untuk mengukur skalabilitas antrian yang berbeda.
Satu utas memposting bilangan bulat ke utas lain melalui satu antrian dan menunggu balasan dari antrian lain (total 2 antrian). Benchmark mengukur total waktu 100.000 ping-pong, terbaik dari 10 berjalan. Pendapat minimal di sini (1-produser-1-konsumen, 1 elemen dalam antrian) untuk dapat mencapai dan mengukur latensi terendah. Melaporkan rata-rata waktu pulang pergi.
Kontribusi lebih dari diterima. .editorconfig dan .clang-format dapat digunakan untuk secara otomatis mencocokkan pemformatan kode.
Beberapa buku tentang masalah pemrograman multi-utas yang menurut saya cukup instruktif:
Hak Cipta (C) 2019 Maxim Egorushkin. Lisensi MIT. Lihat lisensi lengkap dalam lisensi file.
