[Updated on March 2021 with new devices!]
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. Try to toggle the logarithmic axis to see the actual difference between an $O(N^2)$ and an $O(N \log N)$ algorithm!
Scores (lower is better)
|Device||Running on||Score||Relative to MacBook Pro, 2012, Chrome 36|
|MacBook Air (M1, 2020), 11.2.3||Safari 14.0.3||5,275||0.36x|
|MacBook Pro (Retina, late 2012), 10.9.4||Chrome 36||14,641||1.0x|
|iPhone 5S, 7.1.2||Safari||63,841||4.4x|
|Mercury (no JIT)||561,033||38.3x|
|iPhone 5C, 7.1.2||Safari||147,141||10.0x|
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:
- Avoid creating closures, when possible.
- Use node.js to profile the application and identify functions that are not getting optimized (using --trace-opt).
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).