Context Navigation

source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ df75fe97

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

Last change on this file since df75fe97 was 9421f3d8, checked in by Thierry Delisle <tdelisle@…>, 4 years ago
Adding some of the implemented code. Current state: relaxed list is achieves at least 6M ops/sec total
Property mode set to `100644`
File size: 10.0 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
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	}
116
117	~relaxed_list() {
118	lists.reset();
119	#ifndef NO_STATS
120	std::cout << "Difference : "
121	<< ssize_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num ) << " avg\t"
122	<< intrusive_queue_t::stat::dif.max << "max" << std::endl;
123	#endif
124	}
125
126	__attribute__((noinline, hot)) void push(node_t * node) {
127	node->_links.ts = rdtscl();
128
129	while(true) {
130	// Pick a random list
131	unsigned i = tls.rng.next() % numLists;
132
133	#ifndef NO_STATS
134	tls.pick.push.attempt++;
135	#endif
136
137	// If we can't lock it retry
138	if( !lists[i].lock.try_lock() ) continue;
139
140	__attribute__((unused)) int num = numNonEmpty;
141
142	// Actually push it
143	if(lists[i].push(node)) {
144	numNonEmpty++;
145	size_t qword = i >> 6ull;
146	size_t bit = i & 63ull;
147	assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
148	__attribute__((unused)) bool ret = bts(list_mask[qword], bit);
149	assert(!ret);
150	assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
151	}
152	assert(numNonEmpty <= (int)numLists);
153
154	// Unlock and return
155	lists[i].lock.unlock();
156
157	#ifndef NO_STATS
158	tls.pick.push.success++;
159	tls.empty.push.value += num;
160	tls.empty.push.count += 1;
161	#endif
162	return;
163	}
164	}
165
166	__attribute__((noinline, hot)) node_t * pop() {
167	#if !defined(NO_BITMASK)
168	// for(int r = 0; r < 10 && numNonEmpty != 0; r++) {
169	// // Pick two lists at random
170	// unsigned i = tls.rng.next() % numLists;
171	// unsigned j = tls.rng.next() % numLists;
172
173	// if(auto node = try_pop(i, j)) return node;
174	// }
175	int nnempty;
176	while(0 != (nnempty = numNonEmpty)) {
177	unsigned i, j;
178	if( numLists < 4 \|\| (numLists / nnempty) < 4 ) {
179	// Pick two lists at random
180	i = tls.rng.next() % numLists;
181	j = tls.rng.next() % numLists;
182	} else {
183	#ifndef NO_STATS
184	// tls.pick.push.mask_attempt++;
185	#endif
186
187	// Pick two lists at random
188	unsigned num = ((numLists - 1) >> 6) + 1;
189
190	unsigned ri = tls.rng.next();
191	unsigned rj = tls.rng.next();
192
193	unsigned wdxi = (ri >> 6u) % num;
194	unsigned wdxj = (rj >> 6u) % num;
195
196	size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
197	size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
198
199	if(maski == 0 && maskj == 0) continue;
200
201	unsigned biti = maski ? ri % __builtin_popcountl(maski) : 0;
202	unsigned bitj = maskj ? rj % __builtin_popcountl(maskj) : 0;
203
204	unsigned bi = 64 - nthSetBit(maski, biti + 1);
205	unsigned bj = 64 - nthSetBit(maskj, bitj + 1);
206
207	assertf(bi < 64, "%zu %u %u", maski, biti, bi);
208	assertf(bj < 64, "%zu %u %u", maskj, bitj, 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
297	static struct Dif {
298	ssize_t value = 0;
299	size_t num = 0;
300	ssize_t max = 0;
301	} dif;
302	};
303
304	private:
305	struct sentinel_t {
306	_LinksFields_t<node_t> _links;
307	};
308
309	lock_t lock;
310	sentinel_t before;
311	sentinel_t after;
312	#ifndef NO_STATS
313	stat s;
314	#endif
315
316	static constexpr auto fields_offset = offsetof( node_t, _links );
317	public:
318	intrusive_queue_t()
319	: before{{ nullptr, tail() }}
320	, after {{ head(), nullptr }}
321	{
322	/* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
323	/* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
324	/* paranoid */ assert(head()->_links.prev == nullptr);
325	/* paranoid */ assert(head()->_links.next == tail() );
326	/* paranoid */ assert(tail()->_links.next == nullptr);
327	/* paranoid */ assert(tail()->_links.prev == head() );
328	/* paranoid / assert(sizeof(this) == 128);
329	/* paranoid */ assert((intptr_t(this) % 128) == 0);
330	}
331
332	~intrusive_queue_t() {
333	#ifndef NO_STATS
334	stat::dif.value+= s.diff;
335	stat::dif.num ++;
336	stat::dif.max = std::abs(stat::dif.max) > std::abs(s.diff) ? stat::dif.max : s.diff;
337	#endif
338	}
339
340	inline node_t * head() const {
341	node_t * rhead = reinterpret_cast<node_t *>(
342	reinterpret_cast<uintptr_t>( &before ) - fields_offset
343	);
344	assert(rhead);
345	return rhead;
346	}
347
348	inline node_t * tail() const {
349	node_t * rtail = reinterpret_cast<node_t *>(
350	reinterpret_cast<uintptr_t>( &after ) - fields_offset
351	);
352	assert(rtail);
353	return rtail;
354	}
355
356	inline bool push(node_t * node) {
357	assert(lock);
358	assert(node->_links.ts != 0);
359	node_t * tail = this->tail();
360
361	node_t * prev = tail->_links.prev;
362	// assertf(node->_links.ts >= prev->_links.ts,
363	// "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
364	node->_links.next = tail;
365	node->_links.prev = prev;
366	prev->_links.next = node;
367	tail->_links.prev = node;
368	#ifndef NO_STATS
369	if(enable_stats) s.diff++;
370	#endif
371	if(before._links.ts == 0l) {
372	before._links.ts = node->_links.ts;
373	assert(node->_links.prev == this->head());
374	return true;
375	}
376	return false;
377	}
378
379	inline std::pair<node_t *, bool> pop() {
380	assert(lock);
381	node_t * head = this->head();
382	node_t * tail = this->tail();
383
384	node_t * node = head->_links.next;
385	node_t * next = node->_links.next;
386	if(node == tail) return {nullptr, false};
387
388	head->_links.next = next;
389	next->_links.prev = head;
390
391	#ifndef NO_STATS
392	if(enable_stats) s.diff--;
393	#endif
394	if(next == tail) {
395	before._links.ts = 0l;
396	return {node, true};
397	}
398	else {
399	assert(next->_links.ts != 0);
400	before._links.ts = next->_links.ts;
401	assert(before._links.ts != 0);
402	return {node, false};
403	}
404	}
405
406	long long ts() const {
407	return before._links.ts;
408	}
409	};
410
411
412	public:
413
414	static __attribute__((aligned(128))) thread_local struct TLS {
415	Random rng = { int(rdtscl()) };
416	pick_stat pick;
417	empty_stat empty;
418	} tls;
419
420	public:
421	std::atomic_int numNonEmpty = 0; // number of non-empty lists
422	std::atomic_size_t list_mask[7] = { 0 }; // which queues are empty
423	private:
424	__attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
425	const unsigned numLists;
426
427	public:
428	static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
429	};

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

Download in other formats: