Context Navigation

source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ 9da5a50

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 9da5a50 was 9da5a50, checked in by Thierry Delisle <tdelisle@…>, 3 years ago
Added new DISCOVER_BITMASK algorithm as a potential ready queue sub-algorithm. It offers may be an improvement but doesn't reduce the contention for the counter
Property mode set to `100644`
File size: 14.4 KB

Line
1	#pragma once
2
3	#ifndef NO_STATS
4	#include <iostream>
5	#endif
6
7	#include <memory>
8	#include <mutex>
9	#include <type_traits>
10
11	#include "assert.hpp"
12	#include "utils.hpp"
13
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	}
70
71	extern bool enable_stats;
72
73	struct pick_stat {
74	struct {
75	size_t attempt = 0;
76	size_t success = 0;
77	} push;
78	struct {
79	size_t attempt = 0;
80	size_t success = 0;
81	size_t mask_attempt = 0;
82	size_t mask_reset = 0;
83	} pop;
84	};
85
86	struct empty_stat {
87	struct {
88	size_t value = 0;
89	size_t count = 0;
90	} push;
91	struct {
92	size_t value = 0;
93	size_t count = 0;
94	} pop;
95	};
96
97	template<typename node_t>
98	struct _LinksFields_t {
99	node_t * prev = nullptr;
100	node_t * next = nullptr;
101	unsigned long long ts = 0;
102	};
103
104	template<typename node_t>
105	class __attribute__((aligned(128))) relaxed_list {
106	static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
107
108	public:
109	relaxed_list(unsigned numLists)
110	: lists(new intrusive_queue_t[numLists])
111	, numLists(numLists)
112	{
113	assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
114	// assert(sizeof(*this) == 128);
115	std::cout << "Constructing Relaxed List with " << numLists << std::endl;
116
117	#ifndef NO_STATS
118	if(head) this->next = head;
119	head = this;
120	#endif
121	}
122
123	~relaxed_list() {
124	std::cout << "Destroying Relaxed List" << std::endl;
125	lists.reset();
126	}
127
128	__attribute__((noinline, hot)) void push(node_t * node) {
129	node->_links.ts = rdtscl();
130
131	while(true) {
132	// Pick a random list
133	unsigned i = tls.rng.next() % numLists;
134
135	#ifndef NO_STATS
136	tls.pick.push.attempt++;
137	#endif
138
139	// If we can't lock it retry
140	if( !lists[i].lock.try_lock() ) continue;
141
142	__attribute__((unused)) int num = numNonEmpty;
143
144	// Actually push it
145	if(lists[i].push(node)) {
146	#if defined(DISCOVER_BITMASK)
147	size_t qword = i >> 6ull;
148	size_t bit = i & 63ull;
149	assert(qword == 0);
150	bts(tls.mask, bit);
151	#elif !defined(NO_BITMASK)
152	numNonEmpty++;
153	size_t qword = i >> 6ull;
154	size_t bit = i & 63ull;
155	assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
156	__attribute__((unused)) bool ret = bts(list_mask[qword], bit);
157	assert(!ret);
158	assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
159	#else
160	numNonEmpty++;
161	#endif
162	}
163	assert(numNonEmpty <= (int)numLists);
164
165	// Unlock and return
166	lists[i].lock.unlock();
167
168	#ifndef NO_STATS
169	tls.pick.push.success++;
170	tls.empty.push.value += num;
171	tls.empty.push.count += 1;
172	#endif
173	return;
174	}
175	}
176
177	__attribute__((noinline, hot)) node_t * pop() {
178	#if defined(DISCOVER_BITMASK)
179	assert(numLists <= 64);
180	while(true) {
181	tls.pick.pop.mask_attempt++;
182	unsigned i, j;
183	{
184	// Pick two lists at random
185	unsigned num = ((numLists - 1) >> 6) + 1;
186
187	// Pick first list totally randomly
188	i = tls.rng.next() % numLists;
189
190	// Pick the other according to the bitmask
191	unsigned r = tls.rng.next();
192
193	size_t mask = tls.mask.load(std::memory_order_relaxed);
194	if(mask == 0) {
195	tls.pick.pop.mask_reset++;
196	mask = (1U << numLists) - 1;
197	}
198
199	unsigned b = rand_bit(r, mask);
200
201	assertf(b < 64, "%zu %u", mask, b);
202
203	j = b;
204
205	assert(j < numLists);
206	}
207
208	if(auto node = try_pop(i, j)) return node;
209	}
210	#elif !defined(NO_BITMASK)
211	int nnempty;
212	while(0 != (nnempty = numNonEmpty)) {
213	tls.pick.pop.mask_attempt++;
214	unsigned i, j;
215	{
216	// Pick two lists at random
217	unsigned num = ((numLists - 1) >> 6) + 1;
218
219	unsigned ri = tls.rng.next();
220	unsigned rj = tls.rng.next();
221
222	unsigned wdxi = (ri >> 6u) % num;
223	unsigned wdxj = (rj >> 6u) % num;
224
225	size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
226	size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
227
228	if(maski == 0 && maskj == 0) continue;
229
230	unsigned bi = rand_bit(ri, maski);
231	unsigned bj = rand_bit(rj, maskj);
232
233	assertf(bi < 64, "%zu %u", maski, bi);
234	assertf(bj < 64, "%zu %u", maskj, bj);
235
236	i = bi \| (wdxi << 6);
237	j = bj \| (wdxj << 6);
238
239	assertf(i < numLists, "%u", wdxi << 6);
240	assertf(j < numLists, "%u", wdxj << 6);
241	}
242
243	if(auto node = try_pop(i, j)) return node;
244	}
245	#else
246	while(numNonEmpty != 0) {
247	// Pick two lists at random
248	int i = tls.rng.next() % numLists;
249	int j = tls.rng.next() % numLists;
250
251	if(auto node = try_pop(i, j)) return node;
252	}
253	#endif
254
255	return nullptr;
256	}
257
258	private:
259	node_t * try_pop(unsigned i, unsigned j) {
260	#ifndef NO_STATS
261	tls.pick.pop.attempt++;
262	#endif
263
264	#if defined(DISCOVER_BITMASK)
265	if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i);
266	if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j);
267	#endif
268
269	// Pick the bet list
270	int w = i;
271	if( __builtin_expect(lists[j].ts() != 0, true) ) {
272	w = (lists[i].ts() < lists[j].ts()) ? i : j;
273	}
274
275	auto & list = lists[w];
276	// If list looks empty retry
277	if( list.ts() == 0 ) return nullptr;
278
279	// If we can't get the lock retry
280	if( !list.lock.try_lock() ) return nullptr;
281
282	__attribute__((unused)) int num = numNonEmpty;
283
284	// If list is empty, unlock and retry
285	if( list.ts() == 0 ) {
286	list.lock.unlock();
287	return nullptr;
288	}
289
290	// Actually pop the list
291	node_t * node;
292	bool emptied;
293	std::tie(node, emptied) = list.pop();
294	assert(node);
295
296	if(emptied) {
297	#if defined(DISCOVER_BITMASK)
298	size_t qword = w >> 6ull;
299	size_t bit = w & 63ull;
300	assert(qword == 0);
301	__attribute__((unused)) bool ret = btr(tls.mask, bit);
302	#elif !defined(NO_BITMASK)
303	numNonEmpty--;
304	size_t qword = w >> 6ull;
305	size_t bit = w & 63ull;
306	assert((list_mask[qword] & (1ul << bit)) != 0);
307	__attribute__((unused)) bool ret = btr(list_mask[qword], bit);
308	assert(ret);
309	assert((list_mask[qword] & (1ul << bit)) == 0);
310	#else
311	numNonEmpty--;
312	#endif
313	}
314
315	// Unlock and return
316	list.lock.unlock();
317	assert(numNonEmpty >= 0);
318	#ifndef NO_STATS
319	tls.pick.pop.success++;
320	tls.empty.pop.value += num;
321	tls.empty.pop.count += 1;
322	#endif
323	return node;
324	}
325
326	private:
327
328	class __attribute__((aligned(128))) intrusive_queue_t {
329	public:
330	typedef spinlock_t lock_t;
331
332	friend class relaxed_list<node_t>;
333
334	struct stat {
335	ssize_t diff = 0;
336	size_t push = 0;
337	size_t pop = 0;
338	// size_t value = 0;
339	// size_t count = 0;
340	};
341
342	private:
343	struct sentinel_t {
344	_LinksFields_t<node_t> _links;
345	};
346
347	lock_t lock;
348	sentinel_t before;
349	sentinel_t after;
350	#ifndef NO_STATS
351	stat s;
352	#endif
353
354	#pragma GCC diagnostic push
355	#pragma GCC diagnostic ignored "-Winvalid-offsetof"
356	static constexpr auto fields_offset = offsetof( node_t, _links );
357	#pragma GCC diagnostic pop
358	public:
359	intrusive_queue_t()
360	: before{{ nullptr, tail() }}
361	, after {{ head(), nullptr }}
362	{
363	/* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
364	/* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
365	/* paranoid */ assert(head()->_links.prev == nullptr);
366	/* paranoid */ assert(head()->_links.next == tail() );
367	/* paranoid */ assert(tail()->_links.next == nullptr);
368	/* paranoid */ assert(tail()->_links.prev == head() );
369	/* paranoid / assert(sizeof(this) == 128);
370	/* paranoid */ assert((intptr_t(this) % 128) == 0);
371	}
372
373	~intrusive_queue_t() = default;
374
375	inline node_t * head() const {
376	node_t * rhead = reinterpret_cast<node_t *>(
377	reinterpret_cast<uintptr_t>( &before ) - fields_offset
378	);
379	assert(rhead);
380	return rhead;
381	}
382
383	inline node_t * tail() const {
384	node_t * rtail = reinterpret_cast<node_t *>(
385	reinterpret_cast<uintptr_t>( &after ) - fields_offset
386	);
387	assert(rtail);
388	return rtail;
389	}
390
391	inline bool push(node_t * node) {
392	assert(lock);
393	assert(node->_links.ts != 0);
394	node_t * tail = this->tail();
395
396	node_t * prev = tail->_links.prev;
397	// assertf(node->_links.ts >= prev->_links.ts,
398	// "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
399	node->_links.next = tail;
400	node->_links.prev = prev;
401	prev->_links.next = node;
402	tail->_links.prev = node;
403	#ifndef NO_STATS
404	if(enable_stats) {
405	s.diff++;
406	s.push++;
407	}
408	#endif
409	if(before._links.ts == 0l) {
410	before._links.ts = node->_links.ts;
411	assert(node->_links.prev == this->head());
412	return true;
413	}
414	return false;
415	}
416
417	inline std::pair<node_t *, bool> pop() {
418	assert(lock);
419	node_t * head = this->head();
420	node_t * tail = this->tail();
421
422	node_t * node = head->_links.next;
423	node_t * next = node->_links.next;
424	if(node == tail) return {nullptr, false};
425
426	head->_links.next = next;
427	next->_links.prev = head;
428
429	#ifndef NO_STATS
430	if(enable_stats) {
431	s.diff--;
432	s.pop ++;
433	}
434	#endif
435	if(next == tail) {
436	before._links.ts = 0l;
437	return {node, true};
438	}
439	else {
440	assert(next->_links.ts != 0);
441	before._links.ts = next->_links.ts;
442	assert(before._links.ts != 0);
443	return {node, false};
444	}
445	}
446
447	long long ts() const {
448	return before._links.ts;
449	}
450	};
451
452
453	public:
454
455	static __attribute__((aligned(128))) thread_local struct TLS {
456	Random rng = { int(rdtscl()) };
457	pick_stat pick;
458	empty_stat empty;
459	__attribute__((aligned(64))) std::atomic_size_t mask = { 0 };
460	} tls;
461
462	public:
463	std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists
464	std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
465	private:
466	__attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
467	const unsigned numLists;
468
469	public:
470	static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
471
472	#ifndef NO_STATS
473	static void stats_print(std::ostream & os) {
474	auto it = head;
475	while(it) {
476	it->stats_print_local(os);
477	it = it->next;
478	}
479	}
480
481	static void stats_tls_tally() {
482	global_stats.pick.push.attempt += tls.pick.push.attempt;
483	global_stats.pick.push.success += tls.pick.push.success;
484	global_stats.pick.pop .attempt += tls.pick.pop.attempt;
485	global_stats.pick.pop .success += tls.pick.pop.success;
486	global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
487	global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;
488
489	global_stats.qstat.push.value += tls.empty.push.value;
490	global_stats.qstat.push.count += tls.empty.push.count;
491	global_stats.qstat.pop .value += tls.empty.pop .value;
492	global_stats.qstat.pop .count += tls.empty.pop .count;
493	}
494
495	private:
496	static struct GlobalStats {
497	struct {
498	struct {
499	std::atomic_size_t attempt = { 0 };
500	std::atomic_size_t success = { 0 };
501	} push;
502	struct {
503	std::atomic_size_t attempt = { 0 };
504	std::atomic_size_t success = { 0 };
505	std::atomic_size_t mask_attempt = { 0 };
506	std::atomic_size_t mask_reset = { 0 };
507	} pop;
508	} pick;
509	struct {
510	struct {
511	std::atomic_size_t value = { 0 };
512	std::atomic_size_t count = { 0 };
513	} push;
514	struct {
515	std::atomic_size_t value = { 0 };
516	std::atomic_size_t count = { 0 };
517	} pop;
518	} qstat;
519	} global_stats;
520
521	// Link list of all lists for stats
522	__attribute__((aligned(64))) relaxed_list<node_t> * next = nullptr;
523
524	static relaxed_list<node_t> * head;
525
526	void stats_print_local(std::ostream & os ) {
527	std::cout << "----- Relaxed List Stats -----" << std::endl;
528	{
529	ssize_t diff = 0;
530	size_t num = 0;
531	ssize_t max = 0;
532
533	for(size_t i = 0; i < numLists; i++) {
534	const auto & list = lists[i];
535	diff+= list.s.diff;
536	num ++;
537	max = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;
538	os << "Local Q ops : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";
539	}
540
541	os << "Difference : " << ssize_t(double(diff) / num ) << " avg\t" << max << "max" << std::endl;
542	}
543
544	const auto & global = global_stats;
545
546	double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
547	double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
548	double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
549	double rpop_sur = (100.0 * double(global.pick.pop .mask_reset) / global.pick.pop .mask_attempt);
550
551	os << "Push Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
552	os << "Pop Pick % : " << pop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
553	os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
554	os << "Pop M Reset % : " << rpop_sur << "(" << global.pick.pop .mask_reset << " / " << global.pick.pop .mask_attempt << ")\n";
555
556	double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
557	double avgQ_pop = double(global.qstat.pop .value) / global.qstat.pop .count;
558	double avgQ = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
559	os << "Push Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
560	os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n";
561	os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
562	}
563	#endif
564	};

Note: See TracBrowser for help on using the repository browser.

Download in other formats: