Late last night, I was surprised when a friend informed me that a fork of my Turing Drawings project had made its way to the front page of Hacker News. The fork by Darius Bacon includes new features such as the ability to make the rendering faster or slower, as well as a new backend which compiles the Turing machines to asm.js instead of interpreting them, offering impressive speedups. The Hacker News community responded with great enthusiasm and found many interesting drawings, some of which I’ve collected below:
- Scooty lightning
- Spilled drink
- Donkey kong
- Sewing machine
- Surprising
- Stream
- Blue
- Wave
- Rebirth
- Glider
- Bubbles
- In 3 acts
- Laser rain
- Gothic Sierpinski
Posters also contributed interesting bits of information. It seems that the idea behind Turing Drawings is not entirely new, but rather an independent re-discovery of an existing formalism called a Turmite, with a finite tape instead of an infinite one. Another poster had the following insight:
The world is finite, so every drawing eventually loops. However, the state space is something like k * 2^18 * n^(2^18), where k is the number of states and n the number of symbols. For the default (4, 3) this is 3.125 * 10^125080, so you could be waiting for a while :)
Someone associated with Wolfram even suggested that it may be possible to participate in a summer school project involving 2D Turing Machines:
Wolframite here: these would make a good summer school project for our summer school (plug: the 2013 one is coming up, apply at https://www.wolframscience.com/summerschool/ if you’re interested in this kind of stuff and want to do a 3-week project).
In fact I studied the space-filling behavior of precisely these 2D Turing machines in 2009. For low numbers of states and colors you can enumerate them exhaustively and calculate the distribution of space-filling efficiency (log-normal, if anyone is interested).
The full spectrum of behavior is quite fascinating to catalog. All these kinds of simple computational system have a character and ‘zaniness’ all their own.
The idea behind Turing Drawings came to me while pondering generative art. I had already experimented with various approaches, such as plotting mathematical functions of two-variables, but had little success in creating interesting patterns. Intuitively, it seemed that Turing machines would be an ideal formalism because, even if they were randomly generated in a naive fashion, they would have a high likelihood of creating complex (and potentially interesting) visual patterns as a side effect of their computational process.
Users of Turing Drawings may find themselves clicking the “random” button many times before seeing anything interesting, but through the power of crowdsourcing, it becomes possible to explore hundreds of thousands of patterns in a relatively short time. Turing Drawings is a toy, but it’s interesting to observe the dynamics of chaos and entropy at play, and to see order come out of randomness and very simple rules.
It’s the first time one of my hobby projects gathers so much attention online (even foreign blogs are covering it :)). I’m happy to see that by making it open source, it’s been possible for Turing Drawings to take on a life of its own. Someone has already informed me that they were interested in adding features to visualize the transitions and better analyze the behavior of the machines. I anticipate that after the Hacker News coverage, more forks are likely to occur.
In case anyone is interested, I should also mention that I tried to apply the idea of Turing Drawings to procedural music generation, with moderate success. The project is called Turing Tunes, and is also open source.
EDIT: Turing Drawings was also covered on MetaFilter and on ikono‘s art blog.
Back in February, I visited Mozilla to present my research on dynamic language optimization and learn more about the architecture of the JIT compiler that powers Mozilla Firefox. The talk I gave at Mozilla was made available online and eventually linked on Reddit. This resulted in Andrei Alexandrescu, co-creator of the D programming language noticing my work and inviting me to present at DConf 2013. I accepted the invitation as this seemed like a great opportunity to get the word out about my research, network with programming language and compiler experts, and of course, to learn more about D.
D programming is serious business
Last week, I had the pleasure of attending DConf. The conference was hosted at the Facebook HQ in Menlo Park, California. The talks gave me more insight into the D language and the philosophy behind its design. I was a little worried about my own talk, trying to fit 70 slides into 55 minutes and touching on many different subjects: dynamic languages, Higgs, my research, a small critique of D, and the potential use of a JIT compiler for D’s Compile-Time Function Execution (CTFE). It seems I managed to thread it together pretty well in front of the audience, however; I ended up receiving several compliments. I agreed to have the talk filmed, and so a video should appear on YouTube in the next few days. In the meantime, the slides are available here.
One of the things I touched on in my talk is the new approach I’m taking with the Higgs JIT. After running into some issues with tracing, I decided that a method JIT would make more sense, and so I spent a few days converting the Higgs JIT to be method-based instead; fortunately, this went surprisingly smoothly. I am planning on using a technique which should hopefully offer some of the same benefits as tracing, without the downsides. I call this technique context-driven block versioning. The idea is similar to that of procedure cloning, but done at a lower level (that of basic blocks). I plan on cloning/versioning block based on type information to remove much of the dispatch overhead.
Higgs interfacing with xlib
On a different front, Tom Brasington is still helping me grow Higgs. He’s completed the implementation of a Foreign Function Interface (FFI) and used this to create a user-friendly wrapper for the C stdio functions. We’ve updated the README file on github to explain how this API can be used. Our hope is to improve the FFI API itself and eventually provide wrappers for graphics and sound libraries. We’d also like to devise a procedure for people to request the inclusion of libraries and tests they wrote into Higgs using pull requests.
I’ve been busy working on various aspects of the new Higgs JIT compiler in the last month or so. Among other things, I decided to expand it into a proper tracing JIT compiler complete with support for side-exit traces (or sub-traces as I like to call them). This brought some performance improvements. I’m also happy to report that the JIT compiler appears quite stable and is enabled by default. At this point, the Higgs JIT is still quite simple and primitive compared to commercial JavaScript VMs, but nevertheless provides marked speedups relative to the interpreter on every benchmark I tested it on.
JIT speedup relative to the interpreter
I’m interested in finding the source code for the latest version of the Mozilla TraceMonkey shell (as well as instructions on how to build it) so that I can compare the performance of Higgs to another JavaScript tracing JIT. TraceMonkey is no longer maintained by Mozilla and is no longer in their main source code repository.
One important optimization I added to Higgs was to implement a stack frame initialization analysis. Previously, Higgs initialized every stack slot as soon as a function was called to make sure that stack frames were always in a consistent state when the garbage collector (GC) was called. As you can imagine, this is is rather slow for large stack frames, and it’s often a complete waste of time if the variables are going to be initialized later on. Now, a simple analysis actually checks which variables have been written to (and so may contain references to heap objects) and the GC uses this information when performing a collection. This significantly reduces the amount of work that has to be done during function calls.
An important limitation of the current JIT compiler is that it directly translates the interpreter’s intermediate representation into a linear list of x86 machine instructions. This is an issue because the machine code produced is of fairly poor quality and would need to be further optimized, but contains little semantic information to facilitate optimization. One of the things I plan to do is to implement a liveness analysis to facilitate basic register allocation and eliminate redundant writes to the interpreter stack. I’m unfortunately not sure what is the best data structure to use (in terms of memory usage) to store liveness information and associate it with a function’s intermediate representation (if anyone has advice, please comment).
Tom, a friend of mine, recently started helping with the Higgs project. Among other things, he took the time to track down and help me fix bugs that were causing crashes in various benchmarks. This process involved fixing many inaccuracies in the Higgs implementation of the JS spec. We’re now at the point where all of the V8 and SunSpider benchmarks are working correctly, except for those using regular expressions. Tom has also started implementing a Foreign Function Interface (FFI) system for Higgs. Once completed, this should allow us to add support for APIs such as OpenGL, and POSIX sockets. This might give Higgs some real usefulness outside of academic experiments.
In the last few days I’ve been prototyping a basic Just-In-Time (JIT) compiler for Higgs. I decided to start with a very simple design which is sometimes referred to as a tracelet JIT. This is simply a compiler which compiles one basic block at a time, basic blocks being defined as single-entry, single-exit sequences of instructions. This compiler is lazy, meaning it doesn’t compile unexecuted blocks. It also only compiles “hot” blocks that have been executed a few hundred times, the idea being to avoid wasting time compiling code that only runs once or very few times (e.g.: initialization code). Another advantage of delaying compilation somewhat is to allow time for profiling statistics to be gathered.
I have to admit that I was very excited to actually begin generating machine code (if you can believe that). It took me a few days to port over the x86 assembler I wrote in JavaScript for Tachyon to D, along with all associated unit tests. Once this was done, I was able to get a very basic tracelet JIT working in less than a day. This first version simply compiled sequences of calls to functions implementing interpreter instructions. This provided small speedups on the order of 5%. I improved on this by adding JIT code generation support for some basic arithmetic, bitwise and branching operations which provided speedups of up to 30%. The next step, in my mind, was to support all branching operations so that tracelets could jump directly into each other without ever needing to fall back to the interpreter. However, I ran into a problem.
The Higgs interpreter was designed with simplicity and maintainability in mind, a choice which has paid off thus far. Unfortunately, this means that some operations aren’t built with pure speed in mind, and one problematic case is the call instruction. The call instruction builds the stack frame for callees. This means it needs to make several conditional checks and push the right number of arguments and local variable slots, which isn’t the same for every callee. I started trying to implement the full dynamic extent of calls in the JIT compiler. I stopped once I realized how big and messy the generated code would be. Since every runtime primitive is self-hosted in Higgs, there are calls everywhere, which would assuredly mean the generated machine code would be huge (bad for the instruction cache).
I decided to try an idea just for the fun of it. Most of the calls in the small benchmarks I was testing were global function calls. For such calls, it’s quite easy to guess correctly who the callee would be. I chose to implement a mechanism which tries to guess the callee and has an optimized call path specifically for the said function. If the callee isn’t correctly guessed, the interpreter’s call instruction logic is used instead. Amazingly, such a simple optimization (two hours of work) yielded a total performance improvement of about 500% over the interpreter on most of the benchmarks I tried.
JIT speedup relative to the interpreter
The numbers above show the speedups I measured on some of the SunSpider benchmarks, going from very simple to medium-sized programs. If you’re familiar with these benchmarks, you might feel that these times are ridiculously slow either way. You should keep in mind that this is still very preliminary work (I did say the JIT was a prototype) and that these values were measured using the linux time utility, and so include initialization time. Higgs is also self-hosted, meaning that it lazily compiles parts of its own standard library when you run a program. As such, Higgs will probably always be at a disadvantage when it comes to very short running programs.
At this point, the tracelet JIT compiler is about 800 lines of D code (excluding the x86-64 assembler). It’s very much a prototype and a platform for me to experiment with, meaning I will probably refactor the design in many ways. I’m already thinking of several improvements I can make over the course of the next week which should bring more significant speedups. The main thing I will be doing is trying to extend tracelets in a trace-like manner, which should tremendously help with loops.
As I said earlier, I designed the Higgs interpreter to be simple and easy to maintain. This decision was partly motivated by my belief that interpreter speed should be largely irrelevant in a system where a JIT compiler is also available. I could have tried hard to make the Higgs interpreter faster, at the cost of tasteless kludges and largely increased code complexity, but I don’t think it would have been worth it, especially now that I’ve shown that 4 days of work can yield a simple JIT compiler producing 500% speedups. Next week, I’d like to have at least 1000% speedups over the interpreter, which I believe is easily achievable.
How Mozilla sees itself
I’m back to Canada after a two week visit to the Mozilla offices in Mountain View. The visit started with a presentation of Higgs and my PhD research work, which was made available online on Air Mozilla. Then, over the next two weeks, I had several one on one meetings with several members of the JS engine and research teams at Mozilla. The Mozilla people were all extremely friendly and forthcoming. Because of Mozilla’s open culture, I was able to get answers to just about any question I might want to ask about their work. I was also invited to give a talk at Apple and briefly meet with the JavaScriptCore team. This trip was a great opportunity to discuss and refine my research ideas, as well as to gain specific insights into the workings of production JavaScript JIT compilers.
Speaking at Apple
There were also unexpected benefits to my visit. The presentation I gave at Mozilla, which was made available online, garnered some attention on twitter and reddit. As a result, I received invitations to meet from Alex Gaynor of the PyPy project and from Ariya Hidayat of the Esprima parser project (both of which I promptly accepted). I was also invited by Andrei Alexandrescu himself to talk about Higgs and my experience using the D programming language at DConf 2013. Finally, I had the pleasant surprise of getting pull requests on the Higgs github repository.
A taste of America
Being in the Silicon Valley area, I also took the opportunity to visit San Francisco on the weekends. I went to an outdoor pub with some friends and got invited to a barbecue party where I was introduced to the infamous Cards Against Humanity. San Francisco is a charming city with its own highly liberal hippie subculture. It has cute little boutiques and cafés, streetfood, and beautiful parks. Public transportation seems rather good, at least in the city itself (I can’t speak so highly of the suburbs).
San Francisco
The bay area, and San Francisco, are truly different from what I’m used to. It seems everyone is involved with technology, or with a startup, in one way or another. Everyone has a smartphone and Apple TV. People use apps on their phones to summon cabs. The rents are very high and almost everybody has housemates (even couples). Because so many people are in tech, the online communities of the bay area are also more active than elsewhere. Getting to experience Silicon Valley was an interesting experience, and makes me understand why so many tech companies choose to establish themselves in the area: nowhere else are people this excited about tech.
At this point, you might be wondering what I’ve done with my research during this trip, besides talking to many people. For one, I started looking more seriously into the area of trace compilation. The Mozilla people have let me know that they had multiple issues with their TraceMonkey JIT, which eventually led to its retirement. One of these issues was trace explosion: the generation of too many independent traces. Another was constant fallback to the interpreter. What I want to do with Higgs, is implement something closer to region-based compilation, and attempt to solve some of these tracing problems.
In terms of code, I started planning the implementation of a simple backend and tracing JIT for Higgs, so that I can begin experimenting with these concepts. I already made some minor refactorings that will be necessary for this JIT to be possible. I also took the time to fix many (dozens of) bugs that were preventing Higgs from running SunSpider and V8 benchmarks. The good news is that Higgs is now much more standards compliant than before, and even better tested. I updated the lists of supported features and supported benchmarks on the Higgs page to reflect this.
My research team (the Dynamic Language Team) and I are taking a plane to San Francisco today so that we can visit the Mozilla headquarters in Mountain View. This will be an opportunity to show them our research work and discuss all things compilers and JavaScript. I will be giving a 30-minute presentation on Higgs and my current research work at their offices tomorrow around 11AM. I’m not sure whether the presentation will be live streamed or filmed, but I will make sure to post my slides afterwards.
EDIT: My presentation was aired live on Air Mozilla at 10:30AM, Feb 1st. A video recording is now available. I’m also putting the slides online for those who might be interested.
The rest of the team is only staying for one day, but I will remain in Mountain View for two weeks, working at the Mozilla offices. The hope is that I will get to learn more details about the internal workings of Mozilla’s JIT technology. I’m particularly interested in the kinds of optimizations their JIT compilers perform, the workings of their tracing JIT, etc. I’m also thinking that this might be an opportunity to spot some upcoming pitfalls I didn’t foresee in the implementation of Higgs. In any case, it will be nice to get a better idea of what the industry is like and maybe get to visit San Francisco a bit.
In terms of my research work, I should mention that the Higgs interpreter is mostly feature complete at this point. I implemented the biggest missing pieces and made sure to unit test everything. Higgs doesn’t support all of JavaScript, but the feature list is already pretty respectable, in my opinion. It includes:
- Objects and methods
- Dynamic addition of object properties
- Prototype-based inheritance
- Dynamically resizeable arrays
- Closures
- Constructor functions
- Variadic functions and arguments object
- If/switch statements
- For/while/do loops
- For-in loop
- Exceptions and try/catch/finally
- UTF-16 strings and string operations
- Integer and floating-point arithmetic
- Dynamically redefinable arithmetic operators
- Low-level arithmetic and pointer manipulation primitives
- Garbage collection
I’m now moving on to the implementation of the type monitoring component of Higgs. It shouldn’t be too long before I can start gathering useful information about benchmark programs.
I just completed the implementation of a garbage collector (GC) for the Higgs JavaScript VM. This brings me much closer to the completion of my interpreter. The GC itself is an almost direct port of the code I wrote for Tachyon. It’s a stop-the-world copying semi-space collector. This design has the advantage of being very simple and easy to maintain at only a few hundred lines of heavily commented code.
Since GC bugs are vicious creatures, I decided to try and catch these early on. For this, I ported over the Tachyon GC unit tests, and wrote some new ones. This, of course, isn’t an ironclad guarantee, but it’s already helped me expose and fix several bugs. I consider the GC to be fairly stable at this point. I dreaded doing this work, but putting off the implementation of the GC would likely have meant more integration pains as Higgs is sure to grow in complexity over time with the addition of a Tracing JIT and additional optimizations.
In the next week or so, I will be adding the few features which are missing from the Higgs interpreter, such as support for the arguments object. Once this is done, I’ll move on to the implementation of a profiling system and a tracing JIT for Higgs (which I’m quite excited about).
