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:15 UTC
[incubator-echarts] branch pr/13317 created (now d6f6300)
This is an automated email from the ASF dual-hosted git repository.
shenyi pushed a change to branch pr/13317
in repository https://gitbox.apache.org/repos/asf/incubator-echarts.git.
at d6f6300 feat(sample): optimize performance of lttb sampling
This branch includes the following new commits:
new d6f6300 feat(sample): optimize performance of lttb sampling
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@echarts.apache.org
For additional commands, e-mail: commits-help@echarts.apache.org
[incubator-echarts] 01/01: feat(sample): optimize performance of
lttb sampling
Posted by sh...@apache.org.
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