Ignore:
Timestamp:
Feb 10, 2020, 11:58:55 AM (21 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
686cb63, 7102540
Parents:
92a9768 (diff), 3b56166 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

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

    r92a9768 r3966d9a  
    3737};
    3838
     39static inline bool bts(std::atomic_size_t & target, size_t bit ) {
     40        //*
     41        int result = 0;
     42        asm volatile(
     43                "LOCK btsq %[bit], %[target]\n\t"
     44                :"=@ccc" (result)
     45                : [target] "m" (target), [bit] "r" (bit)
     46        );
     47        return result != 0;
     48        /*/
     49        size_t mask = 1ul << bit;
     50        size_t ret = target.fetch_or(mask, std::memory_order_relaxed);
     51        return (ret & mask) != 0;
     52        //*/
     53}
     54
     55static inline bool btr(std::atomic_size_t & target, size_t bit ) {
     56        //*
     57        int result = 0;
     58        asm volatile(
     59                "LOCK btrq %[bit], %[target]\n\t"
     60                :"=@ccc" (result)
     61                : [target] "m" (target), [bit] "r" (bit)
     62        );
     63        return result != 0;
     64        /*/
     65        size_t mask = 1ul << bit;
     66        size_t ret = target.fetch_and(~mask, std::memory_order_relaxed);
     67        return (ret & mask) != 0;
     68        //*/
     69}
    3970
    4071extern bool enable_stats;
     
    4879                size_t attempt = 0;
    4980                size_t success = 0;
     81                size_t mask_attempt = 0;
     82        } pop;
     83};
     84
     85struct empty_stat {
     86        struct {
     87                size_t value = 0;
     88                size_t count = 0;
     89        } push;
     90        struct {
     91                size_t value = 0;
     92                size_t count = 0;
    5093        } pop;
    5194};
     
    62105        static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
    63106
    64 
    65107public:
    66108        relaxed_list(unsigned numLists)
    67                 : numNonEmpty{0}
    68                 , lists(new intrusive_queue_t[numLists])
     109                : lists(new intrusive_queue_t[numLists])
    69110                , numLists(numLists)
    70         {}
     111        {
     112                assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
     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
     120        }
    71121
    72122        ~relaxed_list() {
     123                std::cout << "Destroying Relaxed List" << std::endl;
    73124                lists.reset();
    74                 #ifndef NO_STATS
    75                         std::cout << "Difference   : "
    76                                 << ssize_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num  ) << " avg\t"
    77                                 << intrusive_queue_t::stat::dif.max << "max" << std::endl;
    78                 #endif
    79125        }
    80126
     
    84130                while(true) {
    85131                        // Pick a random list
    86                         int i = tls.rng.next() % numLists;
     132                        unsigned i = tls.rng.next() % numLists;
    87133
    88134                        #ifndef NO_STATS
     
    93139                        if( !lists[i].lock.try_lock() ) continue;
    94140
     141                        __attribute__((unused)) int num = numNonEmpty;
     142
    95143                        // Actually push it
    96                         lists[i].push(node, numNonEmpty);
     144                        if(lists[i].push(node)) {
     145                                numNonEmpty++;
     146                                size_t qword = i >> 6ull;
     147                                size_t bit   = i & 63ull;
     148                                assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
     149                                __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
     150                                assert(!ret);
     151                                assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
     152                        }
    97153                        assert(numNonEmpty <= (int)numLists);
    98154
     
    102158                        #ifndef NO_STATS
    103159                                tls.pick.push.success++;
     160                                tls.empty.push.value += num;
     161                                tls.empty.push.count += 1;
    104162                        #endif
    105163                        return;
     
    108166
    109167        __attribute__((noinline, hot)) node_t * pop() {
    110                 while(numNonEmpty != 0) {
    111                         // Pick two lists at random
    112                         int i = tls.rng.next() % numLists;
    113                         int j = tls.rng.next() % numLists;
    114 
    115                         #ifndef NO_STATS
    116                                 tls.pick.pop.attempt++;
    117                         #endif
    118 
    119                         // Pick the bet list
    120                         int w = i;
    121                         if( __builtin_expect(lists[j].ts() != 0, true) ) {
    122                                 w = (lists[i].ts() < lists[j].ts()) ? i : j;
    123                         }
    124 
    125                         auto & list = lists[w];
    126                         // If list looks empty retry
    127                         if( list.ts() == 0 ) continue;
    128 
    129                         // If we can't get the lock retry
    130                         if( !list.lock.try_lock() ) continue;
    131 
    132                         // If list is empty, unlock and retry
    133                         if( list.ts() == 0 ) {
    134                                 list.lock.unlock();
    135                                 continue;
    136                         }
    137 
    138                         // Actually pop the list
    139                         auto node = list.pop(numNonEmpty);
    140                         assert(node);
    141 
    142                         // Unlock and return
    143                         list.lock.unlock();
    144                         assert(numNonEmpty >= 0);
    145                         #ifndef NO_STATS
    146                                 tls.pick.pop.success++;
    147                         #endif
    148                         return node;
    149                 }
     168                #if !defined(NO_BITMASK)
     169                        // for(int r = 0; r < 10 && numNonEmpty != 0; r++) {
     170                        //      // Pick two lists at random
     171                        //      unsigned i = tls.rng.next() % numLists;
     172                        //      unsigned j = tls.rng.next() % numLists;
     173
     174                        //      if(auto node = try_pop(i, j)) return node;
     175                        // }
     176                        int nnempty;
     177                        while(0 != (nnempty = numNonEmpty)) {
     178                                tls.pick.pop.mask_attempt++;
     179                                unsigned i, j;
     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                                {
     186                                        #ifndef NO_STATS
     187                                                // tls.pick.push.mask_attempt++;
     188                                        #endif
     189
     190                                        // Pick two lists at random
     191                                        unsigned num = ((numLists - 1) >> 6) + 1;
     192
     193                                        unsigned ri = tls.rng.next();
     194                                        unsigned rj = tls.rng.next();
     195
     196                                        unsigned wdxi = (ri >> 6u) % num;
     197                                        unsigned wdxj = (rj >> 6u) % num;
     198
     199                                        size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
     200                                        size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
     201
     202                                        if(maski == 0 && maskj == 0) continue;
     203
     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);
     209
     210                                        i = bi | (wdxi << 6);
     211                                        j = bj | (wdxj << 6);
     212
     213                                        assertf(i < numLists, "%u", wdxi << 6);
     214                                        assertf(j < numLists, "%u", wdxj << 6);
     215                                }
     216
     217                                if(auto node = try_pop(i, j)) return node;
     218                        }
     219                #else
     220                        while(numNonEmpty != 0) {
     221                                // Pick two lists at random
     222                                int i = tls.rng.next() % numLists;
     223                                int j = tls.rng.next() % numLists;
     224
     225                                if(auto node = try_pop(i, j)) return node;
     226                        }
     227                #endif
    150228
    151229                return nullptr;
    152230        }
     231
     232private:
     233        node_t * try_pop(unsigned i, unsigned j) {
     234                #ifndef NO_STATS
     235                        tls.pick.pop.attempt++;
     236                #endif
     237
     238                // Pick the bet list
     239                int w = i;
     240                if( __builtin_expect(lists[j].ts() != 0, true) ) {
     241                        w = (lists[i].ts() < lists[j].ts()) ? i : j;
     242                }
     243
     244                auto & list = lists[w];
     245                // If list looks empty retry
     246                if( list.ts() == 0 ) return nullptr;
     247
     248                // If we can't get the lock retry
     249                if( !list.lock.try_lock() ) return nullptr;
     250
     251                __attribute__((unused)) int num = numNonEmpty;
     252
     253                // If list is empty, unlock and retry
     254                if( list.ts() == 0 ) {
     255                        list.lock.unlock();
     256                        return nullptr;
     257                }
     258
     259                // Actually pop the list
     260                node_t * node;
     261                bool emptied;
     262                std::tie(node, emptied) = list.pop();
     263                assert(node);
     264
     265                if(emptied) {
     266                        numNonEmpty--;
     267                        size_t qword = w >> 6ull;
     268                        size_t bit   = w & 63ull;
     269                        assert((list_mask[qword] & (1ul << bit)) != 0);
     270                        __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
     271                        assert(ret);
     272                        assert((list_mask[qword] & (1ul << bit)) == 0);
     273                }
     274
     275                // Unlock and return
     276                list.lock.unlock();
     277                assert(numNonEmpty >= 0);
     278                #ifndef NO_STATS
     279                        tls.pick.pop.success++;
     280                        tls.empty.pop.value += num;
     281                        tls.empty.pop.count += 1;
     282                #endif
     283                return node;
     284        }
    153285
    154286private:
     
    162294                struct stat {
    163295                        ssize_t diff = 0;
    164 
    165                         static struct Dif {
    166                                 ssize_t value = 0;
    167                                 size_t  num   = 0;
    168                                 ssize_t max   = 0;
    169                         } dif;
     296                        size_t  push = 0;
     297                        size_t  pop  = 0;
     298                        // size_t value = 0;
     299                        // size_t count = 0;
    170300                };
    171301
     
    178308                sentinel_t before;
    179309                sentinel_t after;
    180                 stat s;
    181 
     310                #ifndef NO_STATS
     311                        stat s;
     312                #endif
     313
     314#pragma GCC diagnostic push
     315#pragma GCC diagnostic ignored "-Winvalid-offsetof"
    182316                static constexpr auto fields_offset = offsetof( node_t, _links );
     317#pragma GCC diagnostic pop
    183318        public:
    184319                intrusive_queue_t()
     
    186321                        , after {{ head(), nullptr }}
    187322                {
    188                         assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
    189                         assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
    190                         assert(head()->_links.prev == nullptr);
    191                         assert(head()->_links.next == tail() );
    192                         assert(tail()->_links.next == nullptr);
    193                         assert(tail()->_links.prev == head() );
    194                         assert(sizeof(*this) == 128);
    195                         assert((intptr_t(this) % 128) == 0);
    196                 }
    197 
    198                 ~intrusive_queue_t() {
    199                         #ifndef NO_STATS
    200                                 stat::dif.value+= s.diff;
    201                                 stat::dif.num  ++;
    202                                 stat::dif.max  = std::abs(stat::dif.max) > std::abs(s.diff) ? stat::dif.max : s.diff;
    203                         #endif
    204                 }
     323                        /* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
     324                        /* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
     325                        /* paranoid */ assert(head()->_links.prev == nullptr);
     326                        /* paranoid */ assert(head()->_links.next == tail() );
     327                        /* paranoid */ assert(tail()->_links.next == nullptr);
     328                        /* paranoid */ assert(tail()->_links.prev == head() );
     329                        /* paranoid */ assert(sizeof(*this) == 128);
     330                        /* paranoid */ assert((intptr_t(this) % 128) == 0);
     331                }
     332
     333                ~intrusive_queue_t() = default;
    205334
    206335                inline node_t * head() const {
     
    220349                }
    221350
    222                 inline void push(node_t * node, std::atomic_int & nonEmpty) {
     351                inline bool push(node_t * node) {
    223352                        assert(lock);
    224353                        assert(node->_links.ts != 0);
     
    232361                        prev->_links.next = node;
    233362                        tail->_links.prev = node;
     363                        #ifndef NO_STATS
     364                                if(enable_stats) {
     365                                        s.diff++;
     366                                        s.push++;
     367                                }
     368                        #endif
    234369                        if(before._links.ts == 0l) {
    235                                 nonEmpty += 1;
    236370                                before._links.ts = node->_links.ts;
    237                         }
    238                         #ifndef NO_STATS
    239                                 if(enable_stats) s.diff++;
    240                         #endif
    241                 }
    242 
    243                 inline node_t * pop(std::atomic_int & nonEmpty) {
     371                                assert(node->_links.prev == this->head());
     372                                return true;
     373                        }
     374                        return false;
     375                }
     376
     377                inline std::pair<node_t *, bool> pop() {
    244378                        assert(lock);
    245379                        node_t * head = this->head();
     
    248382                        node_t * node = head->_links.next;
    249383                        node_t * next = node->_links.next;
    250                         if(node == tail) return nullptr;
     384                        if(node == tail) return {nullptr, false};
    251385
    252386                        head->_links.next = next;
    253387                        next->_links.prev = head;
    254388
     389                        #ifndef NO_STATS
     390                                if(enable_stats) {
     391                                        s.diff--;
     392                                        s.pop ++;
     393                                }
     394                        #endif
    255395                        if(next == tail) {
    256396                                before._links.ts = 0l;
    257                                 nonEmpty -= 1;
     397                                return {node, true};
    258398                        }
    259399                        else {
     
    261401                                before._links.ts = next->_links.ts;
    262402                                assert(before._links.ts != 0);
    263                         }
    264                         #ifndef NO_STATS
    265                                 if(enable_stats) s.diff--;
    266                         #endif
    267                         return node;
     403                                return {node, false};
     404                        }
    268405                }
    269406
     
    277414
    278415        static __attribute__((aligned(128))) thread_local struct TLS {
    279                 Random    rng = { int(rdtscl()) };
    280                 pick_stat pick;
     416                Random     rng = { int(rdtscl()) };
     417                pick_stat  pick;
     418                empty_stat empty;
    281419        } tls;
    282420
     421public:
     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
    283424private:
    284         std::atomic_int numNonEmpty; // number of non-empty lists
    285425        __attribute__((aligned(64))) std::unique_ptr<intrusive_queue_t []> lists;
    286426        const unsigned numLists;
     
    288428public:
    289429        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
    290519};
Note: See TracChangeset for help on using the changeset viewer.