DEV Community: James Swinton-Bland

Optimising Large Data Set Visualisations with the M4 Algorithm

James Swinton-Bland — Tue, 14 Jan 2025 15:28:31 +0000

Version 11 of AG Charts, our JavaScript Charting Library, includes significant performance enhancements to our Line Series. These improvements allow you to render over a million data points that can be zoomed, panned, and interacted with at over 60 fps, making these transitions appear seamless to users.

To achieve this level of performance, we implemented the M4 algorithm: an aggregation-based time series dimensionality reduction technique that provides error-free visualizations at high data reduction rates. This blog post details our implementation of this algorithm and the performance improvements we've gained from it.

Challenges in Rendering Large Datasets

AG Charts leverages the HTML5 Canvas API for its drawing operations. We've discussed some of the techniques we apply to optimize HTML5 Canvas rendering in a previous blog post, however, no matter what optimisations are applied, rendering a million data points in a chart is computationally intensive.

If you're not already familiar with the Canvas API, drawing lines is akin to instructing a virtual pen: you issue one command to place the pen nib at specific coordinates on the screen, and another command to move the nib to a different set of coordinates, which then draws a line between the two points. This means that as the size of our data grows, so does the number of drawing operations required, which means more work for us to do.

Introducing the M4 Algorithm

Given the way the Canvas API works, the only way to reduce the work needed to draw a chart is to physically draw less, which is where the M4 algorithm comes in. According to the original paper, the M4 algorithm "exploits the semantics of line rasterization to drive the data reduction of high-volume time series data." In other words, this approach allows us to reduce the number of drawing operations required to render a line chart, whilst retaining its original characteristics.

How the M4 Algorithm Works

This algorithm might sound complicated, but it's actually quite simple. Consider the following line chart, which contains 100 data points:

To apply the M4 algorithm, start by determining the range of your x-values. For instance, if your x-data ranges from 100 to 200, you might divide this range into 10 equal buckets: 100–110, 110–120, and so on. In this case, we've divided our example into 5 buckets:

Next, for each bucket, identify the data points that meet the following criteria:

Minimum x-value
Maximum x-value
Minimum y-value
Maximum y-value

Because a data point may fit more than one criterion, each bucket will have up to four points. These have been highlighted in each bucket below:

Finally, connect the selected data points with lines to draw the simplified Line Series:

And that's it... by applying the M4 algorithm we've reduced the number of drawing operations required from 100 to 18.

We purposefully made our buckets large in this example to illustrate how the algorithm works. To make this optimised chart appear almost indistinguishable from if the algorithm had never been applied, you’ll want your number of buckets set so that each bucket is around a pixel wide.

For example, if you're rendering a chart that's 500 pixels wide and contains one million data points, you would divide the data into 500 buckets - one bucket per pixel. Each bucket would contain 2,000 data points (since 1,000,000 divided by 500 equals 2,000). In this example, applying the M4 algorithm reduces each bucket to a maximum of four points, meaning you'd end up with up to 2,000 points in total (500 buckets × 4 points), which is just 0.2% of the original data.

Optimizing for Interactivity

When implementing this algorithm the first problem we encountered was that iterating over a million points is slow. To achieve 60fps performance we need to render each frame in around 16ms, however, our most optimised implementation took around 100ms to complete, which made features like Zoom feel sluggish.

To fix this, we can pre-compute the M4 algorithm at different zoom levels, much like Google Maps does as you zoom out from a small street to a city. This works by starting with of snapshot of the highest detail you have available, and then gradually reducing the level of detail to generate additional snapshots until there is no value in reducing it further.

For the M4 algorithm, we employ a clever technique to accelerate detail reduction. Instead of processing the original dataset at each level of detail, we utilize the results from a previous run by combining each adjacent pair of buckets, effectively halving the number of buckets.

Below is an illustration of our example after merging the buckets:

This approach allows us to reuse the already filtered data, rather than starting from scratch with the entire dataset. When dealing with a dataset of one million points, reducing the filtered data to just a few thousand points makes a huge difference. As an added bonus, each time this step is repeated, it will take less time than the previous run.

Results

As you can see from the chart below, these optimizations have the biggest impact on large datasets:

Try It Out

