Changes in libcfa/src/concurrency/ready_queue.cfa [8fc652e0:fc59df78]

File:

• libcfa/src/concurrency/ready_queue.cfa (modified) (19 diffs)

libcfa/src/concurrency/ready_queue.cfa

@@ -17 +17 @@
 // #define __CFA_DEBUG_PRINT_READY_QUEUE__
 
-// #define USE_SNZI
+// #define USE_MPSC
+
+#define USE_RELAXED_FIFO
+// #define USE_WORK_STEALING
 
 #include "bits/defs.hfa"
@@ -28 +31 @@
 #include <unistd.h>
 
-#include "snzi.hfa"
 #include "ready_subqueue.hfa"
 
 static const size_t cache_line_size = 64;
+
+#if !defined(__CFA_NO_STATISTICS__)
+        #define __STATS(...) __VA_ARGS__
+#else
+        #define __STATS(...)
+#endif
 
 // No overriden function, no environment variable, no define
@@ -39 +47 @@
 #endif
 
-#define BIAS 16
+#if   defined(USE_RELAXED_FIFO)
+        #define BIAS 4
+        #define READYQ_SHARD_FACTOR 4
+        #define SEQUENTIAL_SHARD 1
+#elif defined(USE_WORK_STEALING)
+        #define READYQ_SHARD_FACTOR 2
+        #define SEQUENTIAL_SHARD 2
+#else
+        #error no scheduling strategy selected
+#endif
+
+static inline struct $thread * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats));
+static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j __STATS(, __stats_readyQ_pop_t & stats));
+static inline struct $thread * search(struct cluster * cltr);
+static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred);
+
 
 // returns the maximum number of processors the RWLock support
@@ -93 +116 @@
 //=======================================================================
 // Lock-Free registering/unregistering of threads
-unsigned doregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+void register_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
         __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);
 
@@ -107 +130 @@
                         /*paranoid*/ verify(0 == (__alignof__(data[i]) % cache_line_size));
                         /*paranoid*/ verify((((uintptr_t)&data[i]) % cache_line_size) == 0);
-                        return i;
+                        proc->id = i;
                 }
         }
@@ -134 +157 @@
         /*paranoid*/ verify(__alignof__(data[n]) == (2 * cache_line_size));
         /*paranoid*/ verify((((uintptr_t)&data[n]) % cache_line_size) == 0);
-        return n;
-}
-
-void unregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+        proc->id = n;
+}
+
+void unregister_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
         unsigned id = proc->id;
         /*paranoid*/ verify(id < ready);
@@ -192 +215 @@
 
 //=======================================================================
-// Cforall Reqdy Queue used for scheduling
+// Cforall Ready Queue used for scheduling
 //=======================================================================
 void ?{}(__ready_queue_t & this) with (this) {
         lanes.data  = 0p;
+        lanes.tscs  = 0p;
         lanes.count = 0;
 }
 
 void ^?{}(__ready_queue_t & this) with (this) {
-        verify( 1 == lanes.count );
-        #ifdef USE_SNZI
-                verify( !query( snzi ) );
-        #endif
+        verify( SEQUENTIAL_SHARD == lanes.count );
         free(lanes.data);
+        free(lanes.tscs);
 }
 
 //-----------------------------------------------------------------------
-__attribute__((hot)) bool query(struct cluster * cltr) {
-        #ifdef USE_SNZI
-                return query(cltr->ready_queue.snzi);
-        #endif
-        return true;
-}
-
-static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
-        unsigned i;
-        bool local;
-        #if defined(BIAS)
+#if defined(USE_RELAXED_FIFO)
+        //-----------------------------------------------------------------------
+        // get index from random number with or without bias towards queues
+        static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
+                unsigned i;
+                bool local;
                 unsigned rlow  = r % BIAS;
                 unsigned rhigh = r / BIAS;
@@ -224 +241 @@
                         // (BIAS - 1) out of BIAS chances
                         // Use perferred queues
-                        i = preferred + (rhigh % 4);
+                        i = preferred + (rhigh % READYQ_SHARD_FACTOR);
                         local = true;
                 }
@@ -233 +250 @@
                         local = false;
                 }
