source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp@ 433d352

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 433d352 was f0c3120, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Added unsuccesfull reverse rng attempt
  • Property mode set to 100644
File size: 15.2 KB
Line 
1#pragma once
2#define LIST_VARIANT relaxed_list
3
4#define VANILLA 0
5#define SNZI 1
6#define BITMASK 2
7#define DISCOVER 3
8#define SNZM 4
9#define BIAS 5
10#define BACK 6
11#define BACKBIAS 7
12
13#ifndef VARIANT
14#define VARIANT VANILLA
15#endif
16
17#ifndef NO_STATS
18#include <iostream>
19#endif
20
21#include <cmath>
22#include <functional>
23#include <memory>
24#include <mutex>
25#include <thread>
26#include <type_traits>
27
28#include "assert.hpp"
29#include "utils.hpp"
30#include "links.hpp"
31#include "snzi.hpp"
32#include "snzi-packed.hpp"
33#include "snzm.hpp"
34
35using namespace std;
36
37struct pick_stat {
38 struct {
39 size_t attempt = 0;
40 size_t success = 0;
41 size_t local = 0;
42 } push;
43 struct {
44 size_t attempt = 0;
45 size_t success = 0;
46 size_t mask_attempt = 0;
47 size_t mask_reset = 0;
48 size_t local = 0;
49 } pop;
50};
51
52struct empty_stat {
53 struct {
54 size_t value = 0;
55 size_t count = 0;
56 } push;
57 struct {
58 size_t value = 0;
59 size_t count = 0;
60 } pop;
61};
62
63template<typename node_t>
64class __attribute__((aligned(128))) relaxed_list {
65 static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
66
67public:
68 static const char * name() {
69 const char * names[] = {
70 "RELAXED: VANILLA",
71 "RELAXED: SNZI",
72 "RELAXED: BITMASK",
73 "RELAXED: SNZI + DISCOVERED MASK",
74 "RELAXED: SNZI + MASK",
75 "RELAXED: SNZI + LOCAL BIAS",
76 "RELAXED: SNZI + REVERSE RNG",
77 "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG"
78 };
79 return names[VARIANT];
80 }
81
82 relaxed_list(unsigned numThreads, unsigned numQueues)
83 : numLists(numThreads * numQueues)
84 , lists(new intrusive_queue_t<node_t>[numLists])
85 #if VARIANT == SNZI || VARIANT == BACK
86 , snzi( std::log2( numLists / (2 * numQueues) ), 2 )
87 #elif VARIANT == BIAS || VARIANT == BACKBIAS
88 #ifdef SNZI_PACKED
89 , snzi( std::ceil( std::log2(numLists) ) )
90 #else
91 , snzi( std::log2( numLists / (2 * numQueues) ), 2 )
92 #endif
93 #elif VARIANT == SNZM || VARIANT == DISCOVER
94 , snzm( numLists )
95 #endif
96 {
97 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
98 std::cout << "Constructing Relaxed List with " << numLists << std::endl;
99 }
100
101 ~relaxed_list() {
102 std::cout << "Destroying Relaxed List" << std::endl;
103 lists.reset();
104 }
105
106 __attribute__((noinline, hot)) void push(node_t * node) {
107 node->_links.ts = rdtscl();
108
109 while(true) {
110 // Pick a random list
111 unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS);
112
113 #ifndef NO_STATS
114 tls.pick.push.attempt++;
115 #endif
116
117 // If we can't lock it retry
118 if( !lists[i].lock.try_lock() ) continue;
119
120 #if VARIANT == VANILLA || VARIANT == BITMASK
121 __attribute__((unused)) int num = numNonEmpty;
122 #endif
123
124 // Actually push it
125 if(lists[i].push(node)) {
126 #if VARIANT == DISCOVER
127 size_t qword = i >> 6ull;
128 size_t bit = i & 63ull;
129 assert(qword == 0);
130 bts(tls.mask, bit);
131 snzm.arrive(i);
132 #elif VARIANT == SNZI || VARIANT == BIAS
133 snzi.arrive(i);
134 #elif VARIANT == BACK || VARIANT == BACKBIAS
135 snzi.arrive(i);
136 tls.rng2.set_raw_state( tls.rng1.get_raw_state());
137 #elif VARIANT == SNZM
138 snzm.arrive(i);
139 #elif VARIANT == BITMASK
140 numNonEmpty++;
141 size_t qword = i >> 6ull;
142 size_t bit = i & 63ull;
143 assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
144 __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
145 assert(!ret);
146 assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
147 #else
148 numNonEmpty++;
149 #endif
150 }
151 #if VARIANT == VANILLA || VARIANT == BITMASK
152 assert(numNonEmpty <= (int)numLists);
153 #endif
154
155 // Unlock and return
156 lists[i].lock.unlock();
157
158 #ifndef NO_STATS
159 tls.pick.push.success++;
160 #if VARIANT == VANILLA || VARIANT == BITMASK
161 tls.empty.push.value += num;
162 tls.empty.push.count += 1;
163 #endif
164 #endif
165 return;
166 }
167 }
168
169 __attribute__((noinline, hot)) node_t * pop() {
170 #if VARIANT == DISCOVER
171 assert(numLists <= 64);
172 while(snzm.query()) {
173 tls.pick.pop.mask_attempt++;
174 unsigned i, j;
175 {
176 // Pick first list totally randomly
177 i = tls.rng1.next() % numLists;
178
179 // Pick the other according to the bitmask
180 unsigned r = tls.rng1.next();
181
182 size_t mask = tls.mask.load(std::memory_order_relaxed);
183 if(mask == 0) {
184 tls.pick.pop.mask_reset++;
185 mask = (1U << numLists) - 1;
186 tls.mask.store(mask, std::memory_order_relaxed);
187 }
188
189 unsigned b = rand_bit(r, mask);
190
191 assertf(b < 64, "%zu %u", mask, b);
192
193 j = b;
194
195 assert(j < numLists);
196 }
197
198 if(auto node = try_pop(i, j)) return node;
199 }
200 #elif VARIANT == SNZI
201 while(snzi.query()) {
202 // Pick two lists at random
203 int i = tls.rng1.next() % numLists;
204 int j = tls.rng1.next() % numLists;
205
206 if(auto node = try_pop(i, j)) return node;
207 }
208
209 #elif VARIANT == BACK
210 while(snzi.query()) {
211 // Pick two lists at random
212 int i = tls.rng2.prev() % numLists;
213 int j = tls.rng2.prev() % numLists;
214
215 if(auto node = try_pop(i, j)) return node;
216 }
217
218 #elif VARIANT == BACKBIAS
219 while(snzi.query()) {
220 // Pick two lists at random
221 int i = idx_from_r(tls.rng2.prev(), true);
222 int j = idx_from_r(tls.rng2.prev(), true);
223
224 if(auto node = try_pop(i, j)) return node;
225 }
226
227 #elif VARIANT == BIAS
228 while(snzi.query()) {
229 // Pick two lists at random
230 unsigned ri = tls.rng1.next();
231 unsigned i;
232 unsigned j = tls.rng1.next();
233 if(0 == (ri & 0xF)) {
234 i = (ri >> 4) % numLists;
235 } else {
236 i = tls.my_queue + ((ri >> 4) % 4);
237 j = tls.my_queue + ((j >> 4) % 4);
238 tls.pick.pop.local++;
239 }
240 i %= numLists;
241 j %= numLists;
242
243 if(auto node = try_pop(i, j)) return node;
244 }
245 #elif VARIANT == SNZM
246 //*
247 while(snzm.query()) {
248 tls.pick.pop.mask_attempt++;
249 unsigned i, j;
250 {
251 // Pick two random number
252 unsigned ri = tls.rng1.next();
253 unsigned rj = tls.rng1.next();
254
255 // Pick two nodes from it
256 unsigned wdxi = ri & snzm.mask;
257 // unsigned wdxj = rj & snzm.mask;
258
259 // Get the masks from the nodes
260 // size_t maski = snzm.masks(wdxi);
261 size_t maskj = snzm.masks(wdxj);
262
263 if(maski == 0 && maskj == 0) continue;
264
265 #if defined(__BMI2__)
266 uint64_t idxsi = _pext_u64(snzm.indexes, maski);
267 // uint64_t idxsj = _pext_u64(snzm.indexes, maskj);
268
269 auto pi = __builtin_popcountll(maski);
270 // auto pj = __builtin_popcountll(maskj);
271
272 ri = pi ? ri & ((pi >> 3) - 1) : 0;
273 rj = pj ? rj & ((pj >> 3) - 1) : 0;
274
275 unsigned bi = (idxsi >> (ri << 3)) & 0xff;
276 unsigned bj = (idxsj >> (rj << 3)) & 0xff;
277 #else
278 unsigned bi = rand_bit(ri >> snzm.depth, maski);
279 unsigned bj = rand_bit(rj >> snzm.depth, maskj);
280 #endif
281
282 i = (bi << snzm.depth) | wdxi;
283 j = (bj << snzm.depth) | wdxj;
284
285 /* paranoid */ assertf(i < numLists, "%u %u", bj, wdxi);
286 /* paranoid */ assertf(j < numLists, "%u %u", bj, wdxj);
287 }
288
289 if(auto node = try_pop(i, j)) return node;
290 }
291 /*/
292 while(snzm.query()) {
293 // Pick two lists at random
294 int i = tls.rng1.next() % numLists;
295 int j = tls.rng1.next() % numLists;
296
297 if(auto node = try_pop(i, j)) return node;
298 }
299 //*/
300 #elif VARIANT == BITMASK
301 int nnempty;
302 while(0 != (nnempty = numNonEmpty)) {
303 tls.pick.pop.mask_attempt++;
304 unsigned i, j;
305 {
306 // Pick two lists at random
307 unsigned num = ((numLists - 1) >> 6) + 1;
308
309 unsigned ri = tls.rng1.next();
310 unsigned rj = tls.rng1.next();
311
312 unsigned wdxi = (ri >> 6u) % num;
313 unsigned wdxj = (rj >> 6u) % num;
314
315 size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
316 size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
317
318 if(maski == 0 && maskj == 0) continue;
319
320 unsigned bi = rand_bit(ri, maski);
321 unsigned bj = rand_bit(rj, maskj);
322
323 assertf(bi < 64, "%zu %u", maski, bi);
324 assertf(bj < 64, "%zu %u", maskj, bj);
325
326 i = bi | (wdxi << 6);
327 j = bj | (wdxj << 6);
328
329 assertf(i < numLists, "%u", wdxi << 6);
330 assertf(j < numLists, "%u", wdxj << 6);
331 }
332
333 if(auto node = try_pop(i, j)) return node;
334 }
335 #else
336 while(numNonEmpty != 0) {
337 // Pick two lists at random
338 int i = tls.rng1.next() % numLists;
339 int j = tls.rng1.next() % numLists;
340
341 if(auto node = try_pop(i, j)) return node;
342 }
343 #endif
344
345 return nullptr;
346 }
347
348private:
349 node_t * try_pop(unsigned i, unsigned j) {
350 #ifndef NO_STATS
351 tls.pick.pop.attempt++;
352 #endif
353
354 #if VARIANT == DISCOVER
355 if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i);
356 if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j);
357 #endif
358
359 // Pick the bet list
360 int w = i;
361 if( __builtin_expect(lists[j].ts() != 0, true) ) {
362 w = (lists[i].ts() < lists[j].ts()) ? i : j;
363 }
364
365 auto & list = lists[w];
366 // If list looks empty retry
367 if( list.ts() == 0 ) return nullptr;
368
369 // If we can't get the lock retry
370 if( !list.lock.try_lock() ) return nullptr;
371
372 #if VARIANT == VANILLA || VARIANT == BITMASK
373 __attribute__((unused)) int num = numNonEmpty;
374 #endif
375
376 // If list is empty, unlock and retry
377 if( list.ts() == 0 ) {
378 list.lock.unlock();
379 return nullptr;
380 }
381
382 // Actually pop the list
383 node_t * node;
384 bool emptied;
385 std::tie(node, emptied) = list.pop();
386 assert(node);
387
388 if(emptied) {
389 #if VARIANT == DISCOVER
390 size_t qword = w >> 6ull;
391 size_t bit = w & 63ull;
392 assert(qword == 0);
393 __attribute__((unused)) bool ret = btr(tls.mask, bit);
394 snzm.depart(w);
395 #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS
396 snzi.depart(w);
397 #elif VARIANT == SNZM
398 snzm.depart(w);
399 #elif VARIANT == BITMASK
400 numNonEmpty--;
401 size_t qword = w >> 6ull;
402 size_t bit = w & 63ull;
403 assert((list_mask[qword] & (1ul << bit)) != 0);
404 __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
405 assert(ret);
406 assert((list_mask[qword] & (1ul << bit)) == 0);
407 #else
408 numNonEmpty--;
409 #endif
410 }
411
412 // Unlock and return
413 list.lock.unlock();
414 #if VARIANT == VANILLA || VARIANT == BITMASK
415 assert(numNonEmpty >= 0);
416 #endif
417 #ifndef NO_STATS
418 tls.pick.pop.success++;
419 #if VARIANT == VANILLA || VARIANT == BITMASK
420 tls.empty.pop.value += num;
421 tls.empty.pop.count += 1;
422 #endif
423 #endif
424 return node;
425 }
426
427 inline unsigned idx_from_r(unsigned r, bool bias) {
428 unsigned i;
429 if(bias) {
430 if(0 == (r & 0x3F)) {
431 i = r >> 6;
432 } else {
433 i = tls.my_queue + ((r >> 6) % 4);
434 tls.pick.push.local++;
435 }
436 } else {
437 i = r;
438 }
439 return i % numLists;
440 }
441
442public:
443
444 static __attribute__((aligned(128))) thread_local struct TLS {
445 Random rng1 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
446 Random rng2 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
447 unsigned my_queue = (ticket++) * 4;
448 pick_stat pick;
449 empty_stat empty;
450 __attribute__((aligned(64))) std::atomic_size_t mask = { 0 };
451 } tls;
452
453private:
454 const unsigned numLists;
455 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
456private:
457 #if VARIANT == SNZI || VARIANT == BACK
458 snzi_t snzi;
459 #elif VARIANT == BIAS || VARIANT == BACKBIAS
460 #ifdef SNZI_PACKED
461 snzip_t snzi;
462 #else
463 snzi_t snzi;
464 #endif
465 #elif VARIANT == SNZM || VARIANT == DISCOVER
466 snzm_t snzm;
467 #else
468 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists
469 #endif
470 #if VARIANT == BITMASK
471 std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
472 #endif
473
474public:
475 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t<node_t>);
476 static std::atomic_uint32_t ticket;
477
478#ifndef NO_STATS
479 static void stats_tls_tally() {
480 global_stats.pick.push.attempt += tls.pick.push.attempt;
481 global_stats.pick.push.success += tls.pick.push.success;
482 global_stats.pick.push.local += tls.pick.push.local;
483 global_stats.pick.pop .attempt += tls.pick.pop.attempt;
484 global_stats.pick.pop .success += tls.pick.pop.success;
485 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
486 global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;
487 global_stats.pick.pop .local += tls.pick.pop.local;
488
489 global_stats.qstat.push.value += tls.empty.push.value;
490 global_stats.qstat.push.count += tls.empty.push.count;
491 global_stats.qstat.pop .value += tls.empty.pop .value;
492 global_stats.qstat.pop .count += tls.empty.pop .count;
493 }
494
495private:
496 static struct GlobalStats {
497 struct {
498 struct {
499 std::atomic_size_t attempt = { 0 };
500 std::atomic_size_t success = { 0 };
501 std::atomic_size_t local = { 0 };
502 } push;
503 struct {
504 std::atomic_size_t attempt = { 0 };
505 std::atomic_size_t success = { 0 };
506 std::atomic_size_t mask_attempt = { 0 };
507 std::atomic_size_t mask_reset = { 0 };
508 std::atomic_size_t local = { 0 };
509 } pop;
510 } pick;
511 struct {
512 struct {
513 std::atomic_size_t value = { 0 };
514 std::atomic_size_t count = { 0 };
515 } push;
516 struct {
517 std::atomic_size_t value = { 0 };
518 std::atomic_size_t count = { 0 };
519 } pop;
520 } qstat;
521 } global_stats;
522
523public:
524 static void stats_print(std::ostream & os ) {
525 std::cout << "----- Relaxed List Stats -----" << std::endl;
526
527 const auto & global = global_stats;
528
529 double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
530 double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
531 double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
532 double rpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_reset);
533
534 double push_len = double(global.pick.push.attempt ) / global.pick.push.success;
535 double pop_len = double(global.pick.pop .attempt ) / global.pick.pop .success;
536 double mpop_len = double(global.pick.pop .mask_attempt) / global.pick.pop .success;
537 double rpop_len = double(global.pick.pop .mask_reset ) / global.pick.pop .success;
538
539 os << "Push Pick : " << push_sur << " %, len " << push_len << " (" << global.pick.push.attempt << " / " << global.pick.push.success << ")\n";
540 os << "Pop Pick : " << pop_sur << " %, len " << pop_len << " (" << global.pick.pop .attempt << " / " << global.pick.pop .success << ")\n";
541 os << "TryPop Pick : " << mpop_sur << " %, len " << mpop_len << " (" << global.pick.pop .mask_attempt << " / " << global.pick.pop .success << ")\n";
542 os << "Pop M Reset : " << rpop_sur << " %, len " << rpop_len << " (" << global.pick.pop .mask_reset << " / " << global.pick.pop .success << ")\n";
543
544 double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
545 double avgQ_pop = double(global.qstat.pop .value) / global.qstat.pop .count;
546 double avgQ = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
547 os << "Push Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
548 os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n";
549 os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
550
551 os << "Local Push : " << global.pick.push.local << "\n";
552 os << "Local Pop : " << global.pick.pop .local << "\n";
553 }
554#endif
555};
Note: See TracBrowser for help on using the repository browser.