<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[196663] trunk/Websites/perf.webkit.org</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/196663">196663</a></dd>
<dt>Author</dt> <dd>rniwa@webkit.org</dd>
<dt>Date</dt> <dd>2016-02-16 15:16:25 -0800 (Tue, 16 Feb 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>Extract the code specific to v2 UI out of shared statistics.js
https://bugs.webkit.org/show_bug.cgi?id=154277
Reviewed by Chris Dumez.
Extracted statistics-strategies.js out of statistics.js for v2 UI and detect-changes.js. The intent is to
deprecate this file once we implement refined statistics tools in v3 UI and adopt it in detect-changes.js.
* public/shared/statistics.js:
(Statistics.movingAverage): Extracted from the "Simple Moving Average" strategy.
(Statistics.cumultaiveMovingAverage): Extracted from the "Cumulative Moving Average" strategy.
(Statistics.exponentialMovingAverage): Extracted from the "Exponential Moving Average" strategy.
Use a temporary "movingAverage" to keep the last moving average instead of relying on the previous
entry in "averages" array to avoid special casing an array of length 1 and starting the loop at i = 1.
(Statistics.segmentTimeSeriesGreedyWithStudentsTTest): Extracted from "Segmentation: Recursive t-test"
strategy. Don't create the list of averages to match segmentTimeSeriesByMaximizingSchwarzCriterion here.
It's done in newly added averagesFromSegments.
(Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Extracted from
"Segmentation: Schwarz criterion" strategy.
(.recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent): Just store the start index to match
* public/v2/app.js:
(App.Pane.updateStatisticsTools):
(App.Pane._computeMovingAverageAndOutliers):
* public/v2/data.js:
* public/v2/index.html:
* public/v2/statistics-strategies.js: Added.
(StatisticsStrategies.MovingAverageStrategies): Added.
(averagesFromSegments): Extracted from "Segmentation: Schwarz criterion" strategy. Now used by both
"Segmentation: Recursive t-test" and "Segmentation: Schwarz criterion" strategies.
(StatisticsStrategies.EnvelopingStrategies): Moved from Statistics.EnvelopingStrategies.
(StatisticsStrategies.TestRangeSelectionStrategies): Moved from Statistics.TestRangeSelectionStrategies.
(createWesternElectricRule): Moved from statistics.js.
(countValuesOnSameSide): Ditto.
(StatisticsStrategies.executeStrategy): Moved from Statistics.executeStrategy.
* tools/detect-changes.js:
(computeRangesForTesting):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkWebsitesperfwebkitorgChangeLog">trunk/Websites/perf.webkit.org/ChangeLog</a></li>
<li><a href="#trunkWebsitesperfwebkitorgpublicsharedstatisticsjs">trunk/Websites/perf.webkit.org/public/shared/statistics.js</a></li>
<li><a href="#trunkWebsitesperfwebkitorgpublicv2appjs">trunk/Websites/perf.webkit.org/public/v2/app.js</a></li>
<li><a href="#trunkWebsitesperfwebkitorgpublicv2datajs">trunk/Websites/perf.webkit.org/public/v2/data.js</a></li>
<li><a href="#trunkWebsitesperfwebkitorgpublicv2indexhtml">trunk/Websites/perf.webkit.org/public/v2/index.html</a></li>
<li><a href="#trunkWebsitesperfwebkitorgtoolsdetectchangesjs">trunk/Websites/perf.webkit.org/tools/detect-changes.js</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkWebsitesperfwebkitorgpublicv2statisticsstrategiesjs">trunk/Websites/perf.webkit.org/public/v2/statistics-strategies.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkWebsitesperfwebkitorgChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/ChangeLog (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/ChangeLog 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/ChangeLog 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -1,5 +1,44 @@
</span><span class="cx"> 2016-02-15 Ryosuke Niwa <rniwa@webkit.org>
</span><span class="cx">
</span><ins>+ Extract the code specific to v2 UI out of shared statistics.js
+ https://bugs.webkit.org/show_bug.cgi?id=154277
+
+ Reviewed by Chris Dumez.
+
+ Extracted statistics-strategies.js out of statistics.js for v2 UI and detect-changes.js. The intent is to
+ deprecate this file once we implement refined statistics tools in v3 UI and adopt it in detect-changes.js.
+
+ * public/shared/statistics.js:
+ (Statistics.movingAverage): Extracted from the "Simple Moving Average" strategy.
+ (Statistics.cumultaiveMovingAverage): Extracted from the "Cumulative Moving Average" strategy.
+ (Statistics.exponentialMovingAverage): Extracted from the "Exponential Moving Average" strategy.
+ Use a temporary "movingAverage" to keep the last moving average instead of relying on the previous
+ entry in "averages" array to avoid special casing an array of length 1 and starting the loop at i = 1.
+ (Statistics.segmentTimeSeriesGreedyWithStudentsTTest): Extracted from "Segmentation: Recursive t-test"
+ strategy. Don't create the list of averages to match segmentTimeSeriesByMaximizingSchwarzCriterion here.
+ It's done in newly added averagesFromSegments.
+ (Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Extracted from
+ "Segmentation: Schwarz criterion" strategy.
+ (.recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent): Just store the start index to match
+ * public/v2/app.js:
+ (App.Pane.updateStatisticsTools):
+ (App.Pane._computeMovingAverageAndOutliers):
+ * public/v2/data.js:
+ * public/v2/index.html:
+ * public/v2/statistics-strategies.js: Added.
+ (StatisticsStrategies.MovingAverageStrategies): Added.
+ (averagesFromSegments): Extracted from "Segmentation: Schwarz criterion" strategy. Now used by both
+ "Segmentation: Recursive t-test" and "Segmentation: Schwarz criterion" strategies.
+ (StatisticsStrategies.EnvelopingStrategies): Moved from Statistics.EnvelopingStrategies.
+ (StatisticsStrategies.TestRangeSelectionStrategies): Moved from Statistics.TestRangeSelectionStrategies.
+ (createWesternElectricRule): Moved from statistics.js.
+ (countValuesOnSameSide): Ditto.
+ (StatisticsStrategies.executeStrategy): Moved from Statistics.executeStrategy.
+ * tools/detect-changes.js:
+ (computeRangesForTesting):
+
+2016-02-15 Ryosuke Niwa <rniwa@webkit.org>
+
</ins><span class="cx"> v1 UI and v2 UI should share statistics.js
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=154262
</span><span class="cx">
</span></span></pre></div>
<a id="trunkWebsitesperfwebkitorgpublicsharedstatisticsjs"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/public/shared/statistics.js (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/public/shared/statistics.js 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/public/shared/statistics.js 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -116,6 +116,80 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ this.movingAverage = function (values, backwardWindowSize, forwardWindowSize) {
+ var averages = new Array(values.length);
+ // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
+ for (var i = 0; i < values.length; i++) {
+ var sum = 0;
+ var count = 0;
+ for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
+ if (j >= 0 && j < values.length) {
+ sum += values[j];
+ count++;
+ }
+ }
+ averages[i] = sum / count;
+ }
+ return averages;
+ }
+
+ this.cumulativeMovingAverage = function (values) {
+ var averages = new Array(values.length);
+ var sum = 0;
+ for (var i = 0; i < values.length; i++) {
+ sum += values[i];
+ averages[i] = sum / (i + 1);
+ }
+ return averages;
+ }
+
+ this.exponentialMovingAverage = function (values, smoothingFactor) {
+ var averages = new Array(values.length);
+ var movingAverage = 0;
+ for (var i = 0; i < values.length; i++) {
+ movingAverage = smoothingFactor * values[i] + (1 - smoothingFactor) * movingAverage;
+ averages[i] = movingAverage;
+ }
+ return averages;
+ }
+
+ // The return value is the starting indices of each segment.
+ this.segmentTimeSeriesGreedyWithStudentsTTest = function (values, minLength) {
+ if (values.length < 2)
+ return [0];
+ var segments = new Array;
+ recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
+ segments.push(values.length);
+ return segments;
+ }
+
+ this.debuggingSegmentation = false;
+ this.segmentTimeSeriesByMaximizingSchwarzCriterion = function (values) {
+ if (values.length < 2)
+ return [0];
+
+ // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
+ var gridLength = 500;
+ var totalSegmentation = [0];
+ for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
+ var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
+ var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);
+
+ if (Statistics.debuggingSegmentation)
+ console.log('grid=' + gridCount, segmentation);
+
+ for (var i = 1; i < segmentation.length - 1; i++)
+ totalSegmentation.push(gridCount * gridLength + segmentation[i]);
+ }
+
+ if (Statistics.debuggingSegmentation)
+ console.log('Final Segmentation', totalSegmentation);
+
+ totalSegmentation.push(values.length);
+
+ return totalSegmentation;
+ }
+
</ins><span class="cx"> function recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, length, minLength, segments) {
</span><span class="cx"> var tMax = 0;
</span><span class="cx"> var argTMax = null;
</span><span class="lines">@@ -131,7 +205,7 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> if (!tMax) {
</span><del>- segments.push(values.slice(startIndex, startIndex + length));
</del><ins>+ segments.push(startIndex);
</ins><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx"> recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, argTMax, minLength, segments);
</span><span class="lines">@@ -191,131 +265,6 @@
</span><span class="cx"> function oneSidedToTwoSidedProbability(probability) { return 2 * probability - 1; }
</span><span class="cx"> function twoSidedToOneSidedProbability(probability) { return (1 - (1 - probability) / 2); }
</span><span class="cx">
</span><del>- this.MovingAverageStrategies = [
- {
- id: 1,
- label: 'Simple Moving Average',
- parameterList: [
- {label: "Backward window size", value: 8, min: 2, step: 1},
- {label: "Forward window size", value: 4, min: 0, step: 1}
- ],
- execute: function (backwardWindowSize, forwardWindowSize, values) {
- var averages = new Array(values.length);
- // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.
- for (var i = 0; i < values.length; i++) {
- var sum = 0;
- var count = 0;
- for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {
- if (j >= 0 && j < values.length) {
- sum += values[j];
- count++;
- }
- }
- averages[i] = sum / count;
- }
- return averages;
- },
-
- },
- {
- id: 2,
- label: 'Cumulative Moving Average',
- execute: function (values) {
- var averages = new Array(values.length);
- var sum = 0;
- for (var i = 0; i < values.length; i++) {
- sum += values[i];
- averages[i] = sum / (i + 1);
- }
- return averages;
- }
- },
- {
- id: 3,
- label: 'Exponential Moving Average',
- parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
- execute: function (smoothingFactor, values) {
- if (!values.length || typeof(smoothingFactor) !== "number")
- return null;
-
- var averages = new Array(values.length);
- var movingAverage = 0;
- averages[0] = values[0];
- for (var i = 1; i < values.length; i++)
- averages[i] = smoothingFactor * values[i] + (1 - smoothingFactor) * averages[i - 1];
- return averages;
- }
- },
- {
- id: 4,
- isSegmentation: true,
- label: 'Segmentation: Recursive t-test',
- description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",
- parameterList: [{label: "Minimum segment length", value: 20, min: 5}],
- execute: function (minLength, values) {
- if (values.length < 2)
- return null;
-
- var averages = new Array(values.length);
- var segments = new Array;
- recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);
- var averageIndex = 0;
- for (var j = 0; j < segments.length; j++) {
- var values = segments[j];
- var mean = Statistics.sum(values) / values.length;
- for (var i = 0; i < values.length; i++)
- averages[averageIndex++] = mean;
- }
-
- return averages;
- }
- },
- {
- id: 5,
- isSegmentation: true,
- label: 'Segmentation: Schwarz criterion',
- description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',
- // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).
- execute: function (values) {
- if (values.length < 2)
- return null;
-
- var averages = new Array(values.length);
- var averageIndex = 0;
-
- // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).
- var gridLength = 500;
- var totalSegmentation = [0];
- for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {
- var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);
- var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);
-
- if (Statistics.debuggingSegmentation)
- console.log('grid=' + gridCount, segmentation);
-
- for (var i = 1; i < segmentation.length - 1; i++)
- totalSegmentation.push(gridCount * gridLength + segmentation[i]);
- }
-
- if (Statistics.debuggingSegmentation)
- console.log('Final Segmentation', totalSegmentation);
-
- totalSegmentation.push(values.length);
-
- for (var i = 1; i < totalSegmentation.length; i++) {
- var segment = values.slice(totalSegmentation[i - 1], totalSegmentation[i]);
- var average = Statistics.sum(segment) / segment.length;
- for (var j = 0; j < segment.length; j++)
- averages[averageIndex++] = average;
- }
-
- return averages;
- }
- },
- ];
-
- this.debuggingSegmentation = false;
-
</del><span class="cx"> function splitIntoSegmentsUntilGoodEnough(values) {
</span><span class="cx"> if (values.length < 2)
</span><span class="cx"> return [0, values.length];
</span><span class="lines">@@ -432,149 +381,8 @@
</span><span class="cx"> return this.costMatrix[from][to - from - 1];
</span><span class="cx"> }
</span><span class="cx">
</span><del>- this.EnvelopingStrategies = [
- {
- id: 100,
- label: 'Average Difference',
- description: 'The average difference between consecutive values.',
- execute: function (values, movingAverages) {
- if (values.length < 1)
- return NaN;
-
- var diff = 0;
- for (var i = 1; i < values.length; i++)
- diff += Math.abs(values[i] - values[i - 1]);
-
- return diff / values.length;
- }
- },
- {
- id: 101,
- label: 'Moving Average Standard Deviation',
- description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
- execute: function (values, movingAverages) {
- if (values.length < 1)
- return NaN;
-
- var diffSquareSum = 0;
- for (var i = 1; i < values.length; i++) {
- var diff = (values[i] - movingAverages[i]);
- diffSquareSum += diff * diff;
- }
-
- return Math.sqrt(diffSquareSum / (values.length - 1));
- }
- },
- ];
-
</del><span class="cx"> this.debuggingTestingRangeNomination = false;
</span><span class="cx">
</span><del>- this.TestRangeSelectionStrategies = [
- {
- id: 301,
- label: "t-test 99% significance",
- execute: function (values, segmentedValues) {
- if (!values.length)
- return [];
-
- var previousMean = segmentedValues[0];
- var selectedRanges = new Array;
- for (var i = 1; i < segmentedValues.length; i++) {
- var currentMean = segmentedValues[i];
- if (currentMean == previousMean)
- continue;
- var found = false;
- for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {
- if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)
- break;
- var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i, 0.98);
- if (result.significantlyDifferent) {
- selectedRanges.push([leftEdge, rightEdge - 1]);
- found = true;
- break;
- }
- }
- if (!found && Statistics.debuggingTestingRangeNomination)
- console.log('Failed to find a testing range at', i, 'changing from', previousMean, 'to', currentMean);
- previousMean = currentMean;
- }
- return selectedRanges;
- }
- }
- ];
-
- function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
- return function (values, movingAverages, deviation) {
- var results = new Array(values.length);
- var limit = limitFactor * deviation;
- for (var i = 0; i < values.length; i++)
- results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
- return results;
- }
- }
-
- function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
- var valuesAboveLimit = 0;
- var valuesBelowLimit = 0;
- var center = movingAverages[startIndex];
- for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
- var diff = values[i] - center;
- valuesAboveLimit += (diff > limit);
- valuesBelowLimit += (diff < -limit);
- }
- return Math.max(valuesAboveLimit, valuesBelowLimit);
- }
-
- this.AnomalyDetectionStrategy = [
- // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
- {
- id: 200,
- label: 'Western Electric: any point beyond 3σ',
- description: 'Any single point falls outside 3σ limit from the moving average',
- execute: createWesternElectricRule(1, 1, 3),
- },
- {
- id: 201,
- label: 'Western Electric: 2/3 points beyond 2σ',
- description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
- execute: createWesternElectricRule(3, 2, 2),
- },
- {
- id: 202,
- label: 'Western Electric: 4/5 points beyond σ',
- description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
- execute: createWesternElectricRule(5, 4, 1),
- },
- {
- id: 203,
- label: 'Western Electric: 9 points on same side',
- description: 'Nine consecutive points on the same side of the moving average',
- execute: createWesternElectricRule(9, 9, 0),
- },
- {
- id: 210,
- label: 'Mozilla: t-test 5 vs. 20 before that',
- description: "Use student's t-test to determine whether the mean of the last five data points differs from the mean of the twenty values before that",
- execute: function (values, movingAverages, deviation) {
- var results = new Array(values.length);
- var p = false;
- for (var i = 20; i < values.length - 5; i++)
- results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;
- return results;
- }
- },
- ]
-
- this.executeStrategy = function (strategy, rawValues, additionalArguments)
- {
- var parameters = (strategy.parameterList || []).map(function (param) {
- var parsed = parseFloat(param.value);
- return Math.min(param.max || Infinity, Math.max(param.min || -Infinity, isNaN(parsed) ? 0 : parsed));
- });
- parameters.push(rawValues);
- return strategy.execute.apply(strategy, parameters.concat(additionalArguments));
- };
-
</del><span class="cx"> })();
</span><span class="cx">
</span><span class="cx"> if (typeof module != 'undefined') {
</span></span></pre></div>
<a id="trunkWebsitesperfwebkitorgpublicv2appjs"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/public/v2/app.js (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/public/v2/app.js 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/public/v2/app.js 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -547,19 +547,19 @@
</span><span class="cx"> }.property('chartData'),
</span><span class="cx"> updateStatisticsTools: function ()
</span><span class="cx"> {
</span><del>- var movingAverageStrategies = Statistics.MovingAverageStrategies.map(this._cloneStrategy.bind(this));
</del><ins>+ var movingAverageStrategies = StatisticsStrategies.MovingAverageStrategies.map(this._cloneStrategy.bind(this));
</ins><span class="cx"> this.set('movingAverageStrategies', [{label: 'None'}].concat(movingAverageStrategies));
</span><span class="cx"> this.set('chosenMovingAverageStrategy', this._configureStrategy(movingAverageStrategies, this.get('movingAverageConfig')));
</span><span class="cx">
</span><del>- var envelopingStrategies = Statistics.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
</del><ins>+ var envelopingStrategies = StatisticsStrategies.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
</ins><span class="cx"> this.set('envelopingStrategies', [{label: 'None'}].concat(envelopingStrategies));
</span><span class="cx"> this.set('chosenEnvelopingStrategy', this._configureStrategy(envelopingStrategies, this.get('envelopingConfig')));
</span><span class="cx">
</span><del>- var testRangeSelectionStrategies = Statistics.TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this));
</del><ins>+ var testRangeSelectionStrategies = StatisticsStrategies.TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this));
</ins><span class="cx"> this.set('testRangeSelectionStrategies', [{label: 'None'}].concat(testRangeSelectionStrategies));
</span><span class="cx"> this.set('chosenTestRangeSelectionStrategy', this._configureStrategy(testRangeSelectionStrategies, this.get('testRangeSelectionConfig')));
</span><span class="cx">
</span><del>- var anomalyDetectionStrategies = Statistics.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
</del><ins>+ var anomalyDetectionStrategies = StatisticsStrategies.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
</ins><span class="cx"> this.set('anomalyDetectionStrategies', anomalyDetectionStrategies);
</span><span class="cx"> }.on('init'),
</span><span class="cx"> _cloneStrategy: function (strategy)
</span><span class="lines">@@ -640,21 +640,21 @@
</span><span class="cx"> if (!movingAverageIsSetByUser)
</span><span class="cx"> return null;
</span><span class="cx">
</span><del>- var movingAverageValues = Statistics.executeStrategy(movingAverageStrategy, rawValues);
</del><ins>+ var movingAverageValues = StatisticsStrategies.executeStrategy(movingAverageStrategy, rawValues);
</ins><span class="cx"> if (!movingAverageValues)
</span><span class="cx"> return null;
</span><span class="cx">
</span><span class="cx"> var testRangeCandidates = [];
</span><span class="cx"> if (movingAverageStrategy && movingAverageStrategy.isSegmentation && testRangeSelectionStrategy && testRangeSelectionStrategy.execute)
</span><del>- testRangeCandidates = Statistics.executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]);
</del><ins>+ testRangeCandidates = StatisticsStrategies.executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]);
</ins><span class="cx">
</span><span class="cx"> if (envelopingStrategy && envelopingStrategy.execute) {
</span><del>- var envelopeDelta = Statistics.executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]);
</del><ins>+ var envelopeDelta = StatisticsStrategies.executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]);
</ins><span class="cx"> var anomalies = {};
</span><span class="cx"> if (anomalyDetectionStrategies.length) {
</span><span class="cx"> var isAnomalyArray = new Array(currentTimeSeriesData.length);
</span><span class="cx"> for (var strategy of anomalyDetectionStrategies) {
</span><del>- var anomalyLengths = Statistics.executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]);
</del><ins>+ var anomalyLengths = StatisticsStrategies.executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]);
</ins><span class="cx"> for (var i = 0; i < currentTimeSeriesData.length; i++)
</span><span class="cx"> isAnomalyArray[i] = isAnomalyArray[i] || anomalyLengths[i];
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkWebsitesperfwebkitorgpublicv2datajs"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/public/v2/data.js (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/public/v2/data.js 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/public/v2/data.js 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -557,7 +557,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (typeof module != 'undefined') {
</span><del>- Statistics = require('./js/statistics.js');
</del><ins>+ Statistics = require('../shared/statistics.js');
</ins><span class="cx"> module.exports.Measurement = Measurement;
</span><span class="cx"> module.exports.RunsData = RunsData;
</span><span class="cx"> module.exports.TimeSeries = TimeSeries;
</span></span></pre></div>
<a id="trunkWebsitesperfwebkitorgpublicv2indexhtml"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/public/v2/index.html (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/public/v2/index.html 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/public/v2/index.html 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -17,6 +17,7 @@
</span><span class="cx"> <script src="js/ember-data.js" defer></script>
</span><span class="cx"> <script src="js/d3/d3.min.js" defer></script>
</span><span class="cx"> <script src="../shared/statistics.js" defer></script>
</span><ins>+ <script src="statistics-strategies.js" defer></script>
</ins><span class="cx"> <script src="data.js" defer></script>
</span><span class="cx"> <script src="app.js" defer></script>
</span><span class="cx"> <script src="manifest.js" defer></script>
</span></span></pre></div>
<a id="trunkWebsitesperfwebkitorgpublicv2statisticsstrategiesjs"></a>
<div class="addfile"><h4>Added: trunk/Websites/perf.webkit.org/public/v2/statistics-strategies.js (0 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/public/v2/statistics-strategies.js (rev 0)
+++ trunk/Websites/perf.webkit.org/public/v2/statistics-strategies.js 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -0,0 +1,217 @@
</span><ins>+
+var StatisticsStrategies = {};
+
+(function () {
+
+StatisticsStrategies.MovingAverageStrategies = [
+ {
+ id: 1,
+ label: 'Simple Moving Average',
+ parameterList: [
+ {label: "Backward window size", value: 8, min: 2, step: 1},
+ {label: "Forward window size", value: 4, min: 0, step: 1}
+ ],
+ execute: function (backwardWindowSize, forwardWindowSize, values) {
+ return Statistics.movingAverage(values, backwardWindowSize, forwardWindowSize);
+ },
+ },
+ {
+ id: 2,
+ label: 'Cumulative Moving Average',
+ execute: Statistics.cumulativeMovingAverage,
+ },
+ {
+ id: 3,
+ label: 'Exponential Moving Average',
+ parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],
+ execute: function (smoothingFactor, values) {
+ if (!values.length || typeof(smoothingFactor) !== "number")
+ return null;
+ return Statistics.exponentialMovingAverage(values, smoothingFactor);
+ }
+ },
+ {
+ id: 4,
+ isSegmentation: true,
+ label: 'Segmentation: Recursive t-test',
+ description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",
+ parameterList: [{label: "Minimum segment length", value: 20, min: 5}],
+ execute: function (minLength, values) {
+ return averagesFromSegments(values, Statistics.segmentTimeSeriesGreedyWithStudentsTTest(values, minLength));
+ }
+ },
+ {
+ id: 5,
+ isSegmentation: true,
+ label: 'Segmentation: Schwarz criterion',
+ description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',
+ // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).
+ execute: function (values) {
+ return averagesFromSegments(values, Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion(values));
+ }
+ },
+];
+
+function averagesFromSegments(values, segmentStartIndices) {
+ var averages = new Array(values.length);
+ var averageIndex = 0;
+ for (var i = 0; i < segmentStartIndices.length; i++) {
+ var segment = values.slice(segmentStartIndices[i - 1], segmentStartIndices[i]);
+ var average = Statistics.sum(segment) / segment.length;
+ for (var j = 0; j < segment.length; j++)
+ averages[averageIndex++] = average;
+ }
+ return averages;
+}
+
+
+StatisticsStrategies.EnvelopingStrategies = [
+ {
+ id: 100,
+ label: 'Average Difference',
+ description: 'The average difference between consecutive values.',
+ execute: function (values, movingAverages) {
+ if (values.length < 1)
+ return NaN;
+
+ var diff = 0;
+ for (var i = 1; i < values.length; i++)
+ diff += Math.abs(values[i] - values[i - 1]);
+
+ return diff / values.length;
+ }
+ },
+ {
+ id: 101,
+ label: 'Moving Average Standard Deviation',
+ description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',
+ execute: function (values, movingAverages) {
+ if (values.length < 1)
+ return NaN;
+
+ var diffSquareSum = 0;
+ for (var i = 1; i < values.length; i++) {
+ var diff = (values[i] - movingAverages[i]);
+ diffSquareSum += diff * diff;
+ }
+
+ return Math.sqrt(diffSquareSum / (values.length - 1));
+ }
+ },
+];
+
+
+StatisticsStrategies.TestRangeSelectionStrategies = [
+ {
+ id: 301,
+ label: "t-test 99% significance",
+ execute: function (values, segmentedValues) {
+ if (!values.length)
+ return [];
+
+ var previousMean = segmentedValues[0];
+ var selectedRanges = new Array;
+ for (var i = 1; i < segmentedValues.length; i++) {
+ var currentMean = segmentedValues[i];
+ if (currentMean == previousMean)
+ continue;
+ var found = false;
+ for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {
+ if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)
+ break;
+ var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i, 0.98);
+ if (result.significantlyDifferent) {
+ selectedRanges.push([leftEdge, rightEdge - 1]);
+ found = true;
+ break;
+ }
+ }
+ if (!found && Statistics.debuggingTestingRangeNomination)
+ console.log('Failed to find a testing range at', i, 'changing from', previousMean, 'to', currentMean);
+ previousMean = currentMean;
+ }
+ return selectedRanges;
+ }
+ }
+];
+
+
+
+function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
+ return function (values, movingAverages, deviation) {
+ var results = new Array(values.length);
+ var limit = limitFactor * deviation;
+ for (var i = 0; i < values.length; i++)
+ results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
+ return results;
+ }
+}
+
+function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
+ var valuesAboveLimit = 0;
+ var valuesBelowLimit = 0;
+ var center = movingAverages[startIndex];
+ for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
+ var diff = values[i] - center;
+ valuesAboveLimit += (diff > limit);
+ valuesBelowLimit += (diff < -limit);
+ }
+ return Math.max(valuesAboveLimit, valuesBelowLimit);
+}
+
+StatisticsStrategies.AnomalyDetectionStrategy = [
+ // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
+ {
+ id: 200,
+ label: 'Western Electric: any point beyond 3σ',
+ description: 'Any single point falls outside 3σ limit from the moving average',
+ execute: createWesternElectricRule(1, 1, 3),
+ },
+ {
+ id: 201,
+ label: 'Western Electric: 2/3 points beyond 2σ',
+ description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
+ execute: createWesternElectricRule(3, 2, 2),
+ },
+ {
+ id: 202,
+ label: 'Western Electric: 4/5 points beyond σ',
+ description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
+ execute: createWesternElectricRule(5, 4, 1),
+ },
+ {
+ id: 203,
+ label: 'Western Electric: 9 points on same side',
+ description: 'Nine consecutive points on the same side of the moving average',
+ execute: createWesternElectricRule(9, 9, 0),
+ },
+ {
+ id: 210,
+ label: 'Mozilla: t-test 5 vs. 20 before that',
+ description: "Use student's t-test to determine whether the mean of the last five data points differs from the mean of the twenty values before that",
+ execute: function (values, movingAverages, deviation) {
+ var results = new Array(values.length);
+ var p = false;
+ for (var i = 20; i < values.length - 5; i++)
+ results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;
+ return results;
+ }
+ },
+]
+
+StatisticsStrategies.executeStrategy = function (strategy, rawValues, additionalArguments)
+{
+ var parameters = (strategy.parameterList || []).map(function (param) {
+ var parsed = parseFloat(param.value);
+ return Math.min(param.max || Infinity, Math.max(param.min || -Infinity, isNaN(parsed) ? 0 : parsed));
+ });
+ parameters.push(rawValues);
+ return strategy.execute.apply(strategy, parameters.concat(additionalArguments));
+};
+
+})();
+
+if (typeof module != 'undefined') {
+ for (var key in StatisticsStrategies)
+ module.exports[key] = StatisticsStrategies[key];
+}
</ins></span></pre></div>
<a id="trunkWebsitesperfwebkitorgtoolsdetectchangesjs"></a>
<div class="modfile"><h4>Modified: trunk/Websites/perf.webkit.org/tools/detect-changes.js (196662 => 196663)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Websites/perf.webkit.org/tools/detect-changes.js 2016-02-16 23:13:18 UTC (rev 196662)
+++ trunk/Websites/perf.webkit.org/tools/detect-changes.js 2016-02-16 23:16:25 UTC (rev 196663)
</span><span class="lines">@@ -6,6 +6,7 @@
</span><span class="cx"> var data = require('../public/v2/data.js');
</span><span class="cx"> var RunsData = data.RunsData;
</span><span class="cx"> var Statistics = require('../public/shared/statistics.js');
</span><ins>+var StatisticsStrategies = require('../public/v2/statistics-strategies.js');
</ins><span class="cx">
</span><span class="cx"> // FIXME: We shouldn't use a global variable like this.
</span><span class="cx"> var settings;
</span><span class="lines">@@ -172,13 +173,13 @@
</span><span class="cx"> {
</span><span class="cx"> // FIXME: Store the segmentation strategy on the server side.
</span><span class="cx"> // FIXME: Configure each strategy.
</span><del>- var segmentationStrategy = findStrategyByLabel(Statistics.MovingAverageStrategies, strategies.segmentation.label);
</del><ins>+ var segmentationStrategy = findStrategyByLabel(StatisticsStrategies.MovingAverageStrategies, strategies.segmentation.label);
</ins><span class="cx"> if (!segmentationStrategy) {
</span><span class="cx"> console.error('Failed to find the segmentation strategy: ' + strategies.segmentation.label);
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- var testRangeStrategy = findStrategyByLabel(Statistics.TestRangeSelectionStrategies, strategies.testRange.label);
</del><ins>+ var testRangeStrategy = findStrategyByLabel(StatisticsStrategies.TestRangeSelectionStrategies, strategies.testRange.label);
</ins><span class="cx"> if (!testRangeStrategy) {
</span><span class="cx"> console.error('Failed to find the test range selection strategy: ' + strategies.testRange.label);
</span><span class="cx"> return;
</span><span class="lines">@@ -204,9 +205,9 @@
</span><span class="cx"> var currentTimeSeries = results[0].timeSeriesByCommitTime();
</span><span class="cx"> var analysisTasks = results[1];
</span><span class="cx"> var rawValues = currentTimeSeries.rawValues();
</span><del>- var segmentedValues = Statistics.executeStrategy(segmentationStrategy, rawValues);
</del><ins>+ var segmentedValues = StatisticsStrategies.executeStrategy(segmentationStrategy, rawValues);
</ins><span class="cx">
</span><del>- var ranges = Statistics.executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) {
</del><ins>+ var ranges = StatisticsStrategies.executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) {
</ins><span class="cx"> var startPoint = currentTimeSeries.findPointByIndex(range[0]);
</span><span class="cx"> var endPoint = currentTimeSeries.findPointByIndex(range[1]);
</span><span class="cx"> return {
</span></span></pre>
</div>
</div>
</body>
</html>