LayoutTests/resources/magnitude-perf.js

   1 // Magnitude gives a best guess estimate of the runtime of a function.
   2 // Magnitude.run can be called multiple times in a single test if desired.
   3 //
   4 // Usage:
   5 // <script src="../resources/magnitude-perf.js"></script>
   6 // <script>
   7 // ...
   8 // Magnitude.run(setup, test, expected)
   9 // </script>
  10 //
  11 // -setup is the function to run once before the test-loop. It takes a magnitude argument
  12 // that is the value of "n".
  13 // -test is the code whose runtime is being tests. It also takes a magnitude argument.
  14 // -expected is one of the run-time constants listed below (e.g. Magnitude.CONSTANT).
  15
  16 if (window.layoutTestController)
  17     layoutTestController.dumpAsText();
  18
  19 // Namespace.
  20 var Magnitude = {};
  21
  22 // The description of what this test is testing. Gets prepended to the dumped markup.
  23 Magnitude.description = function(description)
  24 {
  25     Magnitude._log(description);
  26 }
  27
  28 Magnitude._numPoints = 10;
  29 Magnitude._minIterations = 5;
  30 Magnitude._maxIterations = 1000;
  31
  32 Magnitude.CONSTANT = "O(1)";
  33 Magnitude.LINEAR = "O(n)";
  34 Magnitude.LOGARITHMIC = "O(log n)";
  35 Magnitude.POLYNOMIAL = ">=O(n^2)";
  36 Magnitude.INDETERMINATE = "indeterminate result";
  37
  38 Magnitude._log = function(msg)
  39 {
  40     if (!Magnitude._container)
  41         Magnitude._container = document.createElement('pre');
  42     Magnitude._container.appendChild(document.createTextNode(msg + '\n'));
  43 }
  44
  45 Magnitude._debug = function(msg)
  46 {
  47     Magnitude._debugLog += msg + '\n';
  48 }
  49
  50 Magnitude.run = function(setup, test, expected)
  51 {
  52     Magnitude._debugLog = "\nDEBUG LOG:\n";
  53
  54     Magnitude._magnitudes = [];
  55     for (var i = 0; i < Magnitude._numPoints; i++) {
  56         Magnitude._magnitudes.push(Math.pow(2, i));
  57     }
  58
  59     var milliseconds = 50;
  60     var runsPerIteration = 1;
  61     var numTries = 3;
  62     Magnitude._run(setup, test, expected, milliseconds, runsPerIteration, numTries);
  63 }
  64
  65 Magnitude._run = function(setup, test, expected, milliseconds, runsPerIteration, numTriesLeft)
  66 {
  67     Magnitude._iterations = {};
  68     var maxMagnitude = Magnitude._magnitudes[Magnitude._magnitudes.length - 1];
  69
  70     // We want the largest magnitude to do between Magnitude._minIterations and Magnitude._maxIterations iterations.
  71     // If it's too fast, we increase the runsPerIteration to do more runs per iteration.
  72     // If it's too slow, we increase milliseconds to give each iteration more time.
  73     while (true) {
  74         var iterations = Magnitude._runIteration(setup, test, maxMagnitude, milliseconds, runsPerIteration);
  75         Magnitude._debug("iterations " + iterations);
  76
  77         // If we get too few or too many on the largest magnitude iterations, then we can't trust this run.
  78         // Too many runs means the the test loop itself may be taking more time than running the test.
  79         if (iterations <= Magnitude._minIterations)
  80             milliseconds = Math.max(2, Math.floor(Magnitude._minIterations / iterations)) * milliseconds;
  81         else if (iterations > Magnitude._maxIterations)
  82             runsPerIteration = Math.max(2, Math.floor(iterations / Magnitude._maxIterations)) * runsPerIteration;
  83         else {
  84             Magnitude._iterations[maxMagnitude] = iterations;
  85             break;
  86         }
  87     }
  88
  89     for (var i = 0; i < Magnitude._magnitudes.length - 1; i++) {
  90         var magnitude = Magnitude._magnitudes[i];
  91         Magnitude._iterations[magnitude] = Magnitude._runIteration(setup, test, magnitude, milliseconds, runsPerIteration);
  92     }
  93
  94     Magnitude._logIterationInfo(milliseconds, runsPerIteration);
  95
  96     numTriesLeft--;
  97     var bigO = Magnitude._bigOGuess(milliseconds);
  98     if (bigO == expected || numTriesLeft < 1) {
  99         Magnitude._log(bigO == expected ? "PASS" : "FAIL: got " + bigO + " expected " + expected);
 100
 101         // By default don't log detailed information to layout test results to keep expected results
 102         // consistent from run to run.
 103         if (!window.layoutTestController || bigO != expected)
 104             Magnitude._log(Magnitude._debugLog);
 105     } else {
 106         Magnitude._debug("numTriesLeft: " + numTriesLeft);
 107         arguments.callee(setup, test, expected, milliseconds, runsPerIteration, numTriesLeft);
 108     }
 109 }
 110
 111 Magnitude._rSquared = function(milliseconds, opt_xTransform, opt_yTransform)
 112 {
 113     // Implement http://www.easycalculation.com/statistics/learn-correlation.php.
 114     // x = magnitude
 115     // y = iterations
 116     var sumX = 0;
 117     var sumY = 0;
 118     var sumXSquared = 0;
 119     var sumYSquared = 0;
 120     var sumXTimesY = 0;
 121
 122     var numPoints = Magnitude._magnitudes.length;
 123
 124     for (var i = 0; i < numPoints; i++) {
 125         var x = Magnitude._magnitudes[i];
 126         if (opt_xTransform)
 127             x = opt_xTransform(x);
 128
 129         var y = milliseconds / Magnitude._iterations[Magnitude._magnitudes[i]];
 130         if (opt_yTransform)
 131             y = opt_yTransform(y);
 132
 133         sumX += x;
 134         sumY += y;
 135         sumXSquared += x * x;
 136         sumYSquared += y * y;
 137         sumXTimesY += x * y;
 138     }
 139
 140     var r = (numPoints * sumXTimesY - sumX * sumY) /
 141         Math.sqrt((numPoints * sumXSquared - sumX * sumX) *
 142                   (numPoints * sumYSquared - sumY * sumY));
 143
 144     if (isNaN(r) || r == Math.Infinity)
 145         r = 0;
 146
 147     rSquared = r * r;
 148
 149     var slope = (numPoints * sumXTimesY - sumX * sumY) /
 150         (numPoints * sumXSquared - sumX * sumX);
 151     var intercept = sumY / numPoints - slope * sumX / numPoints;
 152     Magnitude._debug("numPoints " + numPoints + " slope " + slope + " intercept " + intercept + " rSquared " + rSquared);
 153
 154     return rSquared;
 155 }
 156
 157 Magnitude._logIterationInfo = function(milliseconds, runsPerIteration)
 158 {
 159     var iterationsArray = [];
 160     for (var i = 0; i < Magnitude._magnitudes.length; i++) {
 161         var magnitude = Magnitude._magnitudes[i];
 162         var iterations = Magnitude._iterations[magnitude];
 163         iterationsArray.push(iterations);
 164         Magnitude._debug("magnitude: " + magnitude + " iterations: " + iterations + " runsPerIteration " + runsPerIteration +
 165                 " loop-time " + milliseconds + " time/iteration(ms): " + milliseconds / iterations);
 166     }
 167
 168     // Print out the magnitudes/arrays in CSV to afford easy copy-paste to a charting application.
 169     Magnitude._debug("magnitudes: " + Magnitude._magnitudes.join(','));
 170     Magnitude._debug("iterations: " + iterationsArray.join(','));
 171     Magnitude._debug("milliseconds/iteration: " + iterationsArray.map(function(iterations) {return milliseconds / iterations}).join(','));
 172 }
 173
 174 Magnitude._bigOGuess = function(milliseconds)
 175 {
 176     var rSquared = Magnitude._rSquared(milliseconds);
 177     var rSquaredXLog = Magnitude._rSquared(milliseconds, Math.log);
 178     var rSquaredXYLog = Magnitude._rSquared(milliseconds, Math.log, Math.log);
 179     Magnitude._debug("rSquared " + rSquared + " rSquaredXLog " + rSquaredXLog + " rSquaredXYLog " + rSquaredXYLog);
 180
 181     var rSquaredMax = Math.max(rSquared, rSquaredXLog, rSquaredXYLog);
 182
 183     var bigO = Magnitude.INDETERMINATE;
 184
 185     // FIXME: These numbers were chosen arbitrarily.
 186     // Are there a better value to check against? Do we need to check rSquaredMax?
 187     if (rSquared < 0.8 && rSquaredMax < 0.9)
 188         bigO = Magnitude.CONSTANT;
 189     else if (rSquaredMax > 0.9) {
 190         if (rSquared == rSquaredMax)
 191             bigO = Magnitude.LINEAR;
 192         else if (rSquaredXLog == rSquaredMax)
 193             bigO = Magnitude.LOGARITHMIC;
 194         else if (rSquaredXYLog == rSquaredMax)
 195             bigO = Magnitude.POLYNOMIAL;
 196     }
 197
 198     return bigO;
 199 }
 200
 201 Magnitude._runIteration = function(setup, test, magnitude, milliseconds, runsPerIteration)
 202 {
 203     setup(magnitude);
 204
 205     var debugStr = 'run iteration. magnitude ' + magnitude + " milliseconds " + milliseconds + " runsPerIteration " + runsPerIteration;
 206     if (window.GCController) {
 207         if (GCController.getJSObjectCount)
 208             debugStr += " jsObjectCountBefore " + GCController.getJSObjectCount();
 209
 210         // Do a gc to reduce likelihood of gc during the test run.
 211         // Do multiple gc's for V8 to clear DOM wrappers.
 212         GCController.collect();
 213         GCController.collect();
 214         GCController.collect();
 215
 216         if (GCController.getJSObjectCount)
 217             debugStr += " jsObjectCountAfter " + GCController.getJSObjectCount();
 218     }
 219
 220     Magnitude._debug(debugStr);
 221
 222     var iterations = 0;
 223     if (window.chromium) {
 224       // FIXME: If using microseconds turns out to be less flaky, expose microseconds
 225       // from JSC or layoutTestController and use them. Otherwise, get rid of this block.
 226       var microseconds = milliseconds * 1000;
 227       var interval = new chromium.Interval();
 228       interval.start();
 229       while (interval.microseconds() < microseconds) {
 230           // Loop runsPerIteration times to reduce errors due to the overhead and granularity of the Date object.
 231           for (var i = 0; i < runsPerIteration; i++) {
 232               test(magnitude);
 233           }
 234           iterations++;
 235       }
 236       interval.stop();
 237     } else {
 238       var start = Date.now();
 239       while (Date.now() - start < milliseconds) {
 240           // Loop runsPerIteration times to reduce errors due to the overhead and granularity of the Date object.
 241           for (var i = 0; i < runsPerIteration; i++) {
 242               test(magnitude);
 243           }
 244           iterations++;
 245       }
 246     }
 247     return iterations;
 248 }
 249
 250 window.addEventListener('load', function() {
 251     // FIXME: Add Magnitude.waitUntilDone/notifyDone for tests that need to operate after the load event has fired.
 252     if (window.layoutTestController)
 253         document.body.innerHTML = '';
 254     document.body.appendChild(Magnitude._container);
 255 }, false);