Changeset 03045f18 for doc

Timestamp:

Jun 10, 2020, 12:07:36 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:

6089f4d

Parents:

591f084

Message:

Improved printing of probing length

File:

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

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -73 +73 @@
                         "SNZI",
                         "BITMASK",
-                        "DISCOVER",
+                        "SNZI + DISCOVERED MASK",
                         "SNZI + MASK"
                 };
@@ -82 +82 @@
                 : lists(new intrusive_queue_t[numLists])
                 , numLists(numLists)
-                #if VARIANT == SNZI || VARIANT == DISCOVER
+                #if VARIANT == SNZI
                         , snzi( std::log2( numLists / 8 ), 2 )
-                #elif VARIANT == SNZM
+                #elif VARIANT == SNZM || VARIANT == DISCOVER
                         , snzm( numLists )
                 #endif
@@ -128 +128 @@
                                         assert(qword == 0);
                                         bts(tls.mask, bit);
-                                        snzi.arrive(i);
+                                        snzm.arrive(i);
                                 #elif VARIANT == SNZI
                                         snzi.arrive(i);
@@ -166 +166 @@
                 #if VARIANT == DISCOVER
                         assert(numLists <= 64);
-                        while(snzi.query()) {
+                        while(snzm.query()) {
                                 tls.pick.pop.mask_attempt++;
                                 unsigned i, j;
@@ -180 +180 @@
                                                 tls.pick.pop.mask_reset++;
                                                 mask = (1U << numLists) - 1;
+                                                tls.mask.store(mask, std::memory_order_relaxed);
                                         }
 
@@ -202 +203 @@
                         }
                 #elif VARIANT == SNZM
+                        //*
                         while(snzm.query()) {
                                 tls.pick.pop.mask_attempt++;
@@ -235 +237 @@
                                 if(auto node = try_pop(i, j)) return node;
                         }
+                        /*/
+                        while(snzm.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 VARIANT == BITMASK
                         int nnempty;
@@ -329 +340 @@
                                 assert(qword == 0);
                                 __attribute__((unused)) bool ret = btr(tls.mask, bit);
-                                snzi.depart(w);
+                                snzm.depart(w);
                         #elif VARIANT == SNZI
                                 snzi.depart(w);
@@ -500 +511 @@
         const unsigned numLists;
 private:
-        #if VARIANT == SNZI || VARIANT == DISCOVER
+        #if VARIANT == SNZI
                 snzi_t snzi;
-        #elif VARIANT == SNZM
+        #elif VARIANT == SNZM || VARIANT == DISCOVER
                 snzm_t snzm;
         #else
@@ -591 +602 @@
                 double pop_sur  = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
                 double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
-                double rpop_sur = (100.0 * double(global.pick.pop .mask_reset) / global.pick.pop .mask_attempt);
-
-                os << "Push   Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
-                os << "Pop    Pick % : " << pop_sur  << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
-                os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
-                os << "Pop M Reset % : " << rpop_sur << "(" << global.pick.pop .mask_reset << " / " << global.pick.pop .mask_attempt << ")\n";
+                double rpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_reset);
+
+                double push_len = double(global.pick.push.attempt     ) / global.pick.push.success;
+                double pop_len  = double(global.pick.pop .attempt     ) / global.pick.pop .success;
+                double mpop_len = double(global.pick.pop .mask_attempt) / global.pick.pop .success;
+                double rpop_len = double(global.pick.pop .mask_reset  ) / global.pick.pop .success;
+
+                os << "Push   Pick   : " << push_sur << " %, len " << push_len << " (" << global.pick.push.attempt      << " / " << global.pick.push.success << ")\n";
+                os << "Pop    Pick   : " << pop_sur  << " %, len " << pop_len  << " (" << global.pick.pop .attempt      << " / " << global.pick.pop .success << ")\n";
+                os << "TryPop Pick   : " << mpop_sur << " %, len " << mpop_len << " (" << global.pick.pop .mask_attempt << " / " << global.pick.pop .success << ")\n";
+                os << "Pop M Reset   : " << rpop_sur << " %, len " << rpop_len << " (" << global.pick.pop .mask_reset   << " / " << global.pick.pop .success << ")\n";
 
                 double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;