I love Firefox 3.6 loves Workers

This post is late (of course), but I wanted to put in a plug for Firefox 3.6. Tremendous, tremendous work has been done since 3.5 and it all shows. In many ways the drumbeat doesn’t even need to be codified or pushed, as it’s so easy to get swept up in the passion the Mozilla community has for improving the web. My favorite part of witnessing Firefox development is probably the transparency, both in Bugzilla and in blogs, where developers and engineers can say whatever they think is important in the ongoing elucidation of the open web, consequences be damned (and it’s reactions to posts like that that demonstrate how much the rest of the world needs to learn on how to engage in an open dialogue). Congratulations to everyone involved in the new release.

But enough about other people. Most importantly, my Twitter campaign for improving TraceMonkey performance in Web Workers has clearly paid off (actual events might not reflect that statement). 3.6rc1 showed nearly identical performance for gwtBox2d running in a page’s main loop as in a Worker script, and this has carried on through to the final release. I also haven’t had any crashes running any demos (yet), which were caused (I think) by an OOM from the tracing engine. The performance increase due to parallel execution isn’t quite what I was hoping for, but I need to build in some more sophisticated profiling hooks to see what exactly is going on. Also, as fun as Canvas is for some things (and I’m working on some pixel manipulation ideas that are actually suited for the format), the way I’m using it now is much better matched with something like SVGWeb or Raphael(js). I only wish the bindings already existed.

I’ve also been racing to put together some ideas I had on making Web Workers easy to use in any GWT project. That code is finally reaching a usable state and I’ve had the pleasure of learning far more about Generators, Linkers, and the GWT compiler than I thought I would ever have the impetus to. My approach is just about absolutely nuts, but between a js physics library and a fragment-shader mime type, clearly the Scary Door has already been breached. If this project works out at all, there will be a post here in the next day or two.

Posted in Uncategorized | Tagged , , , , , , , , , | Leave a comment

This page best viewed with a quad-core CPU

gwtbox2d demo screenshot

[Update: this demo has evolved quite a bit and now has some actual interactivity and a few more options. See the updated version here.]

I wanted to post the simple demo I mentioned in the last entry, compiled against the latest version of the gwtBox2d library. There are actually two versions, one with the physics simulated in the main loop and one with it done in a Worker script.

A couple of notes:

Continue reading

Posted in Uncategorized | Tagged , , , , , , , , , , , | 1 Comment

gwtBox2d, Worker Threads, and SpiderMonkey

I’m going to try and keep this update short so that I actually finish editing it and it can be published. I’ve also been inspired by David Humphrey’s recent posts about his work to expose <audio> data in Firefox (and his efforts to get his students contributing to open source projects. and his baking.); as long as I’m thinking these things to myself, I might as well write them down. All benchmark times listed below are on my old 2 GHz  Core Duo and should be treated as only coarsely measured.

Really briefly, I’ve been “porting” the Box2D physics library (via JBox2d) to Javascript. Much like the existing Box2DJS, I’m cross-compiling, not from (the perhaps saner choice of) ActionScript, but from Java via the Google Web Toolkit. I put “porting” in quotes because not only is GWT doing most of the heavy lifting here, the JBox2D library was already well insulated from the JRE. Moreover, the maintainers of JBox2D have long worked hard to pool objects wherever possible to cut down on JVM garbage collection, which is also key in a Javascript application. To get an initial build working I had to do very little, replacing some thread-safety code that relied on JRE primitives and a few assorted methods unsupported by JavaScript.

My first demo ran well in Chrome but dragged horribly in Firefox 3.5. Due to the instruction- and branch- heavy nature of the code, SpiderMonkey had difficulty keeping up with the traces it needed to perform and, based on my best analysis of the analysis going on on Mozilla’s Bugzilla, the Javascript engine ended up spending more time looking through traces than running them and, to make matters worse, would occasionally garbage collect compiled code and have to start from scratch. Unfortunately I looked into all of this several months ago, before diving into the wild world of cross-browser CSS transforms, so what I’m writing now is just the best I can recall. Bugs 504829 and 504881 are the most relevant I can find right now, but neither is resolved. Something must have changed, though, because I’m getting a huge performance boost in Firefox 3.6b5. While still taking four to five times longer than Chrome to compute the same step, after some retooling and optimizations the library is highly usable in the latest Firefox.

