New sampling algorithm shows very few points when zoomed out
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 24 Feb 2017 06:57:04 +0000 (06:57 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 24 Feb 2017 06:57:04 +0000 (06:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=168813

Reviewed by Saam Barati.

When a chart is zoomed out to a large time interval, the new sampling algorithm introduced in r212853 can
hide most of the data points because the difference between the preceding point's time and the succeeding
point's time of most points will be below the threshold we computed.

Instead, rank each data point based on the aforementioned time interval difference, and pick the first M data
points when M data points are to be shown.

This makes the new algorithm behave like our old algorithm while keeping it stable still. Note that this
algorithm still biases data points without a close neighboring point but this seems to work out in practice
because such a point tends to be an important sample anyway, and we don't have a lot of space between
data points since we aim to show about one point per pixel.

* browser-tests/index.html:
(CanvasTest.canvasContainsColor): Extracted from one of the test cases and generalized. Returns true when
the specified region of the canvas contains a specified color (alpha is optional).
* browser-tests/time-series-chart-tests.js: Added a test case for sampling. It checks that sampling happens
and that we always show some data point even when zoomed out to a large time interval.
(createChartWithSampleCluster):

* public/v3/components/interactive-time-series-chart.js:
(InteractiveTimeSeriesChart.prototype._sampleTimeSeries):
* public/v3/components/time-series-chart.js:
(TimeSeriesChart.prototype._ensureSampledTimeSeries): M, the number of data points we pick must be computed
based on the width of data points we're about to draw constrained by the canvas size. e.g. when the canvas
is only half filled, we shouldn't be showing two points per pixel in the filled region.
(TimeSeriesChart.prototype._sampleTimeSeries): Refined the algorithm. First, compute the time difference or
the rank for each N data points. Sort those ranks in descending order (in the order we prefer), and include
all data points above the M-th rank in the sample.
(TimeSeriesChart.prototype.computeTimeGrid): Revert the inadvertent change in r212935.

* public/v3/models/time-series.js:
(TimeSeriesView.prototype.filter): Fixed a bug that the indices passed onto the callback were shifted by the
starting index.
* unit-tests/time-series-tests.js: Added a test case to ensure callbacks are called with correct data points
and indices.

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

Websites/perf.webkit.org/ChangeLog
Websites/perf.webkit.org/browser-tests/index.html
Websites/perf.webkit.org/browser-tests/time-series-chart-tests.js
Websites/perf.webkit.org/public/v3/components/interactive-time-series-chart.js
Websites/perf.webkit.org/public/v3/components/time-series-chart.js
Websites/perf.webkit.org/public/v3/models/time-series.js
Websites/perf.webkit.org/unit-tests/time-series-tests.js

index 8233162..6967e13 100644 (file)
@@ -1,5 +1,48 @@
 2017-02-23  Ryosuke Niwa  <rniwa@webkit.org>
 
+        New sampling algorithm shows very few points when zoomed out
+        https://bugs.webkit.org/show_bug.cgi?id=168813
+
+        Reviewed by Saam Barati.
+
+        When a chart is zoomed out to a large time interval, the new sampling algorithm introduced in r212853 can
+        hide most of the data points because the difference between the preceding point's time and the succeeding
+        point's time of most points will be below the threshold we computed.
+
+        Instead, rank each data point based on the aforementioned time interval difference, and pick the first M data
+        points when M data points are to be shown.
+
+        This makes the new algorithm behave like our old algorithm while keeping it stable still. Note that this
+        algorithm still biases data points without a close neighboring point but this seems to work out in practice
+        because such a point tends to be an important sample anyway, and we don't have a lot of space between
+        data points since we aim to show about one point per pixel.
+
+        * browser-tests/index.html:
+        (CanvasTest.canvasContainsColor): Extracted from one of the test cases and generalized. Returns true when
+        the specified region of the canvas contains a specified color (alpha is optional).
+        * browser-tests/time-series-chart-tests.js: Added a test case for sampling. It checks that sampling happens
+        and that we always show some data point even when zoomed out to a large time interval.
+        (createChartWithSampleCluster):
+
+        * public/v3/components/interactive-time-series-chart.js:
+        (InteractiveTimeSeriesChart.prototype._sampleTimeSeries):
+        * public/v3/components/time-series-chart.js:
+        (TimeSeriesChart.prototype._ensureSampledTimeSeries): M, the number of data points we pick must be computed
+        based on the width of data points we're about to draw constrained by the canvas size. e.g. when the canvas
+        is only half filled, we shouldn't be showing two points per pixel in the filled region.
+        (TimeSeriesChart.prototype._sampleTimeSeries): Refined the algorithm. First, compute the time difference or
+        the rank for each N data points. Sort those ranks in descending order (in the order we prefer), and include
+        all data points above the M-th rank in the sample.
+        (TimeSeriesChart.prototype.computeTimeGrid): Revert the inadvertent change in r212935.
+
+        * public/v3/models/time-series.js:
+        (TimeSeriesView.prototype.filter): Fixed a bug that the indices passed onto the callback were shifted by the
+        starting index.
+        * unit-tests/time-series-tests.js: Added a test case to ensure callbacks are called with correct data points
+        and indices.
+
+2017-02-23  Ryosuke Niwa  <rniwa@webkit.org>
+
         REGRESSION(r212542): Make TimeSeriesChart.computeTimeGrid stops x-axis grid prematurely
         https://bugs.webkit.org/show_bug.cgi?id=168812
 
index 28e0045..4778a7f 100644 (file)
@@ -163,6 +163,23 @@ const CanvasTest = {
     },
 
     canvasImageData(canvas) { return canvasImageData(canvas); },
+
+    canvasContainsColor(canvas, color, rect = {})
+    {
+        const content = canvas.getContext('2d').getImageData(rect.x || 0, rect.y || 0, rect.width || canvas.width, rect.height || canvas.height);
+        let found = false;
+        const data = content.data;
+        for (let startOfPixel = 0; startOfPixel < data.length; startOfPixel += 4) {
+            let r = data[startOfPixel];
+            let g = data[startOfPixel + 1];
+            let b = data[startOfPixel + 2];
+            let a = data[startOfPixel + 3];
+            if (r == color.r && g == color.g && b == color.b && (color.a == undefined || a == color.a))
+                return true;
+        }
+        return false;
+    },
+
     expectCanvasesMatch(canvas1, canvas2) { return canvasRefTest(canvas1, canvas2, true); },
     expectCanvasesMismatch(canvas1, canvas2) { return canvasRefTest(canvas1, canvas2, false); },
 }
index d0f8b66..a36ed4d 100644 (file)
@@ -77,9 +77,11 @@ function createChartWithSampleCluster(context, chartOptions = {}, options = {})
     const chart = new TimeSeriesChart([
         {
             type: 'current',
+            lineStyle: options.lineStyle || '#666',
             measurementSet: MeasurementSet.findSet(1, 1, 0),
             interactive: options.interactive || false,
-            includeOutliers: options.includeOutliers || false
+            includeOutliers: options.includeOutliers || false,
+            sampleData: options.sampleData || false,
         }], chartOptions);
     const element = chart.element();
     element.style.width = options.width || '300px';
@@ -541,7 +543,6 @@ describe('TimeSeriesChart', () => {
 
                 expect(chart.content().querySelector('canvas')).to.be(null);
                 return waitForComponentsToRender(context).then(() => {
-                    console.log('done')
                     expect(chart.content().querySelector('canvas')).to.not.be(null);
                 });
             });
@@ -828,19 +829,50 @@ describe('TimeSeriesChart', () => {
                     CanvasTest.expectCanvasesMismatch(canvasWithoutYAxis, canvasWithYAxis1);
                     CanvasTest.expectCanvasesMismatch(canvasWithYAxis1, canvasWithYAxis2);
 
-                    let content1 = CanvasTest.canvasImageData(canvasWithYAxis1);
-                    let foundGridLine = false;
-                    for (let y = 0; y < content1.height; y++) {
-                        let endOfY = content1.width * 4 * y;
-                        let r = content1.data[endOfY - 4];
-                        let g = content1.data[endOfY - 3];
-                        let b = content1.data[endOfY - 2];
-                        if (r == 204 && g == 204 && b == 204) {
-                            foundGridLine = true;
-                            break;
-                        }
-                    }
-                    expect(foundGridLine).to.be(true);
+                    expect(CanvasTest.canvasContainsColor(canvasWithYAxis1, {r: 204, g: 204, b: 204},
+                        {x: canvasWithYAxis1.width - 1, width: 1, y: 0, height: canvasWithYAxis1.height})).to.be(true);
+                });
+            });
+        });
+
+        it('should render the sampled time series', () => {
+            const context = new BrowsingContext();
+            return context.importScripts(scripts, 'ComponentBase', 'TimeSeriesChart', 'InteractiveTimeSeriesChart', 'MeasurementSet', 'MockRemoteAPI').then(() => {
+                const chartWithoutSampling = createChartWithSampleCluster(context, {}, {lineStyle: 'rgb(0, 128, 255)', width: '100px', height: '100px', sampleData: false});
+                const chartWithSampling = createChartWithSampleCluster(context, {}, {lineStyle: 'rgb(0, 128, 255)', width: '100px', height: '100px', sampleData: true});
+
+                chartWithoutSampling.setDomain(sampleCluster.startTime, sampleCluster.endTime);
+                chartWithoutSampling.fetchMeasurementSets();
+                respondWithSampleCluster(context.symbols.MockRemoteAPI.requests[0]);
+
+                chartWithSampling.setDomain(sampleCluster.startTime, sampleCluster.endTime);
+                chartWithSampling.fetchMeasurementSets();
+
+                let canvasWithSampling;
+                let canvasWithoutSampling;
+                return waitForComponentsToRender(context).then(() => {
+                    canvasWithoutSampling = chartWithoutSampling.content().querySelector('canvas');
+                    canvasWithSampling = chartWithSampling.content().querySelector('canvas');
+
+                    CanvasTest.expectCanvasesMatch(canvasWithSampling, canvasWithoutSampling);
+                    expect(CanvasTest.canvasContainsColor(canvasWithoutSampling, {r: 0, g: 128, b: 255})).to.be(true);
+                    expect(CanvasTest.canvasContainsColor(canvasWithSampling, {r: 0, g: 128, b: 255})).to.be(true);
+
+                    const diff = sampleCluster.endTime - sampleCluster.startTime;
+                    chartWithoutSampling.setDomain(sampleCluster.startTime - 2 * diff, sampleCluster.endTime);
+                    chartWithSampling.setDomain(sampleCluster.startTime - 2 * diff, sampleCluster.endTime);
+
+                    CanvasTest.fillCanvasBeforeRedrawCheck(canvasWithoutSampling);
+                    CanvasTest.fillCanvasBeforeRedrawCheck(canvasWithSampling);
+                    return waitForComponentsToRender(context);
+                }).then(() => {
+                    expect(CanvasTest.hasCanvasBeenRedrawn(canvasWithoutSampling)).to.be(true);
+                    expect(CanvasTest.hasCanvasBeenRedrawn(canvasWithSampling)).to.be(true);
+
+                    expect(CanvasTest.canvasContainsColor(canvasWithoutSampling, {r: 0, g: 128, b: 255})).to.be(true);
+                    expect(CanvasTest.canvasContainsColor(canvasWithSampling, {r: 0, g: 128, b: 255})).to.be(true);
+
+                    CanvasTest.expectCanvasesMismatch(canvasWithSampling, canvasWithoutSampling);
                 });
             });
         });
