Ignore:
Timestamp:
Apr 15, 2021, 1:08:16 PM (3 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
200a229, 76c94bf
Parents:
8590328
Message:

Added comparison of the mpsc queue to the protoptype.

Location:
doc/theses/thierry_delisle_PhD/code/readyQ_proto
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/links.hpp

    r8590328 r780a614  
    117117        }
    118118
    119         long long ts() const {
     119        unsigned long long ts() const {
    120120                return before._links.ts;
    121121        }

  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/links2.hpp

    r8590328 r780a614  
    5656template<typename node_t>
    5757class mpsc_queue : private mcs_queue<node_t> {
    58         node_t * volatile head;
     58        node_t * volatile _head;
    5959public:
    60         mpsc_queue(): mcs_queue<node_t>(), head(nullptr) {}
     60        mpsc_queue(): mcs_queue<node_t>(), _head(nullptr) {}
    6161
    6262        inline bool empty() const { return mcs_queue<node_t>::empty(); }
     63
     64        node_t * head() const { return _head; }
    6365
    6466        // Added a new element to the queue
    … …  
    6668        inline node_t * push(node_t * elem) {
    6769                node_t * prev = mcs_queue<node_t>::push(elem);
    68                 if (!prev) head = elem;
     70                if (!prev) _head = elem;
    6971                return prev;
    7072        }
    … …  
    7577        // NOT Multi-Thread Safe
    7678        inline node_t * pop(node_t *& next) {
    77                 node_t * elem = head;
     79                node_t * elem = _head;
    7880                // If head is empty just return
    7981                if (!elem) return nullptr;
    … …  
    8183                // If there is already someone in the list, then it's easy
    8284                if (elem->_links.next) {
    83                         head = next = elem->_links.next;
     85                        _head = next = elem->_links.next;
    8486                        // force memory sync
    8587                        __atomic_thread_fence(__ATOMIC_SEQ_CST);
    … …  
    9395                        // at the CAS in advance and therefore can write to head
    9496                        // after that point, it could overwrite the write in push
    95                         head = nullptr;
     97                        _head = nullptr;
    9698                        next = mcs_queue<node_t>::advance(elem);
    9799
    … …  
    99101                        // it is the only way we can guarantee we are not overwriting
    100102                        // a write made in push
    101                         if (next) head = next;
     103                        if (next) _head = next;
    102104                }
    103105

  • doc/theses/thierry_delisle_PhD/code/readyQ_proto/work_stealing.hpp

    r8590328 r780a614  
    2828template<typename node_t>
    2929struct __attribute__((aligned(128))) localQ_t {
    30         // volatile unsigned long long val = 0;
    31         // mpsc_queue<node_t> queue = {};
    32         // spinlock_t lock = {};
    33         intrusive_queue_t<node_t> list;
    34 
    35         inline auto ts() { return list.ts(); }
    36         inline auto lock() { return list.lock.lock(); }
    37         inline auto try_lock() { return list.lock.try_lock(); }
    38         inline auto unlock() { return list.lock.unlock(); }
    39 
    40         inline auto push( node_t * node ) { return list.push( node ); }
    41         inline auto pop() { return list.pop(); }
     30        #ifdef NO_MPSC
     31                intrusive_queue_t<node_t> list;
     32
     33                inline auto ts() { return list.ts(); }
     34                inline auto lock() { return list.lock.lock(); }
     35                inline auto try_lock() { return list.lock.try_lock(); }
     36                inline auto unlock() { return list.lock.unlock(); }
     37
     38                inline auto push( node_t * node ) { return list.push( node ); }
     39                inline auto pop() { return list.pop(); }
     40        #else
     41                mpsc_queue<node_t> queue = {};
     42                spinlock_t _lock = {};
     43
     44                inline auto ts() { auto h = queue.head(); return h ? h->_links.ts : 0ull; }
     45                inline auto lock() { return _lock.lock(); }
     46                inline auto try_lock() { return _lock.try_lock(); }
     47                inline auto unlock() { return _lock.unlock(); }
     48
     49                inline auto push( node_t * node ) { return queue.push( node ); }
     50                inline auto pop() { return queue.pop(); }
     51        #endif
     52
     53
    4254};
    4355
    … …  
    7385                auto & list = *({
    7486                        unsigned i;
    75                         do {
     87                        #ifdef NO_MPSC
     88                                do {
     89                        #endif
    7690                                tls.stats.push.attempt++;
    7791                                // unsigned r = tls.rng1.next();
    … …  
    8296                                        i = tls.my_queue + (r % nqueues);
    8397                                }
    84                         } while(!lists[i].try_lock());
     98                        #ifdef NO_MPSC
     99                                } while(!lists[i].try_lock());
     100                        #endif
    85101                        &lists[i];
    86102                });
    87103
    88104                list.push( node );
    89                 list.unlock();
     105                #ifdef NO_MPSC
     106                        list.unlock();
     107                #endif
    90108                // tls.rng2.set_raw_state( tls.rng1.get_raw_state());
    91109                // count++;
    … …  
    95113        __attribute__((noinline, hot)) node_t * pop() {
    96114                if(tls.my_queue != outside) {
    97                         if( tls.myfriend == outside ) {
    98                                 auto r  = tls.rng1.next();
    99                                 tls.myfriend = r % numThreads;
    100                                 tls.mytime = lists[(tls.it % nqueues) + tls.my_queue].ts();
    101                                 // times[tls.myfriend].val = 0;
    102                                 // lists[tls.myfriend].val = 0;
    103                         }
    104                         // else if(times[tls.myfriend].val == 0) {
    105                         // else if(lists[tls.myfriend].val == 0) {
    106                         else if(times[tls.myfriend].val < tls.mytime) {
    107                         // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) {
    108                                 node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
    109                                 tls.stats.help++;
    110                                 tls.myfriend = outside;
    111                                 if(n) return n;
    112                         }
     115                        // if( tls.myfriend == outside ) {
     116                        //      auto r  = tls.rng1.next();
     117                        //      tls.myfriend = r % numThreads;
     118                        //      // assert(lists[(tls.it % nqueues) + tls.my_queue].ts() >= lists[((tls.it + 1) % nqueues) + tls.my_queue].ts());
     119                        //      tls.mytime = std::min(lists[(tls.it % nqueues) + tls.my_queue].ts(), lists[((tls.it + 1) % nqueues) + tls.my_queue].ts());
     120                        //      // times[tls.myfriend].val = 0;
     121                        //      // lists[tls.myfriend].val = 0;
     122                        // }
     123                        // // else if(times[tls.myfriend].val == 0) {
     124                        // // else if(lists[tls.myfriend].val == 0) {
     125                        // else if(times[tls.myfriend].val < tls.mytime) {
     126                        // // else if(times[tls.myfriend].val < lists[(tls.it % nqueues) + tls.my_queue].ts()) {
     127                        //      node_t * n = try_pop(tls.myfriend, tls.stats.pop.help);
     128                        //      tls.stats.help++;
     129                        //      tls.myfriend = outside;
     130                        //      if(n) return n;
     131                        // }
    113132                        // if( tls.myfriend == outside ) {
    114133                        //      auto r  = tls.rng1.next();
    … …  
    141160        inline node_t * local() {
    142161                unsigned i = (--tls.it % nqueues) + tls.my_queue;
     162                node_t * n = try_pop(i, tls.stats.pop.local);
     163                if(n) return n;
     164                i = (--tls.it % nqueues) + tls.my_queue;
    143165                return try_pop(i, tls.stats.pop.local);
    144166        }
    … …  
    192214                list.unlock();
    193215                stat.success++;
    194                 // times[i].val = 1;
    195                 times[i].val = node.first->_links.ts;
    196                 // lists[i].val = node.first->_links.ts;
    197                 return node.first;
     216                #ifdef NO_MPSC
     217                        // times[i].val = 1;
     218                        times[i].val = node.first->_links.ts;
     219                        // lists[i].val = node.first->_links.ts;
     220                        return node.first;
     221                #else
     222                        times[i].val = node->_links.ts;
     223                        return node;
     224                #endif
    198225        }
    199226
Note: See TracChangeset for help on using the changeset viewer.