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