Skip to content

Dogfooding Higgs with the Turing Turtle

turing turtle 12

A while back, I wrote Turing Drawings, a JavaScript web app which uses randomly generated Turing machines to produce animated drawings on an HTML5 canvas element. The web app, due to its addictive nature, ended up being featured a few times on Reddit and Hacker News, and was even forked by developers who added interesting new features to it. Since then, I’ve been pretty busy working on Higgs and my PhD thesis, and I haven’t taken the time to work on fun little hobby projects of the sort. That is, until last night.

Thanks to the fine work of Tommy Everett, Higgs now has a 2D drawing library based on X11 with functionality resembling that of the canvas element. I decided to dogfood Higgs and its drawing library by writing a new program inspired from Turing Drawings. This program, which I’ve named Turing Turtle, uses randomly generated Turing machines to control a turtle-style plotter. The machine has an internal tape used for storage, and can perform a number of output actions, such as moving forward, turning left or right, as well as changing the current drawing color. This can produce a variety of interesting drawings, as shown below (click to enlarge):

turing turtle 14

turing turtle 20

turing turtle 16

I’ve uploaded an album with many of these drawings on imgur. I find that randomly generated Turing machines are a simple and effective way to drive generative processes in which you’d like to see repeating patterns emerge. If you’d like to try Turing Turtle for yourself, I’ve added the program to the examples directory of the Higgs repository. You can use the arrow keys to generate new drawings, restart the current drawing as well as increase and decrease the plotter speed. It’s a very fun little program to play with.

My Paper was Rejected… Again

A month ago, I submitted an updated version of my basic block versioning paper to an academic conference (the previous version can be viewed here). We have an improved system, more working benchmarks and better results across all metrics. I was quite proud of this paper, and thought our odds of getting into the said conference were quite high. Unfortunately, the improved paper was again rejected. Comments from the reviewers were mixed. Some quite positive, others extremely negative and harsh. Notably, the paper was shot down by a famous industry researcher who has done extensive work on trace compilation, a competing approach.

Below are some excerpts of the comments from four different reviewers:

The paper is well written and the examples help to understand the tradeoffs of the approach. Overall the approach seems to be sound and deserves further discussion/publication.

 

I fail to see the difference to trace compilation (and the predecessor of trace compilation, dynamic binary translation) [...] Constant propagation and conditional elimination in a trace compiler lead to the same type check elimination that you present.

 

I have had a peek at the code and it very elegant. The paper is well written too. The paper has some weaknesses but  I don’t believe that they are show stoppers. [...] Overall this is a nice idea well worth looking at in more detail.

 

The one big problem I have with the paper is that it does not motivate and put into context lazy block versioning properly. The paper needs to do a better job at explaining which precise problems of current Javascript JIT approaches that are used in production are solved by lazy basic block versioning.

In this improved paper, we’ve managed to show that basic block versioning reduced the number of type tests much more effectively than a static analysis could, and that our approach was able to yield significant speedups. We’ve also addressed one of the most important criticisms of such an approach by showing that it does not result in a code size explosion in practice, but only a moderate code size increase. This, however, wasn’t sufficient for some reviewers. The main criticism they raised is that basic block versioning has similarities with tracing, and that as such, we should have compared its performance against that of a tracing JIT.

I have no issue with writing a detailed comparison of both approaches on paper, but it seems the only way to compare the performance of basic block versioning against that of tracing in a fair manner would be for me to implement a tracing JIT compiler in Higgs. Not only that, I’d probably be expected to implement a tracing JIT with all the latest developments in tracing technology. This could well require an entire year of work. I feel like there’s an unfortunate disregard for the amount of infrastructure work required to do compiler research. It’s becoming increasingly difficult to do academic research on compiler architecture. There’s a high amount of pressure to publish often, but at the same time, conferences expect us to pour several man-years into each publication and to immediately provide an absolute proof that ideas brought forward are better than everything else out there. Curious exploration of new ideas is systematically discouraged.

