Fix PerfTest standard deviation calculation.
authorpdr@google.com <pdr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 2 Oct 2012 08:10:47 +0000 (08:10 +0000)
committerpdr@google.com <pdr@google.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 2 Oct 2012 08:10:47 +0000 (08:10 +0000)
https://bugs.webkit.org/show_bug.cgi?id=98115

Reviewed by Ryosuke Niwa.

Previously our standard deviation calculation was incorrect. This patch
updates perftest.py's algorithm to calculate the sample standard deviation
(with Bessel's correction) using Knuth's online algorithm:
http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm
An existing test has been modified to prove our new results.

This patch also updates runner.js to use Bessel's correction in
its sample standard deviation calculation, which is more accurate
for small sample sizes.

Additionally, runner.js has been modified to not calculate
the 'sum' statistic, which was not very useful.

PerformanceTests:

* resources/runner.js:
(PerfTestRunner.computeStatistics):

Tools:

* Scripts/webkitpy/performance_tests/perftest.py:

    The unused variable valueSum has also been removed.

(PageLoadingPerfTest.run):
* Scripts/webkitpy/performance_tests/perftest_unittest.py:

    This test calculates the stdev of {2000, 3000, ..., 20000} which
    was hand-calculated using a spreadsheet.

(TestPageLoadingPerfTest.test_run):

LayoutTests:

* fast/harness/perftests/perf-runner-compute-statistics-expected.txt:
* fast/harness/perftests/perf-runner-compute-statistics.html:
* fast/harness/perftests/runs-per-second-log-expected.txt:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@130135 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/harness/perftests/perf-runner-compute-statistics-expected.txt
LayoutTests/fast/harness/perftests/perf-runner-compute-statistics.html
LayoutTests/fast/harness/perftests/runs-per-second-log-expected.txt
PerformanceTests/ChangeLog
PerformanceTests/resources/runner.js
Tools/ChangeLog
Tools/Scripts/webkitpy/performance_tests/perftest.py
Tools/Scripts/webkitpy/performance_tests/perftest_unittest.py

index e32951f..9c48fac 100644 (file)
@@ -1,3 +1,27 @@
+2012-10-02  Philip Rogers  <pdr@google.com>
+
+        Fix PerfTest standard deviation calculation.
+        https://bugs.webkit.org/show_bug.cgi?id=98115
+
+        Reviewed by Ryosuke Niwa.
+
+        Previously our standard deviation calculation was incorrect. This patch
+        updates perftest.py's algorithm to calculate the sample standard deviation
+        (with Bessel's correction) using Knuth's online algorithm:
+        http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm
+        An existing test has been modified to prove our new results.
+
+        This patch also updates runner.js to use Bessel's correction in
+        its sample standard deviation calculation, which is more accurate
+        for small sample sizes.
+
+        Additionally, runner.js has been modified to not calculate
+        the 'sum' statistic, which was not very useful.
+
+        * fast/harness/perftests/perf-runner-compute-statistics-expected.txt:
+        * fast/harness/perftests/perf-runner-compute-statistics.html:
+        * fast/harness/perftests/runs-per-second-log-expected.txt:
+
 2012-10-02  Andrey Kosyakov  <caseq@chromium.org>
 
         Unreviewed gardening -- rebaselined canvas-render-layer and 4 week-multiple-fields-appearance tests.
index e9fc205..0208a85 100644 (file)
@@ -1,4 +1,4 @@
-This test verifies PerfTestRunner.computeStatistics(), including: min, max, median, mean, sum, variance, and stdev.
+This test verifies PerfTestRunner.computeStatistics(), including: min, max, median, mean, variance, and stdev.
 
 On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
 
@@ -8,7 +8,6 @@ PASS stats.min is 0
 PASS stats.max is 0
 PASS stats.median is 0
 PASS stats.mean is 0
-PASS stats.sum is 0
 PASS stats.variance is 0
 PASS stats.stdev is 0
 
@@ -20,14 +19,12 @@ PASS stats.min is 1
 PASS stats.max is 20
 PASS stats.median is 5
 PASS stats.mean is 7.6
-PASS stats.sum is 38
 PASS stats.min is 1
 PASS stats.max is 20
 PASS stats.median is 5
 PASS stats.mean is 7.6
-PASS stats.sum is 38
-PASS stats.variance is within 0.0001 of 48.239999999999995
-PASS stats.stdev is within 0.0001 of 6.945502141674135
+PASS stats.variance is within 0.0001 of 60.3
+PASS stats.stdev is within 0.0001 of 7.76530746332687
 
 This test will catch if any order dependencies in the data, such as
 needing to be numerically sorted, are not resolved by the algorithm.
@@ -37,14 +34,12 @@ PASS stats.min is -20
 PASS stats.max is -1
 PASS stats.median is -5
 PASS stats.mean is -7.6
-PASS stats.sum is -38
 PASS stats.min is -20
 PASS stats.max is -1
 PASS stats.median is -5
 PASS stats.mean is -7.6
-PASS stats.sum is -38
-PASS stats.variance is within 0.0001 of 48.239999999999995
-PASS stats.stdev is within 0.0001 of 6.945502141674135
+PASS stats.variance is within 0.0001 of 60.3
+PASS stats.stdev is within 0.0001 of 7.76530746332687
 
 Ensure no latent divide by 0's for an even number of elements.
 data = [0,0,0,0]
index e79fdd0..58d7c84 100644 (file)
@@ -32,13 +32,12 @@ var alternateComputeStatistics = {
     },
     variance: function(array) {
         var mean = alternateComputeStatistics.mean(array);
-        var arrayOfSquaredDiffs = [];
+        var sumOfSquaredDiffs = 0;
         for (var index in array) {
             var squaredDiff = array[index] - mean;
-            squaredDiff *= squaredDiff;
-            arrayOfSquaredDiffs.push(squaredDiff);
+            sumOfSquaredDiffs += squaredDiff * squaredDiff;
         };
-        return alternateComputeStatistics.mean(arrayOfSquaredDiffs);
+        return sumOfSquaredDiffs / (array.length - 1);
     },
     stdev: function(array) {
         return Math.sqrt(alternateComputeStatistics.variance(array));
@@ -52,7 +51,7 @@ var alternateComputeStatistics = {
 
 <script type="text/javascript">
 description("This test verifies PerfTestRunner.computeStatistics(), " +
-            "including: min, max, median, mean, sum, variance, and stdev.");
+            "including: min, max, median, mean, variance, and stdev.");
 </script>
 
 <div id="console"></div>
@@ -69,7 +68,6 @@ shouldEvaluateTo("stats.min", 0);
 shouldEvaluateTo("stats.max", 0);
 shouldEvaluateTo("stats.median", 0);
 shouldEvaluateTo("stats.mean", 0);
-shouldEvaluateTo("stats.sum", 0);
 shouldEvaluateTo("stats.variance", 0);
 shouldEvaluateTo("stats.stdev", 0);
 debug("");
@@ -85,13 +83,11 @@ shouldEvaluateTo("stats.min", 1);
 shouldEvaluateTo("stats.max", 20);
 shouldEvaluateTo("stats.median", 5);
 shouldEvaluateTo("stats.mean", (38/5));
-shouldEvaluateTo("stats.sum", (1+2+5+10+20));
 // using alternate implementation
 shouldEvaluateTo("stats.min", alternateComputeStatistics.min(data));
 shouldEvaluateTo("stats.max", alternateComputeStatistics.max(data));
 shouldEvaluateTo("stats.median", alternateComputeStatistics.median(data));
 shouldEvaluateTo("stats.mean", alternateComputeStatistics.mean(data));
-shouldEvaluateTo("stats.sum", alternateComputeStatistics.sum(data));
 shouldBeCloseTo("stats.variance", alternateComputeStatistics.variance(data), 0.0001);
 shouldBeCloseTo("stats.stdev", alternateComputeStatistics.stdev(data), 0.0001);
 debug("");
@@ -107,13 +103,11 @@ shouldEvaluateTo("stats.min", -20);
 shouldEvaluateTo("stats.max", -1);
 shouldEvaluateTo("stats.median", -5);
 shouldEvaluateTo("stats.mean", (-38/5));
-shouldEvaluateTo("stats.sum", (-1-2-5-10-20));
 // using alternate implementation
 shouldEvaluateTo("stats.min", alternateComputeStatistics.min(data));
 shouldEvaluateTo("stats.max", alternateComputeStatistics.max(data));
 shouldEvaluateTo("stats.median", alternateComputeStatistics.median(data));
 shouldEvaluateTo("stats.mean", alternateComputeStatistics.mean(data));
-shouldEvaluateTo("stats.sum", alternateComputeStatistics.sum(data));
 shouldBeCloseTo("stats.variance", alternateComputeStatistics.variance(data), 0.0001);
 shouldBeCloseTo("stats.stdev", alternateComputeStatistics.stdev(data), 0.0001);
 debug("");
index 136606c..05257df 100644 (file)
@@ -12,7 +12,7 @@ Time:
 values 2, 4, 5, 8, 10 runs/s
 avg 5.8 runs/s
 median 5 runs/s
-stdev 2.86 runs/s
+stdev 3.19 runs/s
 min 2 runs/s
 max 10 runs/s
 
index d18237a..a82e3d3 100644 (file)
@@ -1,3 +1,26 @@
+2012-10-02  Philip Rogers  <pdr@google.com>
+
+        Fix PerfTest standard deviation calculation.
+        https://bugs.webkit.org/show_bug.cgi?id=98115
+
+        Reviewed by Ryosuke Niwa.
+
+        Previously our standard deviation calculation was incorrect. This patch
+        updates perftest.py's algorithm to calculate the sample standard deviation
+        (with Bessel's correction) using Knuth's online algorithm:
+        http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm
+        An existing test has been modified to prove our new results.
+
+        This patch also updates runner.js to use Bessel's correction in
+        its sample standard deviation calculation, which is more accurate
+        for small sample sizes.
+
+        Additionally, runner.js has been modified to not calculate
+        the 'sum' statistic, which was not very useful.
+
+        * resources/runner.js:
+        (PerfTestRunner.computeStatistics):
+
 2012-10-01  Ryosuke Niwa  <rniwa@webkit.org>
 
         PerfTestRunner: Move all functions into the closure and always use double quotation for string literals
index c22810c..7b4fbb2 100755 (executable)
@@ -69,20 +69,18 @@ if (window.testRunner) {
             median: data.length % 2 ? data[middle] : (data[middle - 1] + data[middle]) / 2,
         };
 
-        // Compute the mean and variance using a numerically stable algorithm.
+        // Compute the mean and variance using Knuth's online algorithm (has good numerical stability).
         var squareSum = 0;
         result.values = times;
-        result.mean = data[0];
-        result.sum = data[0];
-        for (var i = 1; i < data.length; ++i) {
+        result.mean = 0;
+        for (var i = 0; i < data.length; ++i) {
             var x = data[i];
             var delta = x - result.mean;
             var sweep = i + 1.0;
             result.mean += delta / sweep;
-            result.sum += x;
-            squareSum += delta * delta * (i / sweep);
+            squareSum += delta * (x - result.mean);
         }
-        result.variance = squareSum / data.length;
+        result.variance = squareSum / (data.length - 1);
         result.stdev = Math.sqrt(result.variance);
         result.unit = unit || "ms";
 
index d6710dd..1bb209f 100644 (file)
@@ -1,3 +1,35 @@
+2012-10-02  Philip Rogers  <pdr@google.com>
+
+        Fix PerfTest standard deviation calculation.
+        https://bugs.webkit.org/show_bug.cgi?id=98115
+
+        Reviewed by Ryosuke Niwa.
+
+        Previously our standard deviation calculation was incorrect. This patch
+        updates perftest.py's algorithm to calculate the sample standard deviation
+        (with Bessel's correction) using Knuth's online algorithm:
+        http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm
+        An existing test has been modified to prove our new results.
+
+        This patch also updates runner.js to use Bessel's correction in
+        its sample standard deviation calculation, which is more accurate
+        for small sample sizes.
+
+        Additionally, runner.js has been modified to not calculate
+        the 'sum' statistic, which was not very useful.
+
+        * Scripts/webkitpy/performance_tests/perftest.py:
+
+            The unused variable valueSum has also been removed.
+
+        (PageLoadingPerfTest.run):
+        * Scripts/webkitpy/performance_tests/perftest_unittest.py:
+
+            This test calculates the stdev of {2000, 3000, ..., 20000} which
+            was hand-calculated using a spreadsheet.
+
+        (TestPageLoadingPerfTest.test_run):
+
 2012-10-01  Raphael Kubo da Costa  <raphael.kubo.da.costa@intel.com>
 
         webkitpy should accept a different httpd.conf specified by the user
index fdac35b..762e231 100644 (file)
@@ -218,15 +218,14 @@ class PageLoadingPerfTest(PerfTest):
 
         sorted_test_times = sorted(test_times)
 
-        # Compute the mean and variance using a numerically stable algorithm.
+        # Compute the mean and variance using Knuth's online algorithm (has good numerical stability).
         squareSum = 0
         mean = 0
-        valueSum = sum(sorted_test_times)
         for i, time in enumerate(sorted_test_times):
             delta = time - mean
             sweep = i + 1.0
             mean += delta / sweep
-            squareSum += delta * delta * (i / sweep)
+            squareSum += delta * (time - mean)
 
         middle = int(len(test_times) / 2)
         results = {'values': test_times,
@@ -234,7 +233,7 @@ class PageLoadingPerfTest(PerfTest):
             'min': sorted_test_times[0],
             'max': sorted_test_times[-1],
             'median': sorted_test_times[middle] if len(sorted_test_times) % 2 else (sorted_test_times[middle - 1] + sorted_test_times[middle]) / 2,
-            'stdev': math.sqrt(squareSum),
+            'stdev': math.sqrt(squareSum / (len(sorted_test_times) - 1)),
             'unit': 'ms'}
         self.output_statistics(self.test_name(), results, '')
         return {self.test_name(): results}
index 27a4bb3..6922ba9 100755 (executable)
@@ -117,13 +117,13 @@ class TestPageLoadingPerfTest(unittest.TestCase):
         output_capture.capture_output()
         try:
             self.assertEqual(test.run(driver, None),
-                {'some-test': {'max': 20000, 'avg': 11000.0, 'median': 11000, 'stdev': math.sqrt(570 * 1000 * 1000), 'min': 2000, 'unit': 'ms',
+                {'some-test': {'max': 20000, 'avg': 11000.0, 'median': 11000, 'stdev': 5627.314338711378, 'min': 2000, 'unit': 'ms',
                     'values': [i * 1000 for i in range(2, 21)]}})
         finally:
             actual_stdout, actual_stderr, actual_logs = output_capture.restore_output()
         self.assertEqual(actual_stdout, '')
         self.assertEqual(actual_stderr, '')
-        self.assertEqual(actual_logs, 'RESULT some-test= 11000.0 ms\nmedian= 11000 ms, stdev= 23874.6727726 ms, min= 2000 ms, max= 20000 ms\n')
+        self.assertEqual(actual_logs, 'RESULT some-test= 11000.0 ms\nmedian= 11000 ms, stdev= 5627.31433871 ms, min= 2000 ms, max= 20000 ms\n')
 
     def test_run_with_bad_output(self):
         output_capture = OutputCapture()