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

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 0092853 was 0092853, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Fixed Variants

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