Changes in / [2f1cb37:2802824]
- Location:
- doc/theses/thierry_delisle_PhD/code
- Files:
-
- 1 added
- 2 edited
-
relaxed_list.hpp (modified) (14 diffs)
-
snzi.hpp (added)
-
utils.hpp (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r2f1cb37 r2802824 11 11 #include "assert.hpp" 12 12 #include "utils.hpp" 13 #include "snzi.hpp" 13 14 14 15 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 16 71 17 extern bool enable_stats; … … 80 26 size_t success = 0; 81 27 size_t mask_attempt = 0; 28 size_t mask_reset = 0; 82 29 } pop; 83 30 }; … … 109 56 : lists(new intrusive_queue_t[numLists]) 110 57 , numLists(numLists) 58 #if defined(SIMPLE_SNZI) 59 , snzi(4) 60 #endif 111 61 { 112 62 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists"); … … 139 89 if( !lists[i].lock.try_lock() ) continue; 140 90 141 __attribute__((unused)) int num = numNonEmpty; 91 #if !defined(SIMPLE_SNZI) 92 __attribute__((unused)) int num = numNonEmpty; 93 #endif 142 94 143 95 // Actually push it 144 96 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); 97 #if defined(DISCOVER_BITMASK) 98 size_t qword = i >> 6ull; 99 size_t bit = i & 63ull; 100 assert(qword == 0); 101 bts(tls.mask, bit); 102 #elif defined(SIMPLE_SNZI) 103 snzi.arrive(i); 104 #elif !defined(NO_BITMASK) 105 numNonEmpty++; 106 size_t qword = i >> 6ull; 107 size_t bit = i & 63ull; 108 assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 109 __attribute__((unused)) bool ret = bts(list_mask[qword], bit); 110 assert(!ret); 111 assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit)); 112 #else 113 numNonEmpty++; 114 #endif 115 } 116 #if !defined(SIMPLE_SNZI) 117 assert(numNonEmpty <= (int)numLists); 118 #endif 154 119 155 120 // Unlock and return … … 158 123 #ifndef NO_STATS 159 124 tls.pick.push.success++; 160 tls.empty.push.value += num; 161 tls.empty.push.count += 1; 125 #if !defined(SIMPLE_SNZI) 126 tls.empty.push.value += num; 127 tls.empty.push.count += 1; 128 #endif 162 129 #endif 163 130 return; … … 166 133 167 134 __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 // } 135 #if defined(DISCOVER_BITMASK) 136 assert(numLists <= 64); 137 while(true) { 138 tls.pick.pop.mask_attempt++; 139 unsigned i, j; 140 { 141 // Pick two lists at random 142 unsigned num = ((numLists - 1) >> 6) + 1; 143 144 // Pick first list totally randomly 145 i = tls.rng.next() % numLists; 146 147 // Pick the other according to the bitmask 148 unsigned r = tls.rng.next(); 149 150 size_t mask = tls.mask.load(std::memory_order_relaxed); 151 if(mask == 0) { 152 tls.pick.pop.mask_reset++; 153 mask = (1U << numLists) - 1; 154 } 155 156 unsigned b = rand_bit(r, mask); 157 158 assertf(b < 64, "%zu %u", mask, b); 159 160 j = b; 161 162 assert(j < numLists); 163 } 164 165 if(auto node = try_pop(i, j)) return node; 166 } 167 #elif defined(SIMPLE_SNZI) 168 while(snzi.query()) { 169 // Pick two lists at random 170 int i = tls.rng.next() % numLists; 171 int j = tls.rng.next() % numLists; 172 173 if(auto node = try_pop(i, j)) return node; 174 } 175 #elif !defined(NO_BITMASK) 176 176 int nnempty; 177 177 while(0 != (nnempty = numNonEmpty)) { 178 178 tls.pick.pop.mask_attempt++; 179 179 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 180 { 186 #ifndef NO_STATS187 // tls.pick.push.mask_attempt++;188 #endif189 190 181 // Pick two lists at random 191 182 unsigned num = ((numLists - 1) >> 6) + 1; … … 236 227 #endif 237 228 229 #if defined(DISCOVER_BITMASK) 230 if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i); 231 if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j); 232 #endif 233 238 234 // Pick the bet list 239 235 int w = i; … … 249 245 if( !list.lock.try_lock() ) return nullptr; 250 246 251 __attribute__((unused)) int num = numNonEmpty; 247 #if !defined(SIMPLE_SNZI) 248 __attribute__((unused)) int num = numNonEmpty; 249 #endif 252 250 253 251 // If list is empty, unlock and retry … … 264 262 265 263 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); 264 #if defined(DISCOVER_BITMASK) 265 size_t qword = w >> 6ull; 266 size_t bit = w & 63ull; 267 assert(qword == 0); 268 __attribute__((unused)) bool ret = btr(tls.mask, bit); 269 #elif defined(SIMPLE_SNZI) 270 snzi.depart(w); 271 #elif !defined(NO_BITMASK) 272 numNonEmpty--; 273 size_t qword = w >> 6ull; 274 size_t bit = w & 63ull; 275 assert((list_mask[qword] & (1ul << bit)) != 0); 276 __attribute__((unused)) bool ret = btr(list_mask[qword], bit); 277 assert(ret); 278 assert((list_mask[qword] & (1ul << bit)) == 0); 279 #else 280 numNonEmpty--; 281 #endif 273 282 } 274 283 275 284 // Unlock and return 276 285 list.lock.unlock(); 277 assert(numNonEmpty >= 0); 286 #if !defined(SIMPLE_SNZI) 287 assert(numNonEmpty >= 0); 288 #endif 278 289 #ifndef NO_STATS 279 290 tls.pick.pop.success++; 280 tls.empty.pop.value += num; 281 tls.empty.pop.count += 1; 291 #if !defined(SIMPLE_SNZI) 292 tls.empty.pop.value += num; 293 tls.empty.pop.count += 1; 294 #endif 282 295 #endif 283 296 return node; … … 296 309 size_t push = 0; 297 310 size_t pop = 0; 298 // size_t value = 0;299 // size_t count = 0;300 311 }; 301 312 … … 417 428 pick_stat pick; 418 429 empty_stat empty; 430 __attribute__((aligned(64))) std::atomic_size_t mask = { 0 }; 419 431 } tls; 420 432 421 public:422 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists423 std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty424 433 private: 425 434 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists; 426 435 const unsigned numLists; 436 private: 437 #if defined(SIMPLE_SNZI) 438 snzi_t snzi; 439 #else 440 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists 441 std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty 442 #endif 427 443 428 444 public: … … 444 460 global_stats.pick.pop .success += tls.pick.pop.success; 445 461 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt; 462 global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset; 446 463 447 464 global_stats.qstat.push.value += tls.empty.push.value; … … 462 479 std::atomic_size_t success = { 0 }; 463 480 std::atomic_size_t mask_attempt = { 0 }; 481 std::atomic_size_t mask_reset = { 0 }; 464 482 } pop; 465 483 } pick; … … 504 522 double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt); 505 523 double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt); 524 double rpop_sur = (100.0 * double(global.pick.pop .mask_reset) / global.pick.pop .mask_attempt); 506 525 507 526 os << "Push Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n"; 508 527 os << "Pop Pick % : " << pop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n"; 509 528 os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n"; 529 os << "Pop M Reset % : " << rpop_sur << "(" << global.pick.pop .mask_reset << " / " << global.pick.pop .mask_attempt << ")\n"; 510 530 511 531 double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count; -
doc/theses/thierry_delisle_PhD/code/utils.hpp
r2f1cb37 r2802824 143 143 #endif 144 144 } 145 146 struct spinlock_t { 147 std::atomic_bool ll = { false }; 148 149 inline void lock() { 150 while( __builtin_expect(ll.exchange(true),false) ) { 151 while(ll.load(std::memory_order_relaxed)) 152 asm volatile("pause"); 153 } 154 } 155 156 inline bool try_lock() { 157 return false == ll.exchange(true); 158 } 159 160 inline void unlock() { 161 ll.store(false, std::memory_order_release); 162 } 163 164 inline explicit operator bool() { 165 return ll.load(std::memory_order_relaxed); 166 } 167 }; 168 169 static inline bool bts(std::atomic_size_t & target, size_t bit ) { 170 //* 171 int result = 0; 172 asm volatile( 173 "LOCK btsq %[bit], %[target]\n\t" 174 :"=@ccc" (result) 175 : [target] "m" (target), [bit] "r" (bit) 176 ); 177 return result != 0; 178 /*/ 179 size_t mask = 1ul << bit; 180 size_t ret = target.fetch_or(mask, std::memory_order_relaxed); 181 return (ret & mask) != 0; 182 //*/ 183 } 184 185 static inline bool btr(std::atomic_size_t & target, size_t bit ) { 186 //* 187 int result = 0; 188 asm volatile( 189 "LOCK btrq %[bit], %[target]\n\t" 190 :"=@ccc" (result) 191 : [target] "m" (target), [bit] "r" (bit) 192 ); 193 return result != 0; 194 /*/ 195 size_t mask = 1ul << bit; 196 size_t ret = target.fetch_and(~mask, std::memory_order_relaxed); 197 return (ret & mask) != 0; 198 //*/ 199 }
Note: See TracChangeset
for help on using the changeset viewer.
