Colliding N-body spheres: Particle Mayhem!

When Giants Collide — WGC for short — is one of the “fun” projects I am working on. Once finished, it will be a small in-browser simulator where you can collide giant planets together (with some degree of realism). You can see my progress on my GitHub repo and the series of blog posts under this category.

In this little demo app, you can run an N-body simulation in your browser where you make two spheres made of point masses “collide”. You can tweak various parameters (collision speed,  impact parameter, distance and number of particles) to change the outcome of the simulation.

Underneath it all: TreeSPH.js

The app above is powered by the portion of WGC’s code that computes the gravitational force between a set of point particles (a gravitational N-body system). The gravitational force is computed using the Barnes-Hut tree gravity algorithm, and the coordinates of the points are evolved using a third-order embedded Runge-Kutta algorithm. The code is available in the GitHub repo for WGC.

I am now working on writing the hydrodynamical part (via the SPH algorithm), which will let me simulate the collision between two gaseous spheres. The resulting library will be called treesph.js.

treesph.js will be an open-source JavaScript library able to power small-scale hydrodynamical simulations — either in the browser (through web workers), or within a JavaScript environment (e.g. Node.js). It comes with:

– a library to set up initial equilibrium conditions (e.g. Lane-Emden spheres, or N-body spheres with isotropic velocity dispersion);
– a canvas-based library to plot and animate the simulation snapshots;
– a fast library for operating on vectors and matrices that minimizes allocations and copying, and other math routines.

Performance notes

While playing with the app, you may be wondering (a) why there is a “buffering” stage before you can see the evolution of the system, and (b) why so few particles?

Buffering: it’s all about delayed gratification

The app animates the particle motion at 30 frames per second. This requirement places a hard and fast constraint: if you want to compute the particle motion at each frame request, then the computation must take less than 1/30th of a second, otherwise the webpage will freeze as the JavaScript engine tries to catch up with the accumulated frame requests. For reasonable number of particles (say, 100 or more — see below) and the time steps required by the above app, this requirement is way overshot.

This issue can be ameliorated by running the numerical computation in a separate thread (a web worker), and drawing frames on the main thread as soon as they are computed. This is still not as optimal: while it solves the UI freezing issue, the particle motion will appear very jerky as it will be animated at (typically) less than a frame per second!

In order to solve this issue, I created a small JavaScript library (streamingcontroller.js; available in the same GitHub repo, documentation upcoming). Streamingcontroller.js first estimates the expected wall time — the time in seconds — needed to complete the simulation. Then, within the web worker thread, it “buffers” the simulation snapshots by adding them to a pool of snapshots. Once the buffer is big enough that the simulation can be run in real time without hiccups, the library starts streaming the snapshots back to the main thread where the animation is drawn. In the main thread, a second buffer receives the snapshots; the second buffer is then emptied at 30 frames per second.

More particles, pretty please?

The default setting of the app is to animate 250 particles (125 per sphere). Why so few, when typical number of particles quoted for N-body simulations routinely exceed millions — or even billions! — of particles?

There are three bottlenecks at work. The first is obvious: the code isn’t fully optimized and profiled yet, and I am certain there is room for improvement. I am writing a small math library of common mathematical routines called math.js (also in the same GitHub repo) which will be fully optimized for V8.

The second is also obvious: simulations with lots of particles are usually run at full-speed, on multiple cores, and in the background. These simulations can save their snapshots, to be plotted and animated at the end of the run. An online app (or game) with real-time requirements (or, say, a <1 minute buffering time) doesn’t have this kind of luxury!

The third is the worst hurdle, and it is inherent to the nature of JavaScript: JavaScript is slow. I am not a JavaScript guru by any means, but I do have a good amount of experience writing performant numerical code in a variety of languages (mostly C). While JavaScript is typically fast enough for most tasks on the web, it is slow on personal computers and even slower on mobile platforms for physically-motivated, accurate simulations. In its present form, it is not well-suited to run these kinds of numerical tasks as quickly as the underlying hardware allows. Although JavaScript interpreters have been improving by leaps and bounds, and careful code can exploit some of these optimizations, they are hitting a wall of diminishing returns. Since JavaScript is the only runtime available on browsers, it is the ultimate bottleneck.

You can check out the other demos using code from WGC in this webpage.