Friday, June 6, 2008

SVG "Rule 30" Denial-of-Service

With my brain jammed in neutral the other day, I decided to implement a little program that I thought would be interesting, quick, and capable of knocking me into a productive mental gear. I got more than I bargained for.

What I implemented was Stephen Wolfram's "rule 30" one-dimensional cellular automaton, using SVG for the graphics, and Javascript for the logic. Between the innate simplicity of the automaton, and the fact that this implementation is only 192 cells wide, this program is computationally insignificant. Nonetheless, if you make the mistake of clicking in the display area below to start it running, it will bring Safari 3.1.1, Firefox and Firefox 3.0 to their knees. Their CPU utilization hits 100%, and they are rendered almost, or completely, unresponsive either immediately, or once the first 192 rows have been generated and scrolling is supposed to commence. In principle, clicking on the display area again should stop this program, but Firefox is so stuck it seems to respond to nothing but a forced quit. Firefox 3.0 will eventually respond, but it can take minutes. Safari 3.1.1 is more responsive than that, but still very bad.

If your browser supports the Scalable Vector Graphics (SVG) standard, you'll see the Rule 30 one-dimensional cellular automaton here. Otherwise, it's time to upgrade to a modern browser like Safari or Firefox.

This program does not try to consume all available CPU cycles. As mentioned earlier, it is computationally insignificant. It is also rate-limited to 24 updates per second. So, the varying speeds of the Javascript interpreters shouldn't make much, if any, difference to performance. However, I have yet to find a browser that can manage more than about three updates per second once the display fills and scrolling commences. This seems to be either a problem with their DOM implementations in general (a full display of 192 rows will typically be composed of about 9,200 rectangles, each one a DOM object), or their SVG implementations (which build on the DOM implementation), or both. In the context of modern computing power, it's hard to take seriously the idea that handling 9,200 essentially static graphics objects (and simple rectangles, at that) should be a problem, but for one reason or another, that is the case.

The only browser I've tested that handles this program at all gracefully is WebKit, in its most recent nightly builds. (WebKit is the open-source browser engine on which Apple's Safari browser is built.) Although the WebKit team announced earlier this week that they've replaced their Javascipt engine with a new one named "SquirrelFish" that is substantially faster than its predecessor, due to the computational simplicity of this program, I doubt that SquirrelFish is the reason for WebKit's better performance relative to the other browsers. I continue to think that DOM and/or SVG implementations are the key to this program's performance, or lack thereof.

Congratulations (seriously) to the WebKit team for having created by far the best browser I've tested, but, as far as this little program is concerned, there's still a lot of room for improvement.


  1. Anonymous8:16 AM CDT

    I tried this on Opera 9.51 on Leopard and it was noticeably smoother and faster than Safari.

  2. In light of the previous comment, I tried this with Opera 9.52 on Mac OS X 10.5.4. Opera manages to fill the screen much faster than Safari (so does Firefox 3) provided that the output is NOT surrounded by that blue border. Being new to Opera, I don't know what that blue outline signifies, or does, but I'll refer to it as a selection box, for lack of a better term. So, if the selection box is present, Opera's performance during the initial screen-filling phase is very poor. Strangely, the exact opposite is true when the output reaches the bottom of the display and new rows of output are added at the bottom by scrolling-up everything else. When the selection box is PRESENT the performance is on par with Safari 4 (AKA the WebKit nightlies), which means that relative to other browsers, it's best-of-breed. (Though there's still ample room for improvement.) However, when not selected, the scrolling output is very slow - about five seconds per line in my tests. Safari 4 does not have this strange modal behavior, so it's still the reigning champion relative to all of my SVG/Javascript programs.

    An additional issue is with Opera's Javascript support - it doesn't appear to allow function invocation chaining, and therefore can't run some of my SVG/Javascript programs (notably Clock 3) that Firefox and Safari can run without difficulty.

    All in all, I'd characterize Opera 9.5.2 as having a lot of potential, but also a number of significant problems, and/or weird behaviors.