[56c8b86] | 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 | |
---|
| 13 | std::mutex mtx_; |
---|
| 14 | |
---|
| 15 | template<typename node_t> |
---|
| 16 | class __attribute__((aligned(128))) dyn_ent_list { |
---|
| 17 | const unsigned numLists; |
---|
| 18 | __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists; |
---|
| 19 | |
---|
| 20 | public: |
---|
| 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 |
---|
[a1b9bc3] | 35 | i = idx_from_r(tls.rng1.next(), tls.my_queue).first; |
---|
[56c8b86] | 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; |
---|
[a1b9bc3] | 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); |
---|
[56c8b86] | 53 | |
---|
[a1b9bc3] | 54 | i = reti.first; locali = reti.second; |
---|
| 55 | j = retj.first; localj = retj.second; |
---|
[56c8b86] | 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 | |
---|
| 79 | private: |
---|
| 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 | |
---|
[a1b9bc3] | 110 | inline std::pair<unsigned, bool> idx_from_r(unsigned r, unsigned preferred) { |
---|
[56c8b86] | 111 | unsigned i; |
---|
[a1b9bc3] | 112 | bool local; |
---|
[56c8b86] | 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); |
---|
[a1b9bc3] | 119 | local = true; |
---|
[56c8b86] | 120 | } |
---|
| 121 | else { |
---|
| 122 | // 1 out of BIAS chances |
---|
| 123 | // Use all queues |
---|
| 124 | i = rhigh; |
---|
[a1b9bc3] | 125 | local = false; |
---|
[56c8b86] | 126 | } |
---|
[a1b9bc3] | 127 | return {i % numLists, local}; |
---|
[56c8b86] | 128 | } |
---|
| 129 | private: |
---|
| 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()) }; |
---|
[a1b9bc3] | 143 | Random rng3 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) }; |
---|
[56c8b86] | 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; |
---|
| 159 | public: |
---|
| 160 | static const char * name() { |
---|
| 161 | return "Dynamic Entropy List"; |
---|
| 162 | } |
---|
| 163 | |
---|
| 164 | public: |
---|
| 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 | |
---|
[a1b9bc3] | 188 | static void stats_print(std::ostream & os, double) { |
---|
[56c8b86] | 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 | }; |
---|