Uses cdsstree framework in folly sequential queue test cases
[folly.git] / folly / stress-test / stress-sequential-folly-queue.cpp
1 #include "queue_test.h"
2
3 namespace folly_test {
4
5 class FollyQueueEnqueueDequeueTest_Sequential
6     : public cds_test::stress_fixture {
7 protected:
8   // Unbounded queue
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;
14
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;
22
23   // AtomicLinkedList
24   static size_t s_nAtomicLinkedListSize;
25   static size_t s_nAtomicLinkedListPassCount;
26
27   // MPMC Queue (linearizable)
28   static size_t s_nMPMCQueueEnqueueStride;
29   static size_t s_nMPMCQueueCapacity;
30   static size_t s_nMPMCQueueEnqueueCount;
31
32   static void SetUpTestCase() {
33     const cds_test::config &cfg = get_config("SequentialFollyQueue");
34     // Unbounded queue
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);
47     // AtomicLinkedList
48     GetConfigNonZeroExpected(AtomicLinkedListSize, 50000);
49     GetConfigNonZeroExpected(AtomicLinkedListPassCount, 10000);
50     // MPMC Queue (linearizable)
51     GetConfigNonZeroExpected(MPMCQueueEnqueueStride, 10000);
52     GetConfigNonZeroExpected(MPMCQueueCapacity, 50000);
53     GetConfigNonZeroExpected(MPMCQueueEnqueueCount, 500000000);
54   }
55
56   static void run_atomic_linkedlist() {
57     for (size_t pass = 0; pass < s_nAtomicLinkedListPassCount; pass++) {
58       std::unique_ptr<AtomicLinkedList> list(new AtomicLinkedList());
59       bool in_order = true;
60       for (size_t i = 0; i < s_nAtomicLinkedListSize; i++) {
61         list->insertHead(i);
62       }
63       size_t nSum = 0;
64       auto func = [&nSum](size_t elem) { nSum += elem; };
65       if (in_order) {
66         list->sweep(func);
67       } else {
68         list->reverseSweep(func);
69       }
70       in_order = !in_order;
71
72       size_t supposed_sum =
73           s_nAtomicLinkedListSize * (s_nAtomicLinkedListSize - 1) / 2;
74       EXPECT_EQ(nSum, supposed_sum);
75     }
76   }
77
78   template <typename Queue>
79   static void run_queue(Queue *q, size_t enqueue_count, size_t enqueue_stride) {
80     size_t nNo = 0;
81     size_t pop_sum = 0;
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++) {
85         q->enqueue(nNo++);
86       }
87       size_t res;
88       for (size_t i = 0; i < curr_push_count; i++) {
89         q->dequeue(res);
90         pop_sum += res;
91       }
92     }
93     size_t supposed_sum = enqueue_count * (enqueue_count - 1) / 2;
94     EXPECT_EQ(pop_sum, supposed_sum);
95   }
96
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);
102   }
103
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);
110   }
111 };
112
113 // MPMC Specialization.
114 template <>
115 void FollyQueueEnqueueDequeueTest_Sequential::run_queue(MPMCQueue *q,
116                                                         size_t enqueue_count,
117                                                         size_t enqueue_stride) {
118   size_t nNo = 0;
119   size_t push_sum = 0;
120   size_t pop_sum = 0;
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++) {
124       if (q->write(nNo)) {
125         push_sum += nNo;
126         nNo++;
127       }
128     }
129     size_t res;
130     while (q->read(res)) {
131       pop_sum += res;
132     }
133   }
134
135   size_t supposed_sum = enqueue_count * (enqueue_count - 1) / 2;
136   EXPECT_EQ(pop_sum, supposed_sum);
137 }
138
139 // Unbounded queue
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;
153 // AtomicLinkedList
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;
160
161 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyMPMCQueue) {
162   run_with_initial_capacity<MPMCQueue>(s_nMPMCQueueCapacity,
163                                        s_nMPMCQueueEnqueueCount,
164                                        s_nMPMCQueueEnqueueStride);
165 }
166
167 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyAtomicLinkedList) {
168   run_atomic_linkedlist();
169 }
170
171 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_SPSC) {
172   run_without_initial_capacity<USPSCQueue>(s_nUSPSCQueueEnqueueCount,
173                                            s_nUnboundedQueueEnqueueStride);
174 }
175
176 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_MPSC) {
177   run_without_initial_capacity<UMPSCQueue>(s_nUMPSCQueueEnqueueCount,
178                                            s_nUnboundedQueueEnqueueStride);
179 }
180
181 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_SPMC) {
182   run_without_initial_capacity<USPMCQueue>(s_nUSPMCQueueEnqueueCount,
183                                            s_nUnboundedQueueEnqueueStride);
184 }
185
186 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyUnboundedQueue_MPMC) {
187   run_without_initial_capacity<UMPMCQueue>(s_nUMPMCQueueEnqueueCount,
188                                            s_nUnboundedQueueEnqueueStride);
189 }
190
191 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_SPSC) {
192   // DynamicBoundedQueue
193   run_with_initial_capacity<DSPSCQueue>(s_nDynamicBoundedQueueCapacity,
194                                         s_nDSPSCQueueEnqueueCount,
195                                         s_nDynamicBoundedQueueEnqueueStride);
196 }
197
198 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_MPSC) {
199   run_with_initial_capacity<DMPSCQueue>(s_nDynamicBoundedQueueCapacity,
200                                         s_nDMPSCQueueEnqueueCount,
201                                         s_nDynamicBoundedQueueEnqueueStride);
202 }
203
204 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_SPMC) {
205   run_with_initial_capacity<DSPMCQueue>(s_nDynamicBoundedQueueCapacity,
206                                         s_nDSPMCQueueEnqueueCount,
207                                         s_nDynamicBoundedQueueEnqueueStride);
208 }
209
210 TEST_F(FollyQueueEnqueueDequeueTest_Sequential, FollyDynamicBoundedQueue_MPMC) {
211   run_with_initial_capacity<DMPMCQueue>(s_nDynamicBoundedQueueCapacity,
212                                         s_nDMPMCQueueEnqueueCount,
213                                         s_nDynamicBoundedQueueEnqueueStride);
214 }
215
216 } // namespace folly_test