+2015-04-02 Ryosuke Niwa <rniwa@webkit.org>
+
+ Perf dashboard should have UI to test out anomaly detection strategies
+ https://bugs.webkit.org/show_bug.cgi?id=143290
+
+ Reviewed by Benjamin Poulain.
+
+ Added the UI to select anomaly detection strategies. The detected anomalies are highlighted in the graph.
+
+ Implemented the Western Electric Rules 1 through 4 in http://en.wikipedia.org/wiki/Western_Electric_rules
+ as well as Welch's t-test that compares the last five points to the prior twenty points.
+
+ The latter is what Mozilla uses (or at least did in the past) to detect performance regressions on their
+ performance tests although they compare medians instead of means.
+
+ All of these strategies don't quite work for us since our data points are too noisy but this is a good start.
+
+ * public/v2/app.js:
+ (App.Pane.updateStatisticsTools): Clone anomaly detection strategies.
+ (App.Pane._updateMovingAverageAndEnvelope): Highlight anomalies detected by the enabled strategies.
+ (App.Pane._movingAverageOrEnvelopeStrategyDidChange): Observe changes to anomaly detection strategies.
+ (App.Pane._computeMovingAverageAndOutliers): Detect anomalies by each strategy and aggregate results.
+ Only report the first data point when multiple consecutive data points are detected as anomalies.
+ * public/v2/chart-pane.css: Updated styles.
+ * public/v2/index.html: Added the pane for selecting anomaly detection strategies.
+ * public/v2/js/statistics.js:
+ (Statistics.testWelchsT): Added. Implements Welch's t-test.
+ (.sampleMeanAndVarianceForValues): Added.
+ (.createWesternElectricRule): Added.
+ (.countValuesOnSameSide): Added.
+ (Statistics.AnomalyDetectionStrategy): Added.
+
2015-03-31 Ryosuke Niwa <rniwa@webkit.org>
REGRESSION: Searching commits can highlight wrong data points
var envelopingStrategies = Statistics.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
this.set('envelopingStrategies', [{label: 'None'}].concat(envelopingStrategies));
this.set('chosenEnvelopingStrategy', this._configureStrategy(envelopingStrategies, this.get('envelopingConfig')));
+
+ var anomalyDetectionStrategies = Statistics.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
+ this.set('anomalyDetectionStrategies', anomalyDetectionStrategies);
}.on('init'),
_cloneStrategy: function (strategy)
{
var envelopingStrategy = this.get('chosenEnvelopingStrategy');
this._updateStrategyConfigIfNeeded(envelopingStrategy, 'envelopingConfig');
-
- chartData.movingAverage = this._computeMovingAverageAndOutliers(chartData, movingAverageStrategy, envelopingStrategy);
+
+ var anomalyDetectionStrategies = this.get('anomalyDetectionStrategies').filterBy('enabled');
+ var anomalies = {};
+ chartData.movingAverage = this._computeMovingAverageAndOutliers(chartData, movingAverageStrategy, envelopingStrategy, anomalyDetectionStrategies, anomalies);
+ this.set('highlightedItems', anomalies);
},
_movingAverageOrEnvelopeStrategyDidChange: function () {
this._updateMovingAverageAndEnvelope();
this.set('chartData', newChartData);
}.observes('chosenMovingAverageStrategy', 'chosenMovingAverageStrategy.parameterList.@each.value',
- 'chosenEnvelopingStrategy', 'chosenEnvelopingStrategy.parameterList.@each.value'),
- _computeMovingAverageAndOutliers: function (chartData, movingAverageStrategy, envelopingStrategy)
+ 'chosenEnvelopingStrategy', 'chosenEnvelopingStrategy.parameterList.@each.value',
+ 'anomalyDetectionStrategies.@each.enabled'),
+ _computeMovingAverageAndOutliers: function (chartData, movingAverageStrategy, envelopingStrategy, anomalyDetectionStrategies, anomalies)
{
var currentTimeSeriesData = chartData.current.series();
var movingAverageIsSetByUser = movingAverageStrategy && movingAverageStrategy.execute;
if (!envelopeIsSetByUser)
envelopeDelta = null;
+ var isAnomalyArray = new Array(currentTimeSeriesData.length);
+ for (var strategy of anomalyDetectionStrategies) {
+ var anomalyLengths = this._executeStrategy(strategy, currentTimeSeriesData, [movingAverageValues, envelopeDelta]);
+ for (var i = 0; i < currentTimeSeriesData.length; i++)
+ isAnomalyArray[i] = isAnomalyArray[i] || anomalyLengths[i];
+ }
+ for (var i = 0; i < isAnomalyArray.length; i++) {
+ if (!isAnomalyArray[i])
+ continue;
+ anomalies[currentTimeSeriesData[i].measurement.id()] = true;
+ while (isAnomalyArray[i] && i < isAnomalyArray.length)
+ ++i;
+ }
+
if (movingAverageIsSetByUser) {
return new TimeSeries(currentTimeSeriesData.map(function (point, index) {
var value = movingAverageValues[index];
return [mean - delta, mean + delta];
}
+ // Welch's t-test (http://en.wikipedia.org/wiki/Welch%27s_t_test)
+ this.testWelchsT = function (values1, values2, probability) {
+ var stat1 = sampleMeanAndVarianceForValues(values1);
+ var stat2 = sampleMeanAndVarianceForValues(values2);
+ var sumOfSampleVarianceOverSampleSize = stat1.variance / stat1.size + stat2.variance / stat2.size;
+ var t = (stat1.mean - stat2.mean) / Math.sqrt(sumOfSampleVarianceOverSampleSize);
+
+ // http://en.wikipedia.org/wiki/Welch–Satterthwaite_equation
+ var degreesOfFreedom = sumOfSampleVarianceOverSampleSize * sumOfSampleVarianceOverSampleSize
+ / (stat1.variance * stat1.variance / stat1.size / stat1.size / stat1.degreesOfFreedom
+ + stat2.variance * stat2.variance / stat2.size / stat2.size / stat2.degreesOfFreedom);
+
+ // They're different beyond the confidence interval of the specified probability.
+ return Math.abs(t) > tDistributionQuantiles[probability || 0.9][Math.round(degreesOfFreedom - 1)];
+ }
+
+ function sampleMeanAndVarianceForValues(values) {
+ var sum = Statistics.sum(values);
+ var squareSum = Statistics.squareSum(values);
+ var sampleMean = sum / values.length;
+ // FIXME: Maybe we should be using the biased sample variance.
+ var unbiasedSampleVariance = (squareSum - sum * sum / values.length) / (values.length - 1);
+ return {
+ mean: sampleMean,
+ variance: unbiasedSampleVariance,
+ size: values.length,
+ degreesOfFreedom: values.length - 1,
+ }
+ }
+
+ // One-sided t-distribution.
var tDistributionQuantiles = {
0.9: [
3.077684, 1.885618, 1.637744, 1.533206, 1.475884, 1.439756, 1.414924, 1.396815, 1.383029, 1.372184,
}
},
];
+
+ 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);
+ }
+ window.countValuesOnSameSide = countValuesOnSameSide;
+
+ 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.99) ? 5 : 0;
+ return results;
+ }
+ },
+ ]
+
})();
if (typeof module != 'undefined') {
git://git.webkit.org / WebKit-https.git / commitdiff