atomic_queue
1.0.0
C ++ 14基於圓形緩衝液和std::atomic多生產者 - 消費者鎖定隊的無鎖隊列。
設計的目標是最大程度地減少一個線程之間的延遲，將元素推入隊列和另一個線程從隊列中彈出。
它已在Linux上開發，測試和基準測試，但應支持實現std::atomic任何C ++ 14個平台。報告稱與Windows兼容，但是GitHub託管的連續集成僅適用於Ubuntu-20.04和Ubuntu-22.04上的X86_64平台。歡迎拉動請求擴展連續集成以在其他體系結構和/或平台上運行。
當最小化延遲時，良好的設計不是當沒有剩下的添加時，而是在沒有剩下的刪除時，這些隊列的例證。
最小化延遲自然可以最大化吞吐量。在理想的數學和實用工程意義上，低延遲倒數是高度的高位。低潛伏期與任何延遲和/或批處理都不兼容，這些延遲和/或批處理破壞了原始（硬件）全球事件的全局時間順序，這些事件被不同的線程推入一個隊列。另一方面，可以通過延遲和分批多個更新來以延遲延遲來最大化吞吐量。
這些隊列遵循的主要設計原則是極簡主義，這導致了這樣的設計選擇：
push / pop上進行副本/移動，因此無法獲得隊列中的元素的引用/指針。這些小型設計選擇對自己的影響幾乎是無法衡量的，但是它們的總影響要大得多，遠遠超過了成分影響的簡單總和，也就是超級量表複合或協同作用。從將這些小型設計選擇組合在一起的多個將CPU在最小阻礙的峰值容量下進行的協同作用。
這些設計選擇也是局限性：
超低延遲應用需要僅需要，僅此而已。極簡主義的回報，請參閱吞吐量和延遲基準。
其他幾個已建立良好且流行的線程安全容器也用於基準中的參考：
std::mutex帶有std::mutex固定尺寸擋板。pthread_spinlock帶有pthread_spinlock_t的固定尺寸擋板。boost::lockfree::spsc_queue BOOST Library的無候補單生產者單生成隊列隊列。boost::lockfree::queue - BOOST庫中的無鎖多生產商 - 元製造商隊列。moodycamel::ConcurrentQueue無鎖的多生產者 - 消費者隊列在非阻滯模式下使用。該隊列旨在以延遲為代價，並避免通過不同線程推入一個隊列的全局時間順序以最大化的吞吐量。它不等於在這方面基準的其他隊列。moodycamel::ReaderWriterQueue無鎖的單生產者單架 - 消費者隊列，用於非阻止模式。xenium::michael_scott_queue Michael和Scott提出的無鎖的多生產商 - 消費者隊列（此隊列類似於boost::lockfree::queue ，這也基於同一建議）。xenium::ramalhete_queue Ramalheete和Correia提出的無鎖的多生產者 - 消費者隊列。xenium::vyukov_bounded_queue基於Vyukov提出的版本，有限的多生產商 - 消費者隊列。tbb::spin_mutex鎖定的固定尺寸彈跳器，帶有tbb::spin_mutex來自英特爾螺紋構建塊。tbb::concurrent_bounded_queue來自英特爾螺紋構建塊的非阻滯模式下使用的同名隊列。所提供的容器是僅標題類模板，無需建造/安裝。
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include目錄（使用完整路徑）到構建系統的包含路徑。#include <atomic_queue/atomic_queue.h>在您的C ++源中。 vcpkg install atomic-queue
請關注官方教程，以了解如何消費柯南包裹。該庫的特定詳細信息可在Conancenter中找到。
所提供的容器是僅需要#include <atomic_queue/atomic_queue.h>僅限類模板，無需建造/安裝。
建築物對於運行測試和基準是必要的。
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
基準還需要Intel TBB庫可用。它假設它安裝在/usr/local/include和/usr/local/lib中。如果在其他地方安裝了它，則可能需要在Makefile中修改cppflags.tbb和ldlibs.tbb 。
AtomicQueue原子元素的固定尺寸彈跳器。OptimistAtomicQueue一種更快的固定尺寸環形緩衝器，適用於原子元素，在空或滿時繁忙等待。它是AtomicQueue ，與push / pop一起使用，而不是try_push / try_pop 。AtomicQueue2非原子元件的固定尺寸擋板。OptimistAtomicQueue2更快的固定尺寸擋板彈鍋，用於非原子元素，在空或滿時忙碌的等待。它是AtomicQueue2 ，用於push / pop而不是try_push / try_pop 。這些容器具有相應的AtomicQueueB ， OptimistAtomicQueueB ， AtomicQueueB2 ， OptimistAtomicQueueB2版本，其中緩衝區大小被指定為構造函數的參數。
支持完全有序模式。在這種模式下，消費者以相同的FIFO順序接收消息。支持此模式以用於push和pop功能，而不是try_版本。截至2019年，在英特爾X86上，完全有序的模式為0。
支持單生產者單個消費者模式。在這種模式下，不需要昂貴的原子讀取 - 修飾 - 定量 - 僅需說明，只有最便宜的原子負載和商店。這可以顯著改善隊列吞吐量。
完全支持僅移動隊列元素類型。例如， std::unique_ptr<T>元素的隊列將是AtomicQueue2B<std::unique_ptr<T>>或AtomicQueue2<std::unique_ptr<T>, CAPACITY> 。
隊列類模板提供以下成員功能：
try_push將元素附加到隊列的末尾。隊列已滿時返回false 。try_pop從隊列的正面刪除元素。隊列為空時返回false 。push （樂觀主義者） - 將元素附加到隊列的末端。隊列已滿時忙著等待。當隊列不滿時，比try_push快。可選的FIFO生產商排隊和總訂單。pop （樂觀主義者） - 從隊列的正面刪除元素。隊列為空時忙著等待。當隊列不為空時，比try_pop快。可選的FIFO消費者排隊和總訂單。was_size返回通話過程中無需耗盡元素的數量。在檢查返回值時，狀態可能已經改變。was_empty如果容器在通話過程中為空，則返回true 。在檢查返回值時，狀態可能已經改變。was_full如果在通話過程中該容器已滿，則返回true 。在檢查返回值時，狀態可能已經改變。capacity - 返回隊列可能保留的最大元素數量。原子元素是std::atomic<T>{T{}}.is_lock_free()返回true ，當C ++ 17功能可用時， std::atomic<T>::is_always_lock_free在編譯時為true評估。換句話說，CPU可以在本地原子上加載，存儲和分解此類元素。在x86-64上，此類元素都是C ++標準算術和指針類型。
原子元素的隊列保留一個值作為空元素NIL ，其默認值為0 。無需將NIL值推入隊列，並且在push功能中有一個assert語句，以防止在調試模式構建中。將NIL元素推入釋放模式的隊列會導致不確定的行為，例如死鎖和/或丟失的隊列元素。
請注意，樂觀是隊列修改操作控制流的選擇，而不是隊列類型。當隊列在大多數情況下不滿時，樂觀主義者的push是最快的，這是一個樂觀的pop - 當隊列在大多數情況下不是空的時。樂觀的和不限制的操作可以混合在一起。基準中的OptimistAtomicQueue S僅使用Opperist push和pop 。
有關用法示例，請參見示例。
push and try_push操作與同一隊列對象的任何後續pop或try_pop操作同步（如std::memory_order中定義）。意思是：
push / try_push ，這是memory_order::release操作。與std::mutex::unlock相同的內存順序。pop / try_pop之前，沒有非原子負載 /存儲會重新排序，這是memory_order::acquire操作。與std::mutex::lock的內存順序相同。push / try_push插入隊列中，在消費者的線程中可見，該線程pop / try_pop pop / try_pop該特定元素。 這裡可用的隊列使用彈跳器陣列來存儲元素。隊列的容量在編譯時間或施工時間固定。
在生產多生產商 - 消費者場景中，應設置為最大預期隊列大小。當彈跳器變滿時，這意味著消費者無法足夠快地消耗元素。解決此問題的方法是：
push and pop呼叫總是會引起一些昂貴的CPU週期，以保持隊列狀態以原子/一致/隔離的方式相對於其他線程的完整性，並且隨著隊列競爭的增長，這些成本會超級線性增加。一個事件導致的多個小元素或一個隊列消息的生產者批處理通常是一個合理的解決方案。使用-2環形緩衝陣列尺寸可以進行幾個重要的優化：
% SIZE ，作者和讀者索引被映射到彈跳器陣列索引中。剩餘的二進制運算符%通常會生成不便宜的Division CPU指令，但是使用2殺劑大小的轉換，其餘操作員變成了一項便宜的二進制and CPU指令，並且它的速度也很快。M消費者一起在同一環形緩存線路中的隨後元素競爭的N競爭中，它只是一個與一個消費者競爭的生產者（當CPU的數量不超過可以適合一個緩存線的元素數量時）。這種優化隨生產者和消費者的數量以及元素大小而縮放得更好。由於生產者和消費者數量少（這些基準中的每個基準中最多2個）可能會產生更好的吞吐量（但跨行動的差異更高）。容器使用unsigned類型用於大小和內部索引。在X86-64上， unsigned平台為32位寬，而size_t為64位寬。 64位指令使用額外的字節說明前綴，從而對CPU指令緩存和前端產生更大的壓力。因此，使用32位unsigned索引來最大化性能。這將隊列大小限制為4,294,967,295個元素，對於許多應用來說，這似乎是一個合理的硬限制。
雖然可以將原子隊列與任何可移動元素類型（包括std::unique_ptr ）一起使用，但為了獲得最佳吞吐量和延遲，隊列元素應該便宜地複制和鎖定（例如unsigned或T* ），以便push和pop操作完全最快。
從概念上講， push或pop操作執行了兩個原子步驟：
head索引，消費者會增加tail索引。每個插槽僅由一個生產商和一個消費者線程訪問。NIL ，從一個老虎機加載的消費者加載會改變其狀態為NIL 。該插槽是其一個生產商和一個消費者線程的自旋鎖。這些隊列預計進行push或pop線程可能會完成步驟1，然後在完成步驟2之前先搶占。
如果保證在系統範圍內有保證的情況下，則無鎖。這些隊列通過以下屬性確保系統範圍的進展：
push都獨立於任何前面的push 。一個生產者線程不完整的（先發製人） push不會影響任何其他線程的push 。pop都獨立於任何前面的pop 。一個消費者線程不完整的（預先搶占） pop不會影響任何其他線程的pop 。push只會影響一個消費者線程，從這個特定的隊列插槽中pop一個元素。所有其他pop均不受影響。pop只會影響一個生產者線程，將一個元素push入這個特定的隊列插槽，同時期望它很久以前就消耗了，而在生產商不太可能將整個消費者包裹在整個消費者pop的情況下，該消費者卻沒有完成。所有其他線程push s和pop s均未受到影響。 Linux任務調度程序線程搶占性是用戶空間過程不應影響或逃脫的東西，否則任何/每個惡意應用程序都會利用這一點。
儘管如此，人們仍然可以做一些事情來最大程度地減少對任務關鍵應用程序的搶先攻擊：
SCHED_FIFO調度類用於線程，例如chrt --fifo 50 <app> 。較高的優先級SCHED_FIFO線程或內核中斷處理程序仍然可以搶占您的SCHED_FIFO線程。SCHED_OTHER違反了使用這些隊列的目的。SCHED_FIFO實時線程被限制。taskset集的這些孤立核心應明確放置任務關鍵應用程序。人們經常提出限制忙碌的待辦事，然後隨後呼叫std::this_thread::yield() / sched_yield / pthread_yield 。但是， sched_yield是一個錯誤的鎖定工具，因為它不會與OS內核通信該線程在等待的內容，因此OS線程調度程序永遠無法在共享狀態發生更改的正確時間安排調用線程（除非沒有其他可以在此CPU核心上運行的線程，否則該線程立即恢復了Caller）。有關更多詳細信息，請參見man sched_yield中的註釋部分和有關sched_yield和Spinlock的Linux內核線程。
在Linux中，有Mutex類型的PTHREAD_MUTEX_ADAPTIVE_NP ，它忙於等待鎖定的靜音，以進行許多迭代，然後將SYSCALL封鎖到內核中以取消等待線程。在基準測試中，這是表現最差的人，我找不到使其表現更好的方法，這就是它不包括在基準中的原因。
在英特爾CPU上，可以使用4個調試控制寄存器來監視Spinlock內存區域以進行寫入訪問並使用select （及其朋友）或sigwait等待（請參閱perf_event_open和uapi/linux/hw_breakpoint.h有關更多詳細信息）。 Spinlock服務員可以使用select或sigwait暫停自己，直到Spinlock狀態更新為止。但是只有4個寄存器，因此這樣的解決方案不會擴展。
查看吞吐量和延遲基準圖表。
有一些操作系統行為使基準測試複雜化：
SCHED_FIFO Priority 50用於禁用調度程序時間量子到期，並使線程通過較低的優先級過程/線程不可奪回。benchmarks的效果至少運行33次。基準圖表顯示平均值。圖表工具提示還顯示標準偏差，最小值和最大值。單生產者單圈隊的基準性能boost::lockfree::spsc_queue ， moodycamel::ReaderWriterQueue和這些隊列在單生產者單個消費者模式下應該是相同的，因為它們使用完全相同的算法實現了完全相同的算法。 boost::lockfree::spsc_queue實現當時的基準測試沒有優化可最大程度地減少L1D高速緩存的爭論，Cold Branch錯誤預測或從插圖碼中明顯的小說中的問題。
我只能訪問幾台X86-64機器。如果您可以訪問其他硬件，請隨時提交scripts/run-benchmarks.sh的輸出文件。
當有大量頁面可用時，基準測試使用1x1GB或16x2MB的巨大頁面以使排隊最大程度地減少TLB失誤。為了使大型頁面做一個：
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
另外，您可能希望在系統中啟用透明的大型頁面，並使用大型意見分配器，例如TCMALLOC。
默認情況下，Linux調度程序會從消耗100％CPU的實時線程中，這對基準測試有害。完整的詳細信息可以在實時組計劃中找到。禁用實時線程節流：
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
n生產商線程將4字節整數推入一個同一隊列，n消費者線程從隊列中彈出整數。所有生產商總共發布了1,000,000條消息。總時間發送和接收所有消息。該基準的運行量是從1個生產商和1個消費者到(total-number-of-cpus / 2)生產商 /消費者的基準，以衡量不同隊列的可擴展性。
一個線程通過一個隊列將整數張貼到另一個線程，並等待另一個隊列的答复（總共2個隊列）。基準測量總時間為100,000次乒乓球，最好的10次運行。爭論在這裡很小（1-生產者1-消費者，隊列中的1個元素），能夠達到和測量最低的延遲。報告平均往返時間。
貢獻非常受歡迎。 .editorconfig和.clang-format可用於自動匹配代碼格式。
我發現一些有關多線程編程主題的書：我發現很有啟發性：
版權（C）2019 Maxim Egorushkin。麻省理工學院許可證。請參閱文件許可證中的完整許可證。
