[BUG] Hover is slow in line graphs when there are many points

[green7ea]

Chart.js becomes very slow when we create a line graph of 5 000 points or more.

Expected Behavior

5 000 points is not a big graph. There shouldn't be any performance problems when used on a modern computer or even a cell phone.

Current Behavior

By looking at the code quickly, it seems that the problem lies in the way the hover behavior calculates intersections. Currently, in core.interaction.js, it seems that getIntersectItems evaluates every visible item which is not ideal in a line chart. Idealy, you want to do a binary search on the x-axis since the data should be x-sorted before graphing.

Possible Solution

Calculate the intersection using a binary search on the x-axis instead of looking at every visible point for line graphs. This intersection calculation occurs every mouse move over the canvas and so happens very frequently. A binary search would mean a reduction, for 5000 visible elements, from 5000 iterations to log2(5000) ~= 13 iterations.

Steps to Reproduce (for bugs)

The following copepen ( https://codepen.io/anon/pen/WjMgVw ) show that there are performance problems when we have 5000 points in a line graph.

Context

Because of this issue, our company has had to use a different graphing library since we need to be able to graph 16k or so points.

[SesioN]

I can agree and also notice the slow downs even tho I don't even have 5000k points.

+1

[etimberg]

@green7ea I looked at the profiles from your codepen. Most of the time is not spent searching for the visible point. On my machine I see the function that does the search, getElementAtEventForMode taking only 0.1ms.

The binary search is an interesting idea, however it's not a simple drop in to the current code since it can only be performed on monotonic regions of a dataset. In a scatter chart, it would not work because points do not have to be sorted by increasing X values. I did prototype using a quad tree a few months ago, but there was a lot of overhead to insertion that wouldn't be amortized over a long enough period.

The big performance issue in the codepen is render time. It's taking 70ms to render the chart which happens on the main thread and slows down the page. Some potential options for improving performance here could be

1. Pre-render the point image to an off-screen canvas and then use drawImage to pull it in but this only works if every point is the same.
2. Add in data decimation to chart.js; currently we expect the data to be decimated before it gets sent to the chart
3. Only draw the points and not the line

[yusufozturk]

@etimberg HTML tooltips are also slow when there are many points. Is that related with this issue?

[sam-lex]

Hello, would like to add a few observations, maybe it can help detect where the problem is...
I've noticed slow performance with horizontal bars when there's a lot of items (13 so far).
Item being a product, with 2 datasets: Gross sales and quantity sold. (This is for a sales report, so it could go up to 100-200 items depending on the period it is generated).

I'm using responsive approach, so it resizes with the window, it's height is dynamically set depending on products length, (something like 40px * products.length). This works perfectly well for 5-6 items, but with perhaps 10 or more, it becomes really slow.

If I resize however, making the bars short. It becomes fast again.

[solsticedhiver]

I also notice a 100% cpu usage (during the time to lookup for the tooltip data) on the tab that displays a chart.js chart with more than 20k point on a line chart with custom tooltip callbacks (but no HTML).

Tooltips take quite a while before showing up. The slow-down appears with a chart with fewer point like 5k, mentionned above

[etimberg]

@kurkle think we can close this based on the new animation system?

[leeoniya]

i think chartjs's poor hover performance is not related to animation but due to excessive chart redraw, which is still a significant issue: https://github.com/leeoniya/uPlot#performance

[benmccann]

Performance is somewhat better in master for the time scale because we improved the performance of finding the hovered element (#6716)

However, performance could still be better improved by minimizing redraws as @leeoniya mentioned. When the tooltip and other hover actions are disabled, the chart is still redrawn when hovering on it, but really shouldn't be. Fixing this would make external custom html tooltips massively faster than using the default on-canvas tooltip

[kurkle]

i think chartjs's poor hover performance is not related to animation but due to excessive chart redraw, which is still a significant issue: https://github.com/leeoniya/uPlot#performance

What do you consider excessive redraw? more than once per animation frame?

[leeoniya]

What do you consider excessive redraw?

that's a tough one to answer, considering uPlot does 0 redraw by delegating interactive elements to dom-land. if you guys are not drawing interactive elements on their own dedicated canvas and instead redrawing all the paths (and text labels) every 16ms, i would consider that excessive. if you do redraw all paths, you should at minimum be caching them in Path2D objects and simply repainting them without reconstructing them.

i don't know the specifics of what chart.js does internally, i just see that the end result spins up my laptop's cpu fan during series toggling and mousemoves.