Interestingly, drawing the scene to a Canvas in Chrome takes just as long as a physics simulation step (math in V8 is fast). If the UI hangs and the Canvas object doesn’t update, you just lose a frame of animation. The problem comes when simulation steps are delayed; this causes the world to play out in slow motion as a shorter time period is simulated than actually passes. Meanwhile, in Firefox, long (40ms) calculation times cause the rest of the interface (including that of the browser) to feel sluggish. Finally, the culprit in all of this is a script that never touches the DOM or the Window, except to update a small set of object positions. This all adds up to a perfect use case for Worker scripts.

There are a few implementations using Workers or something like them in GWT, notably GALGWT, utilizing the WorkerPool in Google Gears, and the newly released Speed Tracer. I’ve adapted code from Speed Tracer and GWT’s default single-script linker to compile the gwtBox2d library to a Worker, using JSON to pass transformation data (per simulated body) back and forth. It runs just a touch slower in Chrome, but this is made up for by the fact that the interface and the simulation are now decoupled. However, even in the latest Firefox, 3.6b5, the old SpiderMonkey problems are showing up again! The calculation time per step quickly balloons to over 600ms. What really cements the fact that this is the same problem is that, when the Script panel of Firebug is enabled (thereby disabling tracing and JIT compilation in SpiderMonkey), calculation times drop to about 80ms, only twice the time of a step computed in the main thread. From this we can also deduce that a) pure math is fast, even in “interpreted” mode and b) the main-thread time of 40ms is probably “slow,” i.e. my code is already exiting traces like crazy anyway, it just isn’t exploding the tracer in the process.

Anyway, this was pretty disappointing. Clearly Firefox is executing Javascript slightly differently within Workers than without, so perhaps recent patches to main-thread Javascript execution couldn’t be applied there. Automatically generated code isn’t exactly the best test case to submit to Bugzilla, so I’m not sure the best place to take this problem yet. Moreover, even with a submitted bug, there’s no way a change will make it into 3.6 at this point, so it will be a while before Firefox gets a nice Worker-based physics library. In the meantime, I’ll work on making the JSON interface and drop-in nature of the library compelling enough to make it a worthy goal (Box2DJS is already used as a test case of sorts, filed under “would be nice to have running perfectly at some point in the future”) and maybe get a copy of the trace-debug build of Firefox so that, if its not a fundamentally algorithmic problem, I can cut down on the code that’s been kicking SpiderMonkey around.

You can see (almost) all the code over at the (otherwise threadbare) gwt-ns library on Google Code.

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Rip Van Winkle

Just saw this slide about Javascript engine speed in the video of Google’s latest Campfire One. Apologies for the youtube screengrab.

I left for the Family Islands of The Bahamas (and $.10/MB internet) in the summer of 2006. I came back to this. I would say that there are almost too many new toys, but how could that ever be true?

Posted in Uncategorized | Tagged , , , | Leave a comment

Transformable DOM elements in GWT

In high school, any time I was bored in class I usually turned to programming my graphing calculator. I’m not sure what fancy compiler software they have now (TI doesn’t seem to be in a rush to update the hardware, at least), but back then, if you were programming on the calculator itself, you only had the built in BASIC variant at your disposal. As a result, I spent a lot of time figuring out things like the smallest rectangle I could clear every frame to keep the graphics up to date (And not learning Spanish. Oops).

As people tend to do, I eventually wanted to enter the 3d fray, probably spurred on by some terrible calculator Descent clone I had found on the internet (and programmed in…assembly? C?). I started with rotating a quad around either the (screen) x- or y-axes (which is just a scaling in either y or x). But when you did both, the “rotating” quad just looked like a shrinking rectangle…which, of course, it was. I asked my precalculus teacher if there was some kind of (dark) mathematics that could take a rectangle and calculate what kind of shape to draw on the screen after a rotation. That conversation seems preposterous to me now; that’s why we have an internet! This must have been 1998, and David and my website was definitely up, but I think back then, to me, the internet was for looking up things about the internet itself (and looking at startrek.com when I was at the library, since they had an ISDN or something). (And yes, I realize I’m telling my “back in my day” story about 1998.)

