Changeset 196663 in webkit
- Timestamp:
- Feb 16, 2016 3:16:25 PM (8 years ago)
- Location:
- trunk/Websites/perf.webkit.org
- Files:
-
- 1 added
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Websites/perf.webkit.org/ChangeLog
r196605 r196663 1 2016-02-15 Ryosuke Niwa <rniwa@webkit.org> 2 3 Extract the code specific to v2 UI out of shared statistics.js 4 https://bugs.webkit.org/show_bug.cgi?id=154277 5 6 Reviewed by Chris Dumez. 7 8 Extracted statistics-strategies.js out of statistics.js for v2 UI and detect-changes.js. The intent is to 9 deprecate this file once we implement refined statistics tools in v3 UI and adopt it in detect-changes.js. 10 11 * public/shared/statistics.js: 12 (Statistics.movingAverage): Extracted from the "Simple Moving Average" strategy. 13 (Statistics.cumultaiveMovingAverage): Extracted from the "Cumulative Moving Average" strategy. 14 (Statistics.exponentialMovingAverage): Extracted from the "Exponential Moving Average" strategy. 15 Use a temporary "movingAverage" to keep the last moving average instead of relying on the previous 16 entry in "averages" array to avoid special casing an array of length 1 and starting the loop at i = 1. 17 (Statistics.segmentTimeSeriesGreedyWithStudentsTTest): Extracted from "Segmentation: Recursive t-test" 18 strategy. Don't create the list of averages to match segmentTimeSeriesByMaximizingSchwarzCriterion here. 19 It's done in newly added averagesFromSegments. 20 (Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Extracted from 21 "Segmentation: Schwarz criterion" strategy. 22 (.recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent): Just store the start index to match 23 * public/v2/app.js: 24 (App.Pane.updateStatisticsTools): 25 (App.Pane._computeMovingAverageAndOutliers): 26 * public/v2/data.js: 27 * public/v2/index.html: 28 * public/v2/statistics-strategies.js: Added. 29 (StatisticsStrategies.MovingAverageStrategies): Added. 30 (averagesFromSegments): Extracted from "Segmentation: Schwarz criterion" strategy. Now used by both 31 "Segmentation: Recursive t-test" and "Segmentation: Schwarz criterion" strategies. 32 (StatisticsStrategies.EnvelopingStrategies): Moved from Statistics.EnvelopingStrategies. 33 (StatisticsStrategies.TestRangeSelectionStrategies): Moved from Statistics.TestRangeSelectionStrategies. 34 (createWesternElectricRule): Moved from statistics.js. 35 (countValuesOnSameSide): Ditto. 36 (StatisticsStrategies.executeStrategy): Moved from Statistics.executeStrategy. 37 * tools/detect-changes.js: 38 (computeRangesForTesting): 39 1 40 2016-02-15 Ryosuke Niwa <rniwa@webkit.org> 2 41 -
trunk/Websites/perf.webkit.org/public/shared/statistics.js
r196605 r196663 117 117 } 118 118 119 this.movingAverage = function (values, backwardWindowSize, forwardWindowSize) { 120 var averages = new Array(values.length); 121 // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors. 122 for (var i = 0; i < values.length; i++) { 123 var sum = 0; 124 var count = 0; 125 for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) { 126 if (j >= 0 && j < values.length) { 127 sum += values[j]; 128 count++; 129 } 130 } 131 averages[i] = sum / count; 132 } 133 return averages; 134 } 135 136 this.cumulativeMovingAverage = function (values) { 137 var averages = new Array(values.length); 138 var sum = 0; 139 for (var i = 0; i < values.length; i++) { 140 sum += values[i]; 141 averages[i] = sum / (i + 1); 142 } 143 return averages; 144 } 145 146 this.exponentialMovingAverage = function (values, smoothingFactor) { 147 var averages = new Array(values.length); 148 var movingAverage = 0; 149 for (var i = 0; i < values.length; i++) { 150 movingAverage = smoothingFactor * values[i] + (1 - smoothingFactor) * movingAverage; 151 averages[i] = movingAverage; 152 } 153 return averages; 154 } 155 156 // The return value is the starting indices of each segment. 157 this.segmentTimeSeriesGreedyWithStudentsTTest = function (values, minLength) { 158 if (values.length < 2) 159 return [0]; 160 var segments = new Array; 161 recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments); 162 segments.push(values.length); 163 return segments; 164 } 165 166 this.debuggingSegmentation = false; 167 this.segmentTimeSeriesByMaximizingSchwarzCriterion = function (values) { 168 if (values.length < 2) 169 return [0]; 170 171 // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2). 172 var gridLength = 500; 173 var totalSegmentation = [0]; 174 for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) { 175 var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength); 176 var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues); 177 178 if (Statistics.debuggingSegmentation) 179 console.log('grid=' + gridCount, segmentation); 180 181 for (var i = 1; i < segmentation.length - 1; i++) 182 totalSegmentation.push(gridCount * gridLength + segmentation[i]); 183 } 184 185 if (Statistics.debuggingSegmentation) 186 console.log('Final Segmentation', totalSegmentation); 187 188 totalSegmentation.push(values.length); 189 190 return totalSegmentation; 191 } 192 119 193 function recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, startIndex, length, minLength, segments) { 120 194 var tMax = 0; … … 132 206 } 133 207 if (!tMax) { 134 segments.push( values.slice(startIndex, startIndex + length));208 segments.push(startIndex); 135 209 return; 136 210 } … … 191 265 function oneSidedToTwoSidedProbability(probability) { return 2 * probability - 1; } 192 266 function twoSidedToOneSidedProbability(probability) { return (1 - (1 - probability) / 2); } 193 194 this.MovingAverageStrategies = [195 {196 id: 1,197 label: 'Simple Moving Average',198 parameterList: [199 {label: "Backward window size", value: 8, min: 2, step: 1},200 {label: "Forward window size", value: 4, min: 0, step: 1}201 ],202 execute: function (backwardWindowSize, forwardWindowSize, values) {203 var averages = new Array(values.length);204 // We use naive O(n^2) algorithm for simplicy as well as to avoid accumulating round-off errors.205 for (var i = 0; i < values.length; i++) {206 var sum = 0;207 var count = 0;208 for (var j = i - backwardWindowSize; j < i + backwardWindowSize; j++) {209 if (j >= 0 && j < values.length) {210 sum += values[j];211 count++;212 }213 }214 averages[i] = sum / count;215 }216 return averages;217 },218 219 },220 {221 id: 2,222 label: 'Cumulative Moving Average',223 execute: function (values) {224 var averages = new Array(values.length);225 var sum = 0;226 for (var i = 0; i < values.length; i++) {227 sum += values[i];228 averages[i] = sum / (i + 1);229 }230 return averages;231 }232 },233 {234 id: 3,235 label: 'Exponential Moving Average',236 parameterList: [{label: "Smoothing factor", value: 0.1, min: 0.001, max: 0.9}],237 execute: function (smoothingFactor, values) {238 if (!values.length || typeof(smoothingFactor) !== "number")239 return null;240 241 var averages = new Array(values.length);242 var movingAverage = 0;243 averages[0] = values[0];244 for (var i = 1; i < values.length; i++)245 averages[i] = smoothingFactor * values[i] + (1 - smoothingFactor) * averages[i - 1];246 return averages;247 }248 },249 {250 id: 4,251 isSegmentation: true,252 label: 'Segmentation: Recursive t-test',253 description: "Recursively split values into two segments if Welch's t-test detects a statistically significant difference.",254 parameterList: [{label: "Minimum segment length", value: 20, min: 5}],255 execute: function (minLength, values) {256 if (values.length < 2)257 return null;258 259 var averages = new Array(values.length);260 var segments = new Array;261 recursivelySplitIntoTwoSegmentsAtMaxTIfSignificantlyDifferent(values, 0, values.length, minLength, segments);262 var averageIndex = 0;263 for (var j = 0; j < segments.length; j++) {264 var values = segments[j];265 var mean = Statistics.sum(values) / values.length;266 for (var i = 0; i < values.length; i++)267 averages[averageIndex++] = mean;268 }269 270 return averages;271 }272 },273 {274 id: 5,275 isSegmentation: true,276 label: 'Segmentation: Schwarz criterion',277 description: 'Adaptive algorithm that maximizes the Schwarz criterion (BIC).',278 // Based on Detection of Multiple Change–Points in Multivariate Time Series by Marc Lavielle (July 2006).279 execute: function (values) {280 if (values.length < 2)281 return null;282 283 var averages = new Array(values.length);284 var averageIndex = 0;285 286 // Split the time series into grids since splitIntoSegmentsUntilGoodEnough is O(n^2).287 var gridLength = 500;288 var totalSegmentation = [0];289 for (var gridCount = 0; gridCount < Math.ceil(values.length / gridLength); gridCount++) {290 var gridValues = values.slice(gridCount * gridLength, (gridCount + 1) * gridLength);291 var segmentation = splitIntoSegmentsUntilGoodEnough(gridValues);292 293 if (Statistics.debuggingSegmentation)294 console.log('grid=' + gridCount, segmentation);295 296 for (var i = 1; i < segmentation.length - 1; i++)297 totalSegmentation.push(gridCount * gridLength + segmentation[i]);298 }299 300 if (Statistics.debuggingSegmentation)301 console.log('Final Segmentation', totalSegmentation);302 303 totalSegmentation.push(values.length);304 305 for (var i = 1; i < totalSegmentation.length; i++) {306 var segment = values.slice(totalSegmentation[i - 1], totalSegmentation[i]);307 var average = Statistics.sum(segment) / segment.length;308 for (var j = 0; j < segment.length; j++)309 averages[averageIndex++] = average;310 }311 312 return averages;313 }314 },315 ];316 317 this.debuggingSegmentation = false;318 267 319 268 function splitIntoSegmentsUntilGoodEnough(values) { … … 433 382 } 434 383 435 this.EnvelopingStrategies = [436 {437 id: 100,438 label: 'Average Difference',439 description: 'The average difference between consecutive values.',440 execute: function (values, movingAverages) {441 if (values.length < 1)442 return NaN;443 444 var diff = 0;445 for (var i = 1; i < values.length; i++)446 diff += Math.abs(values[i] - values[i - 1]);447 448 return diff / values.length;449 }450 },451 {452 id: 101,453 label: 'Moving Average Standard Deviation',454 description: 'The square root of the average deviation from the moving average with Bessel\'s correction.',455 execute: function (values, movingAverages) {456 if (values.length < 1)457 return NaN;458 459 var diffSquareSum = 0;460 for (var i = 1; i < values.length; i++) {461 var diff = (values[i] - movingAverages[i]);462 diffSquareSum += diff * diff;463 }464 465 return Math.sqrt(diffSquareSum / (values.length - 1));466 }467 },468 ];469 470 384 this.debuggingTestingRangeNomination = false; 471 472 this.TestRangeSelectionStrategies = [473 {474 id: 301,475 label: "t-test 99% significance",476 execute: function (values, segmentedValues) {477 if (!values.length)478 return [];479 480 var previousMean = segmentedValues[0];481 var selectedRanges = new Array;482 for (var i = 1; i < segmentedValues.length; i++) {483 var currentMean = segmentedValues[i];484 if (currentMean == previousMean)485 continue;486 var found = false;487 for (var leftEdge = i - 2, rightEdge = i + 2; leftEdge >= 0 && rightEdge <= values.length; leftEdge--, rightEdge++) {488 if (segmentedValues[leftEdge] != previousMean || segmentedValues[rightEdge - 1] != currentMean)489 break;490 var result = Statistics.computeWelchsT(values, leftEdge, i - leftEdge, values, i, rightEdge - i, 0.98);491 if (result.significantlyDifferent) {492 selectedRanges.push([leftEdge, rightEdge - 1]);493 found = true;494 break;495 }496 }497 if (!found && Statistics.debuggingTestingRangeNomination)498 console.log('Failed to find a testing range at', i, 'changing from', previousMean, 'to', currentMean);499 previousMean = currentMean;500 }501 return selectedRanges;502 }503 }504 ];505 506 function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {507 return function (values, movingAverages, deviation) {508 var results = new Array(values.length);509 var limit = limitFactor * deviation;510 for (var i = 0; i < values.length; i++)511 results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;512 return results;513 }514 }515 516 function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {517 var valuesAboveLimit = 0;518 var valuesBelowLimit = 0;519 var center = movingAverages[startIndex];520 for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {521 var diff = values[i] - center;522 valuesAboveLimit += (diff > limit);523 valuesBelowLimit += (diff < -limit);524 }525 return Math.max(valuesAboveLimit, valuesBelowLimit);526 }527 528 this.AnomalyDetectionStrategy = [529 // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules530 {531 id: 200,532 label: 'Western Electric: any point beyond 3σ',533 description: 'Any single point falls outside 3σ limit from the moving average',534 execute: createWesternElectricRule(1, 1, 3),535 },536 {537 id: 201,538 label: 'Western Electric: 2/3 points beyond 2σ',539 description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',540 execute: createWesternElectricRule(3, 2, 2),541 },542 {543 id: 202,544 label: 'Western Electric: 4/5 points beyond σ',545 description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',546 execute: createWesternElectricRule(5, 4, 1),547 },548 {549 id: 203,550 label: 'Western Electric: 9 points on same side',551 description: 'Nine consecutive points on the same side of the moving average',552 execute: createWesternElectricRule(9, 9, 0),553 },554 {555 id: 210,556 label: 'Mozilla: t-test 5 vs. 20 before that',557 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",558 execute: function (values, movingAverages, deviation) {559 var results = new Array(values.length);560 var p = false;561 for (var i = 20; i < values.length - 5; i++)562 results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.98) ? 5 : 0;563 return results;564 }565 },566 ]567 568 this.executeStrategy = function (strategy, rawValues, additionalArguments)569 {570 var parameters = (strategy.parameterList || []).map(function (param) {571 var parsed = parseFloat(param.value);572 return Math.min(param.max || Infinity, Math.max(param.min || -Infinity, isNaN(parsed) ? 0 : parsed));573 });574 parameters.push(rawValues);575 return strategy.execute.apply(strategy, parameters.concat(additionalArguments));576 };577 385 578 386 })(); -
trunk/Websites/perf.webkit.org/public/v2/app.js
r192817 r196663 548 548 updateStatisticsTools: function () 549 549 { 550 var movingAverageStrategies = Statistics .MovingAverageStrategies.map(this._cloneStrategy.bind(this));550 var movingAverageStrategies = StatisticsStrategies.MovingAverageStrategies.map(this._cloneStrategy.bind(this)); 551 551 this.set('movingAverageStrategies', [{label: 'None'}].concat(movingAverageStrategies)); 552 552 this.set('chosenMovingAverageStrategy', this._configureStrategy(movingAverageStrategies, this.get('movingAverageConfig'))); 553 553 554 var envelopingStrategies = Statistics .EnvelopingStrategies.map(this._cloneStrategy.bind(this));554 var envelopingStrategies = StatisticsStrategies.EnvelopingStrategies.map(this._cloneStrategy.bind(this)); 555 555 this.set('envelopingStrategies', [{label: 'None'}].concat(envelopingStrategies)); 556 556 this.set('chosenEnvelopingStrategy', this._configureStrategy(envelopingStrategies, this.get('envelopingConfig'))); 557 557 558 var testRangeSelectionStrategies = Statistics .TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this));558 var testRangeSelectionStrategies = StatisticsStrategies.TestRangeSelectionStrategies.map(this._cloneStrategy.bind(this)); 559 559 this.set('testRangeSelectionStrategies', [{label: 'None'}].concat(testRangeSelectionStrategies)); 560 560 this.set('chosenTestRangeSelectionStrategy', this._configureStrategy(testRangeSelectionStrategies, this.get('testRangeSelectionConfig'))); 561 561 562 var anomalyDetectionStrategies = Statistics .AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));562 var anomalyDetectionStrategies = StatisticsStrategies.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this)); 563 563 this.set('anomalyDetectionStrategies', anomalyDetectionStrategies); 564 564 }.on('init'), … … 641 641 return null; 642 642 643 var movingAverageValues = Statistics .executeStrategy(movingAverageStrategy, rawValues);643 var movingAverageValues = StatisticsStrategies.executeStrategy(movingAverageStrategy, rawValues); 644 644 if (!movingAverageValues) 645 645 return null; … … 647 647 var testRangeCandidates = []; 648 648 if (movingAverageStrategy && movingAverageStrategy.isSegmentation && testRangeSelectionStrategy && testRangeSelectionStrategy.execute) 649 testRangeCandidates = Statistics .executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]);649 testRangeCandidates = StatisticsStrategies.executeStrategy(testRangeSelectionStrategy, rawValues, [movingAverageValues]); 650 650 651 651 if (envelopingStrategy && envelopingStrategy.execute) { 652 var envelopeDelta = Statistics .executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]);652 var envelopeDelta = StatisticsStrategies.executeStrategy(envelopingStrategy, rawValues, [movingAverageValues]); 653 653 var anomalies = {}; 654 654 if (anomalyDetectionStrategies.length) { 655 655 var isAnomalyArray = new Array(currentTimeSeriesData.length); 656 656 for (var strategy of anomalyDetectionStrategies) { 657 var anomalyLengths = Statistics .executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]);657 var anomalyLengths = StatisticsStrategies.executeStrategy(strategy, rawValues, [movingAverageValues, envelopeDelta]); 658 658 for (var i = 0; i < currentTimeSeriesData.length; i++) 659 659 isAnomalyArray[i] = isAnomalyArray[i] || anomalyLengths[i]; -
trunk/Websites/perf.webkit.org/public/v2/data.js
r194121 r196663 558 558 559 559 if (typeof module != 'undefined') { 560 Statistics = require('. /js/statistics.js');560 Statistics = require('../shared/statistics.js'); 561 561 module.exports.Measurement = Measurement; 562 562 module.exports.RunsData = RunsData; -
trunk/Websites/perf.webkit.org/public/v2/index.html
r196605 r196663 18 18 <script src="js/d3/d3.min.js" defer></script> 19 19 <script src="../shared/statistics.js" defer></script> 20 <script src="statistics-strategies.js" defer></script> 20 21 <script src="data.js" defer></script> 21 22 <script src="app.js" defer></script> -
trunk/Websites/perf.webkit.org/tools/detect-changes.js
r196605 r196663 7 7 var RunsData = data.RunsData; 8 8 var Statistics = require('../public/shared/statistics.js'); 9 var StatisticsStrategies = require('../public/v2/statistics-strategies.js'); 9 10 10 11 // FIXME: We shouldn't use a global variable like this. … … 173 174 // FIXME: Store the segmentation strategy on the server side. 174 175 // FIXME: Configure each strategy. 175 var segmentationStrategy = findStrategyByLabel(Statistics .MovingAverageStrategies, strategies.segmentation.label);176 var segmentationStrategy = findStrategyByLabel(StatisticsStrategies.MovingAverageStrategies, strategies.segmentation.label); 176 177 if (!segmentationStrategy) { 177 178 console.error('Failed to find the segmentation strategy: ' + strategies.segmentation.label); … … 179 180 } 180 181 181 var testRangeStrategy = findStrategyByLabel(Statistics .TestRangeSelectionStrategies, strategies.testRange.label);182 var testRangeStrategy = findStrategyByLabel(StatisticsStrategies.TestRangeSelectionStrategies, strategies.testRange.label); 182 183 if (!testRangeStrategy) { 183 184 console.error('Failed to find the test range selection strategy: ' + strategies.testRange.label); … … 205 206 var analysisTasks = results[1]; 206 207 var rawValues = currentTimeSeries.rawValues(); 207 var segmentedValues = Statistics .executeStrategy(segmentationStrategy, rawValues);208 209 var ranges = Statistics .executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) {208 var segmentedValues = StatisticsStrategies.executeStrategy(segmentationStrategy, rawValues); 209 210 var ranges = StatisticsStrategies.executeStrategy(testRangeStrategy, rawValues, [segmentedValues]).map(function (range) { 210 211 var startPoint = currentTimeSeries.findPointByIndex(range[0]); 211 212 var endPoint = currentTimeSeries.findPointByIndex(range[1]);
Note: See TracChangeset
for help on using the changeset viewer.