Changeset 9da5a50 for doc/theses/thierry_delisle_PhD/code

Timestamp:

May 14, 2020, 3:33:38 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:

33e62f1b

Parents:

1b143de

Message:

Added new DISCOVER_BITMASK algorithm as a potential ready queue sub-algorithm.
It offers may be an improvement but doesn't reduce the contention for the counter

File:

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

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -80 +80 @@
                 size_t success = 0;
                 size_t mask_attempt = 0;
+                size_t mask_reset = 0;
         } pop;
 };
@@ -143 +144 @@
                         // Actually push it
                         if(lists[i].push(node)) {
-                                numNonEmpty++;
-                                size_t qword = i >> 6ull;
-                                size_t bit   = i & 63ull;
-                                assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
-                                __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
-                                assert(!ret);
-                                assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
+                                #if defined(DISCOVER_BITMASK)
+                                        size_t qword = i >> 6ull;
+                                        size_t bit   = i & 63ull;
+                                        assert(qword == 0);
+                                        bts(tls.mask, bit);
+                                #elif !defined(NO_BITMASK)
+                                        numNonEmpty++;
+                                        size_t qword = i >> 6ull;
+                                        size_t bit   = i & 63ull;
+                                        assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
+                                        __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
+                                        assert(!ret);
+                                        assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
+                                #else
+                                        numNonEmpty++;
+                                #endif
                         }
                         assert(numNonEmpty <= (int)numLists);
@@ -166 +176 @@
 
         __attribute__((noinline, hot)) node_t * pop() {
-                #if !defined(NO_BITMASK)
-                        // for(int r = 0; r < 10 && numNonEmpty != 0; r++) {
-                        //      // Pick two lists at random
-                        //      unsigned i = tls.rng.next() % numLists;
-                        //      unsigned j = tls.rng.next() % numLists;
-
-                        //      if(auto node = try_pop(i, j)) return node;
-                        // }
+                #if defined(DISCOVER_BITMASK)
+                        assert(numLists <= 64);
+                        while(true) {
+                                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;
+
+                                        // Pick the other according to the bitmask
+                                        unsigned r = tls.rng.next();
+
+                                        size_t mask = tls.mask.load(std::memory_order_relaxed);
+                                        if(mask == 0) {
+                                                tls.pick.pop.mask_reset++;
+                                                mask = (1U << numLists) - 1;
+                                        }
+
+                                        unsigned b = rand_bit(r, mask);
+
+                                        assertf(b < 64, "%zu %u", mask, b);
+
+                                        j = b;
+
+                                        assert(j < numLists);
+                                }
+
+                                if(auto node = try_pop(i, j)) return node;
+                        }
+                #elif !defined(NO_BITMASK)
                         int nnempty;
                         while(0 != (nnempty = numNonEmpty)) {
                                 tls.pick.pop.mask_attempt++;
                                 unsigned i, j;
-                                // if( numLists < 4 || (numLists / nnempty) < 4 ) {
-                                //      // Pick two lists at random
-                                //      i = tls.rng.next() % numLists;
-                                //      j = tls.rng.next() % numLists;
-                                // } else
                                 {
-                                        #ifndef NO_STATS
-                                                // tls.pick.push.mask_attempt++;
-                                        #endif
-
                                         // Pick two lists at random
                                         unsigned num = ((numLists - 1) >> 6) + 1;
@@ -236 +262 @@
                 #endif
 
+                #if defined(DISCOVER_BITMASK)
+                        if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i);
+                        if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j);
+                #endif
+
                 // Pick the bet list
                 int w = i;
@@ -264 +295 @@
 
                 if(emptied) {
-                        numNonEmpty--;
-                        size_t qword = w >> 6ull;
-                        size_t bit   = w & 63ull;
-                        assert((list_mask[qword] & (1ul << bit)) != 0);
-                        __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
-                        assert(ret);
-                        assert((list_mask[qword] & (1ul << bit)) == 0);
+                        #if defined(DISCOVER_BITMASK)
+                                size_t qword = w >> 6ull;
+                                size_t bit   = w & 63ull;
+                                assert(qword == 0);
+                                __attribute__((unused)) bool ret = btr(tls.mask, bit);
+                        #elif !defined(NO_BITMASK)
+                                numNonEmpty--;
+                                size_t qword = w >> 6ull;
+                                size_t bit   = w & 63ull;
+                                assert((list_mask[qword] & (1ul << bit)) != 0);
+                                __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
+                                assert(ret);
+                                assert((list_mask[qword] & (1ul << bit)) == 0);
+                        #else
+                                numNonEmpty--;
+                        #endif
                 }
 
@@ -417 +457 @@
                 pick_stat  pick;
                 empty_stat empty;
+                __attribute__((aligned(64))) std::atomic_size_t mask = { 0 };
         } tls;
 
@@ -444 +485 @@
                 global_stats.pick.pop .success += tls.pick.pop.success;
                 global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
+                global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;
 
                 global_stats.qstat.push.value += tls.empty.push.value;
@@ -462 +504 @@
                                 std::atomic_size_t success = { 0 };
                                 std::atomic_size_t mask_attempt = { 0 };
+                                std::atomic_size_t mask_reset = { 0 };
                         } pop;
                 } pick;
@@ -504 +547 @@
                 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 avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;