Looking for ways to speed this up D3js and routing
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

We are rendering a floorplan and then allowing some mapping between 2 areas on the floorplan. we got this done using Dijkstra's and reimagined in js. While the results work, they are generally slow. On chrome its not too bad, we are seeing sub 3-4 second numbers, on iphone5 we are seeing just over 10 and on FF we are seeing anywhere from 15-25sec. so obviously we have a problem we need to think about, my target is mobile so asking someone to wait 10+ seconds to get directions between 2 points might be tough.

What I am looking for on this bounty and I am very willing to tip is some suggestions w/proof on how to speed this thing up a lot.

Here is the link to the run time, nothing is minified so it should be viewable from there. In FF you will likely get some js warnings about the script pointing to you underscrorejs line 79, there appears to be a large foreach statement there.

http://quotient.github.io/D3_Floorplan/?from=1703&to=1603

Something you can try is including only minified versions of your javascript.
alv-c 4 years ago

Crowdsource coding tasks.

4 Solutions


The algorithm is fine. Your problem is just with SVG loading. It uses like 80% of your loading time in Chrome. Check the Developer Tools timeline: http://i.imgur.com/Ggqge73.png

Your best shot is improving your SVG, maybe reducing the number of elements.

The issue falls really in creating the route path for the nearest path to run. The time and latency is in creating that. So I think in need minds focused on that specifically. If you drop the query path and just load the map its really fast
Qdev 4 years ago

Very similar to what @iurisilvio said, the SVG is to blame for a lot because from my tests it's the SVG rendering that's taking up the majority (50-80%) of the loading time, but the mapping also took a long time. But you probably already knew that. So nothing was really accomplished in telling you that. The real question is how to fix it. I'm going to split this up into two parts, the SVG part and the mapping part.

SVG

Due to the nature of SVG, a lot of time is spent in browser just rendering the SVG, and every time you pan or zoom, the browser has to re-render the SVG. Sure, this may not be a problem after the path has been drawn, but you should probably fix it either way. There are two ways to attempt to fix this (okay, three, but the third way is a combination of both ways): using canvas (it's wayyyy faster, I guarantee you!), simplifying your diagram, or both…

Firstly, using canvas is a GREAT idea here because canvas can take advantage of hardware acceleration among other things, though it does take quite a bit of code to get working.

If canvas is not an option, then use SVGs with less paths (though this might not be possible in your situation). The less paths there are, the less rendering takes place, and the less calculations are needed.

Finally, if you can switch to canvas, you should probably also try to simplify your map (or at least split it into chunks).

Mapping

I see nothing wrong with the way the paths are calculated, but there's just so many elements in your map that slows it down. My only advice is to lower the amount of elements.

Final Thoughts

In the end, although switching to canvas and using less elements will cut down the rendering time it is probably not a good idea because you're going to write a lot more code. If I was in this situation, I would try to process this stuff through a server and then spit the data out to the client.


Don't have enough time to try anything but here are some suggestions:

A* search algorithm
Instead of using Dijkstra's algorithm use its extension, A*, which achieves much better time performance by using heuristics. I suggest using the Manhattan distance as the heuristic function h(x).

Divide and conquer
Find the halfway point between start and end, and calculate the shortest paths from start to middle and from middle to end.

Server-side computing
Calculate the shortest path server-side so that your site's performance is independant of the user's processing power or javascript engine.

Precomputing
Precompute the shortest paths between each pair of nodes using Dijkstra's algorithm so you don't have to do it on each request. This would be more suitable if you had fewer nodes. You have 718 nodes, which gives us 718!/(2!*716!)=257403 unique pairs.

Tom - how can I contact you direct on this?
Qdev 4 years ago
Through the "Contact" tab in my profile.
tomtoump 4 years ago

First of all, I ran some tests (repeatedly) and these were the timing results I got:

Android 2.2.1
-------------
http://quotient.github.io/D3_Floorplan/                  = ∞ (failed to render)

Android 4.1.1
-------------
http://quotient.github.io/D3_Floorplan/                  = 9s
http://quotient.github.io/D3_Floorplan/?from=388&to=2621 = 38s

Firefox 22.0 (no Cache)
-----------------------
http://quotient.github.io/D3_Floorplan/                  = 2s
http://quotient.github.io/D3_Floorplan/?from=388&to=2621 = 3s

Chromium 28.0.1500.71 (no Cache)
--------------------------------
http://quotient.github.io/D3_Floorplan/                  = 1s
http://quotient.github.io/D3_Floorplan/?from=388&to=2621 = 2s

I chose the booths 388 and 2621 because the pathway is more expensive to generate.


While the Dijkstra's algorithm is extremelly slow on Android, the D3/SVG performance is still not negligible on my mobile hardware - I would expect the experience to be way smoother on iOS however. Regarding the rendering, I suggest you read this Google Groups discussion that goes a little bit into the whole SVG/Canvas debate - the bottom line I take from it is that canvas is not necessarely faster than SVG and that the performance of the whole thing highly depends on the client implementation and hardware accelaration support as well as what you're doing with it (resizes and orientation changes are specially harder on SVG - altought, in this specific case, that doesn't seem to be a problem on Android 4.1.1).

As for the Javascript code, after looking for a while at booth.js, a couple of things caught my eye. It seems to me that there are a lot of optimizations that could be made, specially in the code that get executed in loops. I haven't spend a whole lot of time examining, but:

  1. do you need to define zoom() inside the selection.each() callback of chart()?
  2. in chart(), chart.search(), chart.drawPath(), chart.updateBooth(), chart.updatePlan() is it necessary to define div, divSize (among others) in the selection.each() callback?
  3. the D3 helper attr() (and some others too) is called at least twice per each SVG element, I'm wondering if doing jQuery.attr({width: x, height: y}) once wouldn't benefit performance

These Google talks shed lots of insight into Javascript (specially V8) optimization:

This SlideShare presentation on Javascript performance also has some great and concrete examples - most are very easy to refactor - on how to improve the execution speed of your code. Granted, not all those follow the DRY principle, but that's a price you sometimes have to pay in order to achieve maximum performance.

Here's what the Chromium CPU Profiler tab shows with ?from=388&to=2621:

CPU Profile

Seems like chart.pathSearch() and chart.pathSearchStep() are the slowest methods of your code, however they seem to be very well implemented already. Have you considered using the A* algorithm instead of Dijkstra's? While googling around, I found PathFinding.js, which is a awesome Javascript (both server-side and client-side) library that has superb implementations of several path-finding algorithms - one of them being A*. You can find a (deliberately slowed down) demo here that lets you define input/output/obstacle points and tells you how many operations it needed to find the shortest path using the algorithm you chose.

One other option you may want to consider (either with A* or Dijkstra's) is making a Ajax call to the server with the input/output booth IDs as well as the map ID or matrix (which would obviouslly take longer to send) and have the server compute the shortest path and return it to the client.

Also (this goes without saying) but when you go into production, you should combine and minify all your Javascript files (and serve them gzipped as well). Google's Closure Compiler is a favourite of mine, it lets you merge all the Javascript code with awesome minification results (specially if you can afford to tick the advanced optimizations option).

Aside from code minification, Closure Compiler will also try to optimize (via variable interpolation for instance) your code - but only if the optimization doesn't make the filesize bigger.

View Timeline