third_party/WebKit/LayoutTests/resources/magnitude-perf.js - chromium/src.git - Git at Google

 // Magnitude verifies time complexity of a function.
 // Magnitude.run can be called multiple times in a single script if desired,
 // optionally with different parameters each time.
 //
 // Usage:
 // <script src="../resources/magnitude-perf.js"></script>
 // <script>
 // function setup(magnitude)
 // {
 //     ...
 // }
 //
 // function test(magnitude)
 // {
 //     ...
 // }
 // ...
 // Magnitude.description('Test that foo is linear in number of nodes.');
 // Magnitude.run(setup, test, expected);
 // </script>
 //
 // setup: function to run once before the test-loop. Takes a magnitude
 //        argument that is the value of 'n'.
 // test: function whose runtime is being tested. Also takes a magnitude
 //       argument.
 // expected: one of the run-time constants listed below, e.g.:
 //           Magnitude.CONSTANT, Magnitude.LINEAR, etc.

 if (window.testRunner)
     testRunner.dumpAsText();

 // Namespace
 var Magnitude = {};

 // Description of test; prepended to the dumped markup
 Magnitude.description = function(description)
 {
     Magnitude._log(description);
 };

 // Parameters (customize per test)
 // See "Time Complexity Tests" document for details:
 // http://dev.chromium.org/developers/testing/time-complexity-tests
 // Specify over which range the growth rate should hold:
 //   2^n ... 2^(n+k-1)  where n = initialExponent, k = numPoints
 Magnitude.initialExponent = 0;
 Magnitude.numPoints = 8;
 // Number of trials to run
 // (Trial = compute times for all magnitudes, compute statistical test,
 //  decide if for this dataset, the data fits the model)
 Magnitude.numTrials = 3;
 // Fraction of trials that must succeed for test overall to PASS
 // (Default 50% means 2 out of 3 must succeed)
 Magnitude.successThreshold = 0.50;
 // Run = for each magnitude, run test function until pass this time limit,
 // then stop and compute average time
 Magnitude.millisecondsPerRun = 25;
 // Strict tolerance, so noisy tests explicitly state noisiness
 // Ok to relax for noisy tests;
 // try tolerance = 0.10 or 0.20, and/or trim = 1 or 2 to relax slightly
 // tolerance is "max (trimmed) deviation from expected",
 // where "expected" is:
 // * expected slope (linear, polynomial),
 // * median value (constant),
 // * predicted value in linear regression (logarithmic).
 // For log this often needs to be very large (due to scaling), and 1.00 is ok.
 Magnitude.trim = 0; // trim = 1 useful if unusual value on initial run
 Magnitude.tolerance = 0.05;

 Magnitude.CONSTANT = 'O(1)';
 Magnitude.LINEAR = 'O(n)';
 Magnitude.POLYNOMIAL = '>=O(n^2)';

 // Utility functions
 Magnitude._max = function(array) {
     return Math.max.apply(null, array);
 };

 Magnitude._min = function(array) {
     return Math.min.apply(null, array);
 };

 Magnitude._sortTrimArray = function(array, trim) {
     // sort array, then trim both ends
     // used for computing trimmed maximum absolute deviation
     var sorted_array = array.map(Math.abs).sort(function(a, b) { return a - b; });
     if (!trim)
         return sorted_array;
     else
         return sorted_array.slice(trim, -trim);
 };

 Magnitude._relativeDeviations = function(array, ref)
 {
     return array.map(function(x) { return (x - ref) / ref; });
 };

 Magnitude._absSortDownTrimTop = function(array, trim) {
     // only trim the top of array
     // used for computing trimmed maximum absolute deviation
     if (trim === undefined)
         trim = 0;
     return array.map(Math.abs).sort(
         function(a, b) { return b - a; }).slice(trim);
 };

 Magnitude._median = function(array) {
     array.sort(function(a, b) { return a - b; });
     var len = array.length;
     if (!len)
         return;
     var half = Math.floor(len / 2);
     if (len % 2)
         return array[half];
     return (array[half - 1] + array[half]) / 2;
 };

 // Logging functions
 Magnitude._log = function(msg)
 {
     if (!Magnitude._container)
         Magnitude._container = document.createElement('pre');
     Magnitude._container.appendChild(document.createTextNode(msg + '\n'));
 };

 Magnitude._debug = function(msg)
 {
     Magnitude._debugLog += msg + '\n';
 };

 Magnitude._logRunTimes = function()
 {
     // Print out the magnitudes and times in CSV
     // to afford easy copy-paste to a charting application.
     Magnitude._debug('magnitudes: ' + Magnitude._magnitudes.join(','));
     Magnitude._debug('times: ' + Magnitude._times.join(','));
 };

 Magnitude._for = function(n, body, callback)
 {
     var i = 0;
     var results = [];

     function iteration(result) {
         results.push(result);
         if (++i === n)
             callback(results);
         else
             body(i, iteration);
     }

     if (Magnitude._async) {
         body(i, iteration);
     } else {
         for (; i < n; ++i) {
             body(i, function(result) {
                 results.push(result);
             });
         }
         callback(results);
     }
 };

 Magnitude._while = function(condition, body, callback)
 {
     function iteration() {
         if (condition())
             body(iteration);
         else
             callback();
     }

     if (Magnitude._async) {
         iteration();
     } else {
         while (condition()) {
             body(function() {});
         }
         callback();
     }
 };

 // Main
 Magnitude.run = function(setup, test, expected)
 {
     function runTest(magnitude, callback) {
         test(magnitude);
         callback();
     }
     Magnitude._run(setup, runTest, expected, false);
 };

 Magnitude.runAsync = function(setup, test, expected)
 {
     if (window.testRunner)
         testRunner.waitUntilDone();
     window.addEventListener('load', function() {
         Magnitude._run(setup, test, expected, true);
     }, false);
 };

 Magnitude._run = function(setup, test, expected, async)
 {
     Magnitude._async = async;
     Magnitude._debugLog = '\nDEBUG LOG:\n';
     Magnitude._debug('Expected complexity: ' + expected);

     Magnitude._exponents = [];
     Magnitude._magnitudes = [];
     var maxExponent = Magnitude.initialExponent + Magnitude.numPoints;
     for (var i = Magnitude.initialExponent; i < maxExponent; i++) {
         Magnitude._exponents.push(i);
         Magnitude._magnitudes.push(Math.pow(2, i));
     }

     Magnitude._numSuccesses = 0;
     function runTrial(trialNumber, nextTrial)
     {
         Magnitude._trialNumber = trialNumber;
         Magnitude._debug('\nTrial #' + trialNumber);
         Magnitude._for(Magnitude.numPoints, Magnitude._runTime.bind(null, setup, test), completeTrial.bind(null, nextTrial));
     }
     function completeTrial(nextTrial, times)
     {
         Magnitude._times = times;
         Magnitude._logRunTimes();
         switch (expected) {
             case Magnitude.CONSTANT:
                 passed = Magnitude._isConstant();
                 break;
             case Magnitude.LINEAR:
                 passed = Magnitude._isLinear();
                 break;
             case Magnitude.POLYNOMIAL:
                 passed = Magnitude._isPolynomial();
                 break;
             default:
                 Magnitude._log('FAIL: unrecognized order of growth: ' + expected);
                 passed = false;
                 break;
         }
         Magnitude._debug('Trial #' + Magnitude._trialNumber + ': ' +
             (passed ? 'SUCCESS' : 'FAILURE'));
         if (passed)
           Magnitude._numSuccesses++;
         nextTrial();
     }
     Magnitude._for(Magnitude.numTrials, runTrial, Magnitude._finish);
 };

 Magnitude._finish = function()
 {
     var neededToPass = Magnitude.numTrials * Magnitude.successThreshold;
     Magnitude._debug('Successes: ' + Magnitude._numSuccesses + ', need ' +
         neededToPass + ' (' + (100 * Magnitude.successThreshold) + '%) ' +
         'to pass');
     var passedOverall = (Magnitude._numSuccesses >= neededToPass);
     Magnitude._log(passedOverall ? 'PASS' : 'FAIL');

     // By default don't log detailed information to layout test results,
     // in order to keep expected results consistent from run to run.
     if (!window.testRunner || !passedOverall)
         Magnitude._log(Magnitude._debugLog);

     if (Magnitude._async && window.testRunner)
         testRunner.notifyDone();
 };

 Magnitude._runTime = function(setup, test, pointIndex, callback)
 {
     var magnitude = Magnitude._magnitudes[pointIndex];
     setup(magnitude);

     var debugStr = 'run for magnitude ' + magnitude;
     if (window.GCController) {
         if (GCController.getJSObjectCount)
             debugStr += ' jsObjectCountBefore ' + GCController.getJSObjectCount();

         GCController.collectAll();

         if (GCController.getJSObjectCount)
             debugStr += ' jsObjectCountAfter ' + GCController.getJSObjectCount();
     }

     Magnitude._debug(debugStr);

     var nowFunction = window.performance && window.performance.now ?
         window.performance.now.bind(window.performance) : Date.now;

     // Possibly run multiple times, to deal with delays at end
     var runOk = false;
     var attempt = 0;
     var maxAttempts = 5;
     var millisecondsPerIteration;
     var totalTimeMilliseconds;
     var iterations;

     function iteration(nextIteration)
     {
         var start = nowFunction();
         iterations = 0;
         totalTimeMilliseconds = 0;
         function completeRun(nextRun)
         {
              iterations++;
              totalTimeMilliseconds = nowFunction() - start;
              nextRun();
         }
         Magnitude._while(function() { return totalTimeMilliseconds < Magnitude.millisecondsPerRun; }, function(nextRun) { test(magnitude, completeRun.bind(null, nextRun)); }, completeIteration.bind(null, nextIteration));
     }

     function completeIteration(nextIteration)
     {
         millisecondsPerIteration = totalTimeMilliseconds / iterations;
         Magnitude._debug(iterations + ' iterations in ' +
             totalTimeMilliseconds + ' milliseconds, ' +
             'average ' + millisecondsPerIteration +
             ' milliseconds per iteration');

         var overTime = totalTimeMilliseconds - Magnitude.millisecondsPerRun;
         var relativeOverTimeTolerance = 0.001;
         var overTimeTolerance = Magnitude.millisecondsPerRun *
             relativeOverTimeTolerance;
         // If overTime is more than the duration of a run,
         // there was some delay, which introduces noise.
         // Allow a small amount of tolerance.
         if (overTime < (millisecondsPerIteration + overTimeTolerance))
             runOk = true;
         else {
             Magnitude._debug('over-time: ' + overTime +
                 ' exceeds average run-time ' + millisecondsPerIteration +
                 ' by more than tolerance of ' + overTimeTolerance +
                 ' assuming delay');
             attempt++;
             if (attempt < maxAttempts)
                 Magnitude._debug('Retrying to reduce delay noise');
             else {
                 Magnitude._debug('Failed to reduce delay noise after ' +
                     maxAttempts + ' attempts, proceeding with noisy data');
                 runOk = true;
             }
         }
         nextIteration();
     }
     Magnitude._while(function() { return !runOk; }, iteration, function() { callback(millisecondsPerIteration); });
 };

 // Auxiliary computations
 Magnitude._log2Ratios = function()
 {
     // Compute base-2 logarithm of ratios of times,
     // equivalently the difference of the base-2 logarithms:
     // log_2(t[i+1]/t[i]) = log_2(t[i+1]) - log_2(t[i])
     // Since times are exponentially spaced (base 2),
     // this is the slope of the step on the log-log scale,
     // and hence for O(n^k) growth should be k (the exponent).
     var ratioArray = [];
     var log2RatioArray = [];
     for (var i = 0; i < Magnitude.numPoints - 1; i++) {
         var ratio = Magnitude._times[i + 1] / Magnitude._times[i];
         var log2Ratio = Math.log(ratio) / Math.log(2);
         ratioArray.push(ratio);
         log2RatioArray.push(log2Ratio);
     }
     Magnitude._debug('ratios: ' + ratioArray.join(','));
     Magnitude._debug('log-ratios (base 2): ' + log2RatioArray.join(','));
     return log2RatioArray;
 };

 // Statistical tests
 Magnitude._isConstant = function()
 {
     // Time should be approximately constant.
     // To deal with noise, instead of constant, check that
     // (trimmed) abs relative deviation from median is within tolerance of 0.
     var times = Magnitude._times;
     var median = Magnitude._median(times);
     var relativeDeviations = Magnitude._relativeDeviations(times, median);
     Magnitude._debug('Median time: ' + median);
     Magnitude._debug('Relative deviations: ' + relativeDeviations.join(','));
     var trimmedAbsRelativeDeviations = Magnitude._absSortDownTrimTop(relativeDeviations, Magnitude.trim);
     Magnitude._debug('Trimmed sorted absolute relative deviations: ' +
         trimmedAbsRelativeDeviations.join(','));
     var maxAbsDeviation = trimmedAbsRelativeDeviations[0];
     Magnitude._debug('Maximum Absolute Relative Deviation: ' + maxAbsDeviation);
     return maxAbsDeviation <= Magnitude.tolerance;
 };

 Magnitude._isLinear = function()
 {
     // Exponent of a monomial is the slope on the log-log scale.
     // Magnitudes are exponentially stepped, so log ratio is slope
     // of secant on log-log scale.
     // In linear growth, (trimmed) log2Ratio should equal 1, to within tolerance
     // (Special case of polynomial; see below for why this is separate.)
     //
     // Can do better by removing outlying points (and then computing the
     // slope between the neighboring points) instead of trimming ratios,
     // so we retain the data of the slope of that double step, but since we are
     // only looking at the Maximum (Absolute) Deviation, in practice these
     // generally amount to the same: given an outlier, the slope coming into
     // the point and the slope going out will generally be high/low or low/high,
     // and thus both be trimmed, while the slope of the double step will
     // generally not be extreme, so not informative.
     var logRatios = Magnitude._log2Ratios();
     var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
     var minLogRatio = Magnitude._min(trimmedLogRatios);
     var maxLogRatio = Magnitude._max(trimmedLogRatios);
     var maxAbsDeviation = Math.max(Math.abs(1 - minLogRatio),
                                    Math.abs(maxLogRatio - 1));
     Magnitude._debug('Maximum Absolute Deviation: ' + maxAbsDeviation);
     Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
     return maxAbsDeviation <= Magnitude.tolerance;
 };

 Magnitude._isPolynomial = function()
 {
     // Exponent of a monomial is the slope on the log-log scale.
     // Magnitudes are exponentially stepped, so log ratio is slope
     // of secant on log-log scale.
     // Polynomial growth is expected to be O(n^2) or greater,
     // so logRatio should be at least 2: check (trimmed) min with tolerance
     //
     // Linear is fundamentally a special case of polynomial,
     // but here not specifying a specific exponent, and instead testing
     // that it grows *at least* quadratically (>= 2, rather than = 2 or = 3).
     // Thus we have separate functions.
     var logRatios = Magnitude._log2Ratios();
     var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
     var minLogRatio = Magnitude._min(trimmedLogRatios);
     var absDeviationMin = Math.abs(2 - minLogRatio);
     Magnitude._debug('Absolute Deviation of Minimum: ' + absDeviationMin);
     Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
     return absDeviationMin <= Magnitude.tolerance;
 };

 // Register listener
 window.addEventListener('load', function() {
     // FIXME: Add Magnitude.waitUntilDone/notifyDone for tests that need to
     // operate after the load event has fired.
     if (window.testRunner)
         document.body.innerHTML = '';
     document.body.appendChild(Magnitude._container);
 }, false);
	// Magnitude verifies time complexity of a function.
	// Magnitude.run can be called multiple times in a single script if desired,
	// optionally with different parameters each time.
	//
	// Usage:
	// <script src="../resources/magnitude-perf.js"></script>
	// <script>
	// function setup(magnitude)
	// {
	// ...
	// }
	//
	// function test(magnitude)
	// {
	// ...
	// }
	// ...
	// Magnitude.description('Test that foo is linear in number of nodes.');
	// Magnitude.run(setup, test, expected);
	// </script>
	//
	// setup: function to run once before the test-loop. Takes a magnitude
	// argument that is the value of 'n'.
	// test: function whose runtime is being tested. Also takes a magnitude
	// argument.
	// expected: one of the run-time constants listed below, e.g.:
	// Magnitude.CONSTANT, Magnitude.LINEAR, etc.

	if (window.testRunner)
	testRunner.dumpAsText();

	// Namespace
	var Magnitude = {};

	// Description of test; prepended to the dumped markup
	Magnitude.description = function(description)
	{
	Magnitude._log(description);
	};

	// Parameters (customize per test)
	// See "Time Complexity Tests" document for details:
	// http://dev.chromium.org/developers/testing/time-complexity-tests
	// Specify over which range the growth rate should hold:
	// 2^n ... 2^(n+k-1) where n = initialExponent, k = numPoints
	Magnitude.initialExponent = 0;
	Magnitude.numPoints = 8;
	// Number of trials to run
	// (Trial = compute times for all magnitudes, compute statistical test,
	// decide if for this dataset, the data fits the model)
	Magnitude.numTrials = 3;
	// Fraction of trials that must succeed for test overall to PASS
	// (Default 50% means 2 out of 3 must succeed)
	Magnitude.successThreshold = 0.50;
	// Run = for each magnitude, run test function until pass this time limit,
	// then stop and compute average time
	Magnitude.millisecondsPerRun = 25;
	// Strict tolerance, so noisy tests explicitly state noisiness
	// Ok to relax for noisy tests;
	// try tolerance = 0.10 or 0.20, and/or trim = 1 or 2 to relax slightly
	// tolerance is "max (trimmed) deviation from expected",
	// where "expected" is:
	// * expected slope (linear, polynomial),
	// * median value (constant),
	// * predicted value in linear regression (logarithmic).
	// For log this often needs to be very large (due to scaling), and 1.00 is ok.
	Magnitude.trim = 0; // trim = 1 useful if unusual value on initial run
	Magnitude.tolerance = 0.05;

	Magnitude.CONSTANT = 'O(1)';
	Magnitude.LINEAR = 'O(n)';
	Magnitude.POLYNOMIAL = '>=O(n^2)';

	// Utility functions
	Magnitude._max = function(array) {
	return Math.max.apply(null, array);
	};

	Magnitude._min = function(array) {
	return Math.min.apply(null, array);
	};

	Magnitude._sortTrimArray = function(array, trim) {
	// sort array, then trim both ends
	// used for computing trimmed maximum absolute deviation
	var sorted_array = array.map(Math.abs).sort(function(a, b) { return a - b; });
	if (!trim)
	return sorted_array;
	else
	return sorted_array.slice(trim, -trim);
	};

	Magnitude._relativeDeviations = function(array, ref)
	{
	return array.map(function(x) { return (x - ref) / ref; });
	};

	Magnitude._absSortDownTrimTop = function(array, trim) {
	// only trim the top of array
	// used for computing trimmed maximum absolute deviation
	if (trim === undefined)
	trim = 0;
	return array.map(Math.abs).sort(
	function(a, b) { return b - a; }).slice(trim);
	};

	Magnitude._median = function(array) {
	array.sort(function(a, b) { return a - b; });
	var len = array.length;
	if (!len)
	return;
	var half = Math.floor(len / 2);
	if (len % 2)
	return array[half];
	return (array[half - 1] + array[half]) / 2;
	};

	// Logging functions
	Magnitude._log = function(msg)
	{
	if (!Magnitude._container)
	Magnitude._container = document.createElement('pre');
	Magnitude._container.appendChild(document.createTextNode(msg + '\n'));
	};

	Magnitude._debug = function(msg)
	{
	Magnitude._debugLog += msg + '\n';
	};

	Magnitude._logRunTimes = function()
	{
	// Print out the magnitudes and times in CSV
	// to afford easy copy-paste to a charting application.
	Magnitude._debug('magnitudes: ' + Magnitude._magnitudes.join(','));
	Magnitude._debug('times: ' + Magnitude._times.join(','));
	};

	Magnitude._for = function(n, body, callback)
	{
	var i = 0;
	var results = [];

	function iteration(result) {
	results.push(result);
	if (++i === n)
	callback(results);
	else
	body(i, iteration);
	}

	if (Magnitude._async) {
	body(i, iteration);
	} else {
	for (; i < n; ++i) {
	body(i, function(result) {
	results.push(result);
	});
	}
	callback(results);
	}
	};

	Magnitude._while = function(condition, body, callback)
	{
	function iteration() {
	if (condition())
	body(iteration);
	else
	callback();
	}

	if (Magnitude._async) {
	iteration();
	} else {
	while (condition()) {
	body(function() {});
	}
	callback();
	}
	};

	// Main
	Magnitude.run = function(setup, test, expected)
	{
	function runTest(magnitude, callback) {
	test(magnitude);
	callback();
	}
	Magnitude._run(setup, runTest, expected, false);
	};

	Magnitude.runAsync = function(setup, test, expected)
	{
	if (window.testRunner)
	testRunner.waitUntilDone();
	window.addEventListener('load', function() {
	Magnitude._run(setup, test, expected, true);
	}, false);
	};

	Magnitude._run = function(setup, test, expected, async)
	{
	Magnitude._async = async;
	Magnitude._debugLog = '\nDEBUG LOG:\n';
	Magnitude._debug('Expected complexity: ' + expected);

	Magnitude._exponents = [];
	Magnitude._magnitudes = [];
	var maxExponent = Magnitude.initialExponent + Magnitude.numPoints;
	for (var i = Magnitude.initialExponent; i < maxExponent; i++) {
	Magnitude._exponents.push(i);
	Magnitude._magnitudes.push(Math.pow(2, i));
	}

	Magnitude._numSuccesses = 0;
	function runTrial(trialNumber, nextTrial)
	{
	Magnitude._trialNumber = trialNumber;
	Magnitude._debug('\nTrial #' + trialNumber);
	Magnitude._for(Magnitude.numPoints, Magnitude._runTime.bind(null, setup, test), completeTrial.bind(null, nextTrial));
	}
	function completeTrial(nextTrial, times)
	{
	Magnitude._times = times;
	Magnitude._logRunTimes();
	switch (expected) {
	case Magnitude.CONSTANT:
	passed = Magnitude._isConstant();
	break;
	case Magnitude.LINEAR:
	passed = Magnitude._isLinear();
	break;
	case Magnitude.POLYNOMIAL:
	passed = Magnitude._isPolynomial();
	break;
	default:
	Magnitude._log('FAIL: unrecognized order of growth: ' + expected);
	passed = false;
	break;
	}
	Magnitude._debug('Trial #' + Magnitude._trialNumber + ': ' +
	(passed ? 'SUCCESS' : 'FAILURE'));
	if (passed)
	Magnitude._numSuccesses++;
	nextTrial();
	}
	Magnitude._for(Magnitude.numTrials, runTrial, Magnitude._finish);
	};

	Magnitude._finish = function()
	{
	var neededToPass = Magnitude.numTrials * Magnitude.successThreshold;
	Magnitude._debug('Successes: ' + Magnitude._numSuccesses + ', need ' +
	neededToPass + ' (' + (100 * Magnitude.successThreshold) + '%) ' +
	'to pass');
	var passedOverall = (Magnitude._numSuccesses >= neededToPass);
	Magnitude._log(passedOverall ? 'PASS' : 'FAIL');

	// By default don't log detailed information to layout test results,
	// in order to keep expected results consistent from run to run.
	if (!window.testRunner \|\| !passedOverall)
	Magnitude._log(Magnitude._debugLog);

	if (Magnitude._async && window.testRunner)
	testRunner.notifyDone();
	};

	Magnitude._runTime = function(setup, test, pointIndex, callback)
	{
	var magnitude = Magnitude._magnitudes[pointIndex];
	setup(magnitude);

	var debugStr = 'run for magnitude ' + magnitude;
	if (window.GCController) {
	if (GCController.getJSObjectCount)
	debugStr += ' jsObjectCountBefore ' + GCController.getJSObjectCount();

	GCController.collectAll();

	if (GCController.getJSObjectCount)
	debugStr += ' jsObjectCountAfter ' + GCController.getJSObjectCount();
	}

	Magnitude._debug(debugStr);

	var nowFunction = window.performance && window.performance.now ?
	window.performance.now.bind(window.performance) : Date.now;

	// Possibly run multiple times, to deal with delays at end
	var runOk = false;
	var attempt = 0;
	var maxAttempts = 5;
	var millisecondsPerIteration;
	var totalTimeMilliseconds;
	var iterations;

	function iteration(nextIteration)
	{
	var start = nowFunction();
	iterations = 0;
	totalTimeMilliseconds = 0;
	function completeRun(nextRun)
	{
	iterations++;
	totalTimeMilliseconds = nowFunction() - start;
	nextRun();
	}
	Magnitude._while(function() { return totalTimeMilliseconds < Magnitude.millisecondsPerRun; }, function(nextRun) { test(magnitude, completeRun.bind(null, nextRun)); }, completeIteration.bind(null, nextIteration));
	}

	function completeIteration(nextIteration)
	{
	millisecondsPerIteration = totalTimeMilliseconds / iterations;
	Magnitude._debug(iterations + ' iterations in ' +
	totalTimeMilliseconds + ' milliseconds, ' +
	'average ' + millisecondsPerIteration +
	' milliseconds per iteration');

	var overTime = totalTimeMilliseconds - Magnitude.millisecondsPerRun;
	var relativeOverTimeTolerance = 0.001;
	var overTimeTolerance = Magnitude.millisecondsPerRun *
	relativeOverTimeTolerance;
	// If overTime is more than the duration of a run,
	// there was some delay, which introduces noise.
	// Allow a small amount of tolerance.
	if (overTime < (millisecondsPerIteration + overTimeTolerance))
	runOk = true;
	else {
	Magnitude._debug('over-time: ' + overTime +
	' exceeds average run-time ' + millisecondsPerIteration +
	' by more than tolerance of ' + overTimeTolerance +
	' assuming delay');
	attempt++;
	if (attempt < maxAttempts)
	Magnitude._debug('Retrying to reduce delay noise');
	else {
	Magnitude._debug('Failed to reduce delay noise after ' +
	maxAttempts + ' attempts, proceeding with noisy data');
	runOk = true;
	}
	}
	nextIteration();
	}
	Magnitude._while(function() { return !runOk; }, iteration, function() { callback(millisecondsPerIteration); });
	};

	// Auxiliary computations
	Magnitude._log2Ratios = function()
	{
	// Compute base-2 logarithm of ratios of times,
	// equivalently the difference of the base-2 logarithms:
	// log_2(t[i+1]/t[i]) = log_2(t[i+1]) - log_2(t[i])
	// Since times are exponentially spaced (base 2),
	// this is the slope of the step on the log-log scale,
	// and hence for O(n^k) growth should be k (the exponent).
	var ratioArray = [];
	var log2RatioArray = [];
	for (var i = 0; i < Magnitude.numPoints - 1; i++) {
	var ratio = Magnitude._times[i + 1] / Magnitude._times[i];
	var log2Ratio = Math.log(ratio) / Math.log(2);
	ratioArray.push(ratio);
	log2RatioArray.push(log2Ratio);
	}
	Magnitude._debug('ratios: ' + ratioArray.join(','));
	Magnitude._debug('log-ratios (base 2): ' + log2RatioArray.join(','));
	return log2RatioArray;
	};

	// Statistical tests
	Magnitude._isConstant = function()
	{
	// Time should be approximately constant.
	// To deal with noise, instead of constant, check that
	// (trimmed) abs relative deviation from median is within tolerance of 0.
	var times = Magnitude._times;
	var median = Magnitude._median(times);
	var relativeDeviations = Magnitude._relativeDeviations(times, median);
	Magnitude._debug('Median time: ' + median);
	Magnitude._debug('Relative deviations: ' + relativeDeviations.join(','));
	var trimmedAbsRelativeDeviations = Magnitude._absSortDownTrimTop(relativeDeviations, Magnitude.trim);
	Magnitude._debug('Trimmed sorted absolute relative deviations: ' +
	trimmedAbsRelativeDeviations.join(','));
	var maxAbsDeviation = trimmedAbsRelativeDeviations[0];
	Magnitude._debug('Maximum Absolute Relative Deviation: ' + maxAbsDeviation);
	return maxAbsDeviation <= Magnitude.tolerance;
	};

	Magnitude._isLinear = function()
	{
	// Exponent of a monomial is the slope on the log-log scale.
	// Magnitudes are exponentially stepped, so log ratio is slope
	// of secant on log-log scale.
	// In linear growth, (trimmed) log2Ratio should equal 1, to within tolerance
	// (Special case of polynomial; see below for why this is separate.)
	//
	// Can do better by removing outlying points (and then computing the
	// slope between the neighboring points) instead of trimming ratios,
	// so we retain the data of the slope of that double step, but since we are
	// only looking at the Maximum (Absolute) Deviation, in practice these
	// generally amount to the same: given an outlier, the slope coming into
	// the point and the slope going out will generally be high/low or low/high,
	// and thus both be trimmed, while the slope of the double step will
	// generally not be extreme, so not informative.
	var logRatios = Magnitude._log2Ratios();
	var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
	var minLogRatio = Magnitude._min(trimmedLogRatios);
	var maxLogRatio = Magnitude._max(trimmedLogRatios);
	var maxAbsDeviation = Math.max(Math.abs(1 - minLogRatio),
	Math.abs(maxLogRatio - 1));
	Magnitude._debug('Maximum Absolute Deviation: ' + maxAbsDeviation);
	Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
	return maxAbsDeviation <= Magnitude.tolerance;
	};

	Magnitude._isPolynomial = function()
	{
	// Exponent of a monomial is the slope on the log-log scale.
	// Magnitudes are exponentially stepped, so log ratio is slope
	// of secant on log-log scale.
	// Polynomial growth is expected to be O(n^2) or greater,
	// so logRatio should be at least 2: check (trimmed) min with tolerance
	//
	// Linear is fundamentally a special case of polynomial,
	// but here not specifying a specific exponent, and instead testing
	// that it grows at least quadratically (>= 2, rather than = 2 or = 3).
	// Thus we have separate functions.
	var logRatios = Magnitude._log2Ratios();
	var trimmedLogRatios = Magnitude._sortTrimArray(logRatios, Magnitude.trim);
	var minLogRatio = Magnitude._min(trimmedLogRatios);
	var absDeviationMin = Math.abs(2 - minLogRatio);
	Magnitude._debug('Absolute Deviation of Minimum: ' + absDeviationMin);
	Magnitude._debug('Tolerance: ' + Magnitude.tolerance);
	return absDeviationMin <= Magnitude.tolerance;
	};

	// Register listener
	window.addEventListener('load', function() {
	// FIXME: Add Magnitude.waitUntilDone/notifyDone for tests that need to
	// operate after the load event has fired.
	if (window.testRunner)
	document.body.innerHTML = '';
	document.body.appendChild(Magnitude._container);
	}, false);