michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: // Explanation of minItemsTestingThreshold:
michael@0: //
michael@0: // If the volume of input items in a test is small, then all of them
michael@0: // may be processed during warmup alone, and the parallel-invocation
michael@0: // will trivially succeed even if we are intentionally trying to
michael@0: // detect a failure.
michael@0: //
michael@0: // The maximum number of items processed by sequential warmups for
michael@0: // ArrayBuildPar is:
michael@0: //      maxSeqItems = maxBailouts * numSlices * CHUNK_SIZE
michael@0: //
michael@0: // For maxBailouts = 3, maxSeqItems == 3 * 8 * 32 == 768
michael@0: // For maxBailouts = 5, maxSeqItems == 5 * 8 * 32 == 1280
michael@0: //
michael@0: // Our test code does not have access to the values of these constants
michael@0: // (maxBailouts, numSlices, CHUNK_SIZE).  Therefore, the value of
michael@0: // minItemsTestingThreshold should be kept in sync with some value
michael@0: // greater than maxSeqItems as calculated above.
michael@0: //
michael@0: // This is still imperfect since it assumes numSlices <= 8, but
michael@0: // numSlices is machine-dependent.
michael@0: // (TODO: consider exposing numSlices via builtin/TestingFunctions.cpp)
michael@0: 
michael@0: var minItemsTestingThreshold = 1024;
michael@0: 
michael@0: // The standard sequence of modes to test.
michael@0: // First mode compiles for parallel exec.
michael@0: // Second mode checks that parallel exec does not bail.
michael@0: // Final mode tests the sequential fallback path.
michael@0: var MODE_STRINGS = ["compile", "par", "seq"];
michael@0: var MODES = MODE_STRINGS.map(s => ({mode: s}));
michael@0: 
michael@0: var INVALIDATE_MODE_STRINGS = ["seq", "compile", "par", "seq"];
michael@0: var INVALIDATE_MODES = INVALIDATE_MODE_STRINGS.map(s => ({mode: s}));
michael@0: 
michael@0: function build(n, f) {
michael@0:   var result = [];
michael@0:   for (var i = 0; i < n; i++)
michael@0:     result.push(f(i));
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: function range(n, m) {
michael@0:   // Returns an array with [n..m] (include on n, exclusive on m)
michael@0: 
michael@0:   var result = [];
michael@0:   for (var i = n; i < m; i++)
michael@0:     result.push(i);
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: function seq_scan(array, f) {
michael@0:   // Simple sequential version of scan() that operates over an array
michael@0: 
michael@0:   var result = [];
michael@0:   result[0] = array[0];
michael@0:   for (var i = 1; i < array.length; i++) {
michael@0:     result[i] = f(result[i-1], array[i]);
michael@0:   }
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: function assertAlmostEq(v1, v2) {
michael@0:   if (v1 === v2)
michael@0:     return true;
michael@0:   // + and other fp ops can vary somewhat when run in parallel!
michael@0:   assertEq(typeof v1, "number");
michael@0:   assertEq(typeof v2, "number");
michael@0:   var diff = Math.abs(v1 - v2);
michael@0:   var percent = diff / v1 * 100.0;
michael@0:   print("v1 = " + v1);
michael@0:   print("v2 = " + v2);
michael@0:   print("% diff = " + percent);
michael@0:   assertEq(percent < 1e-10, true); // off by an less than 1e-10%...good enough.
michael@0: }
michael@0: 
michael@0: function assertStructuralEq(e1, e2) {
michael@0:     if (e1 instanceof Array && e2 instanceof Array) {
michael@0:       assertEqArray(e1, e2);
michael@0:     } else if (e1 instanceof Object && e2 instanceof Object) {
michael@0:       assertEq(e1.__proto__, e2.__proto__);
michael@0:       for (prop in e1) {
michael@0:         if (e1.hasOwnProperty(prop)) {
michael@0:           assertEq(e2.hasOwnProperty(prop), true);
michael@0:           assertStructuralEq(e1[prop], e2[prop]);
michael@0:         }
michael@0:       }
michael@0:     } else {
michael@0:       assertEq(e1, e2);
michael@0:     }
michael@0: }
michael@0: 
michael@0: function assertEqArray(a, b) {
michael@0:     assertEq(a.length, b.length);
michael@0:     for (var i = 0, l = a.length; i < l; i++) {
michael@0:       try {
michael@0:         assertStructuralEq(a[i], b[i]);
michael@0:       } catch (e) {
michael@0:         print("...in index", i, "of", l);
michael@0:         throw e;
michael@0:       }
michael@0:     }
michael@0: }
michael@0: 
michael@0: // Checks that whenever we execute this in parallel mode,
michael@0: // it bails out. `opFunction` should be a closure that takes a
michael@0: // mode parameter and performs some parallel array operation.
michael@0: // This closure will be invoked repeatedly.
michael@0: //
michael@0: // Here is an example of the expected usage:
michael@0: //
michael@0: //    assertParallelExecWillBail(function(m) {
michael@0: //        Array.buildPar(..., m)
michael@0: //    });
michael@0: //
michael@0: // where the `Array.buildPar(...)` is a stand-in
michael@0: // for some parallel array operation.
michael@0: function assertParallelExecWillBail(opFunction) {
michael@0:   opFunction({mode:"compile"}); // get the script compiled
michael@0:   opFunction({mode:"bailout"}); // check that it bails when executed
michael@0: }
michael@0: 
michael@0: // Checks that when we execute this in parallel mode,
michael@0: // some bailouts will occur but we will recover and
michael@0: // return to parallel execution mode. `opFunction` is a closure
michael@0: // that expects a mode, just as in `assertParallelExecWillBail`.
michael@0: function assertParallelExecWillRecover(opFunction) {
michael@0:   opFunction({mode:"compile"}); // get the script compiled
michael@0:   opFunction({mode:"recover"}); // check that it bails when executed
michael@0: }
michael@0: 
michael@0: // Checks that we will (eventually) be able to compile and exection
michael@0: // `opFunction` in parallel mode. Invokes `cmpFunction` with the
michael@0: // result.  For some tests, it takes many compile rounds to reach a TI
michael@0: // fixed point. So this function will repeatedly attempt to invoke
michael@0: // `opFunction` with `compile` and then `par` mode until getting a
michael@0: // successful `par` run.  After enough tries, of course, we give up
michael@0: // and declare a test failure.
michael@0: function assertParallelExecSucceeds(opFunction, cmpFunction) {
michael@0:   var failures = 0;
michael@0:   while (true) {
michael@0:     print("Attempting compile #", failures);
michael@0:     var result = opFunction({mode:"compile"});
michael@0:     cmpFunction(result);
michael@0: 
michael@0:     try {
michael@0:       print("Attempting parallel run #", failures);
michael@0:       var result = opFunction({mode:"par"});
michael@0:       cmpFunction(result);
michael@0:       break;
michael@0:     } catch (e) {
michael@0:       failures++;
michael@0:       if (failures > 5) {
michael@0:         throw e; // doesn't seem to be reaching a fixed point!
michael@0:       } else {
michael@0:         print(e);
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   print("Attempting sequential run");
michael@0:   var result = opFunction({mode:"seq"});
michael@0:   cmpFunction(result);
michael@0: }
michael@0: 
michael@0: // Compares an Array constructed in parallel against one constructed
michael@0: // sequentially. `func` should be the closure to provide as argument. For
michael@0: // example:
michael@0: //
michael@0: //    assertArraySeqParResultsEq([1, 2, 3], "map", i => i + 1)
michael@0: //
michael@0: // would check that `[1, 2, 3].map(i => i+1)` and `[1, 2, 3].mapPar(i => i+1)`
michael@0: // yield the same result.
michael@0: //
michael@0: // Based on `assertParallelExecSucceeds`
michael@0: function assertArraySeqParResultsEq(arr, op, func, cmpFunc) {
michael@0:   if (!cmpFunc)
michael@0:     cmpFunc = assertStructuralEq;
michael@0:   var expected = arr[op].apply(arr, [func]);
michael@0:   assertParallelExecSucceeds(
michael@0:     function (m) { return arr[op + "Par"].apply(arr, [func, m]); },
michael@0:     function (r) { cmpFunc(expected, r); });
michael@0: }
michael@0: 
michael@0: // Similar to `compareAgainstArray`, but for the `scan` method which
michael@0: // does not appear on array.
michael@0: function testArrayScanPar(jsarray, func, cmpFunction) {
michael@0:   if (!cmpFunction)
michael@0:     cmpFunction = assertStructuralEq;
michael@0:   var expected = seq_scan(jsarray, func);
michael@0: 
michael@0:   // Unfortunately, it sometimes happens that running 'par' twice in a
michael@0:   // row causes bailouts and other unfortunate things!
michael@0: 
michael@0:   assertParallelExecSucceeds(
michael@0:     function(m) {
michael@0:       print(m.mode + " " + m.expect);
michael@0:       var p = jsarray.scanPar(func, m);
michael@0:       return p;
michael@0:     },
michael@0:     function(r) {
michael@0:       cmpFunction(expected, r);
michael@0:     });
michael@0: }
michael@0: 
michael@0: // Checks that `opFunction`, when run with each of the modes
michael@0: // in `modes`, returns the same value each time.
michael@0: function assertParallelModesCommute(modes, opFunction) {
michael@0:   var expected = undefined;
michael@0:   var acc = opFunction(modes[0]);
michael@0:   assertParallelExecSucceeds(
michael@0:     opFunction,
michael@0:     function(r) {
michael@0:       if (expected === undefined)
michael@0:         expected = r;
michael@0:       else
michael@0:         assertStructuralEq(expected, r);
michael@0:     });
michael@0: }