src/third_party/WebKit/LayoutTests/resources/magnitude-perf.js

   1 // Magnitude verifies time complexity of a function.
   2 // Magnitude.run can be called multiple times in a single script if desired,
   3 // optionally with different parameters each time.
   4 //
   5 // Usage:
   6 // <script src="../resources/magnitude-perf.js"></script>
   7 // <script>
   8 // function setup(magnitude)
   9 // {
  10 //     ...
  11 // }
  12 //
  13 // function test(magnitude)
  14 // {
  15 //     ...
  16 // }
  17 // ...
  18 // Magnitude.description('Test that foo is linear in number of nodes.');
  19 // Magnitude.run(setup, test, expected);
  20 // </script>
  21 //
  22 // setup: function to run once before the test-loop. Takes a magnitude
  23 //        argument that is the value of 'n'.
  24 // test: function whose runtime is being tested. Also takes a magnitude
  25 //       argument.
  26 // expected: one of the run-time constants listed below, e.g.:
  27 //           Magnitude.CONSTANT, Magnitude.LINEAR, etc.
  28
  29 if (window.testRunner)
  30     testRunner.dumpAsText();
  31
  32 // Namespace
  33 var Magnitude = {};
  34
  35 // Description of test; prepended to the dumped markup
  36 Magnitude.description = function(description)
  37 {
  38     Magnitude._log(description);
  39 };
  40
  41 // Parameters (customize per test)
  42 // See "Time Complexity Tests" document for details:
  43 // http://dev.chromium.org/developers/testing/time-complexity-tests
  44 // Specify over which range the growth rate should hold:
  45 //   2^n ... 2^(n+k-1)  where n = initialExponent, k = numPoints
  46 Magnitude.initialExponent = 0;
  47 Magnitude.numPoints = 8;
  48 // Number of trials to run
  49 // (Trial = compute times for all magnitudes, compute statistical test,
  50 //  decide if for this dataset, the data fits the model)
  51 Magnitude.numTrials = 3;
  52 // Fraction of trials that must succeed for test overall to PASS
  53 // (Default 50% means 2 out of 3 must succeed)
  54 Magnitude.successThreshold = 0.50;
  55 // Run = for each magnitude, run test function until pass this time limit,
  56 // then stop and compute average time
  57 Magnitude.millisecondsPerRun = 25;
  58 // Strict tolerance, so noisy tests explicitly state noisiness
  59 // Ok to relax for noisy tests;
  60 // try tolerance = 0.10 or 0.20, and/or trim = 1 or 2 to relax slightly
  61 // tolerance is "max (trimmed) deviation from expected",
  62 // where "expected" is:
  63 // * expected slope (linear, polynomial),
  64 // * median value (constant),
  65 // * predicted value in linear regression (logarithmic).
  66 // For log this often needs to be very large (due to scaling), and 1.00 is ok.
  67 Magnitude.trim = 0; // trim = 1 useful if unusual value on initial run
  68 Magnitude.tolerance = 0.05;
  69
  70 Magnitude.CONSTANT = 'O(1)';
  71 Magnitude.LINEAR = 'O(n)';
  72 Magnitude.POLYNOMIAL = '>=O(n^2)';
  73
  74 // Utility functions
  75 Magnitude._max = function(array) {
  76     return Math.max.apply(null, array);
  77 };
  78
  79 Magnitude._min = function(array) {
  80     return Math.min.apply(null, array);
  81 };
  82
  83 Magnitude._sortTrimArray = function(array, trim) {
  84     // sort array, then trim both ends
  85     // used for computing trimmed maximum absolute deviation
  86     var sorted_array = array.map(Math.abs).sort(function(a, b) { return a - b; });
  87     if (!trim)
  88         return sorted_array;
  89     else
  90         return sorted_array.slice(trim, -trim);
  91 };
  92
  93 Magnitude._relativeDeviations = function(array, ref)
  94 {
  95     return array.map(function(x) { return (x - ref) / ref; });
  96 };
  97
  98 Magnitude._absSortDownTrimTop = function(array, trim) {
  99     // only trim the top of array
 100     // used for computing trimmed maximum absolute deviation
 101     if (trim === undefined)
 102         trim = 0;
 103     return array.map(Math.abs).sort(
 104         function(a, b) { return b - a; }).slice(trim);
 105 };
 106
 107 Magnitude._median = function(array) {
 108     array.sort(function(a, b) { return a - b; });
 109     var len = array.length;
 110     if (!len)
 111         return;
 112     var half = Math.floor(len / 2);
 113     if (len % 2)
 114         return array[half];
 115     return (array[half - 1] + array[half]) / 2;
 116 };
 117
 118 // Logging functions
 119 Magnitude._log = function(msg)
 120 {
 121     if (!Magnitude._container)
 122         Magnitude._container = document.createElement('pre');
 123     Magnitude._container.appendChild(document.createTextNode(msg + '\n'));
 124 };
 125
 126 Magnitude._debug = function(msg)
 127 {
 128     Magnitude._debugLog += msg + '\n';
 129 };
 130
 131 Magnitude._logRunTimes = function()
 132 {
 133     // Print out the magnitudes and times in CSV
 134     // to afford easy copy-paste to a charting application.
 135     Magnitude._debug('magnitudes: ' + Magnitude._magnitudes.join(','));
 136     Magnitude._debug('times: ' + Magnitude._times.join(','));
 137 };
 138
 139 Magnitude._for = function(n, body, callback)
 140 {
 141     var i = 0;
 142     var results = [];
 143
 144     function iteration(result) {
 145         results.push(result);
 146         if (++i === n)
 147             callback(results);
 148         else
 149             body(i, iteration);
 150     }
 151
 152     if (Magnitude._async) {
 153         body(i, iteration);
 154     } else {
 155         for (; i < n; ++i) {
 156             body(i, function(result) {
 157                 results.push(result);
 158             });
 159         }
 160         callback(results);
 161     }
 162 };
 163
 164 Magnitude._while = function(condition, body, callback)
 165 {
 166     function iteration() {
 167         if (condition())
 168             body(iteration);
 169         else
 170             callback();
 171     }
 172
 173     if (Magnitude._async) {
 174         iteration();
 175     } else {
 176         while (condition()) {
 177             body(function() {});
 178         }
 179         callback();
 180     }
 181 };
 182
 183 // Main
 184 Magnitude.run = function(setup, test, expected)
 185 {
 186     function runTest(magnitude, callback) {
 187         test(magnitude);
 188         callback();
 189     }
 190     Magnitude._run(setup, runTest, expected, false);
 191 };
 192
 193 Magnitude.runAsync = function(setup, test, expected)
 194 {
 195     if (window.testRunner)
 196         testRunner.waitUntilDone();
 197     window.addEventListener('load', function() {
 198         Magnitude._run(setup, test, expected, true);
 199     }, false);
 200 };
 201
 202 Magnitude._run = function(setup, test, expected, async)
 203 {
 204     Magnitude._async = async;
 205     Magnitude._debugLog = '\nDEBUG LOG:\n';
 206     Magnitude._debug('Expected complexity: ' + expected);
 207
 208     Magnitude._exponents = [];
 209     Magnitude._magnitudes = [];
 210     var maxExponent = Magnitude.initialExponent + Magnitude.numPoints;
 211     for (var i = Magnitude.initialExponent; i < maxExponent; i++) {
 212         Magnitude._exponents.push(i);
 213         Magnitude._magnitudes.push(Math.pow(2, i));
 214     }
 215
 216     Magnitude._numSuccesses = 0;
 217     function runTrial(trialNumber, nextTrial)
 218     {
 219         Magnitude._trialNumber = trialNumber;
 220         Magnitude._debug('\nTrial #' + trialNumber);
 221         Magnitude._for(Magnitude.numPoints, Magnitude._runTime.bind(null, setup, test), completeTrial.bind(null, nextTrial));
 222     }
 223     function completeTrial(nextTrial, times)
 224     {
 225         Magnitude._times = times;
 226         Magnitude._logRunTimes();
 227         switch (expected) {
 228             case Magnitude.CONSTANT:
 229                 passed = Magnitude._isConstant();
 230                 break;
 231             case Magnitude.LINEAR:
 232                 passed = Magnitude._isLinear();
 233                 break;
 234             case Magnitude.POLYNOMIAL:
 235                 passed = Magnitude._isPolynomial();
 236                 break;
 237             default:
 238                 Magnitude._log('FAIL: unrecognized order of growth: ' + expected);
 239                 passed = false;
 240                 break;
 241         }
 242         Magnitude._debug('Trial #' + Magnitude._trialNumber + ': ' +
 243             (passed ? 'SUCCESS' : 'FAILURE'));
 244         if (passed)
 245           Magnitude._numSuccesses++;
 246         nextTrial();
 247     }
 248     Magnitude._for(Magnitude.numTrials, runTrial, Magnitude._finish);
 249 };
 250
 251 Magnitude._finish = function()
 252 {
 253     var neededToPass = Magnitude.numTrials * Magnitude.successThreshold;
 254     Magnitude._debug('Successes: ' + Magnitude._numSuccesses + ', need ' +
 255         neededToPass + ' (' + (100 * Magnitude.successThreshold) + '%) ' +
 256         'to pass');
 257     var passedOverall = (Magnitude._numSuccesses >= neededToPass);
 258     Magnitude._log(passedOverall ? 'PASS' : 'FAIL');
 259
 260     // By default don't log detailed information to layout test results,
 261     // in order to keep expected results consistent from run to run.
 262     if (!window.testRunner || !passedOverall)
 263         Magnitude._log(Magnitude._debugLog);
 264
 265     if (Magnitude._async && window.testRunner)
 266         testRunner.notifyDone();
 267 };
 268
 269 Magnitude._runTime = function(setup, test, pointIndex, callback)
 270 {
 271     var magnitude = Magnitude._magnitudes[pointIndex];
 272     setup(magnitude);
 273
 274     var debugStr = 'run for magnitude ' + magnitude;
 275     if (window.GCController) {
 276         if (GCController.getJSObjectCount)
 277             debugStr += ' jsObjectCountBefore ' + GCController.getJSObjectCount();
 278
 279         GCController.collectAll();
 280
 281         if (GCController.getJSObjectCount)
 282             debugStr += ' jsObjectCountAfter ' + GCController.getJSObjectCount();
 283     }
 284
 285     Magnitude._debug(debugStr);
 286
 287     var nowFunction = window.performance && window.performance.now ?
 288         window.performance.now.bind(window.performance) : Date.now;
 289
 290     // Possibly run multiple times, to deal with delays at end
 291     var runOk = false;
 292     var attempt = 0;
 293     var maxAttempts = 5;
 294     var millisecondsPerIteration;
 295     var totalTimeMilliseconds;
 296     var iterations;
 297
 298     function iteration(nextIteration)
 299     {
 300         var start = nowFunction();
 301         iterations = 0;
 302         totalTimeMilliseconds = 0;
 303         function completeRun(nextRun)
 304         {
 305              iterations++;
 306              totalTimeMilliseconds = nowFunction() - start;
 307              nextRun();
 308         }
 309         Magnitude._while(function() { return totalTimeMilliseconds < Magnitude.millisecondsPerRun; }, function(nextRun) { test(magnitude, completeRun.bind(null, nextRun)); }, completeIteration.bind(null, nextIteration));
 310     }
 311
 312     function completeIteration(nextIteration)
 313     {
 314         millisecondsPerIteration = totalTimeMilliseconds / iterations;
 315         Magnitude._debug(iterations + ' iterations in ' +
 316             totalTimeMilliseconds + ' milliseconds, ' +
 317             'average ' + millisecondsPerIteration +
 318             ' milliseconds per iteration');
 319
 320         var overTime = totalTimeMilliseconds - Magnitude.millisecondsPerRun;
 321         var relativeOverTimeTolerance = 0.001;
 322         var overTimeTolerance = Magnitude.millisecondsPerRun *
 323             relativeOverTimeTolerance;
 324         // If overTime is more than the duration of a run,
 325         // there was some delay, which introduces noise.
 326         // Allow a small amount of tolerance.
 327         if (overTime < (millisecondsPerIteration + overTimeTolerance))
 328             runOk = true;
 329         else {
 330             Magnitude._debug('over-time: ' + overTime +
 331                 ' exceeds average run-time ' + millisecondsPerIteration +
 332                 ' by more than tolerance of ' + overTimeTolerance +
 333                 ' assuming delay');
 334             attempt++;
 335             if (attempt < maxAttempts)
 336                 Magnitude._debug('Retrying to reduce delay noise');
 337             else {
 338                 Magnitude._debug('Failed to reduce delay noise after ' +
 339                     maxAttempts + ' attempts, proceeding with noisy data');
 340                 runOk = true;
 341             }
 342         }
 343         nextIteration();
 344     }
 345     Magnitude._while(function() { return !runOk; }, iteration, function() { callback(millisecondsPerIteration); });
 346 };
 347
 348 // Auxiliary computations
 349 Magnitude._log2Ratios = function()
 350 {
 351     // Compute base-2 logarithm of ratios of times,
 352     // equivalently the difference of the base-2 logarithms:
 353     // log_2(t[i+1]/t[i]) = log_2(t[i+1]) - log_2(t[i])
 354     // Since times are exponentially spaced (base 2),
 355     // this is the slope of the step on the log-log scale,
 356     // and hence for O(n^k) growth should be k (the exponent).
 357     var ratioArray = [];
 358     var log2RatioArray = [];
 359     for (var i = 0; i < Magnitude.numPoints - 1; i++) {
 360         var ratio = Magnitude._times[i + 1] / Magnitude._times[i];
 361         var log2Ratio = Math.log(ratio) / Math.log(2);
 362         ratioArray.push(ratio);
 363         log2RatioArray.push(log2Ratio);
 364     }
 365     Magnitude._debug('ratios: ' + ratioArray.join(','));
 366     Magnitude._debug('log-ratios (base 2): ' + log2RatioArray.join(','));
 367     return log2RatioArray;
 368 };
 369
 370 // Statistical tests
 371 Magnitude._isConstant = function()
 372 {
 373     // Time should be approximately constant.
 374     // To deal with noise, instead of constant, check that
 375     // (trimmed) abs relative deviation from median is within tolerance of 0.
 376     var times = Magnitude._times;
 377     var median = Magnitude._median(times);
 378     var relativeDeviations = Magnitude._relativeDeviations(times, median);
 379     Magnitude._debug('Median time: ' + median);
 380     Magnitude._debug('Relative deviations: ' + relativeDeviations.join(','));
 381     var trimmedAbsRelativeDeviations = Magnitude._absSortDownTrimTop(relativeDeviations, Magnitude.trim);
 382     Magnitude._debug('Trimmed sorted absolute relative deviations: ' +
 383         trimmedAbsRelativeDeviations.join(','));
 384     var maxAbsDeviation = trimmedAbsRelativeDeviations[0];
 385     Magnitude._debug('Maximum Absolute Relative Deviation: ' + maxAbsDeviation);
 386     return maxAbsDeviation <= Magnitude.tolerance;
 387 };
 388
 389 Magnitude._isLinear = function()
 390 {
 391     // Exponent of a monomial is the slope on the log-log scale.
 392     // Magnitudes are exponentially stepped, so log ratio is slope
 393     // of secant on log-log scale.
 394     // In linear growth, (trimmed) log2Ratio should equal 1, to within tolerance
 395     // (Special case of polynomial; see below for why this is separate.)
 396     //
 397     // Can do better by removing outlying points (and then computing the
 398     // slope between the neighboring points) instead of trimming ratios,
 399     // so we retain the data of the slope of that double step, but since we are
 400     // only looking at the Maximum (Absolute) Deviation, in practice these
 401     // generally amount to the same: given an outlier, the slope coming into
 402     // the point and the slope going out will generally be high/low or low/high,
 403     // and thus both be trimmed, while the slope of the double step will
 404     // generally not be extreme, so not informative.
 405     var logRatios = Magnitude._log2Ratios();
 406     var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
 407     var minLogRatio = Magnitude._min(trimmedLogRatios);
 408     var maxLogRatio = Magnitude._max(trimmedLogRatios);
 409     var maxAbsDeviation = Math.max(Math.abs(1 - minLogRatio),
 410                                    Math.abs(maxLogRatio - 1));
 411     Magnitude._debug('Maximum Absolute Deviation: ' + maxAbsDeviation);
 412     Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
 413     return maxAbsDeviation <= Magnitude.tolerance;
 414 };
 415
 416 Magnitude._isPolynomial = function()
 417 {
 418     // Exponent of a monomial is the slope on the log-log scale.
 419     // Magnitudes are exponentially stepped, so log ratio is slope
 420     // of secant on log-log scale.
 421     // Polynomial growth is expected to be O(n^2) or greater,
 422     // so logRatio should be at least 2: check (trimmed) min with tolerance
 423     //
 424     // Linear is fundamentally a special case of polynomial,
 425     // but here not specifying a specific exponent, and instead testing
 426     // that it grows *at least* quadratically (>= 2, rather than = 2 or = 3).
 427     // Thus we have separate functions.
 428     var logRatios = Magnitude._log2Ratios();
 429     var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
 430     var minLogRatio = Magnitude._min(trimmedLogRatios);
 431     var absDeviationMin = Math.abs(2 - minLogRatio);
 432     Magnitude._debug('Absolute Deviation of Minimum: ' + absDeviationMin);
 433     Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
 434     return absDeviationMin <= Magnitude.tolerance;
 435 };
 436
 437 // Register listener
 438 window.addEventListener('load', function() {
 439     // FIXME: Add Magnitude.waitUntilDone/notifyDone for tests that need to
 440     // operate after the load event has fired.
 441     if (window.testRunner)
 442         document.body.innerHTML = '';
 443     document.body.appendChild(Magnitude._container);
 444 }, false);