source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/relaxed_list.hpp @ f9f3775

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since f9f3775 was f9f3775, checked in by Thierry Delisle <tdelisle@…>, 14 months ago

Moved phd code for the readQ prototype to it's own folder

  • 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.