segmentTimeSeriesByMaximizingSchwarzCriterion returns a bogus result on empty charts
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 5 Aug 2016 20:22:52 +0000 (20:22 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 5 Aug 2016 20:22:52 +0000 (20:22 +0000)
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@204190 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Websites/perf.webkit.org/ChangeLog
Websites/perf.webkit.org/public/shared/statistics.js
Websites/perf.webkit.org/unit-tests/statistics-tests.js

index e6501db..72bc7c8 100644 (file)
@@ -1,5 +1,28 @@
 2016-08-05  Ryosuke Niwa  <rniwa@webkit.org>
 
+        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  <rniwa@webkit.org>
+
         Perf dashboard sometimes tries to fetch a non-existent measurement-set JSON
         https://bugs.webkit.org/show_bug.cgi?id=160577
 
index 72215c5..58b7c16 100644 (file)
@@ -174,9 +174,6 @@ var Statistics = new (function () {
 
     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 @@ var Statistics = new (function () {
         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,6 +344,13 @@ var Statistics = new (function () {
                 }
             }
         }
+    }
+
+    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');
@@ -393,8 +406,6 @@ var Statistics = new (function () {
         return this.costMatrix[from][to - from - 1];
     }
 
-    this.debuggingTestingRangeNomination = false;
-
 })();
 
 if (typeof module != 'undefined')
index dece88e..161ecbc 100644 (file)
@@ -355,6 +355,11 @@ describe('Statistics', function () {
     });
 
     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]);