Context Navigation

source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ 7119daa

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

Last change on this file since 7119daa was 807a632, checked in by Thierry Delisle <tdelisle@…>, 5 years ago
Adding current version of the C++ relaxed_list code and benchmark
Property mode set to `100644`
File size: 13.1 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	} pop;
83	};
84
85	struct empty_stat {
86	struct {
87	size_t value = 0;
88	size_t count = 0;
89	} push;
90	struct {
91	size_t value = 0;
92	size_t count = 0;
93	} pop;
94	};
95
96	template<typename node_t>
97	struct _LinksFields_t {
98	node_t * prev = nullptr;
99	node_t * next = nullptr;
100	unsigned long long ts = 0;
101	};
102
103	template<typename node_t>
104	class __attribute__((aligned(128))) relaxed_list {
105	static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
106
107	public:
108	relaxed_list(unsigned numLists)
109	: lists(new intrusive_queue_t[numLists])
110	, numLists(numLists)
111	{
112	assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
113	// assert(sizeof(*this) == 128);
114	std::cout << "Constructing Relaxed List with " << numLists << std::endl;
115
116	#ifndef NO_STATS
117	if(head) this->next = head;
118	head = this;
119	#endif
120	}
121
122	~relaxed_list() {
123	std::cout << "Destroying Relaxed List" << std::endl;
124	lists.reset();
125	}
126
127	__attribute__((noinline, hot)) void push(node_t * node) {
128	node->_links.ts = rdtscl();
129
130	while(true) {
131	// Pick a random list
132	unsigned i = tls.rng.next() % numLists;
133
134	#ifndef NO_STATS
135	tls.pick.push.attempt++;
136	#endif
137
138	// If we can't lock it retry
139	if( !lists[i].lock.try_lock() ) continue;
140
141	__attribute__((unused)) int num = numNonEmpty;
142
143	// Actually push it
144	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);
154
155	// Unlock and return
156	lists[i].lock.unlock();
157
158	#ifndef NO_STATS
159	tls.pick.push.success++;
160	tls.empty.push.value += num;
161	tls.empty.push.count += 1;
162	#endif
163	return;
164	}
165	}
166
167	__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	// }
176	int nnempty;
177	while(0 != (nnempty = numNonEmpty)) {
178	tls.pick.pop.mask_attempt++;
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
185	{
186	#ifndef NO_STATS
187	// tls.pick.push.mask_attempt++;
188	#endif
189
190	// Pick two lists at random
191	unsigned num = ((numLists - 1) >> 6) + 1;
192
193	unsigned ri = tls.rng.next();
194	unsigned rj = tls.rng.next();
195
196	unsigned wdxi = (ri >> 6u) % num;
197	unsigned wdxj = (rj >> 6u) % num;
198
199	size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
200	size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
201
202	if(maski == 0 && maskj == 0) continue;
203
204	unsigned bi = rand_bit(ri, maski);
205	unsigned bj = rand_bit(rj, maskj);
206
207	assertf(bi < 64, "%zu %u", maski, bi);
208	assertf(bj < 64, "%zu %u", maskj, bj);
209
210	i = bi \| (wdxi << 6);
211	j = bj \| (wdxj << 6);
212
213	assertf(i < numLists, "%u", wdxi << 6);
214	assertf(j < numLists, "%u", wdxj << 6);
215	}
216
217	if(auto node = try_pop(i, j)) return node;
218	}
219	#else
220	while(numNonEmpty != 0) {
221	// Pick two lists at random
222	int i = tls.rng.next() % numLists;
223	int j = tls.rng.next() % numLists;
224
225	if(auto node = try_pop(i, j)) return node;
226	}
227	#endif
228
229	return nullptr;
230	}
231
232	private:
233	node_t * try_pop(unsigned i, unsigned j) {
234	#ifndef NO_STATS
235	tls.pick.pop.attempt++;
236	#endif
237
238	// Pick the bet list
239	int w = i;
240	if( __builtin_expect(lists[j].ts() != 0, true) ) {
241	w = (lists[i].ts() < lists[j].ts()) ? i : j;
242	}
243
244	auto & list = lists[w];
245	// If list looks empty retry
246	if( list.ts() == 0 ) return nullptr;
247
248	// If we can't get the lock retry
249	if( !list.lock.try_lock() ) return nullptr;
250
251	__attribute__((unused)) int num = numNonEmpty;
252
253	// If list is empty, unlock and retry
254	if( list.ts() == 0 ) {
255	list.lock.unlock();
256	return nullptr;
257	}
258
259	// Actually pop the list
260	node_t * node;
261	bool emptied;
262	std::tie(node, emptied) = list.pop();
263	assert(node);
264
265	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);
273	}
274
275	// Unlock and return
276	list.lock.unlock();
277	assert(numNonEmpty >= 0);
278	#ifndef NO_STATS
279	tls.pick.pop.success++;
280	tls.empty.pop.value += num;
281	tls.empty.pop.count += 1;
282	#endif
283	return node;
284	}
285
286	private:
287
288	class __attribute__((aligned(128))) intrusive_queue_t {
289	public:
290	typedef spinlock_t lock_t;
291
292	friend class relaxed_list<node_t>;
293
294	struct stat {
295	ssize_t diff = 0;
296	size_t push = 0;
297	size_t pop = 0;
298	// size_t value = 0;
299	// size_t count = 0;
300	};
301
302	private:
303	struct sentinel_t {
304	_LinksFields_t<node_t> _links;
305	};
306
307	lock_t lock;
308	sentinel_t before;
309	sentinel_t after;
310	#ifndef NO_STATS
311	stat s;
312	#endif
313
314	#pragma GCC diagnostic push
315	#pragma GCC diagnostic ignored "-Winvalid-offsetof"
316	static constexpr auto fields_offset = offsetof( node_t, _links );
317	#pragma GCC diagnostic pop
318	public:
319	intrusive_queue_t()
320	: before{{ nullptr, tail() }}
321	, after {{ head(), nullptr }}
322	{
323	/* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
324	/* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
325	/* paranoid */ assert(head()->_links.prev == nullptr);
326	/* paranoid */ assert(head()->_links.next == tail() );
327	/* paranoid */ assert(tail()->_links.next == nullptr);
328	/* paranoid */ assert(tail()->_links.prev == head() );
329	/* paranoid / assert(sizeof(this) == 128);
330	/* paranoid */ assert((intptr_t(this) % 128) == 0);
331	}
332
333	~intrusive_queue_t() = default;
334
335	inline node_t * head() const {
336	node_t * rhead = reinterpret_cast<node_t *>(
337	reinterpret_cast<uintptr_t>( &before ) - fields_offset
338	);
339	assert(rhead);
340	return rhead;
341	}
342
343	inline node_t * tail() const {
344	node_t * rtail = reinterpret_cast<node_t *>(
345	reinterpret_cast<uintptr_t>( &after ) - fields_offset
346	);
347	assert(rtail);
348	return rtail;
349	}
350
351	inline bool push(node_t * node) {
352	assert(lock);
353	assert(node->_links.ts != 0);
354	node_t * tail = this->tail();
355
356	node_t * prev = tail->_links.prev;
357	// assertf(node->_links.ts >= prev->_links.ts,
358	// "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
359	node->_links.next = tail;
360	node->_links.prev = prev;
361	prev->_links.next = node;
362	tail->_links.prev = node;
363	#ifndef NO_STATS
364	if(enable_stats) {
365	s.diff++;
366	s.push++;
367	}
368	#endif
369	if(before._links.ts == 0l) {
370	before._links.ts = node->_links.ts;
371	assert(node->_links.prev == this->head());
372	return true;
373	}
374	return false;
375	}
376
377	inline std::pair<node_t *, bool> pop() {
378	assert(lock);
379	node_t * head = this->head();
380	node_t * tail = this->tail();
381
382	node_t * node = head->_links.next;
383	node_t * next = node->_links.next;
384	if(node == tail) return {nullptr, false};
385
386	head->_links.next = next;
387	next->_links.prev = head;
388
389	#ifndef NO_STATS
390	if(enable_stats) {
391	s.diff--;
392	s.pop ++;
393	}
394	#endif
395	if(next == tail) {
396	before._links.ts = 0l;
397	return {node, true};
398	}
399	else {
400	assert(next->_links.ts != 0);
401	before._links.ts = next->_links.ts;
402	assert(before._links.ts != 0);
403	return {node, false};
404	}
405	}
406
407	long long ts() const {
408	return before._links.ts;
409	}
410	};
411
412
413	public:
414
415	static __attribute__((aligned(128))) thread_local struct TLS {
416	Random rng = { int(rdtscl()) };
417	pick_stat pick;
418	empty_stat empty;
419	} tls;
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
424	private:
425	__attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
426	const unsigned numLists;
427
428	public:
429	static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
430
431	#ifndef NO_STATS
432	static void stats_print(std::ostream & os) {
433	auto it = head;
434	while(it) {
435	it->stats_print_local(os);
436	it = it->next;
437	}
438	}
439
440	static void stats_tls_tally() {
441	global_stats.pick.push.attempt += tls.pick.push.attempt;
442	global_stats.pick.push.success += tls.pick.push.success;
443	global_stats.pick.pop .attempt += tls.pick.pop.attempt;
444	global_stats.pick.pop .success += tls.pick.pop.success;
445	global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
446
447	global_stats.qstat.push.value += tls.empty.push.value;
448	global_stats.qstat.push.count += tls.empty.push.count;
449	global_stats.qstat.pop .value += tls.empty.pop .value;
450	global_stats.qstat.pop .count += tls.empty.pop .count;
451	}
452
453	private:
454	static struct GlobalStats {
455	struct {
456	struct {
457	std::atomic_size_t attempt = { 0 };
458	std::atomic_size_t success = { 0 };
459	} push;
460	struct {
461	std::atomic_size_t attempt = { 0 };
462	std::atomic_size_t success = { 0 };
463	std::atomic_size_t mask_attempt = { 0 };
464	} pop;
465	} pick;
466	struct {
467	struct {
468	std::atomic_size_t value = { 0 };
469	std::atomic_size_t count = { 0 };
470	} push;
471	struct {
472	std::atomic_size_t value = { 0 };
473	std::atomic_size_t count = { 0 };
474	} pop;
475	} qstat;
476	} global_stats;
477
478	// Link list of all lists for stats
479	__attribute__((aligned(64))) relaxed_list<node_t> * next = nullptr;
480
481	static relaxed_list<node_t> * head;
482
483	void stats_print_local(std::ostream & os ) {
484	std::cout << "----- Relaxed List Stats -----" << std::endl;
485	{
486	ssize_t diff = 0;
487	size_t num = 0;
488	ssize_t max = 0;
489
490	for(size_t i = 0; i < numLists; i++) {
491	const auto & list = lists[i];
492	diff+= list.s.diff;
493	num ++;
494	max = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;
495	os << "Local Q ops : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";
496	}
497
498	os << "Difference : " << ssize_t(double(diff) / num ) << " avg\t" << max << "max" << std::endl;
499	}
500
501	const auto & global = global_stats;
502
503	double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
504	double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
505	double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
506
507	os << "Push Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
508	os << "Pop Pick % : " << pop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
509	os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
510
511	double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
512	double avgQ_pop = double(global.qstat.pop .value) / global.qstat.pop .count;
513	double avgQ = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
514	os << "Push Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
515	os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n";
516	os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
517	}
518	#endif
519	};

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

Download in other formats: