Changeset 9421f3d8 for doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
- Timestamp:
- Oct 30, 2019, 11:26:07 AM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- df75fe97
- Parents:
- b067d9b
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
rb067d9b r9421f3d8 37 37 }; 38 38 39 static 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 55 static 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 } 39 70 40 71 extern bool enable_stats; … … 48 79 size_t attempt = 0; 49 80 size_t success = 0; 81 size_t mask_attempt = 0; 82 } pop; 83 }; 84 85 struct 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; 50 93 } pop; 51 94 }; … … 65 108 public: 66 109 relaxed_list(unsigned numLists) 67 : numNonEmpty{0} 68 , lists(new intrusive_queue_t[numLists]) 110 : lists(new intrusive_queue_t[numLists]) 69 111 , numLists(numLists) 70 {} 112 { 113 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists"); 114 assert(sizeof(*this) == 128); 115 } 71 116 72 117 ~relaxed_list() { … … 84 129 while(true) { 85 130 // Pick a random list 86 inti = tls.rng.next() % numLists;131 unsigned i = tls.rng.next() % numLists; 87 132 88 133 #ifndef NO_STATS … … 93 138 if( !lists[i].lock.try_lock() ) continue; 94 139 140 __attribute__((unused)) int num = numNonEmpty; 141 95 142 // Actually push it 96 lists[i].push(node, numNonEmpty); 143 if(lists[i].push(node)) { 144 numNonEmpty++; 145 size_t qword = i >> 6ull; 146 size_t bit = i & 63ull; 147 assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 148 __attribute__((unused)) bool ret = bts(list_mask[qword], bit); 149 assert(!ret); 150 assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 151 } 97 152 assert(numNonEmpty <= (int)numLists); 98 153 … … 102 157 #ifndef NO_STATS 103 158 tls.pick.push.success++; 159 tls.empty.push.value += num; 160 tls.empty.push.count += 1; 104 161 #endif 105 162 return; … … 108 165 109 166 __attribute__((noinline, hot)) node_t * pop() { 110 while(numNonEmpty != 0) { 111 // Pick two lists at random 112 int i = tls.rng.next() % numLists; 113 int j = tls.rng.next() % numLists; 114 115 #ifndef NO_STATS 116 tls.pick.pop.attempt++; 117 #endif 118 119 // Pick the bet list 120 int w = i; 121 if( __builtin_expect(lists[j].ts() != 0, true) ) { 122 w = (lists[i].ts() < lists[j].ts()) ? i : j; 123 } 124 125 auto & list = lists[w]; 126 // If list looks empty retry 127 if( list.ts() == 0 ) continue; 128 129 // If we can't get the lock retry 130 if( !list.lock.try_lock() ) continue; 131 132 // If list is empty, unlock and retry 133 if( list.ts() == 0 ) { 134 list.lock.unlock(); 135 continue; 136 } 137 138 // Actually pop the list 139 auto node = list.pop(numNonEmpty); 140 assert(node); 141 142 // Unlock and return 143 list.lock.unlock(); 144 assert(numNonEmpty >= 0); 145 #ifndef NO_STATS 146 tls.pick.pop.success++; 147 #endif 148 return node; 149 } 167 #if !defined(NO_BITMASK) 168 // for(int r = 0; r < 10 && numNonEmpty != 0; r++) { 169 // // Pick two lists at random 170 // unsigned i = tls.rng.next() % numLists; 171 // unsigned j = tls.rng.next() % numLists; 172 173 // if(auto node = try_pop(i, j)) return node; 174 // } 175 int nnempty; 176 while(0 != (nnempty = numNonEmpty)) { 177 unsigned i, j; 178 if( numLists < 4 || (numLists / nnempty) < 4 ) { 179 // Pick two lists at random 180 i = tls.rng.next() % numLists; 181 j = tls.rng.next() % numLists; 182 } else { 183 #ifndef NO_STATS 184 // tls.pick.push.mask_attempt++; 185 #endif 186 187 // Pick two lists at random 188 unsigned num = ((numLists - 1) >> 6) + 1; 189 190 unsigned ri = tls.rng.next(); 191 unsigned rj = tls.rng.next(); 192 193 unsigned wdxi = (ri >> 6u) % num; 194 unsigned wdxj = (rj >> 6u) % num; 195 196 size_t maski = list_mask[wdxi].load(std::memory_order_relaxed); 197 size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed); 198 199 if(maski == 0 && maskj == 0) continue; 200 201 unsigned biti = maski ? ri % __builtin_popcountl(maski) : 0; 202 unsigned bitj = maskj ? rj % __builtin_popcountl(maskj) : 0; 203 204 unsigned bi = 64 - nthSetBit(maski, biti + 1); 205 unsigned bj = 64 - nthSetBit(maskj, bitj + 1); 206 207 assertf(bi < 64, "%zu %u %u", maski, biti, bi); 208 assertf(bj < 64, "%zu %u %u", maskj, bitj, 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 150 228 151 229 return nullptr; 152 230 } 231 232 private: 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 } 153 285 154 286 private: … … 178 310 sentinel_t before; 179 311 sentinel_t after; 180 stat s; 312 #ifndef NO_STATS 313 stat s; 314 #endif 181 315 182 316 static constexpr auto fields_offset = offsetof( node_t, _links ); … … 186 320 , after {{ head(), nullptr }} 187 321 { 188 assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));189 assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));190 assert(head()->_links.prev == nullptr);191 assert(head()->_links.next == tail() );192 assert(tail()->_links.next == nullptr);193 assert(tail()->_links.prev == head() );194 assert(sizeof(*this) == 128);195 assert((intptr_t(this) % 128) == 0);322 /* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before)); 323 /* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after )); 324 /* paranoid */ assert(head()->_links.prev == nullptr); 325 /* paranoid */ assert(head()->_links.next == tail() ); 326 /* paranoid */ assert(tail()->_links.next == nullptr); 327 /* paranoid */ assert(tail()->_links.prev == head() ); 328 /* paranoid */ assert(sizeof(*this) == 128); 329 /* paranoid */ assert((intptr_t(this) % 128) == 0); 196 330 } 197 331 … … 220 354 } 221 355 222 inline void push(node_t * node, std::atomic_int & nonEmpty) {356 inline bool push(node_t * node) { 223 357 assert(lock); 224 358 assert(node->_links.ts != 0); … … 232 366 prev->_links.next = node; 233 367 tail->_links.prev = node; 234 if(before._links.ts == 0l) {235 nonEmpty += 1;236 before._links.ts = node->_links.ts;237 }238 368 #ifndef NO_STATS 239 369 if(enable_stats) s.diff++; 240 370 #endif 241 } 242 243 inline node_t * pop(std::atomic_int & nonEmpty) { 371 if(before._links.ts == 0l) { 372 before._links.ts = node->_links.ts; 373 assert(node->_links.prev == this->head()); 374 return true; 375 } 376 return false; 377 } 378 379 inline std::pair<node_t *, bool> pop() { 244 380 assert(lock); 245 381 node_t * head = this->head(); … … 248 384 node_t * node = head->_links.next; 249 385 node_t * next = node->_links.next; 250 if(node == tail) return nullptr;386 if(node == tail) return {nullptr, false}; 251 387 252 388 head->_links.next = next; 253 389 next->_links.prev = head; 254 390 391 #ifndef NO_STATS 392 if(enable_stats) s.diff--; 393 #endif 255 394 if(next == tail) { 256 395 before._links.ts = 0l; 257 nonEmpty -= 1;396 return {node, true}; 258 397 } 259 398 else { … … 261 400 before._links.ts = next->_links.ts; 262 401 assert(before._links.ts != 0); 263 } 264 #ifndef NO_STATS 265 if(enable_stats) s.diff--; 266 #endif 267 return node; 402 return {node, false}; 403 } 268 404 } 269 405 … … 277 413 278 414 static __attribute__((aligned(128))) thread_local struct TLS { 279 Random rng = { int(rdtscl()) }; 280 pick_stat pick; 415 Random rng = { int(rdtscl()) }; 416 pick_stat pick; 417 empty_stat empty; 281 418 } tls; 282 419 420 public: 421 std::atomic_int numNonEmpty = 0; // number of non-empty lists 422 std::atomic_size_t list_mask[7] = { 0 }; // which queues are empty 283 423 private: 284 std::atomic_int numNonEmpty; // number of non-empty lists285 424 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists; 286 425 const unsigned numLists;
Note: See TracChangeset
for help on using the changeset viewer.
