source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ 33e62f1b

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

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