Bug 974201 - Remove filterPar chunking. (r=nmatsakis)
authorShu-yu Guo <shu@rfrn.org>
Mon, 07 Apr 2014 13:02:20 -0700
changeset 177343 7a1c696cade6bd7b80372dda80c86e6df7b3fc74
parent 177342 8b87a6adad143376550d552cef67d733ebdf6c4c
child 177344 9a92e6a4d02b74f1f2afb1f82e7faa36fb3051e6
push id41995
push usershu@rfrn.org
push dateMon, 07 Apr 2014 19:57:25 +0000
treeherdermozilla-inbound@9a92e6a4d02b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnmatsakis
bugs974201
milestone31.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 974201 - Remove filterPar chunking. (r=nmatsakis)
js/src/builtin/Array.js
js/src/builtin/ParallelUtilities.js
js/src/jit-test/tests/parallel/Array-filterPar-short.js
--- a/js/src/builtin/Array.js
+++ b/js/src/builtin/Array.js
@@ -917,29 +917,27 @@ function ArrayFilterPar(func, mode) {
   parallel: for (;;) { // see ArrayMapPar() to explain why for(;;) etc
     if (ShouldForceSequential())
       break parallel;
     if (!TRY_PARALLEL(mode))
       break parallel;
 
     var slicesInfo = ComputeSlicesInfo(length);
 
-    // Step 1. Compute which items from each slice of the result
-    // buffer should be preserved. When we're done, we have an array
-    // |survivors| containing a bitset for each chunk, indicating
-    // which members of the chunk survived. We also keep an array
-    // |counts| containing the total number of items that are being
-    // preserved from within one slice.
-    //
-    // FIXME(bug 844890): Use typed arrays here.
+    // Step 1. Compute which items from each slice of the result buffer should
+    // be preserved. When we're done, we have a uint8 array |survivors|
+    // containing 0 or 1 for each source element, indicating which members of
+    // the chunk survived. We also keep an array |counts| containing the total
+    // number of items that are being preserved from within one slice.
     var numSlices = slicesInfo.count;
     var counts = NewDenseArray(numSlices);
     for (var i = 0; i < numSlices; i++)
       UnsafePutElements(counts, i, 0);
-    var survivors = NewDenseArray(computeNum32BitChunks(length));
+
+    var survivors = new Uint8Array(length);
     ForkJoin(findSurvivorsThread, 0, numSlices, ForkJoinMode(mode));
 
     // Step 2. Compress the slices into one contiguous set.
     var count = 0;
     for (var i = 0; i < numSlices; i++)
       count += counts[i];
     var buffer = NewDenseArray(count);
     if (count > 0)
@@ -954,97 +952,64 @@ function ArrayFilterPar(func, mode) {
   for (var i = 0; i < length; i++) {
     var elem = self[i];
     if (func(elem, i, self))
       ARRAY_PUSH(buffer, elem);
   }
   return buffer;
 
   /**
-   * Determine the number of 32-bit chunks for use with the survivors bitset.
-   */
-  function computeNum32BitChunks(length) {
-    var chunks = length >>> 5;
-    if (chunks << 5 === length)
-      return chunks;
-    return chunks + 1;
-  }
-
-  /**
-   * As described above, our goal is to determine which items we
-   * will preserve from a given slice. We do this one chunk at a
-   * time. When we finish a chunk, we record our current count and
-   * the next chunk sliceId, lest we should bail.
+   * As described above, our goal is to determine which items we will preserve
+   * from a given slice, storing "to-keep" bits into 32-bit chunks.
    */
   function findSurvivorsThread(workerId, sliceStart, sliceEnd) {
     var sliceShift = slicesInfo.shift;
     var sliceId;
     while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
       var count = 0;
       var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
       var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
-      var chunkStart = computeNum32BitChunks(indexStart);
-      var chunkEnd = computeNum32BitChunks(indexEnd);
-      for (var chunkPos = chunkStart; chunkPos < chunkEnd; chunkPos++, indexStart += 32) {
-        var chunkBits = 0;
-        for (var bit = 0, indexPos = indexStart; bit < 32 && indexPos < indexEnd; bit++, indexPos++) {
-          var keep = !!func(self[indexPos], indexPos, self);
-          chunkBits |= keep << bit;
-          count += keep;
-        }
-        UnsafePutElements(survivors, chunkPos, chunkBits);
+      for (var indexPos = indexStart; indexPos < indexEnd; indexPos++) {
+        var keep = !!func(self[indexPos], indexPos, self);
+        UnsafePutElements(survivors, indexPos, keep);
+        count += keep;
       }
       UnsafePutElements(counts, sliceId, count);
     }
     return sliceId;
   }
 
+  /**
+   * Copies the survivors from this slice into the correct position. Note
+   * that this is an idempotent operation that does not invoke user
+   * code. Therefore, we don't expect bailouts and make an effort to proceed
+   * chunk by chunk or avoid duplicating work.
+   */
   function copySurvivorsThread(workerId, sliceStart, sliceEnd) {
     var sliceShift = slicesInfo.shift;
     var sliceId;
     while (GET_SLICE(sliceStart, sliceEnd, sliceId)) {
-      // Copies the survivors from this slice into the correct position.
-      // Note that this is an idempotent operation that does not invoke
-      // user code. Therefore, we don't expect bailouts and make an
-      // effort to proceed chunk by chunk or avoid duplicating work.
-
       // Total up the items preserved by previous slices.
       var total = 0;
       for (var i = 0; i < sliceId + 1; i++)
         total += counts[i];
 
-      // Compute the final index we expect to write.
+      // Are we done?
       var count = total - counts[sliceId];
       if (count === total)
         continue;
 
-      // Iterate over the chunks assigned to us. Read the bitset for
-      // each chunk. Copy values where a 1 appears until we have
-      // written all the values that we expect to. We can just iterate
-      // from 0...CHUNK_SIZE without fear of a truncated final chunk
-      // because we are already checking for when count==total.
       var indexStart = SLICE_START_INDEX(sliceShift, sliceId);
       var indexEnd = SLICE_END_INDEX(sliceShift, indexStart, length);
-      var chunkStart = computeNum32BitChunks(indexStart);
-      var chunkEnd = computeNum32BitChunks(indexEnd);
-      for (var chunkPos = chunkStart; chunkPos < chunkEnd; chunkPos++, indexStart += 32) {
-        var chunkBits = survivors[chunkPos];
-        if (!chunkBits)
-          continue;
-
-        for (var i = 0; i < 32; i++) {
-          if (chunkBits & (1 << i)) {
-            UnsafePutElements(buffer, count++, self[indexStart + i]);
-            if (count === total)
-              break;
-          }
+      for (var indexPos = indexStart; indexPos < indexEnd; indexPos++) {
+        if (survivors[indexPos]) {
+          UnsafePutElements(buffer, count++, self[indexPos]);
+          if (count == total)
+            break;
         }
-
-        if (count == total)
-          break;
       }
     }
 
     return sliceId;
   }
 
   return undefined;
 }
--- a/js/src/builtin/ParallelUtilities.js
+++ b/js/src/builtin/ParallelUtilities.js
@@ -44,18 +44,16 @@
     ((id = ForkJoinGetSlice((InParallelSection() ? -1 : sliceStart++) | 0)) < sliceEnd)
 
 /**
  * Determine the number and size of slices. The info object has the following
  * properties:
  *
  *  - shift: amount to shift by to compute indices
  *  - count: number of slices
- *  - seqSliceId: the slice id for which slices [0,id] have been run
- *                sequentially and cannot be re-run in parallel.
  */
 function ComputeSlicesInfo(length) {
   var count = length >>> MAX_SLICE_SHIFT;
   var numWorkers = ForkJoinNumWorkers();
   if (count < numWorkers)
     count = numWorkers;
   else if (count >= numWorkers * MAX_SLICES_PER_WORKER)
     count = numWorkers * MAX_SLICES_PER_WORKER;
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallel/Array-filterPar-short.js
@@ -0,0 +1,3 @@
+load(libdir + "parallelarray-helpers.js");
+if (getBuildConfiguration().parallelJS)
+  assertArraySeqParResultsEq(range(0, 4), "filter", function(i) { return i % 2; });