1 #include "queue_test.h"
5 class FollyQueueEnqueueDequeueTest_Sequential
6 : public cds_test::stress_fixture {
9 static size_t s_nUnboundedQueueEnqueueStride;
10 static size_t s_nUSPSCQueueEnqueueCount;
11 static size_t s_nUMPSCQueueEnqueueCount;
12 static size_t s_nUSPMCQueueEnqueueCount;
13 static size_t s_nUMPMCQueueEnqueueCount;
15 // Dynamic bounded queue
16 static size_t s_nDynamicBoundedQueueEnqueueStride;
17 static size_t s_nDynamicBoundedQueueCapacity;
18 static size_t s_nDSPSCQueueEnqueueCount;
19 static size_t s_nDMPSCQueueEnqueueCount;
20 static size_t s_nDSPMCQueueEnqueueCount;
21 static size_t s_nDMPMCQueueEnqueueCount;
24 static size_t s_nAtomicLinkedListSize;
25 static size_t s_nAtomicLinkedListPassCount;
27 // MPMC Queue (linearizable)
28 static size_t s_nMPMCQueueEnqueueStride;
29 static size_t s_nMPMCQueueCapacity;
30 static size_t s_nMPMCQueueEnqueueCount;
32 static void SetUpTestCase() {
33 const cds_test::config &cfg = get_config("SequentialFollyQueue");
35 GetConfigNonZeroExpected(UnboundedQueueEnqueueStride, 10000);
36 GetConfigNonZeroExpected(USPSCQueueEnqueueCount, 1200000000);
37 GetConfigNonZeroExpected(UMPSCQueueEnqueueCount, 320000000);
38 GetConfigNonZeroExpected(USPMCQueueEnqueueCount, 320000000);
39 GetConfigNonZeroExpected(UMPMCQueueEnqueueCount, 320000000);
40 // Dynamic bounded queue
41 GetConfigNonZeroExpected(DynamicBoundedQueueEnqueueStride, 50000);
42 GetConfigNonZeroExpected(DynamicBoundedQueueCapacity, 200000);
43 GetConfigNonZeroExpected(DSPSCQueueEnqueueCount, 1200000000);
44 GetConfigNonZeroExpected(DMPSCQueueEnqueueCount, 320000000);
45 GetConfigNonZeroExpected(DSPMCQueueEnqueueCount, 320000000);
46 GetConfigNonZeroExpected(DMPMCQueueEnqueueCount, 320000000);
48 GetConfigNonZeroExpected(AtomicLinkedListSize, 50000);
49 GetConfigNonZeroExpected(AtomicLinkedListPassCount, 10000);
50 // MPMC Queue (linearizable)
51 GetConfigNonZeroExpected(MPMCQueueEnqueueStride, 10000);
52 GetConfigNonZeroExpected(MPMCQueueCapacity, 50000);
53 GetConfigNonZeroExpected(MPMCQueueEnqueueCount, 500000000);
56 static void run_atomic_linkedlist() {
57 for (size_t pass = 0; pass < s_nAtomicLinkedListPassCount; pass++) {
58 std::unique_ptr<AtomicLinkedList> list(new AtomicLinkedList());
60 for (size_t i = 0; i < s_nAtomicLinkedListSize; i++) {
64 auto func = [&nSum](size_t elem) { nSum += elem; };
68 list->reverseSweep(func);
73 s_nAtomicLinkedListSize * (s_nAtomicLinkedListSize - 1) / 2;
74 EXPECT_EQ(nSum, supposed_sum);
78 template <typename Queue>
79 static void run_queue(Queue *q, size_t enqueue_count, size_t enqueue_stride) {
82 while (nNo < enqueue_count) {
83 size_t curr_push_count = std::min(enqueue_count - nNo, enqueue_stride);
84 for (size_t i = 0; i < curr_push_count; i++) {
88 for (size_t i = 0; i < curr_push_count; i++) {
93 size_t supposed_sum = enqueue_count * (enqueue_count - 1) / 2;
94 EXPECT_EQ(pop_sum, supposed_sum);
97 template <typename Queue>
98 static void run_without_initial_capacity(size_t enqueue_count,
99 size_t enqueue_stride) {
100 std::unique_ptr<Queue> q(new Queue());
101 run_queue(q.get(), enqueue_count, enqueue_stride);
104 template <typename Queue>
105 static void run_with_initial_capacity(size_t queue_capacity,
106 size_t enqueue_count,
107 size_t enqueue_stride) {
108 std::unique_ptr<Queue> q(new Queue(queue_capacity));
109 run_queue(q.get(), enqueue_count, enqueue_stride);
113 // MPMC Specialization.
115 void FollyQueueEnqueueDequeueTest_Sequential::run_queue(MPMCQueue *q,
116 size_t enqueue_count,
117 size_t enqueue_stride) {
121 while (nNo < enqueue_count) {
122 size_t curr_push_count = std::min(enqueue_count - nNo, enqueue_stride);
123 for (size_t i = 0; i < curr_push_count; i++) {
130 while (q->read(res)) {
135 size_t supposed_sum = enqueue_count * (enqueue_count - 1) / 2;
136 EXPECT_EQ(pop_sum, supposed_sum);
140 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nUnboundedQueueEnqueueStride;
141 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nUSPSCQueueEnqueueCount;
142 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nUMPSCQueueEnqueueCount;
143 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nUSPMCQueueEnqueueCount;
144 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nUMPMCQueueEnqueueCount;
145 // Dynamic bounded queue
146 size_t FollyQueueEnqueueDequeueTest_Sequential::
147 s_nDynamicBoundedQueueEnqueueStride;
148 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nDynamicBoundedQueueCapacity;
149 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nDSPSCQueueEnqueueCount;
150 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nDMPSCQueueEnqueueCount;
151 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nDSPMCQueueEnqueueCount;
152 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nDMPMCQueueEnqueueCount;
154 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nAtomicLinkedListSize;
155 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nAtomicLinkedListPassCount;
156 // MPMC Queue (linearizable)
157 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nMPMCQueueEnqueueStride;
158 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nMPMCQueueCapacity;
159 size_t FollyQueueEnqueueDequeueTest_Sequential::s_nMPMCQueueEnqueueCount;
161 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyMPMCQueue) {
162 run_with_initial_capacity<MPMCQueue>(s_nMPMCQueueCapacity,
163 s_nMPMCQueueEnqueueCount,
164 s_nMPMCQueueEnqueueStride);
167 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyAtomicLinkedList) {
168 run_atomic_linkedlist();
171 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_SPSC) {
172 run_without_initial_capacity<USPSCQueue>(s_nUSPSCQueueEnqueueCount,
173 s_nUnboundedQueueEnqueueStride);
176 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_MPSC) {
177 run_without_initial_capacity<UMPSCQueue>(s_nUMPSCQueueEnqueueCount,
178 s_nUnboundedQueueEnqueueStride);
181 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_SPMC) {
182 run_without_initial_capacity<USPMCQueue>(s_nUSPMCQueueEnqueueCount,
183 s_nUnboundedQueueEnqueueStride);
186 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_MPMC) {
187 run_without_initial_capacity<UMPMCQueue>(s_nUMPMCQueueEnqueueCount,
188 s_nUnboundedQueueEnqueueStride);
191 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_SPSC) {
192 // DynamicBoundedQueue
193 run_with_initial_capacity<DSPSCQueue>(s_nDynamicBoundedQueueCapacity,
194 s_nDSPSCQueueEnqueueCount,
195 s_nDynamicBoundedQueueEnqueueStride);
198 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_MPSC) {
199 run_with_initial_capacity<DMPSCQueue>(s_nDynamicBoundedQueueCapacity,
200 s_nDMPSCQueueEnqueueCount,
201 s_nDynamicBoundedQueueEnqueueStride);
204 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_SPMC) {
205 run_with_initial_capacity<DSPMCQueue>(s_nDynamicBoundedQueueCapacity,
206 s_nDSPMCQueueEnqueueCount,
207 s_nDynamicBoundedQueueEnqueueStride);
210 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_MPMC) {
211 run_with_initial_capacity<DMPMCQueue>(s_nDynamicBoundedQueueCapacity,
212 s_nDMPMCQueueEnqueueCount,
213 s_nDynamicBoundedQueueEnqueueStride);
216 } // namespace folly_test