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);
قم بإنشاء قائمة انتظار SPSCqueue تحتوي على عناصر من النوع T capacity السعة. يجب أن تكون السعة على الأقل 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();
Dequeue العنصر الأول من قائمة الانتظار. يجب عليك التأكد من أن قائمة الانتظار ليست فارغة قبل الاتصال بـ pop. هذا يعني أن front() يجب أن يكون قد أعاد قيمة غير nullptr قبل كل استدعاء لـ pop() . يتطلب std::is_nothrow_destructible<T>::value == true .
size_t size();
إرجاع عدد العناصر المتوفرة في قائمة الانتظار.
bool empty();
يُرجع صحيحًا إذا كانت قائمة الانتظار فارغة حاليًا.
يمكن لمؤشر ترابط كاتب واحد فقط تنفيذ عمليات قائمة الانتظار، ويمكن لمؤشر ترابط قارئ واحد فقط إجراء عمليات إلغاء الانتظار. وأي استخدام آخر غير صالح.
بالإضافة إلى دعم التخصيص المخصص من خلال واجهة المخصص المخصص القياسية، تدعم هذه المكتبة أيضًا الاقتراح القياسي P0401R3 الذي يوفر تعليقات الحجم في واجهة المخصص. يتيح ذلك الاستخدام المريح للصفحات الضخمة دون إضاعة أي مساحة مخصصة. يتم دعم استخدام تعليقات الحجم فقط عند تمكين C++ 17.
لا تتضمن المكتبة حاليًا مخصصًا ضخمًا للصفحات نظرًا لأن واجهات برمجة التطبيقات لتخصيص الصفحات الضخمة تعتمد على النظام الأساسي وتتعامل مع حجم الصفحة الضخم والوعي بـ 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)); }
}; راجع src/SPSCQueueExampleHugepages.cpp للحصول على المثال الكامل حول كيفية استخدام الصفحات الضخمة على Linux.
يعتمد التنفيذ الأساسي على المخزن المؤقت الحلقي.
لقد تم الحرص على التأكد من تجنب أي مشكلات تتعلق بالمشاركة الزائفة. تتم محاذاة مؤشرات الرأس والذيل ومبطنة بنطاق المشاركة الزائف (حجم سطر ذاكرة التخزين المؤقت). بالإضافة إلى ذلك، يتم تعبئة المخزن المؤقت للفتحات بنطاق المشاركة الزائفة في البداية والنهاية، مما يمنع المشاركة الزائفة مع أي عمليات تخصيص مجاورة.
يتمتع هذا التطبيق بإنتاجية أعلى من المخزن المؤقت الدائري المتزامن النموذجي عن طريق التخزين المؤقت محليًا لمؤشرات الرأس والذيل في الكاتب والقارئ على التوالي. يؤدي التخزين المؤقت إلى زيادة الإنتاجية عن طريق تقليل مقدار حركة مرور تماسك ذاكرة التخزين المؤقت.
لفهم كيفية عمل ذلك، فكر أولاً في عملية القراءة في غياب التخزين المؤقت: يجب تحديث فهرس الرأس (فهرس القراءة) وبالتالي يتم تحميل سطر ذاكرة التخزين المؤقت في ذاكرة التخزين المؤقت L1 في حالة حصرية. يجب قراءة الذيل (فهرس الكتابة) للتأكد من أن قائمة الانتظار ليست فارغة وبالتالي يتم تحميلها في ذاكرة التخزين المؤقت L1 في حالة مشتركة. نظرًا لأن عملية الكتابة في قائمة الانتظار تحتاج إلى قراءة فهرس الرأس، فمن المحتمل أن تتطلب عملية الكتابة بعض حركة مرور تماسك ذاكرة التخزين المؤقت لإعادة سطر ذاكرة التخزين المؤقت لفهرس الرأس إلى الحالة الحصرية. في أسوأ الحالات، سيكون هناك انتقال واحد لخط ذاكرة التخزين المؤقت من مشترك إلى حصري لكل عملية قراءة وكتابة.
بعد ذلك، فكر في قارئ قائمة الانتظار الذي يقوم بتخزين فهرس الذيل مؤقتًا: إذا كان الفهرس الذيل المخزن مؤقتًا يشير إلى أن قائمة الانتظار فارغة، فقم بتحميل فهرس الذيل في فهرس الذيل المخزن مؤقتًا. إذا كانت قائمة الانتظار عبارة عن عمليات قراءة متعددة غير فارغة حتى يمكن إكمال فهرس الذيل المخزن مؤقتًا دون سرقة الحالة الحصرية لخط ذاكرة التخزين المؤقت لفهرس الكاتب. وبالتالي يتم تقليل حركة مرور تماسك ذاكرة التخزين المؤقت. يمكن إجراء وسيطة مماثلة لعملية الكتابة في قائمة الانتظار.
يسمح هذا التنفيذ بعدم القدرة بشكل تعسفي على سعتين، وبدلاً من ذلك تخصيص فتحة قائمة انتظار إضافية للإشارة إلى قائمة الانتظار الكاملة. إذا كنت لا ترغب في إضاعة سعة التخزين لفتحة قائمة انتظار إضافية، فيجب عليك استخدام تطبيق مختلف.
مراجع:
من الصعب اختبار الخوارزميات الخالية من القفل. أنا أستخدم طريقتين لاختبار التنفيذ:
يقيس معيار الإنتاجية الإنتاجية بين خيطين لقائمة انتظار من العناصر int .
يقيس معيار زمن الوصول وقت الرحلة ذهابًا وإيابًا بين خيطين يتواصلان باستخدام طابورتين من عناصر int .
النتائج المعيارية لمعالج AMD Ryzen 9 3900X 12-Core، يعمل الخيطان على نواة مختلفة على نفس الشريحة الصغيرة:
| طابور | الإنتاجية (عمليات / مللي ثانية) | وقت الاستجابة RTT (ns) |
|---|---|---|
| SPSCQueue | 362723 | 133 |
| دفعة::lockfree::spsc | 209877 | 222 |
| حماقة::ProducerConsumerQueue | 148818 | 147 |
تم الاستشهاد بـ SPSCQueue في الأوراق التالية:
تم إنشاء هذا المشروع بواسطة إريك ريجتورب <[email protected]>.
