Pushing Higgs to the Limit

Over a week ago, I received the unfortunate news that my basic block versioning paper was rejected for the third time. We had received five “weak accept” scores, but at the last minute, after the rebuttal period was over, one of the reviewers decided to change his vote and give us a “reject” rating. I won’t lie, even though I knew the paper could be rejected, I found that I had a hard time getting out of bed the next day. For a little while, my motivation was completely crushed. I decided to put the latest version of the paper on arXiv.org. I feel that it’s useful to timestamp my progress, and it seems that sharing the results of my research is more important than getting into academic conferences.

Fortunately, my motivation is beginning to return, in part because I’ve had some ideas on how to make the next version of the paper even better. Conference reviewers criticized us for not discussing compilation times, and raised the issue that perhaps basic block versioning could drastically increase compilation times. I think it will be easy enough to simply include a graph showing that this is not the case in practice, and avoid receiving this criticism ever again. Another thing that has been brought up multiple times is the request for a comparison of basic block versioning against trace compilation. I personally don’t want to dedicate the next year to building a JavaScript tracing JIT to compare Higgs against, but I figured that maybe I could make a convincing case some other way.

I decided to ask around on Twitter and found the last working version of the famous TraceMonkey JIT, which was once part of Mozilla’s JavaScript engine. Numerous papers have been published about this JIT compiler and so it’s relatively famous in the academic community. Hence, I figured that if Higgs could compare favorably to TraceMonkey in terms of performance, that may give us more credibility. Performing well against a well-known commercial JIT compiler will hopefully provide the psychological impact needed for conference reviewers to take us more seriously.

The graph above shows a comparison of the relative execution time of code compiled by Higgs vs TraceMonkey (lower is better). Compilation times are excluded from this comparison because of issues mentioned in a previous blog post. The 26 benchmarks are from the SunSpider and V8 suites, but I’ve excluded regular expression benchmarks since Higgs doesn’t have a regular expression compiler (only an interpreter), and my research is not specifically about regular expressions.

Higgs clearly doesn’t beat TraceMonkey across the board, but it does perform better on half of the above benchmarks, sometimes by a wide margin. What seems clear after some analysis is that TraceMonkey does very well in benchmarks with short, obvious loops, but poorly in benchmarks with more complex control-flow. This should at least highlight the fact that basic block versioning is not the same thing as tracing, and can, in fact, deal with situations to which tracing is less suitable.

Fortunately for me, TraceMonkey is not a moving target in terms of performance, and this week, I’ve been working on helping Higgs catch up. I’ve added string optimizations such as ropes and precaching of one-character strings. I’ve also been working on eliminating bottlenecks in the runtime and standard libraries. Tomorrow, I’ll be optimizing the inefficient way in which Higgs handles for-in loops (property enumerations), which are extensively used in the fasta benchmark.

It’s very motivating to have a goal. You can be sure that the next paper I submit will be showing Higgs beating TraceMonkey on most of these benchmarks. I’m going to keep improving the performance, keep improving our results, and keep amassing more and more evidence that basic block versioning is a worthwhile JIT compiler architecture. I’m going to push Higgs to the limit.