Context Navigation

source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ 8f4f3e0

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 8f4f3e0 was 8f4f3e0, checked in by Thierry Delisle <tdelisle@…>, 4 years ago
bitmask discovery no use snzi
Property mode set to `100644`
File size: 14.1 KB

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

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

Download in other formats: