Ignore:
Timestamp:
May 14, 2020, 3:33:38 PM (4 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:
1 edited

Legend:

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

    r1b143de r9da5a50  
    8080                size_t success = 0;
    8181                size_t mask_attempt = 0;
     82                size_t mask_reset = 0;
    8283        } pop;
    8384};
     
    143144                        // Actually push it
    144145                        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));
     146                                #if defined(DISCOVER_BITMASK)
     147                                        size_t qword = i >> 6ull;
     148                                        size_t bit   = i & 63ull;
     149                                        assert(qword == 0);
     150                                        bts(tls.mask, bit);
     151                                #elif !defined(NO_BITMASK)
     152                                        numNonEmpty++;
     153                                        size_t qword = i >> 6ull;
     154                                        size_t bit   = i & 63ull;
     155                                        assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
     156                                        __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
     157                                        assert(!ret);
     158                                        assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
     159                                #else
     160                                        numNonEmpty++;
     161                                #endif
    152162                        }
    153163                        assert(numNonEmpty <= (int)numLists);
     
    166176
    167177        __attribute__((noinline, hot)) node_t * pop() {
    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                         // }
     178                #if defined(DISCOVER_BITMASK)
     179                        assert(numLists <= 64);
     180                        while(true) {
     181                                tls.pick.pop.mask_attempt++;
     182                                unsigned i, j;
     183                                {
     184                                        // Pick two lists at random
     185                                        unsigned num = ((numLists - 1) >> 6) + 1;
     186
     187                                        // Pick first list totally randomly
     188                                        i = tls.rng.next() % numLists;
     189
     190                                        // Pick the other according to the bitmask
     191                                        unsigned r = tls.rng.next();
     192
     193                                        size_t mask = tls.mask.load(std::memory_order_relaxed);
     194                                        if(mask == 0) {
     195                                                tls.pick.pop.mask_reset++;
     196                                                mask = (1U << numLists) - 1;
     197                                        }
     198
     199                                        unsigned b = rand_bit(r, mask);
     200
     201                                        assertf(b < 64, "%zu %u", mask, b);
     202
     203                                        j = b;
     204
     205                                        assert(j < numLists);
     206                                }
     207
     208                                if(auto node = try_pop(i, j)) return node;
     209                        }
     210                #elif !defined(NO_BITMASK)
    176211                        int nnempty;
    177212                        while(0 != (nnempty = numNonEmpty)) {
    178213                                tls.pick.pop.mask_attempt++;
    179214                                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
    185215                                {
    186                                         #ifndef NO_STATS
    187                                                 // tls.pick.push.mask_attempt++;
    188                                         #endif
    189 
    190216                                        // Pick two lists at random
    191217                                        unsigned num = ((numLists - 1) >> 6) + 1;
     
    236262                #endif
    237263
     264                #if defined(DISCOVER_BITMASK)
     265                        if(lists[i].ts() > 0) bts(tls.mask, i); else btr(tls.mask, i);
     266                        if(lists[j].ts() > 0) bts(tls.mask, j); else btr(tls.mask, j);
     267                #endif
     268
    238269                // Pick the bet list
    239270                int w = i;
     
    264295
    265296                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);
     297                        #if defined(DISCOVER_BITMASK)
     298                                size_t qword = w >> 6ull;
     299                                size_t bit   = w & 63ull;
     300                                assert(qword == 0);
     301                                __attribute__((unused)) bool ret = btr(tls.mask, bit);
     302                        #elif !defined(NO_BITMASK)
     303                                numNonEmpty--;
     304                                size_t qword = w >> 6ull;
     305                                size_t bit   = w & 63ull;
     306                                assert((list_mask[qword] & (1ul << bit)) != 0);
     307                                __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
     308                                assert(ret);
     309                                assert((list_mask[qword] & (1ul << bit)) == 0);
     310                        #else
     311                                numNonEmpty--;
     312                        #endif
    273313                }
    274314
     
    417457                pick_stat  pick;
    418458                empty_stat empty;
     459                __attribute__((aligned(64))) std::atomic_size_t mask = { 0 };
    419460        } tls;
    420461
     
    444485                global_stats.pick.pop .success += tls.pick.pop.success;
    445486                global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
     487                global_stats.pick.pop .mask_reset += tls.pick.pop.mask_reset;
    446488
    447489                global_stats.qstat.push.value += tls.empty.push.value;
     
    462504                                std::atomic_size_t success = { 0 };
    463505                                std::atomic_size_t mask_attempt = { 0 };
     506                                std::atomic_size_t mask_reset = { 0 };
    464507                        } pop;
    465508                } pick;
     
    504547                double pop_sur  = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
    505548                double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
     549                double rpop_sur = (100.0 * double(global.pick.pop .mask_reset) / global.pick.pop .mask_attempt);
    506550
    507551                os << "Push   Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
    508552                os << "Pop    Pick % : " << pop_sur  << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
    509553                os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
     554                os << "Pop M Reset % : " << rpop_sur << "(" << global.pick.pop .mask_reset << " / " << global.pick.pop .mask_attempt << ")\n";
    510555
    511556                double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
Note: See TracChangeset for help on using the changeset viewer.