I was understandably feeling quite frustrated and discouraged after this second rejection. This blog post by Daniel Lemire lifted my spirits a little. It’s clear in my mind that basic block versioning has potential. We have something clearly novel, and it works! No matter what, I can at least take some comfort in the knowledge that basic block versioning has already been presented at several industry conferences, such as DConf, mloc.js and Strange Loop.

I may not be doing very well at the publication game thus far, but thousands of people have watched my talks online. The idea has already been spread around, and I’ve gotten positive responses. I haven’t put this much work into Higgs and my thesis to just give up. I’ve already found two conferences where I can submit further updated versions of the paper, and the deadlines are luckily coming up soon. In addition to this, I’ve already started work towards implementing typed shapes in Higgs, which should lead to another publication next year.

The Constness Problem

These days, I spend most of my programming time working on the Higgs JavaScript JIT compiler for my thesis, and most of the code I write is in D. I don’t always take the time to write the best, most carefully engineered code, especially if I know I might rework a given piece of code later. Still, I try to pay some attention to generally-accepted-best-software-design-practices. One thing I try to pay special attention to is which data should be immutable and which shouldn’t. I write my code in an imperative language, but I too have come to accept that immutable data and immutable data structures can make a program safer and easier to debug.

The main thing I’m working on right now, for Higgs, is a system of shapes (aka hidden classes) to describe object layouts in memory. In the Higgs object system, JavaScript objects are essentially a flat list of slots which can contain values. Shapes are essentially a tree data structure, where each node describes a property in an object, and most importantly, where that property will be stored in a flat object layout (the slot index associated with that property). Each object has an associated pointer to a node in the shape tree. Through this shape node pointer, you can find the properties stored in that object, their names, and which slot you can find them at. The important thing is that the shape tree nodes are essentially immutable. Once such a node is created, the name of the property it describes, the associated slot index, and all other attributes of the node should never change.

As someone who wants to write safe, descriptive code, I wanted to explicitly express those immutability constraints in my code. I wanted to use const(ObjShape) pointers when manipulating shapes. I also wanted to make the fields of the ObjShape class themselves const. Unfortunately, this plan didn’t work out. The DMD compiler wasn’t having it. I quickly found out that the D programming language (which is quite like C++ in this regard) just didn’t offer a way to express the semantics I wanted. Introducing const or immutable keywords in the code introduced strange and unpredictable compiler errors. Struct objects that could be copied by value before couldn’t anymore. Some of the errors reported were entirely nonsensical problems I never saw coming.

Consider the following snippet, and the compiler error it produces

class A { const(A) parent; }

void main()
{
    auto a = new A();
    auto p = a.parent;
    p = new A(); // test.d(7): Error: cannot modify const expression p
}

This is complete utter nonsense, and it deeply offends me! I specified that the parent field of class A should be constant. In D, you get “constness all the way down”, which means that I can’t mutate the parent field, and I also can’t mutate the object that the parent field points to. But, where in this program did I specify that the variable p was immutable and could not be redefined? Nowhere! This is problematic, because as far as I know, there is pretty much no way to write the type of p in such a way that p points to a const(A) object, but p remains mutable, not without ugly, unsafe type casting tricks. There’s no way to have a mutable variable that points to an immutable object? That’s insane!

In my opinion, C++ and D both lack expressivity when it comes to constness. D’s const and immutable keywords are is simply overpowering. It’s an issue in the other direction, too, because “constness all the way down” means that I can’t have a class field that’s immutable without also being forced to assume that the object pointed to by the field is entirely immutable. That’s not necessarily what I want. In the end, I’ve been forced to give up and remove const keywords on many occasions, because I end up fighting with the type system too much, it’s getting in my way.

It’s good that modern imperative languages have some tools to express purity and immutability. However, I think that there’s an issue of granularity. There are ways in which it makes sense to talk about constness, and ways in which it doesn’t. I’d almost say that I prefer JavaScript’s notion of constness, because it’s much simpler. In JavaScript, you can make an object property constant, but what that field points to does not have to be immutable. That is all! This might seem primitive, since you’re only able to painstakingly mark constness on individual object properties one at a time. It might feel like the only tool you have to deal with immutability in JavaScript is a tiny toothpick. This, however, is forgetting that JS has powerful introspection capabilities which allow to write code that makes an entire data structure immutable with a single function call. The language offers you the tools to express constness any way you want to.

