source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/dynamic_entropy.hpp @ 451d958

ADTast-experimentalenumforall-pointer-decaypthread-emulationqualifiedEnum
Last change on this file since 451d958 was a1b9bc3, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Many small changes to prototype code

  • Property mode set to 100644
File size: 5.4 KB
Line 
1#pragma once
2
3#define LIST_VARIANT dyn_ent_list
4
5#include <memory>
6#include <mutex>
7#include <thread>
8
9#include "assert.hpp"
10#include "utils.hpp"
11#include "links.hpp"
12
13std::mutex mtx_;
14
15template<typename node_t>
16class __attribute__((aligned(128))) dyn_ent_list {
17        const unsigned numLists;
18        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists;
19
20public:
21        dyn_ent_list(unsigned numThreads, unsigned)
22                : numLists(numThreads * 4)
23                , lists(new intrusive_queue_t<node_t>[numLists])
24        {
25                std::cout << "Constructing Relaxed List with " << numLists << std::endl;
26        }
27
28        __attribute__((noinline, hot)) void push(node_t * node) {
29                node->_links.ts = rdtscl();
30
31                // Try to pick a lane and lock it
32                unsigned i;
33                do {
34                        // Pick the index of a lane
35                        i = idx_from_r(tls.rng1.next(), tls.my_queue).first;
36                        // i = ret.first; //local = ret.second;
37                        tls.stats.push.attempt++;
38                } while( !lists[i].lock.try_lock() );
39
40                lists[i].push(node);
41                lists[i].lock.unlock();
42                tls.rng2.set_raw_state( tls.rng1.get_raw_state());
43                tls.stats.push.success++;
44        }
45
46        __attribute__((noinline, hot)) node_t * pop() {
47                for(int n = 0; n < 25; n++) {
48                        // Pick two lists at random
49                        unsigned i, j;
50                        bool locali, localj;
51                        auto reti = idx_from_r(tls.rng2.prev(), tls.my_queue);
52                        auto retj = idx_from_r(tls.rng2.prev(), tls.my_queue);
53
54                        i = reti.first; locali = reti.second;
55                        j = retj.first; localj = retj.second;
56                        tls.stats.pop.attempt++;
57
58                        // try popping from the 2 picked lists
59                        node_t * thrd = try_pop(i, j);
60                        if(thrd) {
61                                tls.stats.pop.success++;
62                                return thrd;
63                        }
64                }
65
66                unsigned offset = tls.rng2.next();
67                for(unsigned i = 0; i < numLists; i++) {
68                        unsigned idx = (offset + i) % numLists;
69                        node_t * thrd = try_pop(idx);
70                        if(thrd) {
71                                return thrd;
72                        }
73                }
74
75                // All lanes where empty return 0p
76                return nullptr;
77        }
78
79private:
80        inline node_t * try_pop(unsigned i, unsigned j) {
81                // Pick the bet list
82                int w = i;
83                if( __builtin_expect(!(lists[j].ts() > 0), true) ) {
84                        w = (lists[i].ts() < lists[j].ts()) ? i : j;
85                }
86
87                return try_pop(w);
88        }
89
90        inline node_t * try_pop(unsigned w) {
91                // If list looks empty retry
92                if( lists[w].ts() == 0 ) { tls.stats.pop.empty++; return nullptr; }
93
94                // If we can't get the lock retry
95                if( !lists[w].lock.try_lock() ) { tls.stats.pop.locked++; return nullptr; }
96
97
98                // If list is empty, unlock and retry
99                if( lists[w].ts() == 0 ) {
100                        tls.stats.pop.both++;
101                        lists[w].lock.unlock();
102                        return nullptr;
103                }
104
105                auto node = lists[w].pop();
106                lists[w].lock.unlock();
107                return node.first;
108        }
109
110        inline std::pair<unsigned, bool> idx_from_r(unsigned r, unsigned preferred) {
111                unsigned i;
112                bool local;
113                unsigned rlow  = r % 4;
114                unsigned rhigh = r / 4;
115                if((0 != rlow) && preferred != outside) {
116                        // (BIAS - 1) out of BIAS chances
117                        // Use perferred queues
118                        i = preferred + (rhigh % 4);
119                        local = true;
120                }
121                else {
122                        // 1 out of BIAS chances
123                        // Use all queues
124                        i = rhigh;
125                        local = false;
126                }
127                return {i % numLists, local};
128        }
129private:
130        static std::atomic_uint32_t ticket;
131        static const unsigned outside = 0xFFFFFFFF;
132
133        static inline unsigned calc_preferred() {
134                unsigned t = ticket++;
135                if(t == 0) return outside;
136                unsigned i = 4 * (t - 1);
137                return i;
138        }
139
140        static __attribute__((aligned(128))) thread_local struct TLS {
141                Random     rng1 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
142                Random     rng2 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
143                Random     rng3 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) };
144                unsigned   my_queue = calc_preferred();
145                struct {
146                        struct {
147                                size_t attempt = 0;
148                                size_t success = 0;
149                        } push;
150                        struct {
151                                size_t attempt = 0;
152                                size_t success = 0;
153                                size_t empty   = 0;
154                                size_t locked  = 0;
155                                size_t both    = 0;
156                        } pop;
157                } stats;
158        } tls;
159public:
160        static const char * name() {
161                return "Dynamic Entropy List";
162        }
163
164public:
165        static struct GlobalStats {
166                struct {
167                        std::atomic_size_t attempt = 0;
168                        std::atomic_size_t success = 0;
169                } push;
170                struct {
171                        std::atomic_size_t attempt = 0;
172                        std::atomic_size_t success = 0;
173                        std::atomic_size_t empty   = 0;
174                        std::atomic_size_t locked  = 0;
175                        std::atomic_size_t both    = 0;
176                } pop;
177        } global_stats;
178        static void stats_tls_tally() {
179                global_stats.push.attempt += tls.stats.push.attempt;
180                global_stats.push.success += tls.stats.push.success;
181                global_stats.pop .attempt += tls.stats.pop.attempt;
182                global_stats.pop .success += tls.stats.pop.success;
183                global_stats.pop .empty   += tls.stats.pop.empty;
184                global_stats.pop .locked  += tls.stats.pop.locked;
185                global_stats.pop .both    += tls.stats.pop.both;
186        }
187
188        static void stats_print(std::ostream & os, double) {
189                        const auto & global = global_stats;
190
191                double push_sur = (100.0 * double(global.push.success) / global.push.attempt);
192                double pop_sur  = (100.0 * double(global.pop .success) / global.pop .attempt);
193
194                double push_len = double(global.push.attempt     ) / global.push.success;
195                double pop_len  = double(global.pop .attempt     ) / global.pop .success;
196
197                os << "Push   Pick   : " << push_sur << " %, len " << push_len << " (" << global.push.attempt      << " / " << global.push.success << ")\n";
198                os << "Pop    Pick   : " << pop_sur  << " %, len " << pop_len  << " (" << global.pop .attempt      << " / " << global.pop .success << ")\n";
199                os << "Pop    Fails  : " << global_stats.pop .empty << "e, " << global_stats.pop .locked << "l, " << global_stats.pop .both << "\n";
200        }
201};
Note: See TracBrowser for help on using the repository browser.