You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@echarts.apache.org by sh...@apache.org on 2020/09/23 08:49:16 UTC
[incubator-echarts] 01/01: feat(sample): optimize performance of
lttb sampling
This is an automated email from the ASF dual-hosted git repository.
shenyi pushed a commit to branch pr/13317
in repository https://gitbox.apache.org/repos/asf/incubator-echarts.git
commit d6f63003c22b2e14dfec1d388b527d3abbb0f10d
Author: pissang <bm...@gmail.com>
AuthorDate: Wed Sep 23 16:48:18 2020 +0800
feat(sample): optimize performance of lttb sampling
---
src/data/List.ts | 119 ++++++++++---------
src/processor/dataSample.ts | 2 +-
test/sample-compare.html | 282 +++++++++++++++++++++-----------------------
3 files changed, 201 insertions(+), 202 deletions(-)
diff --git a/src/data/List.ts b/src/data/List.ts
index 9350219..15cebe5 100644
--- a/src/data/List.ts
+++ b/src/data/List.ts
@@ -1694,15 +1694,14 @@ class List<
/**
* Large data down sampling using largest-triangle-three-buckets
- * https://github.com/pingec/downsample-lttb
* @param {string} baseDimension
* @param {string} valueDimension
- * @param {number} threshold target counts
+ * @param {number} rate
*/
lttbDownSample(
baseDimension: DimensionName,
valueDimension: DimensionName,
- threshold: number
+ rate: number
) {
const list = cloneListForMapAndSample(this, [baseDimension, valueDimension]);
const targetStorage = list._storage;
@@ -1711,72 +1710,84 @@ class List<
const len = this.count();
const chunkSize = this._chunkSize;
const newIndices = new (getIndicesCtor(this))(len);
- const getPair = (
- i: number
- ) : Array<any> => {
- const originalChunkIndex = mathFloor(i / chunkSize);
- const originalChunkOffset = i % chunkSize;
- return [
- baseDimStore[originalChunkIndex][originalChunkOffset],
- valueDimStore[originalChunkIndex][originalChunkOffset]
- ];
- };
let sampledIndex = 0;
- const every = (len - 2) / (threshold - 2);
+ const frameSize = mathFloor(1 / rate);
- let a = 0;
+ let currentSelectedIdx = 0;
let maxArea;
let area;
- let nextA;
-
- newIndices[sampledIndex++] = a;
- for (let i = 0; i < threshold - 2; i++) {
+ let nextSelectedIdx;
+
+ for (let chunkIdx = 0; chunkIdx < this._chunkCount; chunkIdx++) {
+ const chunkOffset = chunkSize * chunkIdx;
+ const selfChunkSize = Math.min(len - chunkOffset, chunkSize);
+ const chunkFrameCount = Math.ceil((selfChunkSize - 2) / frameSize);
+ const baseDimChunk = baseDimStore[chunkIdx];
+ const valueDimChunk = valueDimStore[chunkIdx];
+
+ // The first frame is the first data.
+ newIndices[sampledIndex++] = currentSelectedIdx;
+
+ for (let frame = 0; frame < chunkFrameCount - 2; frame++) {
+ let avgX = 0;
+ let avgY = 0;
+ let avgRangeStart = (frame + 1) * frameSize + 1 + chunkOffset;
+ const avgRangeEnd = Math.min((frame + 2) * frameSize + 1, selfChunkSize) + chunkOffset;
+
+ const avgRangeLength = avgRangeEnd - avgRangeStart;
+
+ for (; avgRangeStart < avgRangeEnd; avgRangeStart++) {
+ const x = baseDimChunk[avgRangeStart] as number;
+ const y = valueDimChunk[avgRangeStart] as number;
+ if (isNaN(x) || isNaN(y)) {
+ continue;
+ }
+ avgX += x;
+ avgY += y;
+ }
+ avgX /= avgRangeLength;
+ avgY /= avgRangeLength;
- let avgX = 0;
- let avgY = 0;
- let avgRangeStart = mathFloor((i + 1) * every) + 1;
- let avgRangeEnd = mathFloor((i + 2) * every) + 1;
+ // Get the range for this bucket
+ let rangeOffs = (frame) * frameSize + 1 + chunkOffset;
+ const rangeTo = (frame + 1) * frameSize + 1 + chunkOffset;
- avgRangeEnd = avgRangeEnd < len ? avgRangeEnd : len;
+ // Point A
+ const pointAX = baseDimChunk[currentSelectedIdx] as number;
+ const pointAY = valueDimChunk[currentSelectedIdx] as number;
+ let allNaN = true;
- const avgRangeLength = avgRangeEnd - avgRangeStart;
+ maxArea = area = -1;
- for (; avgRangeStart < avgRangeEnd; avgRangeStart++) {
- avgX += getPair(avgRangeStart)[0] * 1; // * 1 enforces Number (value may be Date)
- avgY += getPair(avgRangeStart)[1] * 1;
- }
- avgX /= avgRangeLength;
- avgY /= avgRangeLength;
-
- // Get the range for this bucket
- let rangeOffs = mathFloor((i + 0) * every) + 1;
- const rangeTo = mathFloor((i + 1) * every) + 1;
-
- // Point a
- const pointAX = getPair(a)[0] * 1; // enforce Number (value may be Date)
- const pointAY = getPair(a)[1] * 1;
-
- maxArea = area = -1;
-
- for (; rangeOffs < rangeTo; rangeOffs++) {
- // Calculate triangle area over three buckets
- area = Math.abs((pointAX - avgX) * (getPair(rangeOffs)[1] - pointAY)
- - (pointAX - getPair(rangeOffs)[0]) * (avgY - pointAY)
- ) * 0.5;
- if (area > maxArea) {
- maxArea = area;
- nextA = rangeOffs; // Next a is this b
+ for (; rangeOffs < rangeTo; rangeOffs++) {
+ const y = valueDimChunk[rangeOffs] as number;
+ const x = baseDimChunk[rangeOffs] as number;
+ if (isNaN(x) || isNaN(y)) {
+ continue;
+ }
+ allNaN = false;
+ // Calculate triangle area over three buckets
+ area = Math.abs((pointAX - avgX) * (y - pointAY)
+ - (pointAX - x) * (avgY - pointAY)
+ );
+ if (area > maxArea) {
+ maxArea = area;
+ nextSelectedIdx = rangeOffs; // Next a is this b
+ }
}
- }
- newIndices[sampledIndex++] = nextA;
+ if (!allNaN) {
+ newIndices[sampledIndex++] = nextSelectedIdx;
+ }
- a = nextA; // This a is the next a (chosen b)
+ currentSelectedIdx = nextSelectedIdx; // This a is the next a (chosen b)
+ }
+ // The last frame is the last data.
+ newIndices[sampledIndex++] = selfChunkSize - 1;
}
- newIndices[sampledIndex++] = len - 1;
list._count = sampledIndex;
list._indices = newIndices;
diff --git a/src/processor/dataSample.ts b/src/processor/dataSample.ts
index 485f6df..7d81fd6 100644
--- a/src/processor/dataSample.ts
+++ b/src/processor/dataSample.ts
@@ -95,7 +95,7 @@ export default function (seriesType: string): StageHandler {
if (rate > 1) {
if (sampling === 'lttb') {
seriesModel.setData(data.lttbDownSample(
- data.mapDimension(baseAxis.dim), data.mapDimension(valueAxis.dim), size
+ data.mapDimension(baseAxis.dim), data.mapDimension(valueAxis.dim), 1 / rate
));
}
let sampler;
diff --git a/test/sample-compare.html b/test/sample-compare.html
index 8b8cfc9..bcd1be1 100644
--- a/test/sample-compare.html
+++ b/test/sample-compare.html
@@ -20,162 +20,150 @@ under the License.
<!doctype html>
<html>
<head>
- <meta charset="utf-8">
- <title>ECharts Demo</title>
- <meta name="viewport" content="width=device-width, initial-scale=1">
+ <meta charset='utf-8'>
+ <title>Downsample Comparasions</title>
+ <meta name='viewport' content='width=device-width, initial-scale=1'>
</head>
<body>
- <h2 id="wait">Loading lib....</h2>
+ <h2 id='wait'>Loading lib....</h2>
- <div id="container" style="height: 600px; width: 100%;"></div>
+ <div id='container' style='height: 600px; width: 1200px;'></div>
- <script src="lib/esl.js"></script>
- <script src="lib/config.js"></script>
+ <script src='lib/esl.js'></script>
+ <script src='lib/config.js'></script>
<script>
require([
'echarts'
// 'echarts/chart/sankey',
// 'echarts/component/tooltip'
- ], function (echarts) {
- function round2(val) {
- return Math.round(val * 100) / 100;
- }
-
- function round3(val) {
- return Math.round(val * 1000) / 1000;
- }
-
- function prepData(packed) {
- // console.time('prep');
-
- // epoch,idl,recv,send,read,writ,used,free
-
- const numFields = packed[0];
- packed = packed.slice(numFields + 1);
-
- var cpu = Array(packed.length/numFields);
-
- for (let i = 0, j = 0; i < packed.length; i += numFields, j++) {
- let date = packed[i] * 60 * 1000;
- cpu[j] = [date, round3(100 - packed[i+1])];
- }
-
- // console.timeEnd('prep');
-
- return [cpu];
- }
-
- function makeChart(data) {
- console.time('chart');
-
- var dom = document.getElementById("container");
- var myChart = echarts.init(dom);
-
- let opts = {
- grid: {
- left: 40,
- top: 0,
- right: 0,
- bottom: 30,
- },
- xAxis: {
- type: 'time',
- splitLine: {
- show: false
- },
- data: data[0],
- },
- yAxis: {
- type: 'value'
- },
- legend: {
- },
- series: [
- {
- name: 'none',
- type: 'line',
- showSymbol: false,
- hoverAnimation: false,
- data: data[0],
- lineStyle: {
- normal: {
- opacity: 0.5,
- width: 1
- }
- }
- },
- {
- name: 'lttb',
- type: 'line',
- showSymbol: false,
- hoverAnimation: false,
- data: data[0],
- sampling: 'lttb',
- lineStyle: {
- normal: {
- opacity: 0.5,
- width: 1
- }
- }
- },
- {
- name: 'average',
- type: 'line',
- showSymbol: false,
- hoverAnimation: false,
- data: data[0],
- sampling: 'average',
- lineStyle: {
- normal: {
- opacity: 0.5,
- width: 1
- }
- }
- },
- {
- name: 'max',
- type: 'line',
- showSymbol: false,
- hoverAnimation: false,
- data: data[0],
- sampling: 'max',
- lineStyle: {
- normal: {
- opacity: 0.5,
- width: 1
- }
- }
- },
- {
- name: 'min',
- type: 'line',
- showSymbol: false,
- hoverAnimation: false,
- data: data[0],
- sampling: 'min',
- lineStyle: {
- normal: {
- opacity: 0.5,
- width: 1
- }
- }
- },
- ]
- };
-
- myChart.setOption(opts, true);
-
- wait.textContent = "Done!";
- console.timeEnd('chart');
- }
-
- let wait = document.getElementById("wait");
- wait.textContent = "Fetching data.json (2.07MB)....";
- fetch("./data/large-data.json").then(r => r.json()).then(packed => {
- wait.textContent = "Rendering...";
- let data = prepData(packed);
- setTimeout(() => makeChart(data), 0);
- });
+ ], function (echarts) {
+ function round2(val) {
+ return Math.round(val * 100) / 100;
+ }
+
+ function round3(val) {
+ return Math.round(val * 1000) / 1000;
+ }
+
+ function prepData(packed) {
+ console.time('prep');
+
+ // epoch,idl,recv,send,read,writ,used,free
+
+ var numFields = packed[0];
+ packed = packed.slice(numFields + 1);
+
+ var repeatTimes = 1;
+
+ var data = new Float64Array((packed.length / numFields) * 4 * repeatTimes);
+
+ var off = 0;
+ var date = packed[0];
+ for (let repeat = 0; repeat < repeatTimes; repeat++) {
+ for (let i = 0, j = 0; i < packed.length; i += numFields, j++) {
+ date += 1;
+ data[off++] = date * 60 * 1000;
+ data[off++] = round3(100 - packed[i + 1]);
+ data[off++] = round2(
+ (100 * packed[i + 5]) / (packed[i + 5] + packed[i + 6])
+ );
+ data[off++] = packed[i + 3];
+ }
+ }
+ console.timeEnd('prep');
+
+ return data;
+ }
+
+ function makeChart(data) {
+ var dom = document.getElementById('container');
+ var myChart = echarts.init(dom);
+
+ let opts = {
+ animation: false,
+ dataset: {
+ source: data,
+ dimensions: ['date', 'cpu', 'ram', 'tcpout']
+ },
+ tooltip: {
+ trigger: 'axis'
+ },
+ legend: {},
+ grid: {
+ containLabel: true,
+ left: 0,
+ top: 50,
+ right: 0,
+ bottom: 30
+ },
+ xAxis: {
+ type: 'time'
+ },
+ yAxis: [{
+ type: 'value',
+ max: 100,
+ axisLabel: {
+ formatter: '{value} %'
+ }
+ }, {
+ type: 'value',
+ max: 100,
+ axisLabel: {
+ formatter: '{value} MB'
+ }
+ }],
+ series: [{
+ name: 'CPU',
+ type: 'line',
+ showSymbol: false,
+ sampling: 'lttb',
+ lineStyle: { width: 1 },
+ emphasis: { lineStyle: { width: 1 } },
+ encode: {
+ x: 'date',
+ y: 'cpu'
+ }
+ }, {
+ name: 'RAM',
+ type: 'line',
+ yAxisIndex: 1,
+ showSymbol: false,
+ sampling: 'lttb',
+ lineStyle: { width: 1 },
+ emphasis: { lineStyle: { width: 1 } },
+ encode: {
+ x: 'date',
+ y: 'ram'
+ }
+ }, {
+ name: 'TCP Out',
+ type: 'line',
+ yAxisIndex: 1,
+ showSymbol: false,
+ sampling: 'lttb',
+ lineStyle: { width: 1 },
+ emphasis: { lineStyle: { width: 1 } },
+ encode: {
+ x: 'date',
+ y: 'tcpout'
+ }
+ }]
+ };
+ const startTime = performance.now();
+ myChart.setOption(opts, true);
+ const endTime = performance.now();
+ wait.textContent = 'Done! ' + (endTime - startTime).toFixed(0) + 'ms';
+ }
+
+ let wait = document.getElementById('wait');
+ wait.textContent = 'Fetching data.json (2.07MB)....';
+ fetch('data/large-data.json')
+ .then(r => r.json())
+ .then(packed => {
+ wait.textContent = 'Rendering...';
+ let data = prepData(packed);
+ setTimeout(() => makeChart(data), 200);
+ });
});
</script>
</body>
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@echarts.apache.org
For additional commands, e-mail: commits-help@echarts.apache.org