source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp@ 03045f18

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

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