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();
ถอนคิวรายการแรกของคิว คุณต้องแน่ใจว่าคิวไม่ว่างเปล่าก่อนที่จะเรียกป๊อป ซึ่งหมายความว่า front() จะต้องส่งคืน non- nullptr ก่อนที่จะเรียก pop() แต่ละครั้ง ต้องใช้ std::is_nothrow_destructible<T>::value == true
size_t size();
ส่งกลับจำนวนรายการที่มีอยู่ในคิว
bool empty();
คืนค่าเป็นจริงหากคิวว่างในขณะนี้
มีเพียงเธรดตัวเขียนเดียวเท่านั้นที่สามารถดำเนินการจัดคิวได้ และมีเพียงเธรดตัวอ่านเดียวเท่านั้นที่สามารถดำเนินการยกเลิกคิวได้ การใช้งานอื่นใดไม่ถูกต้อง
นอกเหนือจากการสนับสนุนการจัดสรรแบบกำหนดเองผ่านอินเทอร์เฟซตัวจัดสรรแบบกำหนดเองมาตรฐาน ไลบรารีนี้ยังสนับสนุนข้อเสนอมาตรฐาน 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)); }
}; ดู src/SPSCQueueExampleHugepages.cpp สำหรับตัวอย่างเต็มเกี่ยวกับวิธีใช้เพจขนาดใหญ่บน Linux
การใช้งานพื้นฐานจะขึ้นอยู่กับบัฟเฟอร์วงแหวน
เราได้ใช้ความระมัดระวังเพื่อหลีกเลี่ยงปัญหาใดๆ เกี่ยวกับการแบ่งปันที่ผิดพลาด ดัชนีหัวและส่วนท้ายถูกจัดตำแหน่งและบุนวมให้กับช่วงการแบ่งปันที่ผิดพลาด (ขนาดเส้นแคช) นอกจากนี้ บัฟเฟอร์สล็อตยังเสริมด้วยช่วงการแบ่งปันที่ผิดพลาดที่จุดเริ่มต้นและสิ้นสุด ซึ่งจะช่วยป้องกันการแชร์ที่ผิดพลาดกับการจัดสรรที่อยู่ติดกัน
การใช้งานนี้มีปริมาณงานสูงกว่าบัฟเฟอร์วงแหวนที่เกิดขึ้นพร้อมกันโดยทั่วไปโดยการแคชดัชนีส่วนหัวและส่วนท้ายในเครื่องเขียนและเครื่องอ่านตามลำดับ การแคชจะเพิ่มปริมาณงานโดยการลดปริมาณการรับส่งข้อมูลการเชื่อมโยงกันของแคช
เพื่อทำความเข้าใจวิธีการทำงาน ขั้นแรกให้พิจารณาการดำเนินการอ่านโดยไม่มีการแคช: ดัชนีส่วนหัว (ดัชนีการอ่าน) จำเป็นต้องได้รับการอัปเดต และด้วยเหตุนี้ บรรทัดแคชจึงถูกโหลดลงในแคช L1 ในสถานะพิเศษ จำเป็นต้องอ่านส่วนท้าย (ดัชนีการเขียน) เพื่อตรวจสอบว่าคิวไม่ว่างเปล่าและโหลดลงในแคช L1 ในสถานะที่ใช้ร่วมกัน เนื่องจากการดำเนินการเขียนคิวจำเป็นต้องอ่านดัชนีส่วนหัว จึงเป็นไปได้ว่าการดำเนินการเขียนจำเป็นต้องมีการรับส่งข้อมูลการเชื่อมโยงกันของแคชเพื่อนำบรรทัดแคชของดัชนีส่วนหัวกลับเข้าสู่สถานะพิเศษ ในกรณีที่เลวร้ายที่สุด จะมีการเปลี่ยนบรรทัดแคชหนึ่งครั้งจากการแบ่งใช้เป็นแบบเอกสิทธิ์เฉพาะบุคคลสำหรับการดำเนินการอ่านและเขียนทุกครั้ง
ถัดไป ให้พิจารณาตัวอ่านคิวที่แคชดัชนีส่วนท้าย: หากดัชนีส่วนท้ายที่แคชระบุว่าคิวว่างเปล่า ให้โหลดดัชนีส่วนท้ายลงในดัชนีส่วนท้ายที่แคชไว้ หากคิวไม่ว่างเปล่า การดำเนินการอ่านหลายครั้งจนกระทั่งดัชนีส่วนท้ายที่แคชไว้สามารถดำเนินการให้เสร็จสิ้นโดยไม่ขโมยสถานะพิเศษของบรรทัดแคชดัชนีส่วนท้ายของผู้เขียน ดังนั้นการรับส่งข้อมูลการเชื่อมโยงกันของแคชจึงลดลง อาร์กิวเมนต์ที่คล้ายคลึงกันสามารถสร้างขึ้นสำหรับการดำเนินการเขียนคิว
การใช้งานนี้อนุญาตให้ใช้ความจุสองความจุได้โดยพลการ โดยแทนที่จะจัดสรรสล็อตคิวเพิ่มเติมเพื่อระบุคิวเต็ม หากคุณไม่ต้องการเสียพื้นที่จัดเก็บสำหรับช่องคิวเพิ่มเติม คุณควรใช้วิธีอื่น
อ้างอิง:
การทดสอบอัลกอริธึมที่ไม่มีการล็อคเป็นเรื่องยาก ฉันใช้สองวิธีในการทดสอบการใช้งาน:
เกณฑ์มาตรฐานปริมาณงานจะวัดปริมาณงานระหว่าง 2 เธรดสำหรับคิวของรายการ int
เกณฑ์มาตรฐานเวลาในการตอบสนองจะวัดเวลาไปกลับระหว่าง 2 เธรดที่สื่อสารโดยใช้รายการ int 2 คิว
ผลลัพธ์เกณฑ์มาตรฐานสำหรับโปรเซสเซอร์ AMD Ryzen 9 3900X 12-Core 2 เธรดทำงานบนคอร์ที่แตกต่างกันบนชิปเล็ตเดียวกัน:
| คิว | ปริมาณงาน (ops/ms) | เวลาแฝง RTT (ns) |
|---|---|---|
| SPSCคิว | 362723 | 133 |
| บูสต์::ล็อคฟรี::spsc | 209877 | 222 |
| ความเขลา::ProducerConsumerQueue | 148818 | 147 |
SPSCQueue ได้รับการอ้างถึงโดยเอกสารต่อไปนี้:
โปรเจ็กต์นี้สร้างโดย Erik Rigtorp <[email protected]>
