Changeset 212946 in webkit

Timestamp:

Feb 23, 2017 10:57:04 PM (7 years ago)

Author:

rniwa@webkit.org

Message:

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.

Location:

trunk/Websites/perf.webkit.org

Files:

• ChangeLog (modified) (1 diff)
• browser-tests/index.html (modified) (1 diff)
• browser-tests/time-series-chart-tests.js (modified) (3 diffs)
• public/v3/components/interactive-time-series-chart.js (modified) (1 diff)
• public/v3/components/time-series-chart.js (modified) (4 diffs)
• public/v3/models/time-series.js (modified) (1 diff)
• unit-tests/time-series-tests.js (modified) (1 diff)

trunk/Websites/perf.webkit.org/ChangeLog

@@ +1 @@
+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>
 

trunk/Websites/perf.webkit.org/browser-tests/index.html

@@ -164 +164 @@
 
     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); },

trunk/Websites/perf.webkit.org/browser-tests/time-series-chart-tests.js

@@ -78 +78 @@
         {
             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();
@@ -542 +544 @@
                 expect(chart.content().querySelector('canvas')).to.be(null);
                 return waitForComponentsToRender(context).then(() => {
-                    console.log('done')
                     expect(chart.content().querySelector('canvas')).to.not.be(null);
                 });
@@ -829 +830 @@
                     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);
                 });
             });

trunk/Websites/perf.webkit.org/public/v3/components/interactive-time-series-chart.js

@@ -383 +383 @@
     }
 
-    _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);
     }
 

trunk/Websites/perf.webkit.org/public/v3/components/time-series-chart.js

@@ -491 +491 @@
                 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();
@@ -505 +502 @@
                 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);
         });
 
@@ -515 +516 @@
     }
 
-    _sampleTimeSeries(view, minimumTimeDiff, excludedPoints)
-    {
-        if (view.length() < 2)
+    _sampleTimeSeries(view, maximumNumberOfPoints, excludedPoints)
+    {
+
+        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;
         });
 
@@ -620 +629 @@
         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;

trunk/Websites/perf.webkit.org/public/v3/models/time-series.js

@@ -168 +168 @@
     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);

trunk/Websites/perf.webkit.org/unit-tests/time-series-tests.js

@@ -277 +277 @@
 
     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();