Test the performance by yourself by selecting a large data set and zooming / scrolling in our live demo.

Conclusion

By implementing the M4 algorithm and optimizing data processing, AG Charts 11 delivers high-performance rendering of large Line Series datasets. These enhancements enable you to create interactive charts that remain fast & responsive, even with millions of data points.

If you've made it this far, you may be interested in some of our other performance-related blogs, that discuss a range of other optimisations we've made to AG Charts to make it The Best JavaScript Charting Library In The World:

Want to add high-performance JavaScript Charts to your application? Get started today, for free:

Get Started

Building AG Charts: Efficient JavaScript Charting with Tree-Based Scene Graphs

James Swinton-Bland — Thu, 26 Sep 2024 09:33:32 +0000

AG Charts is a high-performance, canvas-based JavaScript charting library, designed for creating complex and interactive JavaScript charts. Initially built to power Integrated Charts in AG Grid (our React Data Table library), it now stands alone with over 1 million npm downloads per month.

In this post, we’ll explore how AG Charts leverages a tree-based scene graph abstraction to efficiently render complex JavaScript charts, offering a powerful solution for developers building data visualizations in JavaScript, React, Angular and Vue.

Challenges in JavaScript Charting with HTML Canvas

Rendering graphics on the web can be a double-edged sword. While the HTML Canvas API provides a solid platform for drawing complex shapes and images, it comes with performance considerations, such as:

Rendering Overhead : Canvas operations involve manipulating the pixels of a bitmap, which means that drawing, compositing, and transformations require direct interaction with the GPU or software rendering pipeline.
Browser API Overhead : Each canvas API call incurs a certain amount of overhead due to interaction with the browser's rendering engine.
Repainting and Redrawing : When you draw on a canvas, the entire pixel area being modified has to be recalculated and redrawn, especially for complex shapes or animations.
Single-threaded Execution : JavaScript and canvas rendering both run on the main thread. Intensive canvas operations can block the main thread, leading to slower response times and reduced performance for other JavaScript tasks.
Lack of Hardware Acceleration in Some Cases : While some canvas operations can be hardware accelerated, not all operations benefit from it. This inconsistency can lead to performance bottlenecks, especially with complex or frequent drawing operations.

Given this, we needed a solution that would allow us to work with the canvas as efficiently as possible.

_Enter the scene graph. _

What is a Scene Graph?

A tree-based scene graph is a hierarchical data structure used in computer graphics to represent the spatial and logical relationships between objects in a scene. Each node in the tree corresponds to an object or entity in the scene, and the parent-child relationships between nodes define transformations such as translation, rotation, and scaling relative to their parents.

In AG Charts, the scene graph is an abstraction layer over the HTML Canvas, providing a higher-level API for constructing and manipulating chart elements, such as markers, lines, circles and shapes. The scene graph also provides a layer where we can perform caching and optimise canvas rendering, negating some of the aforementioned performance considerations.

Why a Scene Graph is Essential for JavaScript Chart Libraries

Higher-Order Abstraction for Rendering: The scene graph in AG Charts was designed to simplify the low-level drawing operations required by the Canvas API. Instead of working directly with pixels, chart renderings could work with higher-order constructs like markers, lines, circles, and shapes.
Caching and Optimization: One key advantage of the scene graph is its ability to cache and optimize canvas rendering. Since canvas operations are typically slower than JavaScript operations, caching results and minimizing redraws are essential for maintaining performance.
Support for Matrix Transformations: Initially, we added support for matrix transformations on the base node class of all scene graph nodes, which includes rotation, scaling and translation operations.
Coordinate Conversion Utilities: We also implemented methods for converting points and boxes to and from canvas coordinates. These utilities were used liberally throughout our codebase to manage positioning and layout tasks.

How the Scene Graph Was Implemented in AG Charts

Our scene graph consists of nodes representing different chart elements, with a base node class that includes properties for positioning, styling, and rendering. Each node type—whether a line, shape, or marker—inherits from this base class and implements its own rendering logic.

The base node class also includes support for matrix transformations. Matrix transformations are mathematical operations used to manipulate the position, scale, and rotation of objects within a 2D space. These transformations are represented as matrices, which, when applied to points or objects, alter their geometric properties. The main types of transformations are:

