Category: programming

A Barnes-Hut tree gravity benchmark

In one of my last posts (An interactive Barnes-Hut tree) I talked briefly about one of the “fun” projects I’m working on, When Giants Collide (work in progress, GitHub repo), and promised myself to blog about its development as I went along. I just finished refining the algorithm for building the tree and calculating the gravitational force.

The small app above is a benchmark pitting the Barnes-Hut algorithm for computing gravity (an O(N log(N)) algorithm) against a brute-force direct summation (an O(N^2) algorithm). It calculates the gravitational field of a random collection of particles using both methods for N = 256 to N = 16,384; a lower amount of time spent indicates a faster algorithm. The time used to compute the gravitational force is averaged over 12 iterations to minimize fluctuations. Results are plotted in real time.

Lastly, it calculates an overall “score” for the JavaScript interpreter by only running the Barnes-Hut algorithm for N = 16,384. You can see a table of scores for a few different browsers and devices I have access to (lower is better). If you’d like, send me your score!

Some observations about JavaScript optimization

Chrome turned out to be the fastest browser at this particular benchmark. Surprisingly, a previous version of the same code was actually the  slowest on my MacBook — almost 6x as slow as Safari! That was quite unexpected, as in my (limited) experience building web apps Chrome tends to edge out other browsers in terms of JavaScript execution speed.

So I waded a little bit more into my code to understand what was making my code so inefficient. This Google optimization guide and this post on HTML5Rocks (specifically talking about optimizing for V8, the just-in-time compiler embedded in Chrome) proved very useful. What I learned:

  1. Use the idiomatic JavaScript style for creating classes (using prototypes, new, straightforward constructors etc.) instead of using an object factory and closures.
  2. Avoid creating closures, when possible.
  3. Use node.js to profile the application and identify functions that are not getting optimized (using –trace-opt).
  4. Both Safari and Firefox had good baseline scores even before these optimizations. I found it quite surprising that V8 was much more fastidious about my code than the other JavaScript engines.

Another finding was how much slower alternative browsers (e.g. Chrome, Mercury) are on iOS. Alternative browsers use the same engine as Safari, but they don’t have access to Nitro’s Just-In-Time compilation — this means that they will be quite a bit slower than Safari on a computationally-intensive benchmark. How much slower? On my iPhone 5S, almost a factor of 10!

Web workers are awesome

The benchmark runs in a different thread, so that the page itself remains responsive. This is accomplished using Web Workers, a relatively new technology that allows the page to spin off threads to do computation-heavy work. It’s quite well supported, and I found it pretty easy to learn (aside from some surprising quirks). I plan on spinning off some of the tasks in Systemic Live — which currently either block the interface or use timers — into Web Workers (it’ll be a quite a bit of work, so don’t hold your breath).

AstroBetter: Creating Online Apps for Outreach and Education

I wrote a short article on AstroBetter called “Creating Online Apps for Outreach and Education” about some of the tools and resources I use for my online work.

Chrome developer tools + js2-mode and web-mode in EmacsChrome developer tools + js2-mode and web-mode in Emacs

I’ll be blogging more about this topic in the short term, but here are a few things I’ve been looking at that people might find interesting:

  • Languages that convert to JavaScript: I find the constant context switching between the different programming languages I use for my work very annoying. I’ve used Emscripten for converting my C code into JavaScript to minimize the amount of code rewriting. I’m actively looking at languages that compile to JavaScript — the most famous is probably CoffeeScript, but I’m keeping an eye out for Kotlin. Kotlin is a budding language that primarily runs on the Java Virtual Machine (JVM), but can also be compiled to JS. Since I do use Java and the JVM ecosystem for a substantial amount of my code, it looks very promising. Now, if only there was a kotlin-mode for Emacs I’d be very happy 🙂
  • Three-dimensional visualizations: three.js looks cool but daunting. I’ve been trying to think of a small project to do using the isometric engine Obelisk.js — I’m just enamoured with things that look retro.

Cogito.org, a magazine for young students interested in science, published a short interview with me about how I came to be an astronomer, and why I developed Super Planet Crash. Read it here!

An interactive Barnes-Hut tree

[TL,DR: if you’d like to play with a simple Barnes-Hut octree code, scroll down to the little embedded app.]

Gah! It’s been quite a while since my last post. Despite my best intentions, work (and a lot of feedback from Super Planet Crash!) has taken precedence over blogging. I do have a sizable list of interesting topics that I’ve been meaning to write about, however, so over the next few weeks I’ll try to keep to a more steady posting clip.

Super Planet Crash has been a resounding success. I have been absolutely, positively astounded with the great feedback I received. My colleagues and I have been coming up with lots of ideas for improving the educational value of SPC, add new, interesting physics, and addressing some of the complaints. In order to have the ability to dedicate more time to it, over the past few months, we’ve been furiously applying for educational and scientific grants to fund development. Hopefully something will work out — my goal is to make it into a complete suite of edu-tainment applications.

When Giants Collide

I’ve recently started experimenting with a new  visualization that I think will turn out pretty darn cool. Its draft name is When Giants Collide. When  Giants Collide will address a common request from planetary crashers: “Can I see what happens when two giant planets collide”?

A sketch of the interface.

When Giants Collide will be a super-simple JavaScript app (so it will run in your browser) that will simulate the collision of two massive spheres of gas. The simulation will have to model both gravity and the dynamics of the gas: to address this, I’ve been dusting off and reviewing an old Smoothed-Particle Hydrodynamics (SPH) code I worked on for a brief period in graduate school. SPH is a very simple technique for cheaply simulating gas flows with good spatial accuracy, and is somewhat straightforward to code. There are some shortcuts that have to be taken, too — large time steps, low particle counts, and more (e.g., a polytropic equation of state for the gas giants; more on this in future posts). These shortcuts come at the expense of realism, but will enable fast, smooth animation in the browser.