Anyway, he didn’t know. 3d would have to wait until I discovered OpenGL and the exciting world of Winamp visualizations. If I had been my own math teacher I would have told myself to go back and figure out two dimensional rotations first, because if I could figure that out, 3d would be easy.

The point of this story—besides the fact that I have to tell it here since I’ll probably never find a person in real life who will listen to it (or read it? …)—is to serve as a clumsy segue into introducing a new gwt module for handling transforms. It will wrap Elements and the various draft implementations of transform and present a standard interface to the user. With Firefox’s -moz-transform finally letting it join Webkit and the surprisingly capable IE, the time seems ripe for this. IE does require some layout hatchet work for proper positioning, but part of this project will be developing methods of dealing with that so we can pretend most of the differences don’t exist. Some will remain, though; Webkit, for instance, has native matrix functionality built in, hopefully lending us decent performance in the mobile space.

The best part of this project, though, is that I get to base the software implementation on the first matrix class I ever wrote (homogeneous coordinates!). I’ve made some changes in the interim, but nothing’s better at bringing back memories than trying to figure out why the hell you unrolled a loop the way you did. Javascript should add another 10 years of wondering, easy.

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Retrieving wordpress posts via JSON

Quick piece of code. I ended up using WordPress for my CMS because of my fairly simple needs, the fact that I’ve already played around in the code of some plugins and templates, and the fact that it seems fairly easy to upgrade to something like Drupal if my needs change (that’s the rage now, right?). That said, I had no interest in tying my site too closely to WP or to use a normal template. I had already mostly made the decision to use GWT for my interface, and so really I just needed a way to loosely couple it to content.

The WordPress documentation seems to be getting better constantly, but it still drives me a little crazy that it seems to be mostly examples instead of more succinct and precise definitions. I could be missing something, but it’s not uncommon to find a function’s documentation page made up entirely of something like “here is a list of common usages, but it should not be considered an exhaustive list.” Why not just make an exhaustive list??

Anyway, I wanted a simple php script that could retrieve the latest post and return it, encoded in the JSON format. Google was strangely unhelpful, but I was able to piece together the following and wanted it out there for anyone else looking for similar functionality. It is specifically written to deal with only one post, but it should be trivial to adjust the query_posts parameters (if you can find an exhaustive and well-defined list of them…) and insert the usual while loop, adding each jsonpost to a larger array at the end of the loop. Note that this code will be as slow as any non-cached wordpress page, and your server might not gzip json files by default (mine doesn’t), so think carefully about the latency this will introduce in any AJAX applications.

The code: Continue reading

Posted in Uncategorized | Tagged , , , | Leave a comment

Hyperbinary representations and amateur-hour number theory

I’ve recently become rather obsessed with a math problem, and thought I’d try out my new LaTeX plugin (this one) by talking about it a bit. I came across this great article series on a non-standard proof of the countability of the rationals (\mathbb{Q}? yes!) that gives a list of the rationals, each appearing once and only once, in reduced form. I originally saw it mentioned on Division by Zero here (along with a bunch of other great non-standard proofs), Calkin and Wilf’s original published paper is here, and the series in question was on The Math Less Traveled. I’m going to provide something of an introduction here, but the posts and comments there are extremely accessible, and I can’t recommend them more.

The interesting aspects of this sequence are pretty simple to prove, and I really wish I had had this paper when I was teaching about infinite sets; a well-defined sequence is an absolute joy compared to putting the rationals in a grid and skipping the ones already enumerated. Just try and tell me the nth entry in that sequence (I think I even gave that as a bonus question: is there a pattern in the position of reducible fractions?). Continue reading

Posted in Uncategorized | Tagged , , , , , , , , , | Leave a comment