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 <bm2736...@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-unsubscr...@echarts.apache.org For additional commands, e-mail: commits-h...@echarts.apache.org