source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ 9da5a50

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

Added new DISCOVER_BITMASK algorithm as a potential ready queue sub-algorithm.
It offers may be an improvement but doesn't reduce the contention for the counter

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