Attachment 166626 Details for Bug 98115 – Added link to algorithm in the ChangeLog

[patch] Added link to algorithm in the ChangeLog

98115.4.patch (text/plain), 14.13 KB, created by Philip Rogers on 2012-10-02 00:17:26 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Philip Rogers

Created: 2012-10-02 00:17:26 PDT

Size: 14.13 KB

patch

obsolete

>Index: PerformanceTests/ChangeLog
>===================================================================
>--- PerformanceTests/ChangeLog	(revision 130125)
>+++ PerformanceTests/ChangeLog	(working copy)
>@@ -1,3 +1,26 @@
>+2012-10-01  Philip Rogers  <pdr@google.com>
>+
>+        Fix PerfTest standard deviation calculation.
>+        https://bugs.webkit.org/show_bug.cgi?id=98115
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        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: PerformanceTests/resources/runner.js
>===================================================================
>--- PerformanceTests/resources/runner.js	(revision 130127)
>+++ PerformanceTests/resources/runner.js	(working copy)
>@@ -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: Tools/ChangeLog
>===================================================================
>--- Tools/ChangeLog	(revision 130125)
>+++ Tools/ChangeLog	(working copy)
>@@ -1,3 +1,35 @@
>+2012-10-01  Philip Rogers  <pdr@google.com>
>+
>+        Fix PerfTest standard deviation calculation.
>+        https://bugs.webkit.org/show_bug.cgi?id=98115
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        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: Tools/Scripts/webkitpy/performance_tests/perftest.py
>===================================================================
>--- Tools/Scripts/webkitpy/performance_tests/perftest.py	(revision 129959)
>+++ Tools/Scripts/webkitpy/performance_tests/perftest.py	(working copy)
>@@ -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: Tools/Scripts/webkitpy/performance_tests/perftest_unittest.py
>===================================================================
>--- Tools/Scripts/webkitpy/performance_tests/perftest_unittest.py	(revision 129959)
>+++ Tools/Scripts/webkitpy/performance_tests/perftest_unittest.py	(working copy)
>@@ -117,13 +117,13 @@ class TestPageLoadingPerfTest(unittest.T
>         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()
>Index: LayoutTests/ChangeLog
>===================================================================
>--- LayoutTests/ChangeLog	(revision 130125)
>+++ LayoutTests/ChangeLog	(working copy)
>@@ -1,3 +1,27 @@
>+2012-10-01  Philip Rogers  <pdr@google.com>
>+
>+        Fix PerfTest standard deviation calculation.
>+        https://bugs.webkit.org/show_bug.cgi?id=98115
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        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-01  Pavel Feldman  <pfeldman@chromium.org>
> 
>         Web Inspector: move completions calculation into RuntimeModel (part 1)
>Index: LayoutTests/fast/harness/perftests/perf-runner-compute-statistics-expected.txt
>===================================================================
>--- LayoutTests/fast/harness/perftests/perf-runner-compute-statistics-expected.txt	(revision 130127)
>+++ LayoutTests/fast/harness/perftests/perf-runner-compute-statistics-expected.txt	(working copy)
>@@ -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: LayoutTests/fast/harness/perftests/perf-runner-compute-statistics.html
>===================================================================
>--- LayoutTests/fast/harness/perftests/perf-runner-compute-statistics.html	(revision 130127)
>+++ LayoutTests/fast/harness/perftests/perf-runner-compute-statistics.html	(working copy)
>@@ -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: LayoutTests/fast/harness/perftests/runs-per-second-log-expected.txt
>===================================================================
>--- LayoutTests/fast/harness/perftests/runs-per-second-log-expected.txt	(revision 130127)
>+++ LayoutTests/fast/harness/perftests/runs-per-second-log-expected.txt	(working copy)
>@@ -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
>

Actions: View | Formatted Diff | Diff

Attachments on bug 98115: 166608 | 166621 | 166623 | 166626