News of Higgs

Coming Soon to OSX & BSD

While chatting in the #higgsjs chatroom, Tommy and I found out that several people had tried running Higgs on OSX systems without success. Since he and I both run Linux as our main OS, we were both unaware of the portability issues involved. The unfortunate thing is that this situation has probably been going on for months, and nobody had told us until now. It makes me a little sad to think that quite possibly, several dozen people may have tried and discarded Higgs after running into such problems. Fortunately, Paul Fryzel has generously been helping us test and debug Higgs on his Mac and we’re now pretty close to a working solution. Tommy will also be testing Higgs on BSD for good measure.

Drawing Library

Tommy Everett has completed the first version of a simple 2D drawing library (lib/draw) based on xlib. This library ships with Higgs and allows rendering simple static and interactive graphics.

xUyjEcU

We’ve decided to add an examples directory to the Higgs repository to showcase usage of Higgs-specific libraries and language features. This currently includes a “Hello World” example for the draw library, and a simple pong game clone built for Higgs.

Upcoming Paper

I’ve been spending most of my time working on a paper on Basic Block Versioning (BBV) and incremental compilation. The results so far are very encouraging. BBV is able to eliminate more type tests than a static analysis, and produces measurable improvements in running time on the benchmarks we’ve tested it on. The graph below shows some preliminary results on part of the set of benchmarks tested (lower is better):

Screenshot - 14-05-08 - 09:53:36 AM

While working on the paper, I’ve been optimizing the size and quality of the code generated by Higgs so as to improve performance. I also discovered a strange anomaly in the results. Running the static type analysis produced a very significant slowdown (over 2x) on some benchmarks, even when the results of the said analysis were not used. Simply running the analysis in the same process brought a huge performance penalty in terms of execution time, with the time taken by the analysis itself excluded from measurement.

This led me to discover that the D garbage collector, which is used by the type analysis, is very inefficient, and performs much worse when there is more data allocated. Higgs has its own heap for JS code, but sometimes needs to perform allocations when interacting with the host runtime (written in D). These allocations were much slower than I expected. With a simple change, I was able to eliminate most of them. I also decided to pre-allocate memory for the D garbage collector in order to reduce collection frequency. To my surprise, this yielded a 4x performance improvement on several benchmarks.

The Next Phase

It seems i’ve been able to convince my PhD advisor (Marc Feeley) that the next phase of my research, after the current paper is submitted, should focus on extending basic block versioning to add object/field type analysis capabilities. In my opinion, the right way to do this is to implement a system of typed hidden classes (or shapes, as the Mozilla people call them). This should make it possible to eliminate many more type tests, and accelerate property accesses as well as method calls. As an added bonus, a proper implementation of hidden classes will provide a better foundation to efficiently implement getters and setters in Higgs.

Positive Results for Higgs

7vt91

Great news! The Higgs GitHub repository has 204 stars and 22 forks at the time of this writing. Even better news, however, is that I’ve finally reached a point where Basic Block Versioning (BBV), the compiler optimization technique I’ve been implementing in Higgs as part of my PhD thesis, finally delivers measurable speedups on benchmark programs. Although I was able to demonstrate a few months back that BBV is able to eliminate dynamic type checks quite effectively, one important problem remained, which is that this didn’t immediately translate in improvements in terms of running time. Many optimizations are required in order to make dynamic languages fast, and the quality of the code generated by Higgs was just too poor: removing 50% of type tests or more didn’t make a noticeable performance impact. It was like removing one drop from a bucket of inefficiency.

