Bug 976848 - Add a 32-bit xorshift to ThreadPoolWorker for thread-local PRNG for workstealing. (r=nmatsakis)
authorShu-yu Guo <shu@rfrn.org>
Wed, 26 Feb 2014 19:51:28 -0800
changeset 171239 c1218ef1628ebb0f7174e0f9b7086e37f701c61f
parent 171238 023aed557989b2cf12825c82b701814ef1bf4b09
child 171240 b39e4dce0e0988507b78f90b8a5a5ca97c678f36
push id270
push userpvanderbeken@mozilla.com
push dateThu, 06 Mar 2014 09:24:21 +0000
reviewersnmatsakis
bugs976848
milestone30.0a1
Bug 976848 - Add a 32-bit xorshift to ThreadPoolWorker for thread-local PRNG for workstealing. (r=nmatsakis)
js/src/vm/ThreadPool.cpp
js/src/vm/ThreadPool.h
--- a/js/src/vm/ThreadPool.cpp
+++ b/js/src/vm/ThreadPool.cpp
@@ -28,16 +28,24 @@ ComposeSliceBounds(uint16_t from, uint16
 static inline void
 DecomposeSliceBounds(uint32_t bounds, uint16_t *from, uint16_t *to)
 {
     *from = bounds >> 16;
     *to = bounds & uint16_t(~0);
     MOZ_ASSERT(*from <= *to);
 }
 
+ThreadPoolWorker::ThreadPoolWorker(uint32_t workerId, uint32_t rngSeed, ThreadPool *pool)
+  : workerId_(workerId),
+    pool_(pool),
+    sliceBounds_(0),
+    state_(CREATED),
+    schedulerRNGState_(rngSeed)
+{ }
+
 bool
 ThreadPoolWorker::hasWork() const
 {
     uint16_t from, to;
     DecomposeSliceBounds(sliceBounds_, &from, &to);
     return from != to;
 }
 
@@ -96,16 +104,28 @@ ThreadPoolWorker::stealFrom(ThreadPoolWo
     if (!victim->popSliceBack(sliceId))
         return false;
 #ifdef DEBUG
     pool_->stolenSlices_++;
 #endif
     return true;
 }
 
+ThreadPoolWorker *
+ThreadPoolWorker::randomWorker()
+{
+    // Perform 32-bit xorshift.
+    uint32_t x = schedulerRNGState_;
+    x ^= x << XORSHIFT_A;
+    x ^= x >> XORSHIFT_B;
+    x ^= x << XORSHIFT_C;
+    schedulerRNGState_ = x;
+    return pool_->workers_[x % pool_->numWorkers()];
+}
+
 bool
 ThreadPoolWorker::start()
 {
 #ifndef JS_THREADSAFE
     return false;
 #else
     if (isMainThread())
         return true;
@@ -190,24 +210,20 @@ ThreadPoolWorker::getSlice(ForkJoinConte
     // First see whether we have any work ourself.
     if (popSliceFront(sliceId))
         return true;
 
     // Try to steal work.
     if (!pool_->workStealing())
         return false;
 
-    ThreadPoolWorker *victim;
     do {
         if (!pool_->hasWork())
             return false;
-
-        // Add one to add the main thread into the mix.
-        victim = pool_->workers_[rand() % pool_->numWorkers()];
-    } while (!stealFrom(victim, sliceId));
+    } while (!stealFrom(randomWorker(), sliceId));
 
     return true;
 }
 
 void
 ThreadPoolWorker::terminate(AutoLockMonitor &lock)
 {
     MOZ_ASSERT(lock.isFor(*pool_));
@@ -271,16 +287,18 @@ ThreadPool::workStealing() const
 #ifdef DEBUG
     if (char *stealEnv = getenv("JS_THREADPOOL_STEAL"))
         return !!strtol(stealEnv, nullptr, 10);
 #endif
 
     return true;
 }
 
+extern uint64_t random_next(uint64_t *, int);
+
 bool
 ThreadPool::lazyStartWorkers(JSContext *cx)
 {
     // Starts the workers if they have not already been started.  If
     // something goes wrong, reports an error and ensures that all
     // partially started threads are terminated.  Therefore, upon exit
     // from this function, the workers array is either full (upon
     // success) or empty (upon failure).
@@ -290,18 +308,20 @@ ThreadPool::lazyStartWorkers(JSContext *
         MOZ_ASSERT(workers_.length() == numWorkers());
         return true;
     }
 
     // Allocate workers array and then start the worker threads.
     // Note that numWorkers() is the number of *desired* workers,
     // but workers_.length() is the number of *successfully
     // initialized* workers.
+    uint64_t rngState = 0;
     for (uint32_t workerId = 0; workerId < numWorkers(); workerId++) {
-        ThreadPoolWorker *worker = cx->new_<ThreadPoolWorker>(workerId, this);
+        uint32_t rngSeed = uint32_t(random_next(&rngState, 32));
+        ThreadPoolWorker *worker = cx->new_<ThreadPoolWorker>(workerId, rngSeed, this);
         if (!worker || !workers_.append(worker)) {
             terminateWorkersAndReportOOM(cx);
             return false;
         }
     }
 
     for (uint32_t workerId = 0; workerId < numWorkers(); workerId++) {
         if (!workers_[workerId]->start()) {
--- a/js/src/vm/ThreadPool.h
+++ b/js/src/vm/ThreadPool.h
@@ -43,32 +43,44 @@ class ThreadPoolWorker
     // functions below.
     mozilla::Atomic<uint32_t, mozilla::ReleaseAcquire> sliceBounds_;
 
     // Current point in the worker's lifecycle.
     volatile enum WorkerState {
         CREATED, ACTIVE, TERMINATED
     } state_;
 
+    // Per-worker scheduler RNG state used for picking a random worker during
+    // work stealing.
+    uint32_t schedulerRNGState_;
+
     // The thread's main function.
     static void HelperThreadMain(void *arg);
     void helperLoop();
 
     bool hasWork() const;
     bool popSliceFront(uint16_t *sliceId);
     bool popSliceBack(uint16_t *sliceId);
     bool stealFrom(ThreadPoolWorker *victim, uint16_t *sliceId);
 
+    // Get a worker at random from the pool using our own thread-local RNG
+    // state. This is a weak, but very fast, random function [1]. We choose
+    // [a,b,c] = 11,21,13.
+    //
+    // [1] http://www.jstatsoft.org/v08/i14/paper
   public:
-    ThreadPoolWorker(uint32_t workerId, ThreadPool *pool)
-      : workerId_(workerId),
-        pool_(pool),
-        sliceBounds_(0),
-        state_(CREATED)
-    { }
+    static const uint32_t XORSHIFT_A = 11;
+    static const uint32_t XORSHIFT_B = 21;
+    static const uint32_t XORSHIFT_C = 13;
+
+  private:
+    ThreadPoolWorker *randomWorker();
+
+  public:
+    ThreadPoolWorker(uint32_t workerId, uint32_t rngSeed, ThreadPool *pool);
 
     uint32_t id() const { return workerId_; }
     bool isMainThread() const { return id() == 0; }
 
     // Submits a new set of slices. Assumes !hasWork().
     void submitSlices(uint16_t sliceFrom, uint16_t sliceTo);
 
     // Get the next slice; work stealing happens here if work stealing is