source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ a82a8f4

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since a82a8f4 was a82a8f4, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

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