Recently, after measuring that property access took more than 30% of the execution time in some benchmarks, I decided to implement inline caching into Higgs. This provided noticeable speedups, but still didn’t make BBV win out in terms of running time. In fact, the results on most benchmarks were worse with versioning enabled. I concluded that the issue was probably largely one of code size. By generating multiple versions for some code paths, the code size increases. This can result in worse performance in terms of instruction cache accesses. Modern CPUs have large L2 and L3 caches multiple megabytes in size, but the instruction cache of the Core i7 is still just a puny 32 kilobytes. This cache is easily filled up, especially if the code you’re generating is rather bloated.  Hence, I decided that my next focus should be to try and optimize the size of the machine code generated by Higgs.

I started by implementing a very naive on-the-fly register allocator. The first version spilled values very conservatively and produced many redundant writes and spills whose only purpose was to avoid having the Garbage Collector (GC) ever seeing false pointers (a flaw which has now been fixed). My main concern was to get Higgs to pass all its tests with the register allocator, and only then to optimize it. After many hours of debugging, I got it all working, and to my surprise, despite all the redundant operations, the unoptimized register allocator produced much smaller code and much improved performance. The performance was improved enough, in fact, that BBV finally won out in terms of running time on most benchmarks. I was extremely surprised to find out that on loop microbenchmarks, the naive register allocator produced code that ran more than 10 times faster than similar code loading and storing values on the stack. My conclusion is that when it comes to memory accesses, it’s really the reads that kill performance as the CPU doesn’t have to stall execution for redundant writes.

At this point, I’ve completed a few optimizations to the register allocator. Most of the redundant moves have been eliminated, but spilling still remain to be made less conservative. I’ve also stumbled upon a rather interesting finding. In some cases, it actually turns out that versioning doesn’t increase code size, but actually decreases it. Sometimes, the code it produces is more optimized and more compact than the original. So far, the results are extremely encouraging, but I still believe I can improve on them with additional tweaks. These results are coming in just in time for my presentation in May at DConf 2014. I’ll also be submitting a new publication at a conference in early June.

The performance of the machine code generated by Higgs is slowly but surely becoming more competitive. As I see it, the main flaw Higgs has in terms of usability at this point is that the compilation time is rather slow. Compilation time now largely dominates execution time on most benchmarks. This is something I haven’t had much time to look into. The codebase has become complex enough that I can’t exactly pinpoint where the major inefficiencies might be without some digging. If you’re interested in contributing to this project, profiling and optimizing parsing, analysis and code generation is something we could definitely use help on.

In other news, Tommy Everett has delivered an updated version of his FFI library, and is now working on a graphics library of 2D graphics bindings for Higgs, which he used to create a Pong clone in JavaScript. Stay tuned!

How I Hacked my Stationary Bike and Voided its Warranty

IMG_20140318_184639

Working out is good for your mood, your motivation and energy levels. It’s good for staying thin and looking good, too. Still, going to the gym is impractical. Especially in a city with a harsh winter like Montreal. I just haven’t been able to motivate myself to make that kind of time commitment. Still, I found a nice compromise. I bought myself a Schwinn A10 stationary bike and set it up right next to my desk at home. That way, I can hop on it whenever I want, right in the middle of a coding session. Hit an annoying bug? Need some time to think? Why not take a break to watch a few minutes of an interesting talk while biking. This works pretty well for me, I now do cardio almost every day.

I like my stationary bike: the mechanism is quiet and sturdy, it offers a good resistance level. Unfortunately, it has a slight design flaw. After 5 minutes of inactivity, it goes into sleep mode, and then, if you leave it in sleep mode for more than one minute or so, all of your workout stats get erased. It seems that when it goes in sleep mode, the microcontroller driving it gets powered off completely, and its RAM only survives so long without a refresh. This is problematic since, as I said earlier, I often like to workout in short sessions of a few minutes each, stretching over several hours. Being the tinkerer that I am, I started thinking about ways to work around this problem. I don’t have awesome soldering skills and I didn’t think I could reverse engineer the stationary bike’s control board, but I did think of something.

IMG_20140318_175753 IMG_20140318_184639 IMG_20140318_205224