Translation : Shifts an object from one position to another.
Scaling : Changes the size of an object either uniformly or non-uniformly.
Rotation : Rotates an object around a specific point or axis.

In a scene graph, these transformations are applied hierarchically. Each node in the graph represents an object or a group of objects and holds its transformation matrix. The final transformation of a child node is the result of its own transformation combined with the transformations of all its parent nodes.

In addition to matrix transformations, we also added methods to convert to/from canvas coordinates for points and boxes, which were liberally used around the codebase.

Continuous Improvement of AG Charts JavaScript Charts

Whilst our initial implementation of the scene graph provided many benefits, as AG Charts continues to evolve we've noticed areas for further improvement, namely:

Overhead from Matrix Transformations: Although matrix transformations were supported by default, they were unnecessary for most rendering tasks. In practice, 95% of our scene graph nodes do not require these transformations, leading to unnecessary computational overhead.
Complexity in Coordinate Conversions: The frequent use of coordinate conversion methods added complexity to the codebase, making it harder to maintain and optimize.
Performance Bottlenecks: As our library grew, we noticed that matrix transformations were consuming a non-trivial amount of execution time, even for nodes where these transformations were not needed.

Our Approach to Optimizing the Scene Graph

To address these challenges, we implemented a series of changes aimed at simplifying the scene graph and reducing performance overhead:

Selective Application of Matrix Transformations: We removed all matrix support from the existing scene graph nodes and added mixin classes. This allowed us to selectively re-add matrix transforms to the specific parts of the codebase where they were still needed.
Simplifying Coordinate Transformations: We refactored the base scene-graph nodes by replacing methods that returned canvas coordinates with helper functions using local coordinates, reducing costly matrix operations.
Improving Hit-Testing Performance: We streamlined hit testing (determining whether a mouse or touch event intersects with a specific object drawn on the canvas) by converting to local coordinates upfront and applying transforms as we traverse the scene graph, avoiding the need for continuous coordinate conversions.
Refactoring and Cleanup: As a result of these simplifications and improvements, we were able to generally refactor and clean up redundant operations throughout our codebase, reducing our overall tech debt, and thereby improving maintainability as well as performance.

Key Pull Requests and Changes

These optimizations were implemented across several pull requests. Given AG Charts is entirely open-source, you can dig into these PRs:

Results and Performance Gains

These changes have led to several positive outcomes:

Reduced Overhead from Unnecessary Matrix Transforms: Matrix transformations are now only applied where needed, mostly in rendering leaf nodes of the scene graph, reducing unnecessary computational costs.
Faster Hit-Testing and Rendering: Hit-testing operations are now cheaper and faster, thanks to optimized coordinate handling.
Performance Improvements in Benchmarks: Internal benchmarking shows notable performance gains in large-scale use cases, demonstrating the effectiveness of these optimizations:

bbox caching introduced in b10.1 & Matrix transformations removed in latest (b10.2)

Conclusion

By refining our use of matrix transformations and optimizing the scene graph, we've significantly improved the performance of AG Charts. These changes are now part of the latest (10.2) release, and we're excited to see how they enhance your charting experience. Stay tuned for more updates as we continue to innovate and improve AG Charts!

Want to build JavaScript charts with AG Charts? Get Started today by visiting our documentation:

Get Started with AG Charts JavaScript Charting Library

Introducing AG Charts Enterprise

James Swinton-Bland — Tue, 05 Dec 2023 11:37:40 +0000

Introduction

AG Charts is an open-source JavaScript charting and graphing library from the makers of AG Grid built for React, Angular and Vue. Last week saw the release of AG Charts 9, and, most notably, the introduction of AG Charts Enterprise.

Read on to learn a bit more about the background of AG Charts, how we arrived where we are today, and what you can expect from our brand-new enterprise product 👇

History of AG Charts

AG Charts was built by the AG Grid team in 2019 as a way to power integrated charts in AG Grid - a feature that lets users build charts directly from AG Grid. Sticking to our roots as an open-source company, we released AG Charts as a completely free and stand-alone open-source library. We knew that we had built a great library in its own right, so why not share it? Since then, AG Charts has steadily grown in popularity, now amassing over 300,000 NPM downloads/month (as of 04/12/2023). With this rise in popularity, we decided it was time to invest further in AG Charts which has now culminated in the release of AG Charts 9 and the introduction of AG Charts Enterprise.

