Blog

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?

The Automated Planet Finder, Systemic and Super Planet Crash

[This short article I wrote has been published on The Conversation UK.]

The following is a short article about the Automated Planet Finder, Systemic and Super Planet Crash. We recently announced the first batch of exoplanets that were discovered in the first few months of science operation of APF. The first two systems (HD141399 and Gliese 687) have been submitted and will be available on astro-ph shortly.

Telescope apps help amateurs hunt for exoplanets


Laurie Hatch

People around the world are being invited to learn how to hunt for planets, using two new online apps devised by scientists at the University of Texas at Austin and UC Santa Cruz.

The apps use data from the Automated Planet Finder (APF), Lick Observatory’s newest telescope. The APF is one of the first robotically operated telescopes monitoring stars throughout the entire sky. It is optimised for the detection of planets orbiting nearby stars – the so-called exoplanets.

Systemic is an app that collects observations from APF and other observatories and makes them available to the general public. Anyone can access a simplified interface and follow the steps that astronomers take to tease a planetary signal out of the tiny Doppler shifts collected by the telescope.

Students and amateurs can learn about the process of scientific discovery from their own web browsers, and even conduct their own analysis of the data to validate planet discoveries.

The second app, SuperPlanetCrash, is a simple but addictive game that animates the orbits of planetary systems as a “digital orrery”. Users can play for points and create their own planetary systems, which often end up teetering towards instabilities that eject planets away from their parent stars.

First catch

Despite only being in operation for a few months, APF has already been used to discover new planetary systems.

Night after night, the telescope autonomously selects a list of interesting target stars, based on their position in the sky and observing conditions. The telescope collects light from each target star. The light is then split into a rainbow of colours, called a spectrum. Superimposed on the spectrum is a pattern of dark features, called absorption lines, which is unique to the chemical makeup of the star.

When a planet orbits one of the target stars, its gravitational pull on the star causes the absorption lines to shift back and forth. Astronomers can then interpret the amplitude and periodicity of these shifts to indirectly work out the orbit and the mass of each planet.

This method of detecting exoplanets is dubbed the Doppler (or Radial Velocity) technique, named after the physical effect causing the shift of the absorption lines. The Doppler technique has been extremely productive over the past two decades, leading to the discovery of more than 400 planet candidates orbiting nearby stars – including the first exoplanet orbiting a star similar to our own Sun, 51 Pegasi. To conclusively detect a planetary candidate, each star has to be observed for long stretches of time (months to years) in order to rule out other possible explanations.

The APF has now found two new planetary systems surrounding the stars HD141399 and Gliese 687.

HD141399 hosts four giant, gaseous planets of comparable size to Jupiter. The orbits of the innermost three giant planets are dramatically more compact than the giant planets in our Solar System (Jupiter, Saturn, Uranus and Neptune).

Gliese 687 is a small, red star hosting a Neptune-mass planet orbiting very close to the star: it only takes about 40 days for the planet to complete a full revolution around the star.

Team leader Steve Vogt of the University of California, Santa Cruz has dubbed both of these almost “garden variety” planetary systems, and indeed, they are quite similar to some of the systems discovered over the last few years. However, what look like distinctly unglamorous planetary systems now can still pose a puzzle to scientists.

The new normal

The planetary systems discovered so far are typically very different from our own solar system. More than half of the nearby stars are thought to be accompanied by Neptune-mass or smaller planets, many orbiting closer than Mercury is to the Sun. In our solar system, on the other hand, there is a very clear demarcation between small, rocky planets close to the Sun (from Mercury to Mars) and giant planets far from the Sun (from Jupiter to Neptune). This perhaps suggests that planetary systems like the one we live in are an uncommon outcome of the process of planet formation.

Only further discoveries can clarify whether planetary systems architected like our own are as uncommon as they appear to be. These observations will need to span many years of careful collection of Doppler shifts. Since the APF facility is primarily dedicated to Doppler observations, it is expected to make key contributions to exoplanetary science.

The two apps produced by the APF team make amateur scientists part of the hunt. These applications join the nascent movement of “citizen science”, which enable the general public to understand and even contribute to scientific research, either by lending a hand in analyzing massive sets of scientific data or by flagging interesting datasets that warrant further collection of data.

The Conversation

2,000,000 systems played!

The high scores as of April 13, 2014 for all of posterity. Good job, brave folks.!
The high scores as of April 13, 2014 for all of posterity. Good job, brave folks!

This week has been quite the ride. Super Planet Crash has been featured on io9, Huffington Post, space.com, Motherboard, and other online publications, and it “suffered” from repeated surges of traffic from imgur. Not bad for a game hacked together over the weekend! It overjoyed me to receive emails, and pictures!, by people enjoying the game, especially from the younger generation.

More than 2,000,000 games have been played as of today, and hopefully a fraction of those players will want to know more about exoplanets. I would also encourage everyone who enjoys this little free game to donate to science education funds, such as McDonald Observatory’s Science Education Fund. I would be oh so happy to have bragging rights due to planet crashers donating en masse!

