Changeset 22f94a4 for doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
- Timestamp:
- Aug 11, 2020, 4:40:15 PM (6 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct
- Children:
- 0d070ca
- Parents:
- 07d867b (diff), 129674b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r07d867b r22f94a4 1 1 #pragma once 2 #define LIST_VARIANT relaxed_list 3 4 #define VANILLA 0 5 #define SNZI 1 6 #define BITMASK 2 7 #define DISCOVER 3 8 #define SNZM 4 9 #define BIAS 5 10 #define BACK 6 11 #define BACKBIAS 7 12 13 #ifndef VARIANT 14 #define VARIANT VANILLA 15 #endif 2 16 3 17 #ifndef NO_STATS … … 5 19 #endif 6 20 21 #include <cmath> 22 #include <functional> 7 23 #include <memory> 8 24 #include <mutex> 25 #include <thread> 9 26 #include <type_traits> 10 27 11 28 #include "assert.hpp" 12 29 #include "utils.hpp" 30 #include "links.hpp" 31 #include "snzi.hpp" 32 #include "snzi-packed.hpp" 33 #include "snzm.hpp" 13 34 14 35 using namespace std; 15 16 struct 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 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 }70 71 extern bool enable_stats;72 36 73 37 struct pick_stat { … … 75 39 size_t attempt = 0; 76 40 size_t success = 0; 41 size_t local = 0; 77 42 } push; 78 43 struct { … … 80 45 size_t success = 0; 81 46 size_t mask_attempt = 0; 47 size_t mask_reset = 0; 48 size_t local = 0; 82 49 } pop; 83 50 }; … … 95 62 96 63 template<typename node_t> 97 struct _LinksFields_t {98 node_t * prev = nullptr;99 node_t * next = nullptr;100 unsigned long long ts = 0;101 };102 103 template<typename node_t>104 64 class __attribute__((aligned(128))) relaxed_list { 105 65 static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field"); 106 66 107 67 public: 108 relaxed_list(unsigned numLists) 109 : lists(new intrusive_queue_t[numLists]) 110 , numLists(numLists) 68 static const char * name() { 69 const char * names[] = { 70 "RELAXED: VANILLA", 71 "RELAXED: SNZI", 72 "RELAXED: BITMASK", 73 "RELAXED: SNZI + DISCOVERED MASK", 74 "RELAXED: SNZI + MASK", 75 "RELAXED: SNZI + LOCAL BIAS", 76 "RELAXED: SNZI + REVERSE RNG", 77 "RELAXED: SNZI + LOCAL BIAS + REVERSE RNG" 78 }; 79 return names[VARIANT]; 80 } 81 82 relaxed_list(unsigned numThreads, unsigned numQueues) 83 : numLists(numThreads * numQueues) 84 , lists(new intrusive_queue_t<node_t>[numLists]) 85 #if VARIANT == SNZI || VARIANT == BACK 86 , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) 87 #elif VARIANT == BIAS || VARIANT == BACKBIAS 88 #ifdef SNZI_PACKED 89 , snzi( std::ceil( std::log2(numLists) ) ) 90 #else 91 , snzi( std::log2( numLists / (2 * numQueues) ), 2 ) 92 #endif 93 #elif VARIANT == SNZM || VARIANT == DISCOVER 94 , snzm( numLists ) 95 #endif 111 96 { 112 97 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists"); 113 // assert(sizeof(*this) == 128);114 98 std::cout << "Constructing Relaxed List with " << numLists << std::endl; 115 116 #ifndef NO_STATS117 if(head) this->next = head;118 head = this;119 #endif120 99 } 121 100 … … 130 109 while(true) { 131 110 // Pick a random list 132 unsigned i = tls.rng.next() % numLists;111 unsigned i = idx_from_r(tls.rng1.next(), VARIANT == BIAS || VARIANT == BACKBIAS); 133 112 134 113 #ifndef NO_STATS … … 139 118 if( !lists[i].lock.try_lock() ) continue; 140 119 141 __attribute__((unused)) int num = numNonEmpty; 120 #if VARIANT == VANILLA || VARIANT == BITMASK 121 __attribute__((unused)) int num = numNonEmpty; 122 #endif 142 123 143 124 // Actually push it 144 125 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); 126 #if VARIANT == DISCOVER 127 size_t qword = i >> 6ull; 128 size_t bit = i & 63ull; 129 assert(qword == 0); 130 bts(tls.mask, bit); 131 snzm.arrive(i); 132 #elif VARIANT == SNZI || VARIANT == BIAS 133 snzi.arrive(i); 134 #elif VARIANT == BACK || VARIANT == BACKBIAS 135 snzi.arrive(i); 136 tls.rng2.set_raw_state( tls.rng1.get_raw_state()); 137 #elif VARIANT == SNZM 138 snzm.arrive(i); 139 #elif VARIANT == BITMASK 140 numNonEmpty++; 141 size_t qword = i >> 6ull; 142 size_t bit = i & 63ull; 143 assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 144 __attribute__((unused)) bool ret = bts(list_mask[qword], bit); 145 assert(!ret); 146 assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 147 #else 148 numNonEmpty++; 149 #endif 150 } 151 #if VARIANT == VANILLA || VARIANT == BITMASK 152 assert(numNonEmpty <= (int)numLists); 153 #endif 154 154 155 155 // Unlock and return … … 158 158 #ifndef NO_STATS 159 159 tls.pick.push.success++; 160 tls.empty.push.value += num; 161 tls.empty.push.count += 1; 160 #if VARIANT == VANILLA || VARIANT == BITMASK 161 tls.empty.push.value += num; 162 tls.empty.push.count += 1; 163 #endif 162 164 #endif 163 165 return; … … 166 168 167 169 __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 // } 170 #if VARIANT == DISCOVER 171 assert(numLists <= 64); 172 while(snzm.query()) { 173 tls.pick.pop.mask_attempt++; 174 unsigned i, j; 175 { 176 // Pick first list totally randomly 177 i = tls.rng1.next() % numLists; 178 179 // Pick the other according to the bitmask 180 unsigned r = tls.rng1.next(); 181 182 size_t mask = tls.mask.load(std::memory_order_relaxed); 183 if(mask == 0) { 184 tls.pick.pop.mask_reset++; 185 mask = (1U << numLists) - 1; 186 tls.mask.store(mask, std::memory_order_relaxed); 187 } 188 189 unsigned b = rand_bit(r, mask); 190 191 assertf(b < 64, "%zu %u", mask, b); 192 193 j = b; 194 195 assert(j < numLists); 196 } 197 198 if(auto node = try_pop(i, j)) return node; 199 } 200 #elif VARIANT == SNZI 201 while(snzi.query()) { 202 // Pick two lists at random 203 int i = tls.rng1.next() % numLists; 204 int j = tls.rng1.next() % numLists; 205 206 if(auto node = try_pop(i, j)) return node; 207 } 208 209 #elif VARIANT == BACK 210 while(snzi.query()) { 211 // Pick two lists at random 212 int i = tls.rng2.prev() % numLists; 213 int j = tls.rng2.prev() % numLists; 214 215 if(auto node = try_pop(i, j)) return node; 216 } 217 218 #elif VARIANT == BACKBIAS 219 while(snzi.query()) { 220 // Pick two lists at random 221 int i = idx_from_r(tls.rng2.prev(), true); 222 int j = idx_from_r(tls.rng2.prev(), true); 223 224 if(auto node = try_pop(i, j)) return node; 225 } 226 227 #elif VARIANT == BIAS 228 while(snzi.query()) { 229 // Pick two lists at random 230 unsigned ri = tls.rng1.next(); 231 unsigned i; 232 unsigned j = tls.rng1.next(); 233 if(0 == (ri & 0xF)) { 234 i = (ri >> 4) % numLists; 235 } else { 236 i = tls.my_queue + ((ri >> 4) % 4); 237 j = tls.my_queue + ((j >> 4) % 4); 238 tls.pick.pop.local++; 239 } 240 i %= numLists; 241 j %= numLists; 242 243 if(auto node = try_pop(i, j)) return node; 244 } 245 #elif VARIANT == SNZM 246 //* 247 while(snzm.query()) { 248 tls.pick.pop.mask_attempt++; 249 unsigned i, j; 250 { 251 // Pick two random number 252 unsigned ri = tls.rng1.next(); 253 unsigned rj = tls.rng1.next(); 254 255 // Pick two nodes from it 256 unsigned wdxi = ri & snzm.mask; 257 // unsigned wdxj = rj & snzm.mask; 258 259 // Get the masks from the nodes 260 // size_t maski = snzm.masks(wdxi); 261 size_t maskj = snzm.masks(wdxj); 262 263 if(maski == 0 && maskj == 0) continue; 264 265 #if defined(__BMI2__) 266 uint64_t idxsi = _pext_u64(snzm.indexes, maski); 267 // uint64_t idxsj = _pext_u64(snzm.indexes, maskj); 268 269 auto pi = __builtin_popcountll(maski); 270 // auto pj = __builtin_popcountll(maskj); 271 272 ri = pi ? ri & ((pi >> 3) - 1) : 0; 273 rj = pj ? rj & ((pj >> 3) - 1) : 0; 274 275 unsigned bi = (idxsi >> (ri << 3)) & 0xff; 276 unsigned bj = (idxsj >> (rj << 3)) & 0xff; 277 #else 278 unsigned bi = rand_bit(ri >> snzm.depth, maski); 279 unsigned bj = rand_bit(rj >> snzm.depth, maskj); 280 #endif 281 282 i = (bi << snzm.depth) | wdxi; 283 j = (bj << snzm.depth) | wdxj; 284 285 /* paranoid */ assertf(i < numLists, "%u %u", bj, wdxi); 286 /* paranoid */ assertf(j < numLists, "%u %u", bj, wdxj); 287 } 288 289 if(auto node = try_pop(i, j)) return node; 290 } 291 /*/ 292 while(snzm.query()) { 293 // Pick two lists at random 294 int i = tls.rng1.next() % numLists; 295 int j = tls.rng1.next() % numLists; 296 297 if(auto node = try_pop(i, j)) return node; 298 } 299 //*/ 300 #elif VARIANT == BITMASK 176 301 int nnempty; 177 302 while(0 != (nnempty = numNonEmpty)) { 178 303 tls.pick.pop.mask_attempt++; 179 304 unsigned i, j; 180 // if( numLists < 4 || (numLists / nnempty) < 4 ) {181 // // Pick two lists at random182 // i = tls.rng.next() % numLists;183 // j = tls.rng.next() % numLists;184 // } else185 305 { 186 #ifndef NO_STATS187 // tls.pick.push.mask_attempt++;188 #endif189 190 306 // Pick two lists at random 191 307 unsigned num = ((numLists - 1) >> 6) + 1; 192 308 193 unsigned ri = tls.rng .next();194 unsigned rj = tls.rng .next();309 unsigned ri = tls.rng1.next(); 310 unsigned rj = tls.rng1.next(); 195 311 196 312 unsigned wdxi = (ri >> 6u) % num; … … 220 336 while(numNonEmpty != 0) { 221 337 // Pick two lists at random 222 int i = tls.rng .next() % numLists;223 int j = tls.rng .next() % numLists;338 int i = tls.rng1.next() % numLists; 339 int j = tls.rng1.next() % numLists; 224 340 225 341 if(auto node = try_pop(i, j)) return node; … … 234 350 #ifndef NO_STATS 235 351 tls.pick.pop.attempt++; 352 #endif 353 354 #if VARIANT == DISCOVER 355 if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i); 356 if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j); 236 357 #endif 237 358 … … 249 370 if( !list.lock.try_lock() ) return nullptr; 250 371 251 __attribute__((unused)) int num = numNonEmpty; 372 #if VARIANT == VANILLA || VARIANT == BITMASK 373 __attribute__((unused)) int num = numNonEmpty; 374 #endif 252 375 253 376 // If list is empty, unlock and retry … … 264 387 265 388 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); 389 #if VARIANT == DISCOVER 390 size_t qword = w >> 6ull; 391 size_t bit = w & 63ull; 392 assert(qword == 0); 393 __attribute__((unused)) bool ret = btr(tls.mask, bit); 394 snzm.depart(w); 395 #elif VARIANT == SNZI || VARIANT == BIAS || VARIANT == BACK || VARIANT == BACKBIAS 396 snzi.depart(w); 397 #elif VARIANT == SNZM 398 snzm.depart(w); 399 #elif VARIANT == BITMASK 400 numNonEmpty--; 401 size_t qword = w >> 6ull; 402 size_t bit = w & 63ull; 403 assert((list_mask[qword] & (1ul << bit)) != 0); 404 __attribute__((unused)) bool ret = btr(list_mask[qword], bit); 405 assert(ret); 406 assert((list_mask[qword] & (1ul << bit)) == 0); 407 #else 408 numNonEmpty--; 409 #endif 273 410 } 274 411 275 412 // Unlock and return 276 413 list.lock.unlock(); 277 assert(numNonEmpty >= 0); 414 #if VARIANT == VANILLA || VARIANT == BITMASK 415 assert(numNonEmpty >= 0); 416 #endif 278 417 #ifndef NO_STATS 279 418 tls.pick.pop.success++; 280 tls.empty.pop.value += num; 281 tls.empty.pop.count += 1; 419 #if VARIANT == VANILLA || VARIANT == BITMASK 420 tls.empty.pop.value += num; 421 tls.empty.pop.count += 1; 422 #endif 282 423 #endif 283 424 return node; 284 425 } 285 426 286 private: 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); 427 inline unsigned idx_from_r(unsigned r, bool bias) { 428 unsigned i; 429 if(bias) { 430 if(0 == (r & 0x3F)) { 431 i = r >> 6; 432 } else { 433 i = tls.my_queue + ((r >> 6) % 4); 434 tls.pick.push.local++; 435 } 436 } else { 437 i = r; 331 438 } 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 439 return i % numLists; 440 } 412 441 413 442 public: 414 443 415 444 static __attribute__((aligned(128))) thread_local struct TLS { 416 Random rng = { int(rdtscl()) }; 445 Random rng1 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) }; 446 Random rng2 = { unsigned(std::hash<std::thread::id>{}(std::this_thread::get_id()) ^ rdtscl()) }; 447 unsigned my_queue = (ticket++) * 4; 417 448 pick_stat pick; 418 449 empty_stat empty; 450 __attribute__((aligned(64))) std::atomic_size_t mask = { 0 }; 419 451 } tls; 420 452 453 private: 454 const unsigned numLists; 455 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t<node_t> []> lists; 456 private: 457 #if VARIANT == SNZI || VARIANT == BACK 458 snzi_t snzi; 459 #elif VARIANT == BIAS || VARIANT == BACKBIAS 460 #ifdef SNZI_PACKED 461 snzip_t snzi; 462 #else 463 snzi_t snzi; 464 #endif 465 #elif VARIANT == SNZM || VARIANT == DISCOVER 466 snzm_t snzm; 467 #else 468 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists 469 #endif 470 #if VARIANT == BITMASK 471 std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty 472 #endif 473 421 474 public: 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 424 private: 425 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists; 426 const unsigned numLists; 427 428 public: 429 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t); 475 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t<node_t>); 476 static std::atomic_uint32_t ticket; 430 477 431 478 #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 479 static void stats_tls_tally() { 441 480 global_stats.pick.push.attempt += tls.pick.push.attempt; 442 481 global_stats.pick.push.success += tls.pick.push.success; 482 global_stats.pick.push.local += tls.pick.push.local; 443 483 global_stats.pick.pop .attempt += tls.pick.pop.attempt; 444 484 global_stats.pick.pop .success += tls.pick.pop.success; 445 485 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt; 486 global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset; 487 global_stats.pick.pop .local += tls.pick.pop.local; 446 488 447 489 global_stats.qstat.push.value += tls.empty.push.value; … … 457 499 std::atomic_size_t attempt = { 0 }; 458 500 std::atomic_size_t success = { 0 }; 501 std::atomic_size_t local = { 0 }; 459 502 } push; 460 503 struct { … … 462 505 std::atomic_size_t success = { 0 }; 463 506 std::atomic_size_t mask_attempt = { 0 }; 507 std::atomic_size_t mask_reset = { 0 }; 508 std::atomic_size_t local = { 0 }; 464 509 } pop; 465 510 } pick; … … 476 521 } global_stats; 477 522 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 ) { 523 public: 524 static void stats_print(std::ostream & os ) { 484 525 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 526 501 527 const auto & global = global_stats; … … 504 530 double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt); 505 531 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"; 532 double rpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_reset); 533 534 double push_len = double(global.pick.push.attempt ) / global.pick.push.success; 535 double pop_len = double(global.pick.pop .attempt ) / global.pick.pop .success; 536 double mpop_len = double(global.pick.pop .mask_attempt) / global.pick.pop .success; 537 double rpop_len = double(global.pick.pop .mask_reset ) / global.pick.pop .success; 538 539 os << "Push Pick : " << push_sur << " %, len " << push_len << " (" << global.pick.push.attempt << " / " << global.pick.push.success << ")\n"; 540 os << "Pop Pick : " << pop_sur << " %, len " << pop_len << " (" << global.pick.pop .attempt << " / " << global.pick.pop .success << ")\n"; 541 os << "TryPop Pick : " << mpop_sur << " %, len " << mpop_len << " (" << global.pick.pop .mask_attempt << " / " << global.pick.pop .success << ")\n"; 542 os << "Pop M Reset : " << rpop_sur << " %, len " << rpop_len << " (" << global.pick.pop .mask_reset << " / " << global.pick.pop .success << ")\n"; 510 543 511 544 double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count; … … 515 548 os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n"; 516 549 os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n"; 550 551 os << "Local Push : " << global.pick.push.local << "\n"; 552 os << "Local Pop : " << global.pick.pop .local << "\n"; 517 553 } 518 554 #endif
Note:
See TracChangeset
for help on using the changeset viewer.