index 4ac1c72..9a285dc 100644 (file)
@@ -382,11 +382,11 @@ class InteractiveTimeSeriesChart extends TimeSeriesChart {
         return metrics;
     }
 
-    _sampleTimeSeries(data, minimumTimeDiff, excludedPoints)
+    _sampleTimeSeries(data, maximumNumberOfPoints, excludedPoints)
     {
         if (this._indicatorID)
             excludedPoints.add(this._indicatorID);
-        return super._sampleTimeSeries(data, minimumTimeDiff, excludedPoints);
+        return super._sampleTimeSeries(data, maximumNumberOfPoints, excludedPoints);
     }
 
     _renderChartContent(context, metrics)
index 80374fe..ac6a28f 100644 (file)
@@ -490,9 +490,6 @@ class TimeSeriesChart extends ComponentBase {
             if (!timeSeries)
                 return null;
 
-            // A chart with X px width shouldn't have more than 2X / <radius-of-points> data points.
-            const maximumNumberOfPoints = 2 * metrics.chartWidth / (source.pointRadius || 2);
-
             const pointAfterStart = timeSeries.findPointAfterTime(startTime);
             const pointBeforeStart = (pointAfterStart ? timeSeries.previousPoint(pointAfterStart) : null) || timeSeries.firstPoint();
             const pointAfterEnd = timeSeries.findPointAfterTime(endTime) || timeSeries.lastPoint();
@@ -504,7 +501,11 @@ class TimeSeriesChart extends ComponentBase {
             if (!source.sampleData)
                 return view;
 
-            return this._sampleTimeSeries(view, (endTime - startTime) / maximumNumberOfPoints, new Set);
+            // A chart with X px width shouldn't have more than 2X / <radius-of-points> data points.
+            const viewWidth = Math.min(metrics.chartWidth, metrics.timeToX(pointAfterEnd.time) - metrics.timeToX(pointBeforeStart.time));
+            const maximumNumberOfPoints = 2 * viewWidth / (source.pointRadius || 2);
+
+            return this._sampleTimeSeries(view, maximumNumberOfPoints, new Set);
         });
 
         Instrumentation.endMeasuringTime('TimeSeriesChart', 'ensureSampledTimeSeries');
