Move math portion of forceAtlas plugin to a WebWorker

[DavidBruant]

Resonates with this d3 issue.
ForceAtlas is a math-intensive algorithm. The whole point of it is gradually updating the screen so the user see the graph shaping (initially and when the graph is changed) and can interact with the graph before it's fully positioned. JavaScript in the browser is single-threaded so the math and the graphic rendering compete for the CPU.

The idea of this issue is moving the math away from the screen to a WebWorker. The math will be done in parallel in the WebWorker which will send updates to the main thread to update graphics.

Transferables enables quick message passing.

[jacomyal]

Agreed. If I understand well, Float32Array implements the Transferables Interface, and fits to manipulate the data required by ForceAtlas2 (already used for the WebGL renderer).

But what to do where the Transferables are not supported to deal with data?
@oncletom suggested to batch the FA2 steps, and to interpolate the nodes movement between two batches in the rendering thread.

[DavidBruant]

But what to do where the Transferables are not supported to deal with data?

Which browser supports WebGL but not transferables? ;-)

Transferables seem to be well-supported... hmm... after looking online, it looks like IE11 doesn't support it yet. Damned...
Well, it remains possible to send via normal messaging. It's possible it's worth it anyway. The rendering thread will have to pay the cost of deserializing, but it's probably much less than the cost of FA2 math.
Only experimenting and benchmarking will tell I guess.

@oncletom suggested to batch the FA2 steps, and to interpolate the nodes movement between two batches in the rendering thread.

I'm not sure I understand this part. In any case, in my experience using d3, if you just move a node x and y, if the delta is more than a few pixels, it results in a sluggish animation, so even for one step, it seems like nodes must be animated to their position (instead of being teleported there).
If nodes are animated to their position, when a new position is decided, just keep the animation going, but move the final destination.
Interpolation is useful only if the rendering is much faster than the FA2 steps (which results in the graph visually stopping and restarting when it has new positions). Another idea would be to make sure FA2 steps are never slow, like forcing to send a partial update every 100ms (or whatever arbitrary number).

I need to release a first version of OoI and after that, I'll be experimenting with moving FA2 math to a WebWorker with transferables (or feature detection and fallback for IE11). I'll report my progress here obviously.

[thom4parisot]

The suggested idea was to use Web Workers to continuously update the nodes position BUT to transfer from time to time the new positions + animating the movements with transitions.

The goal is to reduce the costs of the data transfer and the update computations.

Which is basically what you explained as

If nodes are animated to their position, when a new position is decided, just keep the animation going, but move the final destination.

Interpolation is useful only if the rendering is much faster than the FA2 steps (which results in the graph visually stopping and restarting when it has new positions). Another idea would be to make sure FA2 steps are never slow, like forcing to send a partial update every 100ms (or whatever arbitrary number).

[Yomguithereal]

This has been solved quite a long time ago since we have an efficient FA2 web worker now :)