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

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_MPSC
-
-#define USE_RELAXED_FIFO
-// #define USE_WORK_STEALING
+// #define USE_SNZI
 
 #include "bits/defs.hfa"
@@ -31 +28 @@
 #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
@@ -47 +39 @@
 #endif
 
-#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);
-
+#define BIAS 16
 
 // returns the maximum number of processors the RWLock support
@@ -116 +93 @@
 //=======================================================================
 // Lock-Free registering/unregistering of threads
-void register_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+unsigned doregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
         __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);
 
@@ -130 +107 @@
                         /*paranoid*/ verify(0 == (__alignof__(data[i]) % cache_line_size));
                         /*paranoid*/ verify((((uintptr_t)&data[i]) % cache_line_size) == 0);
-                        proc->id = i;
+                        return i;
                 }
         }
@@ -157 +134 @@
         /*paranoid*/ verify(__alignof__(data[n]) == (2 * cache_line_size));
         /*paranoid*/ verify((((uintptr_t)&data[n]) % cache_line_size) == 0);
-        proc->id = n;
-}
-
-void unregister_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+        return n;
+}
+
+void unregister( struct __processor_id_t * proc ) with(*__scheduler_lock) {
         unsigned id = proc->id;
         /*paranoid*/ verify(id < ready);
@@ -215 +192 @@
 
 //=======================================================================
-// Cforall Ready Queue used for scheduling
+// Cforall Reqdy 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( SEQUENTIAL_SHARD == lanes.count );
+        verify( 1 == lanes.count );
+        #ifdef USE_SNZI
+                verify( !query( snzi ) );
+        #endif
         free(lanes.data);
-        free(lanes.tscs);
 }
 
 //-----------------------------------------------------------------------
-#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;
+__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)
                 unsigned rlow  = r % BIAS;
                 unsigned rhigh = r / BIAS;
@@ -241 +224 @@
                         // (BIAS - 1) out of BIAS chances
                         // Use perferred queues
-                        i = preferred + (rhigh % READYQ_SHARD_FACTOR);
+                        i = preferred + (rhigh % 4);
                         local = true;
                 }
@@ -250 +233 @@
                         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++;
+        #else
+                i = r;
+                local = false;
+        #endif
+        return [i, local];
+}
+
+//-----------------------------------------------------------------------
+__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
-
-                #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 the popped thread
-        return thrd;
-}
-
-//-----------------------------------------------------------------------
-// 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) {
+                        return thrd;
+                }
+        }
+
+        // All lanes where empty return 0p
+        return 0p;
+}
+
+__attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
         /* paranoid */ verify( lanes.count > 0 );
         unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
@@ -509 +384 @@
         for(i; count) {
                 unsigned idx = (offset + i) % count;
-                struct $thread * thrd = try_pop(cltr, idx __STATS(, __tls_stats()->ready.pop.search));
+                struct $thread * thrd = try_pop(cltr, idx);
                 if(thrd) {
                         return thrd;
@@ -519 +394 @@
 }
 
+
 //-----------------------------------------------------------------------
-// Check that all the intrusive queues in the data structure are still consistent
+// 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;
+}
+
+//-----------------------------------------------------------------------
+
 static void check( __ready_queue_t & q ) with (q) {
-        #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
+        #if defined(__CFA_WITH_VERIFY__)
                 {
                         for( idx ; lanes.count ) {
@@ -533 +499 @@
                                 assert(tail(sl)->link.prev->link.next == tail(sl) );
 
-                                if(is_empty(sl)) {
+                                if(sl.before.link.ts == 0l) {
                                         assert(tail(sl)->link.prev == head(sl));
                                         assert(head(sl)->link.next == tail(sl));
@@ -545 +511 @@
 }
 
-//-----------------------------------------------------------------------
-// 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 !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
+        // 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);
+        }
 }
 
 // Grow the ready queue
-void ready_queue_grow(struct cluster * cltr) {
-        size_t ncount;
-        int target = cltr->procs.total;
-
+void ready_queue_grow  (struct cluster * cltr, int target) {
         /* paranoid */ verify( ready_mutate_islocked() );
         __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
@@ -615 +538 @@
         // grow the ready queue
         with( cltr->ready_queue ) {
+                #ifdef USE_SNZI
+                        ^(snzi){};
+                #endif
+
                 // Find new count
                 // Make sure we always have atleast 1 list
-                if(target >= 2) {
-                        ncount = target * READYQ_SHARD_FACTOR;
-                } else {
-                        ncount = SEQUENTIAL_SHARD;
-                }
+                size_t ncount = target >= 2 ? target * 4: 1;
 
                 // Allocate new array (uses realloc and memcpies the data)
@@ -638 +561 @@
                 // Update original
                 lanes.count = ncount;
-        }
-
-        fix_times(cltr);
-
-        reassign_cltr_id(cltr);
+
+                #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
+        }
 
         // Make sure that everything is consistent
@@ -653 +582 @@
 
 // Shrink the ready queue
-void ready_queue_shrink(struct cluster * cltr) {
+void ready_queue_shrink(struct cluster * cltr, int target) {
         /* paranoid */ verify( ready_mutate_islocked() );
         __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
@@ -660 +589 @@
         /* 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;
@@ -668 +599 @@
                 // Find new count
                 // Make sure we always have atleast 1 list
-                lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD;
+                lanes.count = target >= 2 ? target * 4: 1;
                 /* paranoid */ verify( ocount >= lanes.count );
-                /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 );
+                /* paranoid */ verify( lanes.count == target * 4 || target < 2 );
 
                 // for printing count the number of displaced threads
@@ -713 +644 @@
                         fix(lanes.data[idx]);
                 }
-        }
-
-        fix_times(cltr);
-
-        reassign_cltr_id(cltr);
+
+                #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
+        }
 
         // Make sure that everything is consistent