@@ -514,19 +515,27 @@ class TimeSeriesChart extends ComponentBase {
         return true;
     }
 
-    _sampleTimeSeries(view, minimumTimeDiff, excludedPoints)
+    _sampleTimeSeries(view, maximumNumberOfPoints, excludedPoints)
     {
-        if (view.length() < 2)
+
+        if (view.length() < 2 || maximumNumberOfPoints >= view.length() || maximumNumberOfPoints < 1)
             return view;
 
         Instrumentation.startMeasuringTime('TimeSeriesChart', 'sampleTimeSeries');
 
-        const sampledData = view.filter((point, i) => {
-            if (excludedPoints.has(point.id))
-                return true;
+        let ranks = new Array(view.length());
+        let i = 0;
+        for (let point of view) {
             let previousPoint = view.previousPoint(point) || point;
             let nextPoint = view.nextPoint(point) || point;
-            return nextPoint.time - previousPoint.time >= minimumTimeDiff;
+            ranks[i] = nextPoint.time - previousPoint.time;
+            i++;
+        }
+
+        const sortedRanks = ranks.slice(0).sort((a, b) => b - a);
+        const minimumRank = sortedRanks[Math.floor(maximumNumberOfPoints)];
+        const sampledData = view.filter((point, i) => {
+            return excludedPoints.has(point.id) || ranks[i] >= minimumRank;
         });
 
         Instrumentation.endMeasuringTime('TimeSeriesChart', 'sampleTimeSeries');
@@ -619,7 +628,7 @@ class TimeSeriesChart extends ComponentBase {
 
         let previousDate = null;
         let previousMonth = null;
-        while (currentTime <= max) {
+        while (currentTime <= max && result.length < maxLabels) {
             const time = new Date(currentTime);
             const month = time.getUTCMonth() + 1;
             const date = time.getUTCDate();
index 2dca221..09bc340 100644 (file)
@@ -167,11 +167,12 @@ class TimeSeriesView {
 
     filter(callback)
     {
-        const data = this._data;
         const filteredData = [];
-        for (let i = this._startingIndex; i < this._afterEndingIndex; i++) {
-            if (callback(data[i], i))
-                filteredData.push(data[i]);
+        let i = 0;
+        for (let point of this) {
+            if (callback(point, i))
+                filteredData.push(point);
+            i++;
         }
         return new TimeSeriesView(this._timeSeries, 0, filteredData.length, filteredData);
     }
index 7701576..2443a76 100644 (file)
@@ -276,6 +276,20 @@ describe('TimeSeries', () => {
 describe('TimeSeriesView', () => {
 
     describe('filter', () => {
+        it('should call callback with an element in the view and its index', () => {
+            const timeSeries = new TimeSeries();
+            addPointsToSeries(timeSeries, fivePoints);
+            const originalView = timeSeries.viewBetweenPoints(fivePoints[1], fivePoints[3]);
+            const points = [];
+            const indices = [];
+            const view = originalView.filter((point, index) => {
+                points.push(point);
+                indices.push(index);
+            });
+            assert.deepEqual(points, [fivePoints[1], fivePoints[2], fivePoints[3]]);
+            assert.deepEqual(indices, [0, 1, 2]);
+        });
+
         it('should create a filtered view', () => {
             const timeSeries = new TimeSeries();
             addPointsToSeries(timeSeries, fivePoints);