Title: [204190] trunk/Websites/perf.webkit.org
- Revision
- 204190
- Author
- [email protected]
- Date
- 2016-08-05 13:22:52 -0700 (Fri, 05 Aug 2016)
Log Message
segmentTimeSeriesByMaximizingSchwarzCriterion returns a bogus result on empty charts
https://bugs.webkit.org/show_bug.cgi?id=160575
Rubber-stamped by Chris Dumez.
The bug was caused by an early return in segmentTimeSeriesByMaximizingSchwarzCriterion.
Removed this early return as the one in splitIntoSegmentsUntilGoodEnough was sufficient.
Also factored out a few functions in findOptimalSegmentation so that they can be better
optimized in JSC's DFG and FTL tiers, and removed unused debuggingTestingRangeNomination.
* public/shared/statistics.js:
(Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Removed an early return.
(Statistics.splitIntoSegmentsUntilGoodEnough):
(.allocateCostUpperTriangularForSegmentation): Extracted from findOptimalSegmentation.
(.allocatePreviousNodeForSegmentation): Ditto.
(.findOptimalSegmentationInternal): Ditto.
(.findOptimalSegmentation):
* unit-tests/statistics-tests.js: Added a test case.
Modified Paths
Diff
Modified: trunk/Websites/perf.webkit.org/ChangeLog (204189 => 204190)
--- trunk/Websites/perf.webkit.org/ChangeLog 2016-08-05 20:21:35 UTC (rev 204189)
+++ trunk/Websites/perf.webkit.org/ChangeLog 2016-08-05 20:22:52 UTC (rev 204190)
@@ -1,5 +1,28 @@
2016-08-05 Ryosuke Niwa <[email protected]>
+ segmentTimeSeriesByMaximizingSchwarzCriterion returns a bogus result on empty charts
+ https://bugs.webkit.org/show_bug.cgi?id=160575
+
+ Rubber-stamped by Chris Dumez.
+
+ The bug was caused by an early return in segmentTimeSeriesByMaximizingSchwarzCriterion.
+ Removed this early return as the one in splitIntoSegmentsUntilGoodEnough was sufficient.
+
+ Also factored out a few functions in findOptimalSegmentation so that they can be better
+ optimized in JSC's DFG and FTL tiers, and removed unused debuggingTestingRangeNomination.
+
+ * public/shared/statistics.js:
+ (Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion): Removed an early return.
+ (Statistics.splitIntoSegmentsUntilGoodEnough):
+ (.allocateCostUpperTriangularForSegmentation): Extracted from findOptimalSegmentation.
+ (.allocatePreviousNodeForSegmentation): Ditto.
+ (.findOptimalSegmentationInternal): Ditto.
+ (.findOptimalSegmentation):
+
+ * unit-tests/statistics-tests.js: Added a test case.
+
+2016-08-05 Ryosuke Niwa <[email protected]>
+
Perf dashboard sometimes tries to fetch a non-existent measurement-set JSON
https://bugs.webkit.org/show_bug.cgi?id=160577
Modified: trunk/Websites/perf.webkit.org/public/shared/statistics.js (204189 => 204190)
--- trunk/Websites/perf.webkit.org/public/shared/statistics.js 2016-08-05 20:21:35 UTC (rev 204189)
+++ trunk/Websites/perf.webkit.org/public/shared/statistics.js 2016-08-05 20:22:52 UTC (rev 204190)
@@ -174,9 +174,6 @@
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];
@@ -308,17 +305,26 @@
return segmentation;
}
- function findOptimalSegmentation(values, costMatrix, segmentCount) {
+ function allocateCostUpperTriangularForSegmentation(values, segmentCount)
+ {
// Dynamic programming. cost[i][k] = The cost to segmenting values up to i into k segments.
var cost = new Array(values.length);
for (var segmentEnd = 0; segmentEnd < values.length; segmentEnd++)
cost[segmentEnd] = new Float32Array(segmentCount + 1);
+ return cost;
+ }
+ function allocatePreviousNodeForSegmentation(values, segmentCount)
+ {
// previousNode[i][k] = The start of the last segment in an optimal segmentation that ends at i with k segments.
var previousNode = new Array(values.length);
for (var i = 0; i < values.length; i++)
previousNode[i] = new Array(segmentCount + 1);
+ return previousNode;
+ }
+ function findOptimalSegmentationInternal(cost, previousNode, values, costMatrix, segmentCount)
+ {
cost[0] = [0]; // The cost of segmenting single value is always 0.
previousNode[0] = [-1];
for (var segmentStart = 0; segmentStart < values.length; segmentStart++) {
@@ -338,7 +344,14 @@
}
}
}
+ }
+ function findOptimalSegmentation(values, costMatrix, segmentCount) {
+ var cost = allocateCostUpperTriangularForSegmentation(values, segmentCount);
+ var previousNode = allocatePreviousNodeForSegmentation(values, segmentCount);
+
+ findOptimalSegmentationInternal(cost, previousNode, values, costMatrix, segmentCount);
+
if (Statistics.debuggingSegmentation) {
console.log('findOptimalSegmentation with', segmentCount, 'segments');
for (var end = 0; end < values.length; end++) {
@@ -393,8 +406,6 @@
return this.costMatrix[from][to - from - 1];
}
- this.debuggingTestingRangeNomination = false;
-
})();
if (typeof module != 'undefined')
Modified: trunk/Websites/perf.webkit.org/unit-tests/statistics-tests.js (204189 => 204190)
--- trunk/Websites/perf.webkit.org/unit-tests/statistics-tests.js 2016-08-05 20:21:35 UTC (rev 204189)
+++ trunk/Websites/perf.webkit.org/unit-tests/statistics-tests.js 2016-08-05 20:22:52 UTC (rev 204190)
@@ -355,6 +355,11 @@
});
describe('segmentTimeSeriesByMaximizingSchwarzCriterion', function () {
+ it('should segment time series of length 0 into a single segment', function () {
+ var values = [];
+ assert.deepEqual(Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion(values), [0, 0]);
+ });
+
it('should not segment time series of length two into two pieces', function () {
var values = [1, 2];
assert.deepEqual(Statistics.segmentTimeSeriesByMaximizingSchwarzCriterion(values), [0, 2]);
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