I designed and built a small board with a microcontroller and a reed relay (low power relay) to trigger a button on the console every 3 minutes. I chose the very basic and inexpensive Atmel ATtiny85 for this. The reed relay is connected to the “enter” button pins on the bike’s control board. Some of you are probably thinking a microcontroller is overkill for this, that I could have used an NE555 timer. I could have, but that would have made for a more complex electronic design. The microcontroller also allows me to easily trigger the “enter” button exactly 3 times in a row, which changes a setting and then restores it to its original value, essentially performing a noop which only serves to keep the bike’s control board from going into sleep mode.

IMG_20140318_215526 IMG_20140318_215513 IMG_20140318_221144

The circuit was tested on a breadboard before I soldered it on a prototype board. Hot glue was used to install the clandestine board inside the bike’s console. The device draws power directly from the bike’s batteries (4 x D cells). It can be turned on and off with a switch I installed on the front console, and there’s a green panel mount LED to indicate its status. My Schwinn A10′s warranty is no doubt voided now, but the annoying flaw is fixed, and this was a fun little hack to work on. Honestly, I was just curious to see if I could make this work ;)

Higgs: Upcoming Talks & New Contributions

Upcoming talks about Higgs

I’ll be giving a talk about my research at mloc.js in Budapest on February 13th. This is going to be the first of my conference talks that is entirely focused on Higgs and my current research. The talk will be filmed and should appear online on InfoQ and Ustream. I’ll also be putting the slides online after the talk. In other news, I received an invitation from Andrei Alexandrescu to present at DConf  this year again. I’m quite looking forward to this as I had a very positive experience at DConf 2013, where I met many very knowledgeable systems engineers (I may also have a crush on the SF bay area).

For those who would like to see some results of my current research right away, I’ve made available a paper which was recently submitted to CC 2014, but unfortunately rejected. This paper explains in depth the technique of basic block versioning, and gives results comparing it to a traditional type propagation analysis. The main reason stated for rejection is that we did not provide comparisons in terms of overall running time (due to limitations of Higgs). I still believe the results are quite encouraging and make a convincing case for basic block versioning. My PhD advisor and I will be submitting an improved version of this paper in a few months.

New JIT online

The lazy incremental JIT I’ve been working on is now in the master branch. It’s far from complete, but it’s reached the crucial milestone where it passes all of the Higgs tests and runs all of the benchmarks. There is currently no type propagation and no register allocation, but I’ve already started implementing incremental inlining of primitive calls. The inlining is currently done in a rather unsophisticated manner which doesn’t eliminate all call overhead, but this will be fine-tuned.

Performance-wise, the new JIT is comparable to the old one. It’s faster on most of the larger benchmarks, probably because there is no more interpreter and the new JIT generates machine code faster. Thus, there is less warmup time required before reaching full speed. I will be working on reintegrating the full power of basic block versioning and improving the performance within the next few months. I expect to exceed the performance of the old JIT on all benchmarks within a few weeks.

New contributions

Following our recent announcement that we were looking for contributors, we’ve started to build a Higgs wiki and created a #higgsjs channel on freenode IRC. It seems that this work has paid off as we’ve gotten several pull requests for bug fixes and improvements.

Notably, zimbabao has sent us bug fixes to the runtime library, the regex engine and the standard library. Thanks to him, the SunSpider crypto-aes benchmark finally works properly. He’s even fixed bugs I wasn’t even aware of! Óscar Toledo has helped us find and track down two parser and two semantic bugs using his nanochess JS1K program. I’ve also taken the initiative of fixing several minor semantic bugs to make Higgs respect the ES5 specification more closely.

My number one, Tommy Everett, has completed a new test framework which will make it easy to add new functionality and regression tests by including a JS file in the source/tests directory and sending us a pull request. He’s also set up the travis build test system to notify us if a build fails. Tommy is currently working on an improved, more convenient version of our FFI library. We have plans to build bindings to SDL and network APIs, among other things.

Should you wish to help, we’re always looking to make Higgs more JS compliant, add new useful features and grow our collection of tests. If you find a bug in Higgs, please open an issue and/or send us a pull request with a failing test. You’re also welcome to write useful libraries to be included with Higgs. You can help us make Higgs insanely great.

Follow

Get every new post delivered to your Inbox.

Join 2,450 other followers