'Point-along-path' d3 visualization performance issue

Question

I have gone through the 'point-along-path' d3 visualization through the code: https://bl.ocks.org/mbostock/1705868. I have noticed that while the point is moving along its path it consumes 7 to 11% of CPU Usage.

Current scenario, I have around 100 paths and on each path, I will have to move points(circles) from sources to destinations. So it consumes more than 90% of the CPU memory as more number of points are moving at the same time.

I have tried as:

                   function translateAlong(path) {
                      var l = path.getTotalLength();
                      return function(d, i, a) {
                          return function(t) {
                               var p = path.getPointAtLength(t * l);
                               return "translate(" + p.x + "," + p.y + ")";
                          };
                       };
                    }

                    // On each path(100 paths), we are moving circles from source to destination.
                    var movingCircle = mapNode.append('circle')
                        .attr('r', 2)
                        .attr('fill', 'white')

                    movingCircle.transition()
                        .duration(10000)
                        .ease("linear")
                        .attrTween("transform", translateAlong(path.node()))
                        .each("end", function() {
                            this.remove();
                        });

So what should be the better way to reduce the CPU usage? Thanks.

Answer 1

There are a few approaches to this, which vary greatly in potential efficacy.

Ultimately, you are conducting expensive operations every animation frame to calculate each point's new location and to re render it. So, every effort should be made to reduce the cost of those operations.

If frame rate is dropping below 60, it probably means we're nearing CPU capacity. I've used frame rate below to help indicate CPU capacity as it is more easily measured than CPU usage (and probably less invasive).

I had all sorts of charts and theory for this approach, but once typed it seemed like it should be intuitive and I didn't want to dwell on it.

Essentially the goal is to maximize how many transitions I can show at 60 frames per second - this way I can scale back the number of transitions and gain CPU capacity.

---

Ok, let's get some transitions running with more than 100 nodes along more than 100 paths at 60 frames per second.

D3v4

First, d3v4 likely offers some benefits here. v4 synchronized transitions, which appears to have had the effect of slightly improved times. d3.transition is very effective and low cost in any event, so this isn't the most useful - but upgrading isn't a bad idea.

There are also minor browser specific gains to be had by using different shaped nodes, positioning by transform or by cx,cy etc. I didn't implement any of those because the gains are relatively trivial.

Canvas

Second, SVG just can't move fast enough. Manipulating the DOM takes time, additional elements slows down operations and takes up more memory. I realize canvas can be less convenient from a coding perspective but canvas is faster than SVG for this sort of task. Use detached circle elements to represent each node (the same as with the paths), and transition these.

Save more time by drawing two canvases: one to draw once and to hold the paths (if needed) and another to be redrawn each frame showing the points. Save further time by setting the datum of each circle to the length of the path it is on: no need to call path.getTotalLength() each time.

Maybe something like this

Canvas Simplified Lines

Third, we still have a detached node that has SVG paths so we can use path.getPointAtLength() - and this is actually pretty effective. A major point slowing this down though is the use of curved lines. If you can do it, draw straight lines (multiple segments are fine) - the difference is substantial.

As a further bonus, use context.fillRect() instead of context.arc()

Pure JS and Canvas

Lastly, D3 and the detached nodes for each path (so we can use path.getTotalLength()) can start to get in the way. If need be leave them behind using typed arrays, context.imageData, and your own formula for positioning nodes on paths. Here's a quick bare bones example (100 000 nodes, 500 000 nodes, 1 000 000 nodes (Chrome is best for this, possible browser limitations. Since the paths now essentially color the entire canvas a solid color I don't show them but the nodes follow them still). These can transition 700 000 nodes at 10 frames per second on my slow system. Compare those 7 million transition positioning calculations and renderings/second against about 7 thousand transition positioning calculations and renderings/second I got with d3v3 and SVG (three orders of magnitude difference):

canvas A is with curved lines (cardinal) and circle markers (link above), canvas B is with straight (multi-segment) lines and square markers.

As you might imagine, a machine and script that can render 1000 transitioning nodes at 60 frames per second will have a fair bit of extra capacity if only rendering 100 nodes.

If the transition position and rendering calculations are the primary activity and CPU usage is at 100%, then half the nodes should free up roughly half the CPU capacity. In the slowest canvas example above, my machine logged 200 nodes transitioning along cardinal curves at 60 frames per second (it then started to drop off, indicating that CPU capacity was limiting frame rate and consequently usage should be near 100%), with 100 nodes we have a pleasant ~50% CPU usage:

Horizontal centerline is 50% CPU usage, transition repeated 6 times

But the key savings are to be found from dropping complex cardinal curves - if possible use straight lines. The other key savings are from customizing your scripts to be purpose built.

Compare the above with straight lines (multi segment still) and square nodes:

Again, horizontal centerline is 50% CPU usage, transition repeated 6 times

The above is 1000 transitioning nodes on 1000 3 segment paths - more than an order of magnitude better than with curved lines and circular markers.

Other Options

These can be combined with methods above.

Don't animate every point each tick

If you can't position all nodes each transition tick before the next animation frame you'll be using close to all of your CPU capacity. One option is don't position each node each tick - you don't have to. This is a complex solution - but position one third of circles each tick - each circle still can be positioned 20 frames per second (pretty smooth), but the amount of calculations per frame are 1/3 of what they would be otherwise. For canvas you still have to render each node - but you could skip calculating the position for two thirds of the nodes. For SVG this is a bit easier as you could modify d3-transition to include an every() method that sets how many ticks pass before transition values are re-calculated (so that one third are transitioned each tick).

Caching

Depending on circumstance, caching is also not a bad idea - but the front-ending of all calculations (or loading of data) may lead to unnecessary delays in the commencement of animation - or slowness on first run. This approach did lead to positive outcomes for me, but is discussed in another answer so I won't go into it here.

Answer 2

Post edit:

• Here is the default. (peak CPU around %99 for 100 points at 2.7Ghz i7)
• Here is my version. (peak CPU around 20% for 100 points at 2.7Ghz i7)

On average I am 5 times faster.

I presume the bottleneck here is the call to getPointAtLength method at every 17ms. I would also avoid lengthy string concatenations if I have to, but in your case its not much long so I think the best way:

• cache points beforehand and only calculate once with a given resolution (I divided here in 1000 parts)
• reduce calls to DOM methods within the requestAnimationFrame (that function you see receiving the normalized t parameter)

In the default case there is 2 calls, 1 when you call getPointAtLength, and then another one when you are setting the translate(under the hood).

You can replace the translateAlong with this below:

 function translateAlong(path){
    var points  = path.__points || collectPoints(path);
    return function (d,i){
        var transformObj = this.transform.baseVal[0];
        return function(t){
            var index = t * 1000 | 0,
                point = points[index];
            transformObj.setTranslate(point[0],point[1]);
        }
    }
}
function collectPoints(path) {
    var l = path.getTotalLength(),
        step = l*1e-3,
        points = [];
    for(var i = 0,p;i<=1000;++i){
        p = path.getPointAtLength(i*step);
        points.push([p.x,p.y]);
    }
    return path.__points = points;
}

And a small modification to that tweening line:

.tween("transform", translateAlong(path.node()))

setting attr is not necessary, calling it is enough. Here is the result:

http://jsfiddle.net/ibowankenobi/8kx04y29/

Tell me if it did improve, because I'm not 100% sure.