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

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

Adding current version of the C++ relaxed_list code and benchmark

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