Index: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
===================================================================
--- doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp	(revision b2a37b045b22a2a00392f054434cf6298517bec0)
+++ doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp	(revision 1e24d136f25283f797c025440eb7b69e0b3e0d9d)
@@ -1,5 +1,8 @@
 #pragma once
 
+#ifndef NO_STATS
 #include <iostream>
+#endif
+
 #include <memory>
 #include <mutex>
@@ -11,13 +14,40 @@
 using namespace std;
 
+struct spinlock_t {
+	std::atomic_bool ll = { false };
+
+	inline void lock() {
+		while( __builtin_expect(ll.exchange(true),false) ) {
+			while(ll.load(std::memory_order_relaxed))
+				asm volatile("pause");
+		}
+	}
+
+	inline bool try_lock() {
+		return false == ll.exchange(true);
+	}
+
+	inline void unlock() {
+		ll.store(false, std::memory_order_release);
+	}
+
+	inline explicit operator bool() {
+		return ll.load(std::memory_order_relaxed);
+	}
+};
+
+
 extern bool enable_stats;
 
-
 struct pick_stat {
-	size_t attempt = 0;
-	size_t success = 0;
-};
-
-extern __attribute__((aligned(64))) thread_local pick_stat local_pick;
+	struct {
+		size_t attempt = 0;
+		size_t success = 0;
+	} push;
+	struct {
+		size_t attempt = 0;
+		size_t success = 0;
+	} pop;
+};
 
 template<typename node_t>
@@ -28,21 +58,6 @@
 };
 
-struct spinlock_t {
-	std::atomic_bool ll = { false };
-
-	inline void lock() {
-		while( __builtin_expect(ll.exchange(true),false) ) {
-			while(ll.load(std::memory_order_relaxed))
-				asm volatile("pause");
-		}
-	}
-
-	inline void unlock() {
-		ll.store(false, std::memory_order_release);
-	}
-};
-
 template<typename node_t>
