Changeset 50aeb6f for doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
- Timestamp:
- Sep 26, 2019, 4:25:04 PM (4 years ago)
- Branches:
- arm-eh, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 1e24d13
- Parents:
- b2a37b0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
rb2a37b0 r50aeb6f 1 1 #pragma once 2 2 3 #ifndef NO_STATS 3 4 #include <iostream> 5 #endif 6 4 7 #include <memory> 5 8 #include <mutex> … … 11 14 using namespace std; 12 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 13 40 extern bool enable_stats; 14 41 15 16 42 struct pick_stat { 17 size_t attempt = 0; 18 size_t success = 0; 19 }; 20 21 extern __attribute__((aligned(64))) thread_local pick_stat local_pick; 43 struct { 44 size_t attempt = 0; 45 size_t success = 0; 46 } push; 47 struct { 48 size_t attempt = 0; 49 size_t success = 0; 50 } pop; 51 }; 22 52 23 53 template<typename node_t> … … 28 58 }; 29 59 30 struct spinlock_t {31 std::atomic_bool ll = { false };32 33 inline void lock() {34 while( __builtin_expect(ll.exchange(true),false) ) {35 while(ll.load(std::memory_order_relaxed))36 asm volatile("pause");37 }38 }39 40 inline void unlock() {41 ll.store(false, std::memory_order_release);42 }43 };44 45 60 template<typename node_t> 46 class relaxed_list {61 class __attribute__((aligned(128))) relaxed_list { 47 62 static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field"); 48 63 … … 50 65 public: 51 66 relaxed_list(unsigned numLists) 52 : numLists(numLists)67 : numNonEmpty{0} 53 68 , lists(new intrusive_queue_t[numLists]) 54 , numNonEmpty(0)69 , numLists(numLists) 55 70 {} 56 71 57 void push(node_t * node) { 58 int i = rng_g.next() % numLists; 59 lists[i].push(node, numNonEmpty); 72 ~relaxed_list() { 73 lists.reset(); 74 #ifndef NO_STATS 75 std::cout << "Difference : " 76 << size_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num ) << " avg\t" 77 << intrusive_queue_t::stat::dif.max << "max" << std::endl; 78 #endif 79 } 80 81 __attribute__((noinline, hot)) void push(node_t * node) { 82 node->_links.ts = rdtscl(); 83 84 while(true) { 85 // Pick a random list 86 int i = tls.rng.next() % numLists; 87 88 #ifndef NO_STATS 89 tls.pick.push.attempt++; 90 #endif 91 92 // If we can't lock it retry 93 if( !lists[i].lock.try_lock() ) continue; 94 95 // Actually push it 96 lists[i].push(node, numNonEmpty); 97 assert(numNonEmpty <= (int)numLists); 98 99 // Unlock and return 100 lists[i].lock.unlock(); 101 102 #ifndef NO_STATS 103 tls.pick.push.success++; 104 #endif 105 return; 106 } 60 107 } 61 108 62 node_t * pop() { 63 int i = pickRandomly(-1); 64 int j = pickRandomly(i); 65 66 if(i == -1) { 67 return nullptr; 68 } 69 70 auto guard = lock(i, j); 71 auto & list = best(i, j); 72 return list.pop(numNonEmpty); 109 __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 } 150 151 return nullptr; 73 152 } 74 153 75 node_t * pop2() {76 int i = pickRandomly(-1);77 int j = pickRandomly(i);78 79 if(i == -1) {80 return nullptr;81 }82 83 auto & list = best2(i, j);84 return list.pop2(numNonEmpty);85 }86 87 154 private: 88 155 89 class intrusive_queue_t {156 class __attribute__((aligned(128))) intrusive_queue_t { 90 157 public: 91 158 typedef spinlock_t lock_t; 92 159 93 160 friend class relaxed_list<node_t>; 161 162 struct stat { 163 ssize_t diff = 0; 164 165 static struct Dif { 166 ssize_t value = 0; 167 size_t num = 0; 168 ssize_t max = 0; 169 } dif; 170 }; 94 171 95 172 private: … … 98 175 }; 99 176 100 struct stat { 101 size_t push = 0; 102 size_t pop = 0; 103 }; 104 105 __attribute__((aligned(64))) lock_t lock; 106 __attribute__((aligned(64))) bool empty; 107 stat s; 177 lock_t lock; 108 178 sentinel_t before; 109 179 sentinel_t after; 180 stat s; 110 181 111 182 static constexpr auto fields_offset = offsetof( node_t, _links ); 112 183 public: 113 184 intrusive_queue_t() 114 : empty(true) 115 , before{{ nullptr, tail() }} 185 : before{{ nullptr, tail() }} 116 186 , after {{ head(), nullptr }} 117 187 { … … 122 192 assert(tail()->_links.next == nullptr); 123 193 assert(tail()->_links.prev == head() ); 194 assert(sizeof(*this) == 128); 195 assert((intptr_t(this) % 128) == 0); 124 196 } 125 197 126 198 ~intrusive_queue_t() { 127 std::cout << " Push: " << s.push << "\tPop: " << s.pop << "\t(this: " << this << ")" << std::endl; 128 } 129 130 node_t * head() const { 131 return reinterpret_cast<node_t *>( 199 #ifndef NO_STATS 200 stat::dif.value+= s.diff; 201 stat::dif.num ++; 202 stat::dif.max = std::max(stat::dif.max, s.diff); 203 #endif 204 } 205 206 inline node_t * head() const { 207 node_t * rhead = reinterpret_cast<node_t *>( 132 208 reinterpret_cast<uintptr_t>( &before ) - fields_offset 133 209 ); 134 } 135 136 node_t * tail() const { 137 return reinterpret_cast<node_t *>( 210 assert(rhead); 211 return rhead; 212 } 213 214 inline node_t * tail() const { 215 node_t * rtail = reinterpret_cast<node_t *>( 138 216 reinterpret_cast<uintptr_t>( &after ) - fields_offset 139 217 ); 140 } 141 142 void push(node_t * node, volatile int & nonEmpty) { 218 assert(rtail); 219 return rtail; 220 } 221 222 inline void push(node_t * node, std::atomic_int & nonEmpty) { 223 assert(lock); 224 assert(node->_links.ts != 0); 143 225 node_t * tail = this->tail(); 144 std::lock_guard<lock_t> guard(lock);145 node->_links.ts = rdtscl();146 226 147 227 node_t * prev = tail->_links.prev; 148 228 // assertf(node->_links.ts >= prev->_links.ts, 149 // "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);229 // "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts); 150 230 node->_links.next = tail; 151 231 node->_links.prev = prev; 152 232 prev->_links.next = node; 153 233 tail->_links.prev = node; 154 if(empty) { 155 __atomic_fetch_add(&nonEmpty, 1, __ATOMIC_SEQ_CST); 156 empty = false; 157 } 158 if(enable_stats) s.push++; 159 } 160 161 node_t * pop(volatile int & nonEmpty) { 234 if(before._links.ts == 0l) { 235 nonEmpty += 1; 236 before._links.ts = node->_links.ts; 237 } 238 #ifndef NO_STATS 239 if(enable_stats) s.diff++; 240 #endif 241 } 242 243 inline node_t * pop(std::atomic_int & nonEmpty) { 244 assert(lock); 162 245 node_t * head = this->head(); 163 246 node_t * tail = this->tail(); … … 171 254 172 255 if(next == tail) { 173 empty = true; 174 __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST); 175 } 176 if(enable_stats) s.pop++; 256 before._links.ts = 0l; 257 nonEmpty -= 1; 258 } 259 else { 260 assert(next->_links.ts != 0); 261 before._links.ts = next->_links.ts; 262 assert(before._links.ts != 0); 263 } 264 #ifndef NO_STATS 265 if(enable_stats) s.diff--; 266 #endif 177 267 return node; 178 268 } 179 269 180 node_t * pop2(volatile int & nonEmpty) { 181 node_t * head = this->head(); 182 node_t * tail = this->tail(); 183 184 std::lock_guard<lock_t> guard(lock); 185 node_t * node = head->_links.next; 186 node_t * next = node->_links.next; 187 if(node == tail) return nullptr; 188 189 head->_links.next = next; 190 next->_links.prev = head; 191 192 if(next == tail) { 193 empty = true; 194 __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST); 195 } 196 if(enable_stats) s.pop++; 197 return node; 198 } 199 200 static intrusive_queue_t & best(intrusive_queue_t & lhs, intrusive_queue_t & rhs) { 201 bool lhs_empty = lhs.empty; 202 bool rhs_empty = rhs.empty; 203 204 if(lhs_empty && rhs_empty) return lhs; 205 if(!lhs_empty && rhs_empty) return lhs; 206 if(lhs_empty && !rhs_empty) return rhs; 207 node_t * lhs_head = lhs.head()->_links.next; 208 node_t * rhs_head = rhs.head()->_links.next; 209 210 assert(lhs_head != lhs.tail()); 211 assert(rhs_head != rhs.tail()); 212 213 if(lhs_head->_links.ts < lhs_head->_links.ts) { 214 return lhs; 215 } else { 216 return rhs; 217 } 218 } 219 220 static intrusive_queue_t & best2(intrusive_queue_t & lhs, intrusive_queue_t & rhs) { 221 node_t * lhs_head = lhs.head()->_links.next; 222 node_t * rhs_head = rhs.head()->_links.next; 223 224 bool lhs_empty = lhs_head != lhs.tail(); 225 bool rhs_empty = rhs_head != rhs.tail(); 226 if(lhs_empty && rhs_empty) return lhs; 227 if(!lhs_empty && rhs_empty) return lhs; 228 if(lhs_empty && !rhs_empty) return rhs; 229 230 if(lhs_head->_links.ts < lhs_head->_links.ts) { 231 return lhs; 232 } else { 233 return rhs; 234 } 270 long long ts() const { 271 return before._links.ts; 235 272 } 236 273 }; 237 274 238 275 276 public: 277 278 static __attribute__((aligned(128))) thread_local struct TLS { 279 Random rng = { int(rdtscl()) }; 280 pick_stat pick; 281 } tls; 282 239 283 private: 240 241 static thread_local Random rng_g; 242 __attribute__((aligned(64))) const unsigned numLists; 243 std::unique_ptr<intrusive_queue_t []> lists; 244 __attribute__((aligned(64))) volatile int numNonEmpty; // number of non-empty lists 245 246 247 private: 248 249 250 251 private: 252 int pickRandomly(const int avoid) { 253 int j; 254 do { 255 local_pick.attempt++; 256 j = rng_g.next() % numLists; 257 if (numNonEmpty < 1 + (avoid != -1)) return -1; 258 } while (j == avoid || lists[j].empty); 259 local_pick.success++; 260 return j; 261 } 262 263 private: 264 265 struct queue_guard { 266 intrusive_queue_t * lists; 267 int i, j; 268 269 queue_guard(intrusive_queue_t * lists, int i, int j) 270 : lists(lists), i(i), j(j) 271 { 272 if(i >= 0) lists[i].lock.lock(); 273 if(j >= 0) lists[j].lock.lock(); 274 } 275 276 queue_guard(const queue_guard &) = delete; 277 queue_guard(queue_guard &&) = default; 278 279 ~queue_guard() { 280 if(i >= 0) lists[i].lock.unlock(); 281 if(j >= 0) lists[j].lock.unlock(); 282 } 283 }; 284 285 auto lock(int i, int j) { 286 assert(i >= 0); 287 assert(i != j); 288 if(j < i) return queue_guard(lists.get(), j, i); 289 return queue_guard(lists.get(), i, j); 290 } 291 292 intrusive_queue_t & best(int i, int j) { 293 assert(i != -1); 294 if(j == -1) return lists[i]; 295 return intrusive_queue_t::best(lists[i], lists[j]); 296 } 297 298 intrusive_queue_t & best2(int i, int j) { 299 assert(i != -1); 300 if(j == -1) return lists[i]; 301 return intrusive_queue_t::best2(lists[i], lists[j]); 302 } 303 }; 284 std::atomic_int numNonEmpty; // number of non-empty lists 285 __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists; 286 const unsigned numLists; 287 288 public: 289 static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t); 290 };
Note: See TracChangeset
for help on using the changeset viewer.
