Changeset 807a632 for doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

Timestamp:

Feb 10, 2020, 11:17:31 AM (3 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

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

Children:

3b56166

Parents:

487198c

Message:

Adding current version of the C++ relaxed_list code and benchmark

File:

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

doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

@@ -105 +105 @@
         static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
 
-
 public:
         relaxed_list(unsigned numLists)
@@ -112 +111 @@
         {
                 assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
-                assert(sizeof(*this) == 128);
+                // assert(sizeof(*this) == 128);
+                std::cout << "Constructing Relaxed List with " << numLists << std::endl;
+
+                #ifndef NO_STATS
+                        if(head) this->next = head;
+                        head = this;
+                #endif
         }
 
         ~relaxed_list() {
+                std::cout << "Destroying Relaxed List" << std::endl;
                 lists.reset();
-                #ifndef NO_STATS
-                        std::cout << "Difference   : "
-                                << ssize_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
         }
 
@@ -175 +176 @@
                         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 {
+                                // 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++;
@@ -199 +202 @@
                                         if(maski == 0 && maskj == 0) continue;
 
-                                        unsigned biti = maski ? ri % __builtin_popcountl(maski) : 0;
-                                        unsigned bitj = maskj ? rj % __builtin_popcountl(maskj) : 0;
-
-                                        unsigned bi = 64 - nthSetBit(maski, biti + 1);
-                                        unsigned bj = 64 - nthSetBit(maskj, bitj + 1);
-
-                                        assertf(bi < 64, "%zu %u %u", maski, biti, bi);
-                                        assertf(bj < 64, "%zu %u %u", maskj, bitj, bj);
+                                        unsigned bi = rand_bit(ri, maski);
+                                        unsigned bj = rand_bit(rj, maskj);
+
+                                        assertf(bi < 64, "%zu %u", maski, bi);
+                                        assertf(bj < 64, "%zu %u", maskj, bj);
 
                                         i = bi | (wdxi << 6);
@@ -294 +294 @@
                 struct stat {
                         ssize_t diff = 0;
-
-                        static struct Dif {
-                                ssize_t value = 0;
-                                size_t  num   = 0;
-                                ssize_t max   = 0;
-                        } dif;
+                        size_t  push = 0;
+                        size_t  pop  = 0;
+                        // size_t value = 0;
+                        // size_t count = 0;
                 };
 
@@ -314 +312 @@
                 #endif
 
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Winvalid-offsetof"
                 static constexpr auto fields_offset = offsetof( node_t, _links );
+#pragma GCC diagnostic pop
         public:
                 intrusive_queue_t()
@@ -330 +331 @@
                 }
 
-                ~intrusive_queue_t() {
-                        #ifndef NO_STATS
-                                stat::dif.value+= s.diff;
-                                stat::dif.num  ++;
-                                stat::dif.max  = std::abs(stat::dif.max) > std::abs(s.diff) ? stat::dif.max : s.diff;
-                        #endif
-                }
+                ~intrusive_queue_t() = default;
 
                 inline node_t * head() const {
@@ -367 +362 @@
                         tail->_links.prev = node;
                         #ifndef NO_STATS
-                                if(enable_stats) s.diff++;
+                                if(enable_stats) {
+                                        s.diff++;
+                                        s.push++;
+                                }
                         #endif
                         if(before._links.ts == 0l) {
@@ -390 +388 @@
 
                         #ifndef NO_STATS
-                                if(enable_stats) s.diff--;
+                                if(enable_stats) {
+                                        s.diff--;
+                                        s.pop ++;
+                                }
                         #endif
                         if(next == tail) {
@@ -419 +420 @@
 
 public:
-        std::atomic_int numNonEmpty  = 0;  // number of non-empty lists
-        std::atomic_size_t list_mask[7] = { 0 }; // which queues are empty
+        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;
@@ -427 +428 @@
 public:
         static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
+
+#ifndef NO_STATS
+        static void stats_print(std::ostream & os) {
+                auto it = head;
+                while(it) {
+                        it->stats_print_local(os);
+                        it = it->next;
+                }
+        }
+
+        static void stats_tls_tally() {
+                global_stats.pick.push.attempt += tls.pick.push.attempt;
+                global_stats.pick.push.success += tls.pick.push.success;
+                global_stats.pick.pop .attempt += tls.pick.pop.attempt;
+                global_stats.pick.pop .success += tls.pick.pop.success;
+                global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
+
+                global_stats.qstat.push.value += tls.empty.push.value;
+                global_stats.qstat.push.count += tls.empty.push.count;
+                global_stats.qstat.pop .value += tls.empty.pop .value;
+                global_stats.qstat.pop .count += tls.empty.pop .count;
+        }
+
+private:
+        static struct GlobalStats {
+                struct {
+                        struct {
+                                std::atomic_size_t attempt = { 0 };
+                                std::atomic_size_t success = { 0 };
+                        } push;
+                        struct {
+                                std::atomic_size_t attempt = { 0 };
+                                std::atomic_size_t success = { 0 };
+                                std::atomic_size_t mask_attempt = { 0 };
+                        } pop;
+                } pick;
+                struct {
+                        struct {
+                                std::atomic_size_t value = { 0 };
+                                std::atomic_size_t count = { 0 };
+                        } push;
+                        struct {
+                                std::atomic_size_t value = { 0 };
+                                std::atomic_size_t count = { 0 };
+                        } pop;
+                } qstat;
+        } global_stats;
+
+        // Link list of all lists for stats
+        __attribute__((aligned(64))) relaxed_list<node_t> * next = nullptr;
+
+        static relaxed_list<node_t> * head;
+
+        void stats_print_local(std::ostream & os ) {
+                std::cout << "----- Relaxed List Stats -----" << std::endl;
+                {
+                        ssize_t diff = 0;
+                        size_t  num  = 0;
+                        ssize_t max  = 0;
+
+                        for(size_t i = 0; i < numLists; i++) {
+                                const auto & list = lists[i];
+                                diff+= list.s.diff;
+                                num ++;
+                                max  = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;
+                                os << "Local Q ops   : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";
+                        }
+
+                        os << "Difference   : " << ssize_t(double(diff) / num  ) << " avg\t" << max << "max" << std::endl;
+                }
+
+                const auto & global = global_stats;
+
+                double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
+                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);
+
+                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";
+
+                double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
+                double avgQ_pop  = double(global.qstat.pop .value) / global.qstat.pop .count;
+                double avgQ      = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
+                os << "Push   Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
+                os << "Pop    Avg Qs : " << avgQ_pop  << " (" << global.qstat.pop .count << "ops)\n";
+                os << "Global Avg Qs : " << avgQ      << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
+        }
+#endif
 };