Ignore:
Timestamp:
Feb 10, 2020, 11:17:31 AM (21 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
3b56166
Parents:
487198c
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp

    r487198c r807a632  
    105105        static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
    106106
    107 
    108107public:
    109108        relaxed_list(unsigned numLists)
     
    112111        {
    113112                assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
    114                 assert(sizeof(*this) == 128);
     113                // assert(sizeof(*this) == 128);
     114                std::cout << "Constructing Relaxed List with " << numLists << std::endl;
     115
     116                #ifndef NO_STATS
     117                        if(head) this->next = head;
     118                        head = this;
     119                #endif
    115120        }
    116121
    117122        ~relaxed_list() {
     123                std::cout << "Destroying Relaxed List" << std::endl;
    118124                lists.reset();
    119                 #ifndef NO_STATS
    120                         std::cout << "Difference   : "
    121                                 << ssize_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num  ) << " avg\t"
    122                                 << intrusive_queue_t::stat::dif.max << "max" << std::endl;
    123                 #endif
    124125        }
    125126
     
    175176                        int nnempty;
    176177                        while(0 != (nnempty = numNonEmpty)) {
     178                                tls.pick.pop.mask_attempt++;
    177179                                unsigned i, j;
    178                                 if( numLists < 4 || (numLists / nnempty) < 4 ) {
    179                                         // Pick two lists at random
    180                                         i = tls.rng.next() % numLists;
    181                                         j = tls.rng.next() % numLists;
    182                                 } else {
     180                                // if( numLists < 4 || (numLists / nnempty) < 4 ) {
     181                                //      // Pick two lists at random
     182                                //      i = tls.rng.next() % numLists;
     183                                //      j = tls.rng.next() % numLists;
     184                                // } else
     185                                {
    183186                                        #ifndef NO_STATS
    184187                                                // tls.pick.push.mask_attempt++;
     
    199202                                        if(maski == 0 && maskj == 0) continue;
    200203
    201                                         unsigned biti = maski ? ri % __builtin_popcountl(maski) : 0;
    202                                         unsigned bitj = maskj ? rj % __builtin_popcountl(maskj) : 0;
    203 
    204                                         unsigned bi = 64 - nthSetBit(maski, biti + 1);
    205                                         unsigned bj = 64 - nthSetBit(maskj, bitj + 1);
    206 
    207                                         assertf(bi < 64, "%zu %u %u", maski, biti, bi);
    208                                         assertf(bj < 64, "%zu %u %u", maskj, bitj, bj);
     204                                        unsigned bi = rand_bit(ri, maski);
     205                                        unsigned bj = rand_bit(rj, maskj);
     206
     207                                        assertf(bi < 64, "%zu %u", maski, bi);
     208                                        assertf(bj < 64, "%zu %u", maskj, bj);
    209209
    210210                                        i = bi | (wdxi << 6);
     
    294294                struct stat {
    295295                        ssize_t diff = 0;
    296 
    297                         static struct Dif {
    298                                 ssize_t value = 0;
    299                                 size_t  num   = 0;
    300                                 ssize_t max   = 0;
    301                         } dif;
     296                        size_t  push = 0;
     297                        size_t  pop  = 0;
     298                        // size_t value = 0;
     299                        // size_t count = 0;
    302300                };
    303301
     
    314312                #endif
    315313
     314#pragma GCC diagnostic push
     315#pragma GCC diagnostic ignored "-Winvalid-offsetof"
    316316                static constexpr auto fields_offset = offsetof( node_t, _links );
     317#pragma GCC diagnostic pop
    317318        public:
    318319                intrusive_queue_t()
     
    330331                }
    331332
    332                 ~intrusive_queue_t() {
    333                         #ifndef NO_STATS
    334                                 stat::dif.value+= s.diff;
    335                                 stat::dif.num  ++;
    336                                 stat::dif.max  = std::abs(stat::dif.max) > std::abs(s.diff) ? stat::dif.max : s.diff;
    337                         #endif
    338                 }
     333                ~intrusive_queue_t() = default;
    339334
    340335                inline node_t * head() const {
     
    367362                        tail->_links.prev = node;
    368363                        #ifndef NO_STATS
    369                                 if(enable_stats) s.diff++;
     364                                if(enable_stats) {
     365                                        s.diff++;
     366                                        s.push++;
     367                                }
    370368                        #endif
    371369                        if(before._links.ts == 0l) {
     
    390388
    391389                        #ifndef NO_STATS
    392                                 if(enable_stats) s.diff--;
     390                                if(enable_stats) {
     391                                        s.diff--;
     392                                        s.pop ++;
     393                                }
    393394                        #endif
    394395                        if(next == tail) {
     
    419420
    420421public:
    421         std::atomic_int numNonEmpty  = 0;  // number of non-empty lists
    422         std::atomic_size_t list_mask[7] = { 0 }; // which queues are empty
     422        std::atomic_int numNonEmpty  = { 0 };  // number of non-empty lists
     423        std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
    423424private:
    424425        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
     
    427428public:
    428429        static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
     430
     431#ifndef NO_STATS
     432        static void stats_print(std::ostream & os) {
     433                auto it = head;
     434                while(it) {
     435                        it->stats_print_local(os);
     436                        it = it->next;
     437                }
     438        }
     439
     440        static void stats_tls_tally() {
     441                global_stats.pick.push.attempt += tls.pick.push.attempt;
     442                global_stats.pick.push.success += tls.pick.push.success;
     443                global_stats.pick.pop .attempt += tls.pick.pop.attempt;
     444                global_stats.pick.pop .success += tls.pick.pop.success;
     445                global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
     446
     447                global_stats.qstat.push.value += tls.empty.push.value;
     448                global_stats.qstat.push.count += tls.empty.push.count;
     449                global_stats.qstat.pop .value += tls.empty.pop .value;
     450                global_stats.qstat.pop .count += tls.empty.pop .count;
     451        }
     452
     453private:
     454        static struct GlobalStats {
     455                struct {
     456                        struct {
     457                                std::atomic_size_t attempt = { 0 };
     458                                std::atomic_size_t success = { 0 };
     459                        } push;
     460                        struct {
     461                                std::atomic_size_t attempt = { 0 };
     462                                std::atomic_size_t success = { 0 };
     463                                std::atomic_size_t mask_attempt = { 0 };
     464                        } pop;
     465                } pick;
     466                struct {
     467                        struct {
     468                                std::atomic_size_t value = { 0 };
     469                                std::atomic_size_t count = { 0 };
     470                        } push;
     471                        struct {
     472                                std::atomic_size_t value = { 0 };
     473                                std::atomic_size_t count = { 0 };
     474                        } pop;
     475                } qstat;
     476        } global_stats;
     477
     478        // Link list of all lists for stats
     479        __attribute__((aligned(64))) relaxed_list<node_t> * next = nullptr;
     480
     481        static relaxed_list<node_t> * head;
     482
     483        void stats_print_local(std::ostream & os ) {
     484                std::cout << "----- Relaxed List Stats -----" << std::endl;
     485                {
     486                        ssize_t diff = 0;
     487                        size_t  num  = 0;
     488                        ssize_t max  = 0;
     489
     490                        for(size_t i = 0; i < numLists; i++) {
     491                                const auto & list = lists[i];
     492                                diff+= list.s.diff;
     493                                num ++;
     494                                max  = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;
     495                                os << "Local Q ops   : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";
     496                        }
     497
     498                        os << "Difference   : " << ssize_t(double(diff) / num  ) << " avg\t" << max << "max" << std::endl;
     499                }
     500
     501                const auto & global = global_stats;
     502
     503                double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
     504                double pop_sur  = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
     505                double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
     506
     507                os << "Push   Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
     508                os << "Pop    Pick % : " << pop_sur  << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
     509                os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
     510
     511                double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
     512                double avgQ_pop  = double(global.qstat.pop .value) / global.qstat.pop .count;
     513                double avgQ      = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
     514                os << "Push   Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
     515                os << "Pop    Avg Qs : " << avgQ_pop  << " (" << global.qstat.pop .count << "ops)\n";
     516                os << "Global Avg Qs : " << avgQ      << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
     517        }
     518#endif
    429519};
Note: See TracChangeset for help on using the changeset viewer.