cxx11_runqueue.cpp
Go to the documentation of this file.
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2016 Dmitry Vyukov <dvyukov@google.com>
5 // Copyright (C) 2016 Benoit Steiner <benoit.steiner.goog@gmail.com>
6 //
7 // This Source Code Form is subject to the terms of the Mozilla
8 // Public License v. 2.0. If a copy of the MPL was not distributed
9 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10 
11 #define EIGEN_USE_THREADS
12 #include <cstdlib>
13 #include "main.h"
14 #include <Eigen/CXX11/ThreadPool>
15 
16 
17 // Visual studio doesn't implement a rand_r() function since its
18 // implementation of rand() is already thread safe
19 int rand_reentrant(unsigned int* s) {
20 #ifdef EIGEN_COMP_MSVC_STRICT
22  return rand();
23 #else
24  return rand_r(s);
25 #endif
26 }
27 
29 {
31  // Check empty state.
32  VERIFY(q.Empty());
33  VERIFY_IS_EQUAL(0u, q.Size());
34  VERIFY_IS_EQUAL(0, q.PopFront());
35  std::vector<int> stolen;
36  VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
37  VERIFY_IS_EQUAL(0u, stolen.size());
38  // Push one front, pop one front.
39  VERIFY_IS_EQUAL(0, q.PushFront(1));
40  VERIFY_IS_EQUAL(1u, q.Size());
41  VERIFY_IS_EQUAL(1, q.PopFront());
42  VERIFY_IS_EQUAL(0u, q.Size());
43  // Push front to overflow.
44  VERIFY_IS_EQUAL(0, q.PushFront(2));
45  VERIFY_IS_EQUAL(1u, q.Size());
46  VERIFY_IS_EQUAL(0, q.PushFront(3));
47  VERIFY_IS_EQUAL(2u, q.Size());
48  VERIFY_IS_EQUAL(0, q.PushFront(4));
49  VERIFY_IS_EQUAL(3u, q.Size());
50  VERIFY_IS_EQUAL(0, q.PushFront(5));
51  VERIFY_IS_EQUAL(4u, q.Size());
52  VERIFY_IS_EQUAL(6, q.PushFront(6));
53  VERIFY_IS_EQUAL(4u, q.Size());
54  VERIFY_IS_EQUAL(5, q.PopFront());
55  VERIFY_IS_EQUAL(3u, q.Size());
56  VERIFY_IS_EQUAL(4, q.PopFront());
57  VERIFY_IS_EQUAL(2u, q.Size());
58  VERIFY_IS_EQUAL(3, q.PopFront());
59  VERIFY_IS_EQUAL(1u, q.Size());
60  VERIFY_IS_EQUAL(2, q.PopFront());
61  VERIFY_IS_EQUAL(0u, q.Size());
62  VERIFY_IS_EQUAL(0, q.PopFront());
63  // Push one back, pop one back.
64  VERIFY_IS_EQUAL(0, q.PushBack(7));
65  VERIFY_IS_EQUAL(1u, q.Size());
66  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
67  VERIFY_IS_EQUAL(1u, stolen.size());
68  VERIFY_IS_EQUAL(7, stolen[0]);
69  VERIFY_IS_EQUAL(0u, q.Size());
70  stolen.clear();
71  // Push back to overflow.
72  VERIFY_IS_EQUAL(0, q.PushBack(8));
73  VERIFY_IS_EQUAL(1u, q.Size());
74  VERIFY_IS_EQUAL(0, q.PushBack(9));
75  VERIFY_IS_EQUAL(2u, q.Size());
76  VERIFY_IS_EQUAL(0, q.PushBack(10));
77  VERIFY_IS_EQUAL(3u, q.Size());
78  VERIFY_IS_EQUAL(0, q.PushBack(11));
79  VERIFY_IS_EQUAL(4u, q.Size());
80  VERIFY_IS_EQUAL(12, q.PushBack(12));
81  VERIFY_IS_EQUAL(4u, q.Size());
82  // Pop back in halves.
83  VERIFY_IS_EQUAL(2u, q.PopBackHalf(&stolen));
84  VERIFY_IS_EQUAL(2u, stolen.size());
85  VERIFY_IS_EQUAL(10, stolen[0]);
86  VERIFY_IS_EQUAL(11, stolen[1]);
87  VERIFY_IS_EQUAL(2u, q.Size());
88  stolen.clear();
89  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
90  VERIFY_IS_EQUAL(1u, stolen.size());
91  VERIFY_IS_EQUAL(9, stolen[0]);
92  VERIFY_IS_EQUAL(1u, q.Size());
93  stolen.clear();
94  VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
95  VERIFY_IS_EQUAL(1u, stolen.size());
96  VERIFY_IS_EQUAL(8, stolen[0]);
97  stolen.clear();
98  VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
99  VERIFY_IS_EQUAL(0u, stolen.size());
100  // Empty again.
101  VERIFY(q.Empty());
102  VERIFY_IS_EQUAL(0u, q.Size());
103  VERIFY_IS_EQUAL(0, q.PushFront(1));
104  VERIFY_IS_EQUAL(0, q.PushFront(2));
105  VERIFY_IS_EQUAL(0, q.PushFront(3));
106  VERIFY_IS_EQUAL(1, q.PopBack());
107  VERIFY_IS_EQUAL(2, q.PopBack());
108  VERIFY_IS_EQUAL(3, q.PopBack());
109  VERIFY(q.Empty());
110  VERIFY_IS_EQUAL(0u, q.Size());
111 }
112 
113 // Empty tests that the queue is not claimed to be empty when is is in fact not.
114 // Emptiness property is crucial part of thread pool blocking scheme,
115 // so we go to great effort to ensure this property. We create a queue with
116 // 1 element and then push 1 element (either front or back at random) and pop
117 // 1 element (either front or back at random). So queue always contains at least
118 // 1 element, but otherwise changes chaotically. Another thread constantly tests
119 // that the queue is not claimed to be empty.
121 {
123  q.PushFront(1);
124  std::atomic<bool> done(false);
125  std::thread mutator([&q, &done]() {
126  unsigned rnd = 0;
127  std::vector<int> stolen;
128  for (int i = 0; i < 1 << 18; i++) {
129  if (rand_reentrant(&rnd) % 2)
130  VERIFY_IS_EQUAL(0, q.PushFront(1));
131  else
132  VERIFY_IS_EQUAL(0, q.PushBack(1));
133  if (rand_reentrant(&rnd) % 2)
134  VERIFY_IS_EQUAL(1, q.PopFront());
135  else {
136  for (;;) {
137  if (q.PopBackHalf(&stolen) == 1) {
138  stolen.clear();
139  break;
140  }
141  VERIFY_IS_EQUAL(0u, stolen.size());
142  }
143  }
144  }
145  done = true;
146  });
147  while (!done) {
148  VERIFY(!q.Empty());
149  int size = q.Size();
150  VERIFY_GE(size, 1);
151  VERIFY_LE(size, 2);
152  }
153  VERIFY_IS_EQUAL(1, q.PopFront());
154  mutator.join();
155 }
156 
157 // Stress is a chaotic random test.
158 // One thread (owner) calls PushFront/PopFront, other threads call PushBack/
159 // PopBack. Ensure that we don't crash, deadlock, and all sanity checks pass.
161 {
162  static const int kEvents = 1 << 18;
164  std::atomic<int> total(0);
165  std::vector<std::unique_ptr<std::thread>> threads;
166  threads.emplace_back(new std::thread([&q, &total]() {
167  int sum = 0;
168  int pushed = 1;
169  int popped = 1;
170  while (pushed < kEvents || popped < kEvents) {
171  if (pushed < kEvents) {
172  if (q.PushFront(pushed) == 0) {
173  sum += pushed;
174  pushed++;
175  }
176  }
177  if (popped < kEvents) {
178  int v = q.PopFront();
179  if (v != 0) {
180  sum -= v;
181  popped++;
182  }
183  }
184  }
185  total += sum;
186  }));
187  for (int i = 0; i < 2; i++) {
188  threads.emplace_back(new std::thread([&q, &total]() {
189  int sum = 0;
190  for (int j = 1; j < kEvents; j++) {
191  if (q.PushBack(j) == 0) {
192  sum += j;
193  continue;
194  }
196  j--;
197  }
198  total += sum;
199  }));
200  threads.emplace_back(new std::thread([&q, &total]() {
201  int sum = 0;
202  std::vector<int> stolen;
203  for (int j = 1; j < kEvents;) {
204  if (q.PopBackHalf(&stolen) == 0) {
206  continue;
207  }
208  while (stolen.size() && j < kEvents) {
209  int v = stolen.back();
210  stolen.pop_back();
211  VERIFY_IS_NOT_EQUAL(v, 0);
212  sum += v;
213  j++;
214  }
215  }
216  while (stolen.size()) {
217  int v = stolen.back();
218  stolen.pop_back();
219  VERIFY_IS_NOT_EQUAL(v, 0);
220  while ((v = q.PushBack(v)) != 0) EIGEN_THREAD_YIELD();
221  }
222  total -= sum;
223  }));
224  }
225  for (size_t i = 0; i < threads.size(); i++) threads[i]->join();
226  VERIFY(q.Empty());
227  VERIFY(total.load() == 0);
228 }
229 
230 EIGEN_DECLARE_TEST(cxx11_runqueue)
231 {
235 }
Work PushBack(Work w)
Definition: RunQueue.h:84
#define VERIFY_IS_NOT_EQUAL(a, b)
Definition: main.h:387
void test_basic_runqueue()
#define CALL_SUBTEST_3(FUNC)
int rand_reentrant(unsigned int *s)
#define VERIFY_GE(a, b)
Definition: main.h:382
Work PopFront()
Definition: RunQueue.h:68
unsigned Size() const
Definition: RunQueue.h:150
Scalar Scalar int size
Definition: benchVecAdd.cpp:17
#define VERIFY_IS_EQUAL(a, b)
Definition: main.h:386
bool Empty() const
Definition: RunQueue.h:154
#define CALL_SUBTEST_1(FUNC)
Array< int, Dynamic, 1 > v
#define EIGEN_THREAD_YIELD()
Definition: ThreadYield.h:17
RealScalar s
EIGEN_DEVICE_FUNC const Scalar & q
#define VERIFY_LE(a, b)
Definition: main.h:383
void test_stress_runqueue()
Work PushFront(Work w)
Definition: RunQueue.h:53
#define VERIFY(a)
Definition: main.h:380
EIGEN_DECLARE_TEST(cxx11_runqueue)
unsigned PopBackHalf(std::vector< Work > *result)
Definition: RunQueue.h:117
#define CALL_SUBTEST_2(FUNC)
Work PopBack()
Definition: RunQueue.h:100
void test_empty_runqueue()
std::ptrdiff_t j
#define EIGEN_UNUSED_VARIABLE(var)
Definition: Macros.h:1076


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:06