Gravity with the  Barnes-Hut algorithm

Gravity is an essential ingredient of When Giants Collide! Even with very low particle counts (say, N = 1000), a brute force calculation that just sums up the mutual gravitational force between particles won’t do if you want to run the simulation at 60 frames per second. Direct summing is an N^2 operation:

(this is a simple force accumulator written in R).

A better way that involves only a slightly more complicated algorithm is to use the Barnes-Hut algorithm (a short Nature paper with more than 1,000 citations!). The algorithm involves recursively subdividing space into cubes and loading them with particles, such that every cube contains either 0 or 1 particles. This is represented in code with an oct-tree structure.  Once such a tree is constructed, one can calculate the gravitational force on a given particle in the brute-force way for close particles, and in an approximate way for distant particles; whether to use one or the other is determined by walking the tree down from the top. An excellent explanation (with great visuals!) is provided in this article.

The other advantage is that, once the tree has been already built for the gravity calculation, it can be used to identify the nearest neighbors of a given particle through the same tree-walking procedure. The nearest neighbors are needed for the hydrodynamical part of the SPH algorithm (see, e.g., this review article by Stefan Rosswog or this one by Daniel Price).

An interactive tree

Below is an interactive JavaScript applet that subdivides space with the Barnes-Hut algorithm. You can add new points by clicking on the surface, or using the buttons to add new, random ones.

The code for building the Barnes-Hut tree from an array of 3D positions is available at the GitHub repository for When Giants Collide. I will be developing the code in the open, and post periodically about my progress. Hopefully by the end of summer I will have an attractive app running on any modern device and web browser. Any ideas on how to gamify it?

Two useful tools: git-flow and git-gutter+

This is just a quick post linking to two very useful tools I just started incorporating into my workflow.

The first is git-flow. Git-flow gives a very nice structure to feature development using git: it imposes some discipline on branching and committing features to the “master” branch, while also providing a very helpful branching naming scheme and a clear path from developing a feature to incorporating it into a release. This post gives a clear overview on how to get started with it.

Fringe Git indicators in Emacs.
Fringe Git indicators in Emacs.

The second is an Emacs package called git-gutter+ (in its “fringe” flavor). It lets you view Git changes directly from the current buffer (the graphical symbols in the fringe shown in the screenshot). Install it from the package manager (MELPA) and add to one of your .el initialization scripts.

Link: Why I’m betting on Julia

Evan Miller: Why I’m betting on Julia

Julia looks to me like a very promising programming language.  Its main appeal is bringing C-like speed to a high-level, well-designed language that is tailored to scientific computation. From the article:

I hesitate to make the comparison, but it’s poised to do for technical computing what Node.js is doing for web development — getting disparate groups of programmers to code in the same language. […]

If you work in a technical group that’s in charge of a dizzying mix of Python, C, C++, Fortran, and R code — or if you’re just a performance-obsessed gunslinging cowboy shoot-from-the-hip Lone Ranger like me — I encourage you to download Julia and take it for a spin.

The “dizzying mix” is very much how I would describe a lot of the code I use and write on a daily basis.  R is too slow for intensive computations, so I drop down to C to write most of my algorithms and then wrap the C code in a higher-level R interface (via FFI); a similar state of affairs exists for Python. Getting communication right between the two worlds (the low-level C and the high-level language) can be daunting, and frankly, the mental context switch is exhausting. (Let’s not even bring Fortran into the discussion.)

I really hope Julia will succeed. What it needs right now is a first-class plotting facility and a bit more widespread adoption, but once that is achieved, I think that Julia will be a serious contender for mindshare.

You gotta get a gimmick: BAM

BAM is a new, extremely lightweight templating system that converts files containing a mixture of code, metadata and text and produces a plain text file. We use a fully-featured version of BAM as an “automated paper writer” in my research group at UC Santa Cruz. A short guide to BAM is available here.


BAM was born out of my conversations with Greg Laughlin on how to automate the somewhat repetitive task of writing certain types of scientific papers and reports. Since we already had a planet discovery tool at our disposal, we decided to focus on planet discovery papers. In its full version, BAM is deeply integrated with the Systemic Console to produce first drafts of planet discovery papers from a reusable template, with the aim of automating as much as possible the writing of the abstract, introduction and quantitative analysis. The Console-integrated BAM has some cool NLG features that we used to write Meschiari et al., 2011 (discovery of HD31253b, HD218566b, HD177830c, HD99492c). Since these planets are somewhat unremarkable, this paper lent itself well to automated writing of the majority of the text. Ideally, BAM templates evolve to contain enough logic to be able to “comment” on the data it processes; for instance, it could write a few remarks about the distribution of the newly discovered planets in period-eccentricity and period-mass plots, such as the one to the right (where the dots are automatically downloaded from the Extrasolar planet encyclopaedia and placed on the plot by BAM, as well).

Following the spirit of literate programming, the paper template contained the procedure for the data analysis, fitting, error estimation and all the plots intermingled with the LaTeX layout and fragments of text. I presented this tool at the European Science Foundation conference (presentation in Keynote format), including a somewhat humorous video of the Console discovering, analyzing and publishing four planetary systems in real time based on the directions of the paper template (see video at Greg’s website). It’s become one of my favorite gimmicky (but useful) tools to show off to people.

While we keep the Console-integrated BAM version private for use by our team, I am making a rewritten and simplified version, available to download now. You should consider this a preliminary 0.1 version and expect bugs and limitations to crop up; features will be added back in future revisions.