Changes in / [2802824:2f1cb37]
- Location:
- doc/theses/thierry_delisle_PhD/code
- Files:
-
- 1 deleted
- 2 edited
-
relaxed_list.hpp (modified) (14 diffs)
-
snzi.hpp (deleted)
-
utils.hpp (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
r2802824 r2f1cb37 11 11 #include "assert.hpp" 12 12 #include "utils.hpp" 13 #include "snzi.hpp"14 13 15 14 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 } 16 70 17 71 extern bool enable_stats; … … 26 80 size_t success = 0; 27 81 size_t mask_attempt = 0; 28 size_t mask_reset = 0;29 82 } pop; 30 83 }; … … 56 109 : lists(new intrusive_queue_t[numLists]) 57 110 , numLists(numLists) 58 #if defined(SIMPLE_SNZI)59 , snzi(4)60 #endif61 111 { 62 112 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists"); … … 89 139 if( !lists[i].lock.try_lock() ) continue; 90 140 91 #if !defined(SIMPLE_SNZI) 92 __attribute__((unused)) int num = numNonEmpty; 93 #endif 141 __attribute__((unused)) int num = numNonEmpty; 94 142 95 143 // Actually push it 96 144 if(lists[i].push(node)) { 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 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); 119 154 120 155 // Unlock and return … … 123 158 #ifndef NO_STATS 124 159 tls.pick.push.success++; 125 #if !defined(SIMPLE_SNZI) 126 tls.empty.push.value += num; 127 tls.empty.push.count += 1; 128 #endif 160 tls.empty.push.value += num; 161 tls.empty.push.count += 1; 129 162 #endif 130 163 return; … … 133 166 134 167 __attribute__((noinline, hot)) node_t * pop() { 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) 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 // } 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 random 182 // i = tls.rng.next() % numLists; 183 // j = tls.rng.next() % numLists; 184 // } else 180 185 { 186 #ifndef NO_STATS 187 // tls.pick.push.mask_attempt++; 188 #endif 189 181 190 // Pick two lists at random 182 191 unsigned num = ((numLists - 1) >> 6) + 1; … … 227 236 #endif 228 237 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 #endif233 234 238 // Pick the bet list 235 239 int w = i; … … 245 249 if( !list.lock.try_lock() ) return nullptr; 246 250 247 #if !defined(SIMPLE_SNZI) 248 __attribute__((unused)) int num = numNonEmpty; 249 #endif 251 __attribute__((unused)) int num = numNonEmpty; 250 252 251 253 // If list is empty, unlock and retry … … 262 264 263 265 if(emptied) { 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 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); 282 273 } 283 274 284 275 // Unlock and return 285 276 list.lock.unlock(); 286 #if !defined(SIMPLE_SNZI) 287 assert(numNonEmpty >= 0); 288 #endif 277 assert(numNonEmpty >= 0); 289 278 #ifndef NO_STATS 290 279 tls.pick.pop.success++; 291 #if !defined(SIMPLE_SNZI) 292 tls.empty.pop.value += num; 293 tls.empty.pop.count += 1; 294 #endif 280 tls.empty.pop.value += num; 281 tls.empty.pop.count += 1; 295 282 #endif 296 283 return node; … … 309 296 size_t push = 0; 310 297 size_t pop = 0; 298 // size_t value = 0; 299 // size_t count = 0; 311 300 }; 312 301 … … 428 417 pick_stat pick; 429 418 empty_stat empty; 430 __attribute__((aligned(64))) std::atomic_size_t mask = { 0 };431 419 } tls; 432 420 421 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 433 424 private: 434 425 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists; 435 426 const unsigned numLists; 436 private:437 #if defined(SIMPLE_SNZI)438 snzi_t snzi;439 #else440 std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists441 std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty442 #endif443 427 444 428 public: … … 460 444 global_stats.pick.pop .success += tls.pick.pop.success; 461 445 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt; 462 global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;463 446 464 447 global_stats.qstat.push.value += tls.empty.push.value; … … 479 462 std::atomic_size_t success = { 0 }; 480 463 std::atomic_size_t mask_attempt = { 0 }; 481 std::atomic_size_t mask_reset = { 0 };482 464 } pop; 483 465 } pick; … … 522 504 double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt); 523 505 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);525 506 526 507 os << "Push Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n"; 527 508 os << "Pop Pick % : " << pop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n"; 528 509 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";530 510 531 511 double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count; -
doc/theses/thierry_delisle_PhD/code/utils.hpp
r2802824 r2f1cb37 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.
