javascript - 'Point-along-path' d3 visualization performance issue - Stack Overflow

admin管理员组

文章数量:1279008

I have gone through the 'point-along-path' d3 visualization through the code: . 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.

I have gone through the 'point-along-path' d3 visualization through the code: https://bl.ocks/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.

• javascript
• performance
• d3.js
• transition

Share Improve this question Follow edited Sep 12, 2018 at 8:49 Sarthak Saxena asked Sep 12, 2018 at 5:52 Sarthak SaxenaSarthak Saxena 11722 silver badges99 bronze badges 1

• I want to reduce the CPU usage while the transition of points is happening. – Sarthak Saxena Commented Sep 12, 2018 at 6:58

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 10

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 plex 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 bined 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 plex 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 mencement of animation - or slowness on first run. This approach did lead to positive outes for me, but is discussed in another answer so I won't go into it here.

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/ibowankenobi/8kx04y29/

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

Another way of achieving this might be to use an svg:animateMotion which you can use to move an element along a given path. Here is an example from the docs. In essence you want:

<svg>
  <path id="path1" d="...">
    <circle cx="" cy="" r="10" fill="red">
      <animateMotion dur="10s" repeatCount="0">
        <mpath xlink:href="#path1" />
      </animateMotion>
    </circle>
  </path>
</svg>

I've not profiled it, but I think you're struggle to get much better performance than using something built into SVG itself.

Browser Support

Note that after a ment from @ibrahimtanyalcin I started checking browser patibility. Turns out that this isn't supported in IE or Microsoft Edge.

On my puter:

• @mbostock uses 8% CPU.
• @ibrahimtanyalcin uses 11% CPU.
• @Ian uses 10% CPU.

For @mbostock and @ibrahimtanyalcin this means the transition and the transform update use the CPU.

If I put 100 of these animations in 1 SVG I get

• @mbostock uses 50% CPU. (1 core full)
• @Ian uses 40% CPU.

All animations look smooth.

One possibility is to add a sleep in the transform update function using https://stackoverflow./a/39914235/9938317

Edit

In the nice Andrew Reid answer i have found a few optimizations.

I have written a version of the Canvas+JS 100 000 test that only does the calculation part and counts how many iterations can be do in 4000ms. Half the time order=false as t controls it.

I have written my own random generator to be sure that I get the same random numbers each time I run the modified code.

The blocks version of the code: 200 iterations

According to the docs for parseInt

parseInt should not be used as a substitute for Math.floor()

Converting a number to a string and then parsing the string up to the . sounds not very efficient.

Replacing parseInt() with Math.floor(): 218 iterations

I also found a line that has no function and looks not important

let p = new Int16Array(2);

It is inside the inner while loop.

Replacing this line with

let p;

gives 300 iterations.

Using these modifications the code can handle more points with a frame rate of 60 Hz.

I tried a few other things but they turn out to be slower.

I was surprised that if I pre-calculate the lengths of the segments and simplify the calculation of segment to a mere array lookup it is slower than doing the 4 array lookups and a couple of Math.pow and additions and a Math.sqrt.

本文标签： javascript39Pointalongpath39 d3 visualization performance issueStack Overflow