-        #else
-                i = r;
-                local = false;
+                return [i, local];
+        }
+
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
+                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
+
+                const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
+                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
+
+                // write timestamp
+                thrd->link.ts = rdtscl();
+
+                bool local;
+                int preferred = external ? -1 : kernelTLS().this_processor->rdq.id;
+
+                // Try to pick a lane and lock it
+                unsigned i;
+                do {
+                        // Pick the index of a lane
+                        unsigned r = __tls_rand_fwd();
+                        [i, local] = idx_from_r(r, preferred);
+
+                        i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+
+                        #if !defined(__CFA_NO_STATISTICS__)
+                                if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.attempt, 1, __ATOMIC_RELAXED);
+                                else if(local) __tls_stats()->ready.push.local.attempt++;
+                                else __tls_stats()->ready.push.share.attempt++;
+                        #endif
+
+                #if defined(USE_MPSC)
+                        // mpsc always succeeds
+                } while( false );
+                #else
+                        // If we can't lock it retry
+                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
+                #endif
+
+                // Actually push it
+                push(lanes.data[i], thrd);
+
+                #if !defined(USE_MPSC)
+                        // Unlock and return
+                        __atomic_unlock( &lanes.data[i].lock );
+                #endif
+
+                // Mark the current index in the tls rng instance as having an item
+                __tls_rand_advance_bck();
+
+                __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
+
+                // Update statistics
+                #if !defined(__CFA_NO_STATISTICS__)
+                        if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
+                        else if(local) __tls_stats()->ready.push.local.success++;
+                        else __tls_stats()->ready.push.share.success++;
+                #endif
+        }
+
+        // Pop from the ready queue from a given cluster
+        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
+                /* paranoid */ verify( lanes.count > 0 );
+                /* paranoid */ verify( kernelTLS().this_processor );
+                /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes.count );
+
+                unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+                int preferred = kernelTLS().this_processor->rdq.id;
+
+
+                // As long as the list is not empty, try finding a lane that isn't empty and pop from it
+                for(25) {
+                        // Pick two lists at random
+                        unsigned ri = __tls_rand_bck();
+                        unsigned rj = __tls_rand_bck();
+
+                        unsigned i, j;
+                        __attribute__((unused)) bool locali, localj;
+                        [i, locali] = idx_from_r(ri, preferred);
+                        [j, localj] = idx_from_r(rj, preferred);
+
+                        i %= count;
+                        j %= count;
+
+                        // try popping from the 2 picked lists
+                        struct $thread * thrd = try_pop(cltr, i, j __STATS(, *(locali || localj ? &__tls_stats()->ready.pop.local : &__tls_stats()->ready.pop.help)));
+                        if(thrd) {
+                                return thrd;
+                        }
+                }
+
+                // All lanes where empty return 0p
+                return 0p;
+        }
+
+        __attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) { return pop_fast(cltr); }
+        __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) {
+                return search(cltr);
+        }
+#endif
+#if defined(USE_WORK_STEALING)
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
+                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
+
+                const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
+                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
+
+                // write timestamp
+                thrd->link.ts = rdtscl();
+
+                // Try to pick a lane and lock it
+                unsigned i;
+                do {
+                        #if !defined(__CFA_NO_STATISTICS__)
+                                if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.attempt, 1, __ATOMIC_RELAXED);
+                                else __tls_stats()->ready.push.local.attempt++;
+                        #endif
+
+                        if(unlikely(external)) {
+                                i = __tls_rand() % lanes.count;
+                        }
+                        else {
+                                processor * proc = kernelTLS().this_processor;
+                                unsigned r = proc->rdq.its++;
+                                i =  proc->rdq.id + (r % READYQ_SHARD_FACTOR);
+                        }
+
+
+                #if defined(USE_MPSC)
+                        // mpsc always succeeds
+                } while( false );
+                #else
+                        // If we can't lock it retry
+                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
+                #endif
+
+                // Actually push it
+                push(lanes.data[i], thrd);
+
+                #if !defined(USE_MPSC)
+                        // Unlock and return
+                        __atomic_unlock( &lanes.data[i].lock );
+                #endif
+
+                #if !defined(__CFA_NO_STATISTICS__)
+                        if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
+                        else __tls_stats()->ready.push.local.success++;
+                #endif
+
+                __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
+        }
+
+        // Pop from the ready queue from a given cluster
+        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
+                /* paranoid */ verify( lanes.count > 0 );
+                /* paranoid */ verify( kernelTLS().this_processor );
+                /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes.count );
+
+                processor * proc = kernelTLS().this_processor;
+
+                if(proc->rdq.target == -1u) {
+                        proc->rdq.target = __tls_rand() % lanes.count;
+                        unsigned it1  = proc->rdq.itr;
+                        unsigned it2  = proc->rdq.itr + 1;
+                        unsigned idx1 = proc->rdq.id + (it1 % READYQ_SHARD_FACTOR);
+                        unsigned idx2 = proc->rdq.id + (it2 % READYQ_SHARD_FACTOR);
+                        unsigned long long tsc1 = ts(lanes.data[idx1]);
+                        unsigned long long tsc2 = ts(lanes.data[idx2]);
+                        proc->rdq.cutoff = min(tsc1, tsc2);
+                        if(proc->rdq.cutoff == 0) proc->rdq.cutoff = -1ull;
+                }
+                else {
+                        unsigned target = proc->rdq.target;
+                        proc->rdq.target = -1u;
+                        if(lanes.tscs[target].tv < proc->rdq.cutoff) {
+                                $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
+                                if(t) return t;
+                        }
+                }
+
+                for(READYQ_SHARD_FACTOR) {
+                        unsigned i = proc->rdq.id + (--proc->rdq.itr % READYQ_SHARD_FACTOR);
+                        if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
+                }
+                return 0p;
+        }
+
+        __attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
+                unsigned i = __tls_rand() % lanes.count;
+                return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
+        }
+
+        __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) with (cltr->ready_queue) {
+                return search(cltr);
+        }
+#endif
+
+//=======================================================================
+// Various Ready Queue utilities
+//=======================================================================
+// these function work the same or almost the same
+// whether they are using work-stealing or relaxed fifo scheduling
+
+//-----------------------------------------------------------------------
+// try to pop from a lane given by index w
+static inline struct $thread * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->ready_queue) {
+        __STATS( stats.attempt++; )
+
+        // Get relevant elements locally
+        __intrusive_lane_t & lane = lanes.data[w];
+
+        // If list looks empty retry
+        if( is_empty(lane) ) {
+                __STATS( stats.espec++; )
+                return 0p;
+        }
+
+        // If we can't get the lock retry
+        if( !__atomic_try_acquire(&lane.lock) ) {
+                __STATS( stats.elock++; )
+                return 0p;
+        }
+
+        // If list is empty, unlock and retry
+        if( is_empty(lane) ) {
+                __atomic_unlock(&lane.lock);
+                __STATS( stats.eempty++; )
+                return 0p;
+        }
+
+        // Actually pop the list
+        struct $thread * thrd;
+        thrd = pop(lane);
+
+        /* paranoid */ verify(thrd);
+        /* paranoid */ verify(lane.lock);
+
+        // Unlock and return
+        __atomic_unlock(&lane.lock);
+
+        // Update statistics
+        __STATS( stats.success++; )
+
+        #if defined(USE_WORK_STEALING)
+                lanes.tscs[w].tv = thrd->link.ts;
         #endif
-        return [i, local];
+
+        // return the popped thread
+        return thrd;
 }
 
 //-----------------------------------------------------------------------