Why AG Charts?

At this point, you may be thinking: "Why another charting library?" or "Why should I use AG Charts?". Our response would be that AG Charts comes with the same performance and reliability our users have come to expect of AG Grid. This reputation, and the subsequent trust we've earned with grid developers, has consistently separated us from our competition. We're confident we can earn that same reputation and trust from Charts developers, too.

Enterprise vs. Community

The obvious next question is, what's the difference between the Enterprise and Community versions of AG Charts? Well, in a nutshell:

AG Charts Community is the original version of AG Charts that is designed to meet most use cases and is free forever.
AG Charts Enterprise is an advanced version of AG Charts, with more series types, features, and dedicated Zendesk support, designed for enterprise use cases and customers.

Let's take a closer look at the series types & features available in AG Charts Enterprise:

Enterprise Series Types

AG Charts Enterprise comes with 13 additional series types - Box Plot, Bullet, Heatmap, Range Area, Range Bar, Radar Area, Radar Line, Radial Bar, Radial Column, Nightingale, Sunburst, Treemap, Waterfall:

See the gallery for a full list of series types & examples.

Enterprise Features

In addition to enhanced series types, AG Charts Enterprise also comes with a range of new features:

Animation of the graph or chart on load or update
Context Menu for additional actions, such as zooming, downloading or whatever else your users may need
Crosshairs for precise analysis of complex graphs
Zoom into and out of data
Error Bars for showing confidence intervals within data
Background Images to brand and style the chart

Check out the animation below that demonstrates some of these features:

0:00
/0:12
1×

Framework Support

AG Charts Community and Enterprise have both been built specifically for React, Angular, and Vue meaning you can build React Charts as easily as you can build JavaScript charts. These aren't just wrappers, either; we've built the library specifically for these frameworks.

Testing and Upgrading

It's free to try out AG Charts Enterprise and you do not need to contact us at all; we just ask that you don't use AG Charts Enterprise in a project intended for production without a licence.

When testing without a valid license key installed, your console log will will show a watermark for 5 seconds and display a series of warnings:

If you would like to remove this watermark or access support via Zendesk, you will need a trial license. Please email info@ag-grid.com to request a trial license key.

Pricing

AG Charts Enterprise pricing at $399 / developer, but there is a limited-time launch price of $199 / developer. Check out the pricing page for more information.

TL;DR

AG Charts was built in 2019 by the AG Grid team to power Integrated Charting within AG Grid.
Sticking to our roots, we released AG Charts as a free, standalone, open-source library.
AG Charts proved to be popular with the community, so we decided to release an Enterprise version in December 2023 with new features, series types and dedicated support.
AG Charts Enterprise requires a license and AG Charts Community will remain free forever
You can trial AG Charts Enterprise for free - it just displays a watermark and a console warning.

Ready to try it out? Get started with AG Charts Enterprise now 👇

Get Started

Introducing the AG Grid Figma Design System

James Swinton-Bland — Tue, 22 Aug 2023 09:01:29 +0000

Intro

If you're a designer working with AG grid it's time to get very excited! With AG Grid version 30.1.0 we've released our new Figma Design System.

If you want to skip the preamble and dig into the design system yourself you can download it directly from our design system documentation page.

Everything you need to design with AG Grid

The new design system implements our Alpine and Alpine Dark themes in Figma. All of the core AG Grid components are fully built out and ready to use, with even more components arriving in future releases. Each component has been carefully crafted to precisely mirror what's available in the AG Grid library.

Make it your own...

And when you're ready to make AG Grid your own we've got you covered. The Alpine and Alpine Dark themes can be extended to create custom AG Grid themes that work with your brand. We even provide a sample style dictionary project so you can export your bespoke themes to json and quickly create custom AG Grid CSS themes.

To learn more about the design system and thow it can help your design workflow watch this short video on Youtube.

Get designing now

Once you're ready to get started with the Figma design system checkout our design system documentation page to download the design system and start creating with AG Grid.