Changeset 33e62f1b for doc/theses/thierry_delisle_PhD/code

Timestamp:

May 21, 2020, 5:11:46 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

2802824

Parents:

9da5a50

Message:

Added simple SNZI implementation for the relaxed list

Location:

doc/theses/thierry_delisle_PhD/code

Files:

• relaxed_list.hpp (modified) (12 diffs)
• snzi.hpp (added)
• utils.hpp (modified) (1 diff)

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -11 +11 @@
 #include "assert.hpp"
 #include "utils.hpp"
+#include "snzi.hpp"
 
 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);
-        }
-};
-
-static inline bool bts(std::atomic_size_t & target, size_t bit ) {
-        //*
-        int result = 0;
-        asm volatile(
-                "LOCK btsq %[bit], %[target]\n\t"
-                :"=@ccc" (result)
-                : [target] "m" (target), [bit] "r" (bit)
-        );
-        return result != 0;
-        /*/
-        size_t mask = 1ul << bit;
-        size_t ret = target.fetch_or(mask, std::memory_order_relaxed);
-        return (ret & mask) != 0;
-        //*/
-}
-
-static inline bool btr(std::atomic_size_t & target, size_t bit ) {
-        //*
-        int result = 0;
-        asm volatile(
-                "LOCK btrq %[bit], %[target]\n\t"
-                :"=@ccc" (result)
-                : [target] "m" (target), [bit] "r" (bit)
-        );
-        return result != 0;
-        /*/
-        size_t mask = 1ul << bit;
-        size_t ret = target.fetch_and(~mask, std::memory_order_relaxed);
-        return (ret & mask) != 0;
-        //*/
-}
 
 extern bool enable_stats;
@@ -110 +56 @@
                 : lists(new intrusive_queue_t[numLists])
                 , numLists(numLists)
+                #if defined(SIMPLE_SNZI)
+                        , snzi(4)
+                #endif
         {
                 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
@@ -140 +89 @@
                         if( !lists[i].lock.try_lock() ) continue;
 
-                        __attribute__((unused)) int num = numNonEmpty;
+                        #if !defined(SIMPLE_SNZI)
+                                __attribute__((unused)) int num = numNonEmpty;
+                        #endif
 
                         // Actually push it
@@ -149 +100 @@
                                         assert(qword == 0);
                                         bts(tls.mask, bit);
+                                #elif defined(SIMPLE_SNZI)
+                                        snzi.arrive(i);
                                 #elif !defined(NO_BITMASK)
                                         numNonEmpty++;
@@ -161 +114 @@
                                 #endif
                         }
-                        assert(numNonEmpty <= (int)numLists);
+                        #if !defined(SIMPLE_SNZI)
+                                assert(numNonEmpty <= (int)numLists);
+                        #endif
 
                         // Unlock and return
@@ -168 +123 @@
                         #ifndef NO_STATS
                                 tls.pick.push.success++;
-                                tls.empty.push.value += num;
-                                tls.empty.push.count += 1;
+                                #if !defined(SIMPLE_SNZI)
+                                        tls.empty.push.value += num;
+                                        tls.empty.push.count += 1;
+                                #endif
                         #endif
                         return;
@@ -208 +165 @@
                                 if(auto node = try_pop(i, j)) return node;
                         }
+                #elif defined(SIMPLE_SNZI)
+                        while(snzi.query()) {
+                                // Pick two lists at random
+                                int i = tls.rng.next() % numLists;
+                                int j = tls.rng.next() % numLists;
+
+                                if(auto node = try_pop(i, j)) return node;
+                        }
                 #elif !defined(NO_BITMASK)
                         int nnempty;
@@ -280 +245 @@
                 if( !list.lock.try_lock() ) return nullptr;
 
-                __attribute__((unused)) int num = numNonEmpty;
+                #if !defined(SIMPLE_SNZI)
+                        __attribute__((unused)) int num = numNonEmpty;
+                #endif
 
                 // If list is empty, unlock and retry
@@ -300 +267 @@
                                 assert(qword == 0);
                                 __attribute__((unused)) bool ret = btr(tls.mask, bit);
+                        #elif defined(SIMPLE_SNZI)
+                                snzi.depart(w);
                         #elif !defined(NO_BITMASK)
                                 numNonEmpty--;
@@ -315 +284 @@
                 // Unlock and return
                 list.lock.unlock();
-                assert(numNonEmpty >= 0);
+                #if !defined(SIMPLE_SNZI)
+                        assert(numNonEmpty >= 0);
+                #endif
                 #ifndef NO_STATS
                         tls.pick.pop.success++;
-                        tls.empty.pop.value += num;
-                        tls.empty.pop.count += 1;
+                        #if !defined(SIMPLE_SNZI)
+                                tls.empty.pop.value += num;
+                                tls.empty.pop.count += 1;
+                        #endif
                 #endif
                 return node;
@@ -336 +309 @@
                         size_t  push = 0;
                         size_t  pop  = 0;
-                        // size_t value = 0;
-                        // size_t count = 0;
                 };
 
@@ -460 +431 @@
         } tls;
 
-public:
-        std::atomic_int numNonEmpty  = { 0 };  // number of non-empty lists
-        std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
 private:
         __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
         const unsigned numLists;
+private:
+        #if defined(SIMPLE_SNZI)
+                snzi_t snzi;
+        #else
+                std::atomic_int numNonEmpty  = { 0 };  // number of non-empty lists
+                std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
+        #endif
 
 public:

doc/theses/thierry_delisle_PhD/code/utils.hpp

@@ -143 +143 @@
 #endif
 }
+
+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);
+        }
+};
+
+static inline bool bts(std::atomic_size_t & target, size_t bit ) {
+        //*
+        int result = 0;
+        asm volatile(
+                "LOCK btsq %[bit], %[target]\n\t"
+                :"=@ccc" (result)
+                : [target] "m" (target), [bit] "r" (bit)
+        );
+        return result != 0;
+        /*/
+        size_t mask = 1ul << bit;
+        size_t ret = target.fetch_or(mask, std::memory_order_relaxed);
+        return (ret & mask) != 0;
+        //*/
+}
+
+static inline bool btr(std::atomic_size_t & target, size_t bit ) {
+        //*
+        int result = 0;
+        asm volatile(
+                "LOCK btrq %[bit], %[target]\n\t"
+                :"=@ccc" (result)
+                : [target] "m" (target), [bit] "r" (bit)
+        );
+        return result != 0;
+        /*/
+        size_t mask = 1ul << bit;
+        size_t ret = target.fetch_and(~mask, std::memory_order_relaxed);
+        return (ret & mask) != 0;
+        //*/
+}