I’m slowly trying to work through some of the feature requests. Not all are feasible on a short timescale (science is my full-time job, after all!), but I will strive to at least try to address the lowest-hanging fruit. One pet peeve shared by many was the inability to see the high-scoring games. In trying to address this, I discovered two bugs in the implementation of the high-scores.

The first is that the server relied too much on trusting the high-scores that were sent from the client (i.e. the Javascript running in the web-browser). Although I had tried to mitigate it somewhat, several fake high-scores were submitted. I added some stricter checks that should further help address the problem. The right solution would be to run the system on the server in order to check for any shenanigans. Unfortunately, this is unfeasible, as too many games are being played: it would place an unduly amount of stress on my server.

The second is a bug in the way systems were recorded and sent to the server. Some of the highest-scoring systems attempt to score high on masses, “crowdedness” (how close are the orbits of the bodies to each other) and habitability. They do that by (a) adding a binary companion (the “dwarf star”) and (b) putting a lot of planets in the same orbit within the habitable zone.

 

Something like this.
Something like this.

The resulting systems are likely highly chaotic, so any small error in recording the state of the system [ref]The state of the system being the current position and velocity of each body.[/ref] will change the outcome very quickly (the so-called “butterfly effect“). Unfortunately, one bug in Super Planet Crash resulted in this exact scenario happening. Any rounding or truncation of the floating point values for the coordinates will also affect the evolution of the system. The most common outcome is that these high-scoring systems will appear to be unstable when replayed. Grrr.

The decision I reached is to clean up the high-score table. The systems should now be recorded the correct way, and everyone will be able to see how the scores were achieved.

I understand this is sad news for the current record holders, so the screenshot at the top of this page will record the brave folks who reached upwards of 300,000,000 points for all posterity. (Just imagine someone unplugged the arcade machine by mistake…)

Next up on my agenda is releasing the game on GitHub. I am cleaning up the last few bits. If you are a programmer, you’ll be able to create pull requests for new features there.

In my next post, I will go into a bit more detail about how I created Super Planet Crash (and so can you!).

Go Crash Some Planets!

Super Planet Crash
A screenshot of Super Planet Crash playing in Safari

 

♥ If you enjoyed playing Super Planet Crash, please consider donating to the Science Education Fund at McDonald Observatory. Every little bit counts. Go support science!

Update 2: 2,000,000 systems were created!
Update: Systemic and Super Planet Crash were featured on io9, Space.com, GlobalNews, Motherboard, Huffington Post, The Verge, and two press releases by UC Santa Cruz and McDonald Observatory. Thank you!

Super Planet Crash is a little game born out of some of my work on the online version of Systemic. It is a digital orrery, integrating the motion of massive bodies forward in time according to Newtonian gravity. It works on any recent web browser and modern tablets.

The main goal of the game is to make a planetary system of your own creation be stable (i.e. no planet is ejected, or collides with another body). This is of course exceedingly easy when your system comprises of a few Earth-mass planets, but dynamical instability can quickly set in when adding a lot of heavier bodies (from giant planets, all the way to stellar companions).

The challenge is then to fit as many massive bodies as possible inside 2 AUs (twice the distance between the Earth and the Sun), teetering close to instability but lasting at least 500 years. Accordingly, the game rewards a daring player with more points (proportionally to the mass of each body added to the system). A few simple rules are listed under the “Help” button.

The game always starts with an Earth-mass planet in a random location, but you can also have fun overloading known planetary systems! Clicking on the “Template” dropdown brings up a list of planetary systems to use as starting templates, including the compact system Kepler-11 and the super-eccentric planet HD80606 (more systems to come). You can even share your creations with your friends by copying the URL in the “Share” box.

The game is open-source, and still under active development. The entire code will be downloadable from GitHub (as soon as I get a bit of work done!).In the near future, I will be adding integration with Systemic Live, a longer list of template planetary systems and smartphone support. In the meantime, have fun crashing planets!

Credits

The game was made possible by the wonderful paper.js library, which let me quickly prototype the app despite having little experience in web gaming. The palette draws from the base16 color set.

Many many thanks to my wonderful testers: Rachael Livermore, Mike Pavel, Joel Green, Nathan Goldbaum, Maria Fernanda Duran, Jeffrey Silverman, Angie Wolfgang, and other cool people.

My work is funded by the W. J. McDonald Postdoctoral Fellowship. If you enjoyed the game, please donate to the McDonald Observatory fund to support science education.

Funniest Software Bugs

This is a cute collection of fun software bugs from Michael Tsai’s blog: Funniest Software Bugs.

I incidentally enjoyed learning about the units shell command, a useful utility to convert between units from the command line:

stefano ~$ units
586 units, 56 prefixes
You have: 100 feet/s
You want: km/hr
	* 109.728
	/ 0.0091134442
You have: 30 J/yr
You want: erg/s
	* 9.5066294
	/ 0.10518975

(Its man page informs me that it cannot convert Celsius to Fahrenheit, since it can only handle multiplicative scale changes: boo!).  And what the heck is a fathom?