Index: doc/theses/thierry_delisle_PhD/code/readyQ_proto/dynamic_entropy.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/readyQ_proto/dynamic_entropy.hpp (revision fe63ae6687cf21ac9ea1960157c172fa0b383ca3) +++ doc/theses/thierry_delisle_PhD/code/readyQ_proto/dynamic_entropy.hpp (revision fe63ae6687cf21ac9ea1960157c172fa0b383ca3) @@ -0,0 +1,200 @@ +#pragma once + +#define LIST_VARIANT dyn_ent_list + +#include +#include +#include + +#include "assert.hpp" +#include "utils.hpp" +#include "links.hpp" + +std::mutex mtx_; + +template +class __attribute__((aligned(128))) dyn_ent_list { + const unsigned numLists; + __attribute__((aligned(64))) std::unique_ptr []> lists; + +public: + dyn_ent_list(unsigned numThreads, unsigned) + : numLists(numThreads * 4) + , lists(new intrusive_queue_t[numLists]) + { + std::cout << "Constructing Relaxed List with " << numLists << std::endl; + } + + __attribute__((noinline, hot)) void push(node_t * node) { + node->_links.ts = rdtscl(); + + // Try to pick a lane and lock it + unsigned i; + do { + // Pick the index of a lane + i = idx_from_r(tls.rng1.next(), tls.my_queue); + // i = ret.first; //local = ret.second; + tls.stats.push.attempt++; + } while( !lists[i].lock.try_lock() ); + + lists[i].push(node); + lists[i].lock.unlock(); + tls.rng2.set_raw_state( tls.rng1.get_raw_state()); + tls.stats.push.success++; + } + + __attribute__((noinline, hot)) node_t * pop() { + for(int n = 0; n < 25; n++) { + // Pick two lists at random + unsigned i, j; + // bool locali, localj; + i = idx_from_r(tls.rng2.prev(), tls.my_queue); + j = idx_from_r(tls.rng2.prev(), tls.my_queue); + + // i = reti.first; //local = reti.second; + // j = retj.first; //local = retj.second; + tls.stats.pop.attempt++; + + // try popping from the 2 picked lists + node_t * thrd = try_pop(i, j); + if(thrd) { + tls.stats.pop.success++; + return thrd; + } + } + + unsigned offset = tls.rng2.next(); + for(unsigned i = 0; i < numLists; i++) { + unsigned idx = (offset + i) % numLists; + node_t * thrd = try_pop(idx); + if(thrd) { + return thrd; + } + } + + // All lanes where empty return 0p + return nullptr; + } + +private: + inline node_t * try_pop(unsigned i, unsigned j) { + // Pick the bet list + int w = i; + if( __builtin_expect(!(lists[j].ts() > 0), true) ) { + w = (lists[i].ts() < lists[j].ts()) ? i : j; + } + + return try_pop(w); + } + + inline node_t * try_pop(unsigned w) { + // If list looks empty retry + if( lists[w].ts() == 0 ) { tls.stats.pop.empty++; return nullptr; } + + // If we can't get the lock retry + if( !lists[w].lock.try_lock() ) { tls.stats.pop.locked++; return nullptr; } + + + // If list is empty, unlock and retry + if( lists[w].ts() == 0 ) { + tls.stats.pop.both++; + lists[w].lock.unlock(); + return nullptr; + } + + auto node = lists[w].pop(); + lists[w].lock.unlock(); + return node.first; + } + + inline unsigned idx_from_r(unsigned r, unsigned preferred) { + unsigned i; + // bool local; + unsigned rlow = r % 4; + unsigned rhigh = r / 4; + if((0 != rlow) && preferred != outside) { + // (BIAS - 1) out of BIAS chances + // Use perferred queues + i = preferred + (rhigh % 4); + // local = true; + } + else { + // 1 out of BIAS chances + // Use all queues + i = rhigh; + // local = false; + } + return i % numLists; + } +private: + static std::atomic_uint32_t ticket; + static const unsigned outside = 0xFFFFFFFF; + + static inline unsigned calc_preferred() { + unsigned t = ticket++; + if(t == 0) return outside; + unsigned i = 4 * (t - 1); + return i; + } + + static __attribute__((aligned(128))) thread_local struct TLS { + Random rng1 = { unsigned(std::hash{}(std::this_thread::get_id()) ^ rdtscl()) }; + Random rng2 = { unsigned(std::hash{}(std::this_thread::get_id()) ^ rdtscl()) }; + unsigned my_queue = calc_preferred(); + struct { + struct { + size_t attempt = 0; + size_t success = 0; + } push; + struct { + size_t attempt = 0; + size_t success = 0; + size_t empty = 0; + size_t locked = 0; + size_t both = 0; + } pop; + } stats; + } tls; +public: + static const char * name() { + return "Dynamic Entropy List"; + } + +public: + static struct GlobalStats { + 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 empty = 0; + std::atomic_size_t locked = 0; + std::atomic_size_t both = 0; + } pop; + } global_stats; + static void stats_tls_tally() { + global_stats.push.attempt += tls.stats.push.attempt; + global_stats.push.success += tls.stats.push.success; + global_stats.pop .attempt += tls.stats.pop.attempt; + global_stats.pop .success += tls.stats.pop.success; + global_stats.pop .empty += tls.stats.pop.empty; + global_stats.pop .locked += tls.stats.pop.locked; + global_stats.pop .both += tls.stats.pop.both; + } + + static void stats_print(std::ostream & os) { + const auto & global = global_stats; + + double push_sur = (100.0 * double(global.push.success) / global.push.attempt); + double pop_sur = (100.0 * double(global.pop .success) / global.pop .attempt); + + double push_len = double(global.push.attempt ) / global.push.success; + double pop_len = double(global.pop .attempt ) / global.pop .success; + + os << "Push Pick : " << push_sur << " %, len " << push_len << " (" << global.push.attempt << " / " << global.push.success << ")\n"; + os << "Pop Pick : " << pop_sur << " %, len " << pop_len << " (" << global.pop .attempt << " / " << global.pop .success << ")\n"; + os << "Pop Fails : " << global_stats.pop .empty << "e, " << global_stats.pop .locked << "l, " << global_stats.pop .both << "\n"; + } +}; Index: doc/theses/thierry_delisle_PhD/code/readyQ_proto/relaxed_list.cpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/readyQ_proto/relaxed_list.cpp (revision 73f4d084fe155d69b7fe36866e5666bde0a03166) +++ doc/theses/thierry_delisle_PhD/code/readyQ_proto/relaxed_list.cpp (revision fe63ae6687cf21ac9ea1960157c172fa0b383ca3) @@ -691,6 +691,6 @@ for(const auto & n : nodes) { - local.valmax = max(local.valmax, size_t(n.value)); - local.valmin = min(local.valmin, size_t(n.value)); + local.valmax = std::max(local.valmax, size_t(n.value)); + local.valmin = std::min(local.valmin, size_t(n.value)); } @@ -773,5 +773,5 @@ try { arg = optarg = argv[optind]; - nnodes = stoul(optarg, &len); + nnodes = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -792,5 +792,5 @@ try { arg = optarg = argv[optind]; - nnodes = stoul(optarg, &len); + nnodes = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -812,5 +812,5 @@ try { arg = optarg = argv[optind]; - nnodes = stoul(optarg, &len); + nnodes = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } nslots = nnodes; @@ -823,5 +823,5 @@ try { arg = optarg = argv[optind]; - nnodes = stoul(optarg, &len); + nnodes = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -831,5 +831,5 @@ try { arg = optarg = argv[optind + 1]; - nslots = stoul(optarg, &len); + nslots = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -884,5 +884,5 @@ case 'd': try { - duration = stod(optarg, &len); + duration = std::stod(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -893,5 +893,5 @@ case 't': try { - nthreads = stoul(optarg, &len); + nthreads = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { @@ -902,5 +902,5 @@ case 'q': try { - nqueues = stoul(optarg, &len); + nqueues = std::stoul(optarg, &len); if(len != arg.size()) { throw std::invalid_argument(""); } } catch(std::invalid_argument &) { Index: doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi-packed.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi-packed.hpp (revision 73f4d084fe155d69b7fe36866e5666bde0a03166) +++ doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi-packed.hpp (revision fe63ae6687cf21ac9ea1960157c172fa0b383ca3) @@ -168,5 +168,4 @@ for(int i = 0; i < width; i++) { int idx = i % hwdith; - std::cout << i << " -> " << idx + width << std::endl; leafs[i].parent = &nodes[ idx ]; } @@ -174,5 +173,4 @@ for(int i = 0; i < root; i++) { int idx = (i / 2) + hwdith; - std::cout << i + width << " -> " << idx + width << std::endl; nodes[i].parent = &nodes[ idx ]; } Index: doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi.hpp =================================================================== --- doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi.hpp (revision 73f4d084fe155d69b7fe36866e5666bde0a03166) +++ doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi.hpp (revision fe63ae6687cf21ac9ea1960157c172fa0b383ca3) @@ -159,5 +159,4 @@ std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ") " << (sizeof(snzi_t::node) * (root + 1)) << " bytes" << std::endl; for(int i = 0; i < root; i++) { - std::cout << i << " -> " << (i / base) + width << std::endl; nodes[i].parent = &nodes[(i / base) + width]; }