-__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
-        __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
-
-        // write timestamp
-        thrd->link.ts = rdtscl();
-
-        __attribute__((unused)) bool local;
-        __attribute__((unused)) int preferred;
-        #if defined(BIAS)
-                preferred =
-                        //*
-                        kernelTLS().this_processor ? kernelTLS().this_processor->id * 4 : -1;
-                        /*/
-                        thrd->link.preferred * 4;
-                        //*/
-        #endif
-
-        // Try to pick a lane and lock it
-        unsigned i;
-        do {
-                // Pick the index of a lane
-                // unsigned r = __tls_rand();
-                unsigned r = __tls_rand_fwd();
-                [i, local] = idx_from_r(r, preferred);
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        if(local) {
-                                __tls_stats()->ready.pick.push.local++;
-                        }
-                #endif
-
-                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        __tls_stats()->ready.pick.push.attempt++;
-                #endif
-
-                // If we can't lock it retry
-        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-
-        bool first = false;
-
-        // Actually push it
-        #ifdef USE_SNZI
-                bool lane_first =
-        #endif
-
-        push(lanes.data[i], thrd);
-
-        #ifdef USE_SNZI
-                // If this lane used to be empty we need to do more
-                if(lane_first) {
-                        // Check if the entire queue used to be empty
-                        first = !query(snzi);
-
-                        // Update the snzi
-                        arrive( snzi, i );
-                }
-        #endif
-
-        __tls_rand_advance_bck();
-
-        // Unlock and return
-        __atomic_unlock( &lanes.data[i].lock );
-
-        __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
-
-        // Update statistics
-        #if !defined(__CFA_NO_STATISTICS__)
-                #if defined(BIAS)
-                        if( local ) __tls_stats()->ready.pick.push.lsuccess++;
-                #endif
-                __tls_stats()->ready.pick.push.success++;
-        #endif
-
-        // return whether or not the list was empty before this push
-        return first;
-}
-
-static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j);
-static struct $thread * try_pop(struct cluster * cltr, unsigned i);
-
-// Pop from the ready queue from a given cluster
-__attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) {
-        /* paranoid */ verify( lanes.count > 0 );
-        unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
-        int preferred;
-        #if defined(BIAS)
-                // Don't bother trying locally too much
-                int local_tries = 8;
-                preferred = kernelTLS().this_processor->id * 4;
-        #endif
-
-
-        // As long as the list is not empty, try finding a lane that isn't empty and pop from it
-        #ifdef USE_SNZI
-                while( query(snzi) ) {
-        #else
-                for(25) {
-        #endif
-                // Pick two lists at random
-                // unsigned ri = __tls_rand();
-                // unsigned rj = __tls_rand();
-                unsigned ri = __tls_rand_bck();
-                unsigned rj = __tls_rand_bck();
-
-                unsigned i, j;
-                __attribute__((unused)) bool locali, localj;
-                [i, locali] = idx_from_r(ri, preferred);
-                [j, localj] = idx_from_r(rj, preferred);
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        if(locali) {
-                                __tls_stats()->ready.pick.pop.local++;
-                        }
-                        if(localj) {
-                                __tls_stats()->ready.pick.pop.local++;
-                        }
-                #endif
-
-                i %= count;
-                j %= count;
-
-                // try popping from the 2 picked lists
-                struct $thread * thrd = try_pop(cltr, i, j);
-                if(thrd) {
-                        #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
-                                if( locali || localj ) __tls_stats()->ready.pick.pop.lsuccess++;
-                        #endif
-                        return thrd;
-                }
-        }
-
-        // All lanes where empty return 0p
-        return 0p;
-}
-
-__attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
+// try to pop from any lanes making sure you don't miss any threads push
+// before the start of the function
+static inline struct $thread * search(struct cluster * cltr) with (cltr->ready_queue) {
         /* paranoid */ verify( lanes.count > 0 );
         unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
@@ -384 +509 @@
         for(i; count) {
                 unsigned idx = (offset + i) % count;
-                struct $thread * thrd = try_pop(cltr, idx);
+                struct $thread * thrd = try_pop(cltr, idx __STATS(, __tls_stats()->ready.pop.search));
                 if(thrd) {
                         return thrd;
@@ -394 +519 @@
 }
 
-
 //-----------------------------------------------------------------------
-// Given 2 indexes, pick the list with the oldest push an try to pop from it
-static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) {
-        #if !defined(__CFA_NO_STATISTICS__)
-                __tls_stats()->ready.pick.pop.attempt++;
-        #endif
-
-        // Pick the bet list
-        int w = i;
-        if( __builtin_expect(!is_empty(lanes.data[j]), true) ) {
-                w = (ts(lanes.data[i]) < ts(lanes.data[j])) ? i : j;
-        }
-
-        return try_pop(cltr, w);
-}
-
-static inline struct $thread * try_pop(struct cluster * cltr, unsigned w) with (cltr->ready_queue) {
-        // Get relevant elements locally
-        __intrusive_lane_t & lane = lanes.data[w];
-
-        // If list looks empty retry
-        if( is_empty(lane) ) return 0p;
-
-        // If we can't get the lock retry
-        if( !__atomic_try_acquire(&lane.lock) ) return 0p;
-
-
-        // If list is empty, unlock and retry
-        if( is_empty(lane) ) {
-                __atomic_unlock(&lane.lock);
-                return 0p;
-        }
-
-        // Actually pop the list
-        struct $thread * thrd;
-        thrd = pop(lane);
-
-        /* paranoid */ verify(thrd);
-        /* paranoid */ verify(lane.lock);
-
-        #ifdef USE_SNZI
-                // If this was the last element in the lane
-                if(emptied) {
-                        depart( snzi, w );
-                }
-        #endif
-
-        // Unlock and return
-        __atomic_unlock(&lane.lock);
-
-        // Update statistics
-        #if !defined(__CFA_NO_STATISTICS__)
-                __tls_stats()->ready.pick.pop.success++;
-        #endif
-
-        // Update the thread bias
-        thrd->link.preferred = w / 4;
-
-        // return the popped thread
-        return thrd;
-}
-//-----------------------------------------------------------------------
-
-bool remove_head(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
-        for(i; lanes.count) {
-                __intrusive_lane_t & lane = lanes.data[i];
-
-                bool removed = false;
-
-                __atomic_acquire(&lane.lock);
-                        if(head(lane)->link.next == thrd) {
-                                $thread * pthrd;
-                                pthrd = pop(lane);
-
-                                /* paranoid */ verify( pthrd == thrd );
-
-                                removed = true;
-                                #ifdef USE_SNZI
-                                        if(emptied) {
-                                                depart( snzi, i );
-                                        }
-                                #endif
-                        }
-                __atomic_unlock(&lane.lock);
-
-                if( removed ) return true;
-        }
-        return false;
-}
-
-//-----------------------------------------------------------------------
-
+// Check that all the intrusive queues in the data structure are still consistent
 static void check( __ready_queue_t & q ) with (q) {
-        #if defined(__CFA_WITH_VERIFY__)
+        #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
                 {
                         for( idx ; lanes.count ) {
@@ -499 +533 @@
                                 assert(tail(sl)->link.prev->link.next == tail(sl) );
 
-                                if(sl.before.link.ts == 0l) {
+                                if(is_empty(sl)) {
                                         assert(tail(sl)->link.prev == head(sl));
                                         assert(head(sl)->link.next == tail(sl));
@@ -511 +545 @@
 }
 
+//-----------------------------------------------------------------------
+// Given 2 indexes, pick the list with the oldest push an try to pop from it
+static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->ready_queue) {
+        // Pick the bet list
+        int w = i;
+        if( __builtin_expect(!is_empty(lanes.data[j]), true) ) {
+                w = (ts(lanes.data[i]) < ts(lanes.data[j])) ? i : j;
+        }
+
+        return try_pop(cltr, w __STATS(, stats));
+}
+
 // Call this function of the intrusive list was moved using memcpy
 // fixes the list so that the pointers back to anchors aren't left dangling
 static inline void fix(__intrusive_lane_t & ll) {
-        // if the list is not empty then follow he pointer and fix its reverse
-        if(!is_empty(ll)) {
-                head(ll)->link.next->link.prev = head(ll);
-                tail(ll)->link.prev->link.next = tail(ll);
-        }
-        // Otherwise just reset the list
-        else {
-                verify(tail(ll)->link.next == 0p);
-                tail(ll)->link.prev = head(ll);
-                head(ll)->link.next = tail(ll);
-                verify(head(ll)->link.prev == 0p);
-        }
+        #if !defined(USE_MPSC)
+                // if the list is not empty then follow he pointer and fix its reverse
+                if(!is_empty(ll)) {
+                        head(ll)->link.next->link.prev = head(ll);
+                        tail(ll)->link.prev->link.next = tail(ll);
+                }
+                // Otherwise just reset the list
+                else {
+                        verify(tail(ll)->link.next == 0p);
+                        tail(ll)->link.prev = head(ll);
+                        head(ll)->link.next = tail(ll);
+                        verify(head(ll)->link.prev == 0p);
+                }
+        #endif
+}
+
+static void assign_list(unsigned & value, dlist(processor, processor) & list, unsigned count) {
+        processor * it = &list`first;
+        for(unsigned i = 0; i < count; i++) {
+                /* paranoid */ verifyf( it, "Unexpected null iterator, at index %u of %u\n", i, count);
+                it->rdq.id = value;
+                it->rdq.target = -1u;
+                value += READYQ_SHARD_FACTOR;
+                it = &(*it)`next;
+        }
+}
+
+static void reassign_cltr_id(struct cluster * cltr) {
+        unsigned preferred = 0;
+        assign_list(preferred, cltr->procs.actives, cltr->procs.total - cltr->procs.idle);
+        assign_list(preferred, cltr->procs.idles  , cltr->procs.idle );
+}
+
+static void fix_times( struct cluster * cltr ) with( cltr->ready_queue ) {
+        #if defined(USE_WORK_STEALING)
+                lanes.tscs = alloc(lanes.count, lanes.tscs`realloc);
+                for(i; lanes.count) {
+                        lanes.tscs[i].tv = ts(lanes.data[i]);
+                }
+        #endif
 }
 
 // Grow the ready queue
-void ready_queue_grow  (struct cluster * cltr, int target) {
+void ready_queue_grow(struct cluster * cltr) {
+        size_t ncount;
+        int target = cltr->procs.total;
+
         /* paranoid */ verify( ready_mutate_islocked() );
         __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
@@ -538 +615 @@
         // grow the ready queue
         with( cltr->ready_queue ) {
-                #ifdef USE_SNZI
-                        ^(snzi){};
-                #endif
-
                 // Find new count
                 // Make sure we always have atleast 1 list
-                size_t ncount = target >= 2 ? target * 4: 1;
+                if(target >= 2) {
+                        ncount = target * READYQ_SHARD_FACTOR;
+                } else {
+                        ncount = SEQUENTIAL_SHARD;
+                }
 
                 // Allocate new array (uses realloc and memcpies the data)
@@ -561 +638 @@
                 // Update original
                 lanes.count = ncount;
-
-                #ifdef USE_SNZI
-                        // Re-create the snzi
-                        snzi{ log2( lanes.count / 8 ) };
-                        for( idx; (size_t)lanes.count ) {
-                                if( !is_empty(lanes.data[idx]) ) {
-                                        arrive(snzi, idx);
-                                }
-                        }
-                #endif
-        }
+        }
+
+        fix_times(cltr);
+
+        reassign_cltr_id(cltr);
 
         // Make sure that everything is consistent
@@ -582 +653 @@
 
 // Shrink the ready queue
-void ready_queue_shrink(struct cluster * cltr, int target) {
+void ready_queue_shrink(struct cluster * cltr) {
         /* paranoid */ verify( ready_mutate_islocked() );
         __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
@@ -589 +660 @@
         /* paranoid */ check( cltr->ready_queue );
 
+        int target = cltr->procs.total;
+
         with( cltr->ready_queue ) {
-                #ifdef USE_SNZI
-                        ^(snzi){};
-                #endif
-
                 // Remember old count
                 size_t ocount = lanes.count;
@@ -599 +668 @@
                 // Find new count
                 // Make sure we always have atleast 1 list
-                lanes.count = target >= 2 ? target * 4: 1;
+                lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD;
                 /* paranoid */ verify( ocount >= lanes.count );
-                /* paranoid */ verify( lanes.count == target * 4 || target < 2 );
+                /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 );
 
                 // for printing count the number of displaced threads
@@ -644 +713 @@
                         fix(lanes.data[idx]);
                 }
-
-                #ifdef USE_SNZI
-                        // Re-create the snzi
-                        snzi{ log2( lanes.count / 8 ) };
-                        for( idx; (size_t)lanes.count ) {
-                                if( !is_empty(lanes.data[idx]) ) {
-                                        arrive(snzi, idx);
-                                }
-                        }
-                #endif
-        }
+        }
+
+        fix_times(cltr);
+
+        reassign_cltr_id(cltr);
 
         // Make sure that everything is consistent