Changeset 8f4f3e0

Timestamp:

May 22, 2020, 4:00:01 PM (4 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:

3bf812b

Parents:

95cb63b

Message:

bitmask discovery no use snzi

File:

• doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (modified) (11 diffs)

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -5 +5 @@
 #endif
 
+#include <cmath>
 #include <memory>
 #include <mutex>
@@ -56 +57 @@
                 : lists(new intrusive_queue_t[numLists])
                 , numLists(numLists)
-                #if defined(SIMPLE_SNZI)
-                        , snzi(4)
+                #if defined(SIMPLE_SNZI) || defined(DISCOVER_BITMASK)
+                        , snzi( std::log2( numLists / 8 ) )
                 #endif
         {
@@ -89 +90 @@
                         if( !lists[i].lock.try_lock() ) continue;
 
-                        #if !defined(SIMPLE_SNZI)
+                        #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                                 __attribute__((unused)) int num = numNonEmpty;
                         #endif
@@ -100 +101 @@
                                         assert(qword == 0);
                                         bts(tls.mask, bit);
+                                        snzi.arrive(i);
                                 #elif defined(SIMPLE_SNZI)
                                         snzi.arrive(i);
@@ -114 +116 @@
                                 #endif
                         }
-                        #if !defined(SIMPLE_SNZI)
+                        #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                                 assert(numNonEmpty <= (int)numLists);
                         #endif
@@ -123 +125 @@
                         #ifndef NO_STATS
                                 tls.pick.push.success++;
-                                #if !defined(SIMPLE_SNZI)
+                                #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                                         tls.empty.push.value += num;
                                         tls.empty.push.count += 1;
@@ -135 +137 @@
                 #if defined(DISCOVER_BITMASK)
                         assert(numLists <= 64);
-                        while(true) {
+                        while(snzi.query()) {
                                 tls.pick.pop.mask_attempt++;
                                 unsigned i, j;
                                 {
-                                        // Pick two lists at random
-                                        unsigned num = ((numLists - 1) >> 6) + 1;
-
                                         // Pick first list totally randomly
                                         i = tls.rng.next() % numLists;
@@ -245 +244 @@
                 if( !list.lock.try_lock() ) return nullptr;
 
-                #if !defined(SIMPLE_SNZI)
+                #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                         __attribute__((unused)) int num = numNonEmpty;
                 #endif
@@ -267 +266 @@
                                 assert(qword == 0);
                                 __attribute__((unused)) bool ret = btr(tls.mask, bit);
+                                snzi.depart(w);
                         #elif defined(SIMPLE_SNZI)
                                 snzi.depart(w);
@@ -284 +284 @@
                 // Unlock and return
                 list.lock.unlock();
-                #if !defined(SIMPLE_SNZI)
+                #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                         assert(numNonEmpty >= 0);
                 #endif
                 #ifndef NO_STATS
                         tls.pick.pop.success++;
-                        #if !defined(SIMPLE_SNZI)
+                        #if !defined(SIMPLE_SNZI) && !defined(DISCOVER_BITMASK)
                                 tls.empty.pop.value += num;
                                 tls.empty.pop.count += 1;
@@ -435 +435 @@
         const unsigned numLists;
 private:
-        #if defined(SIMPLE_SNZI)
+        #if defined(SIMPLE_SNZI) || defined(DISCOVER_BITMASK)
                 snzi_t snzi;
         #else