-class relaxed_list {
+class __attribute__((aligned(128))) relaxed_list {
 	static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
 
@@ -50,46 +65,108 @@
 public:
 	relaxed_list(unsigned numLists)
-		: numLists(numLists)
+	  	: numNonEmpty{0}
 		, lists(new intrusive_queue_t[numLists])
-	  	, numNonEmpty(0)
+		, numLists(numLists)
 	{}
 
-    	void push(node_t * node) {
-		int i = rng_g.next() % numLists;
-		lists[i].push(node, numNonEmpty);
+	~relaxed_list() {
+		lists.reset();
+		#ifndef NO_STATS
+			std::cout << "Difference   : "
+				<< size_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num  ) << " avg\t"
+				<< intrusive_queue_t::stat::dif.max << "max" << std::endl;
+		#endif
+	}
+
+    	__attribute__((noinline, hot)) void push(node_t * node) {
+		node->_links.ts = rdtscl();
+
+		while(true) {
+			// Pick a random list
+			int i = tls.rng.next() % numLists;
+
+			#ifndef NO_STATS
+				tls.pick.push.attempt++;
+			#endif
+
+			// If we can't lock it retry
+			if( !lists[i].lock.try_lock() ) continue;
+
+			// Actually push it
+			lists[i].push(node, numNonEmpty);
+			assert(numNonEmpty <= (int)numLists);
+
+			// Unlock and return
+			lists[i].lock.unlock();
+
+			#ifndef NO_STATS
+				tls.pick.push.success++;
+			#endif
+			return;
+		}
     	}
 
-	node_t * pop() {
-		int i = pickRandomly(-1);
-		int j = pickRandomly(i);
-
-		if(i == -1) {
-			return nullptr;
-		}
-
-		auto guard = lock(i, j);
-		auto & list = best(i, j);
-		return list.pop(numNonEmpty);
+	__attribute__((noinline, hot)) node_t * pop() {
+		while(numNonEmpty != 0) {
+			// Pick two lists at random
+			int i = tls.rng.next() % numLists;
+			int j = tls.rng.next() % numLists;
+
+			#ifndef NO_STATS
+				tls.pick.pop.attempt++;
+			#endif
+
+			// Pick the bet list
+			int w = i;
+			if( __builtin_expect(lists[j].ts() != 0, true) ) {
+				w = (lists[i].ts() < lists[j].ts()) ? i : j;
+			}
+
+			auto & list = lists[w];
+			// If list looks empty retry
+			if( list.ts() == 0 ) continue;
+
+			// If we can't get the lock retry
+			if( !list.lock.try_lock() ) continue;
+
+			// If list is empty, unlock and retry
+			if( list.ts() == 0 ) {
+				list.lock.unlock();
+				continue;
+			}
+
+			// Actually pop the list
+			auto node = list.pop(numNonEmpty);
+			assert(node);
+
+			// Unlock and return
+			list.lock.unlock();
+			assert(numNonEmpty >= 0);
+			#ifndef NO_STATS
+				tls.pick.pop.success++;
+			#endif
+			return node;
+		}
+
+		return nullptr;
     	}
 
-	node_t * pop2() {
-		int i = pickRandomly(-1);
-		int j = pickRandomly(i);
-
-		if(i == -1) {
-			return nullptr;
-		}
-
-		auto & list = best2(i, j);
-		return list.pop2(numNonEmpty);
-    	}
-
 private:
 
-	class intrusive_queue_t {
+	class __attribute__((aligned(128))) intrusive_queue_t {
 	public:
 		typedef spinlock_t lock_t;
 
 		friend class relaxed_list<node_t>;
+
+		struct stat {
+			ssize_t diff = 0;
+
+			static struct Dif {
+				ssize_t value = 0;
+				size_t  num   = 0;
+				ssize_t max   = 0;
+			} dif;
+		};
 
 	private:
@@ -98,20 +175,13 @@
 		};
 
-		struct stat {
-			size_t push = 0;
-			size_t pop  = 0;
-		};
-
-		__attribute__((aligned(64))) lock_t lock;
-		__attribute__((aligned(64))) bool empty;
-		stat s;
+		lock_t lock;
 		sentinel_t before;
 		sentinel_t after;
+		stat s;
 
 		static constexpr auto fields_offset = offsetof( node_t, _links );
 	public:
 		intrusive_queue_t()
-			: empty(true)
-			, before{{ nullptr, tail() }}
+			: before{{ nullptr, tail() }}
 			, after {{ head(), nullptr }}
 		{
@@ -122,42 +192,55 @@
 			assert(tail()->_links.next == nullptr);
 			assert(tail()->_links.prev == head() );
+			assert(sizeof(*this) == 128);
+			assert((intptr_t(this) % 128) == 0);
 		}
 
 		~intrusive_queue_t() {
-			std::cout << " Push: " << s.push << "\tPop: " << s.pop << "\t(this: " << this << ")" << std::endl;
-		}
-
-		node_t * head() const {
-			return reinterpret_cast<node_t *>(
+			#ifndef NO_STATS
+				stat::dif.value+= s.diff;
+				stat::dif.num  ++;
+				stat::dif.max  = std::max(stat::dif.max, s.diff);
+			#endif
+		}
+
+		inline node_t * head() const {
+			node_t * rhead = reinterpret_cast<node_t *>(
 				reinterpret_cast<uintptr_t>( &before ) - fields_offset
 			);
-		}
-
-		node_t * tail() const {
-			return reinterpret_cast<node_t *>(
+			assert(rhead);
+			return rhead;
+		}
+
+		inline node_t * tail() const {
+			node_t * rtail = reinterpret_cast<node_t *>(
 				reinterpret_cast<uintptr_t>( &after ) - fields_offset
 			);
-		}
-
-		void push(node_t * node, volatile int & nonEmpty) {
+			assert(rtail);
+			return rtail;
+		}
+
+		inline void push(node_t * node, std::atomic_int & nonEmpty) {
+			assert(lock);
+			assert(node->_links.ts != 0);
 			node_t * tail = this->tail();
-			std::lock_guard<lock_t> guard(lock);
-			node->_links.ts = rdtscl();
 
 			node_t * prev = tail->_links.prev;
 			// assertf(node->_links.ts >= prev->_links.ts,
-			// "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
+			// 	"New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
 			node->_links.next = tail;
 			node->_links.prev = prev;
 			prev->_links.next = node;
 			tail->_links.prev = node;
-			if(empty) {
-				__atomic_fetch_add(&nonEmpty, 1, __ATOMIC_SEQ_CST);
-				empty = false;
-			}
-			if(enable_stats) s.push++;
-		}
-
-		node_t * pop(volatile int & nonEmpty) {
+			if(before._links.ts == 0l) {
+				nonEmpty += 1;
+				before._links.ts = node->_links.ts;
+			}
+			#ifndef NO_STATS
+				if(enable_stats) s.diff++;
+			#endif
+		}
+
+		inline node_t * pop(std::atomic_int & nonEmpty) {
+			assert(lock);
 			node_t * head = this->head();
 			node_t * tail = this->tail();
@@ -171,133 +254,37 @@
 
 			if(next == tail) {
-				empty = true;
-				__atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
-			}
-			if(enable_stats) s.pop++;
+				before._links.ts = 0l;
+				nonEmpty -= 1;
+			}
+			else {
+				assert(next->_links.ts != 0);
+				before._links.ts = next->_links.ts;
+				assert(before._links.ts != 0);
+			}
+			#ifndef NO_STATS
+				if(enable_stats) s.diff--;
+			#endif
 			return node;
 		}
 
-		node_t * pop2(volatile int & nonEmpty) {
-			node_t * head = this->head();
-			node_t * tail = this->tail();
-
-			std::lock_guard<lock_t> guard(lock);
-			node_t * node = head->_links.next;
-			node_t * next = node->_links.next;
-			if(node == tail) return nullptr;
-
-			head->_links.next = next;
-			next->_links.prev = head;
-
-			if(next == tail) {
-				empty = true;
-				__atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
-			}
-			if(enable_stats) s.pop++;
-			return node;
-		}
-
-		static intrusive_queue_t & best(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
-			bool lhs_empty = lhs.empty;
-			bool rhs_empty = rhs.empty;
-
-			if(lhs_empty && rhs_empty) return lhs;
-			if(!lhs_empty && rhs_empty) return lhs;
-			if(lhs_empty && !rhs_empty) return rhs;
-			node_t * lhs_head = lhs.head()->_links.next;
-			node_t * rhs_head = rhs.head()->_links.next;
-
-			assert(lhs_head != lhs.tail());
-			assert(rhs_head != rhs.tail());
-
-			if(lhs_head->_links.ts < lhs_head->_links.ts) {
-				return lhs;
-			} else {
-				return rhs;
-			}
-		}
-
-		static intrusive_queue_t & best2(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
-			node_t * lhs_head = lhs.head()->_links.next;
-			node_t * rhs_head = rhs.head()->_links.next;
-
-			bool lhs_empty = lhs_head != lhs.tail();
-			bool rhs_empty = rhs_head != rhs.tail();
-			if(lhs_empty && rhs_empty) return lhs;
-			if(!lhs_empty && rhs_empty) return lhs;
-			if(lhs_empty && !rhs_empty) return rhs;
-
-			if(lhs_head->_links.ts < lhs_head->_links.ts) {
-				return lhs;
-			} else {
-				return rhs;
-			}
+		long long ts() const {
+			return before._links.ts;
 		}
 	};
 
 
+public:
+
+	static __attribute__((aligned(128))) thread_local struct TLS {
+		Random    rng = { int(rdtscl()) };
+		pick_stat pick;
+	} tls;
+
 private:
-
-	static thread_local Random rng_g;
-    	__attribute__((aligned(64))) const unsigned numLists;
-	std::unique_ptr<intrusive_queue_t []> lists;
-	__attribute__((aligned(64))) volatile int numNonEmpty; // number of non-empty lists
-
-
-private:
-
-
-
-private:
-	int pickRandomly(const int avoid) {
-		int j;
-		do {
-			local_pick.attempt++;
-			j = rng_g.next() % numLists;
-			if (numNonEmpty < 1 + (avoid != -1)) return -1;
-		} while (j == avoid || lists[j].empty);
-		local_pick.success++;
-		return j;
-	}
-
-private:
-
-	struct queue_guard {
-		intrusive_queue_t * lists;
-		int i, j;
-
-		queue_guard(intrusive_queue_t * lists, int i, int j)
-			: lists(lists), i(i), j(j)
-		{
-			if(i >= 0) lists[i].lock.lock();
-			if(j >= 0) lists[j].lock.lock();
-		}
-
-		queue_guard(const queue_guard &) = delete;
-		queue_guard(queue_guard &&) = default;
-
-		~queue_guard() {
-			if(i >= 0) lists[i].lock.unlock();
-			if(j >= 0) lists[j].lock.unlock();
-		}
-	};
-
-	auto lock(int i, int j) {
-		assert(i >= 0);
-		assert(i != j);
-		if(j < i) return queue_guard(lists.get(), j, i);
-		return queue_guard(lists.get(), i, j);
-	}
-
-	intrusive_queue_t & best(int i, int j) {
-		assert(i != -1);
-		if(j == -1) return lists[i];
-		return intrusive_queue_t::best(lists[i], lists[j]);
-	}
-
-	intrusive_queue_t & best2(int i, int j) {
-		assert(i != -1);
-		if(j == -1) return lists[i];
-		return intrusive_queue_t::best2(lists[i], lists[j]);
-	}
-};
+	std::atomic_int numNonEmpty; // number of non-empty lists
+    	__attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
+	const unsigned numLists;
+
+public:
+	static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
+};
