The Benevolent Dictator

They were new. They were the change. But they heard another change was coming. A new dictator – a symbol of hope supposedly.

He came, but he didn’t like change. He was stone, indifferent to the outside world. He was a conventional slave, who was scared from trying out the new.

It was massacre, one by one he played his moves. These people opposed to the injustice, the oppression in the most gentle way possible. He was ruthless, unwilling to listen to anything. He did not respect women, nor did he follow the standard protocols of running an empire. He left every other minister with no choice but either to follow him or die.

Alas! These new people, their philosophy, all were at the verge of extinction, but he didn’t care. What had they done? They tried to make him understand their value with logical arguments. But given a dictator that he was, he didn’t allow them to speak and hardly met them.

The decision was taken to banish them, to ensure that no further new people is ever born in the state. These people being constitutional beings, looked forward for redress. They had only hope on their side, a hope for a brighter future, a hope for a better world for everyone.

A Brainf*ck JIT

I recently came across an article by Josh Haberman on the web which demonstrates how to make simple fun JITs, with the help of LuaJIT. I am still a beginner in the field of compilers and JITs. So I tried to implement a Brainf*ck JIT with the help of GNU LibJIT library. It proved to be a really entertaining exercise. The results are up here on Github.

The fun is in the part where we directly emit the machine instructions while reading source. The JIT doesn’t make any optimizations to the code, it just directly converts to the machine instructions.

Wikipedia tells us what each of the BF instructions correspond to in C. This makes it easy to write the corresponding instructions for the JIT. The entire BF program is defined as single function that when once compiled will run. I’ll take up sections of the code from bf-jit.c and lookup what they do:

case '>':
    tmp = jit_insn_add(function, ptr, uptr);
    jit_insn_store(function, ptr, tmp);

The > instruction increments the current pointer by an unit address value. The uptr value is defined to have a pointer of unit byte length. Once we do the add, we store the new value back to the ptr (since, ++ptr is equivalent to ptr = ptr + 1).

case '+':
    tmp = jit_insn_load_relative(function, ptr, 0, jit_type_ubyte);
    tmp = jit_insn_add(function, tmp, ubyte);
    tmp = jit_insn_convert(function, tmp, jit_type_ubyte, 0);
    jit_insn_store_relative(function, ptr, 0, tmp);

Similarly the + instruction loads the values from the address stored in ptr. We add one to the byte value and type cast it to ensure that it is still a byte value. We then store the result into the address contained in ptr.

case '.':
    tmp = jit_insn_load_relative(function, ptr, 0, jit_type_ubyte);
    jit_insn_call_native(function, "putchar", putchar, putchar_sig, &tmp, 1, JIT_CALL_NOTHROW);

Here the . instruction prints the character pointed to by the ptr. Then we call a native C function, putchar that prints the character on the screen.

Making the loop constructs are the most interesting part. We defined a struct that has the labels to the start and end of the loop in the program. It also has a pointer to the parent loop, so that we can return to the parent loop.

case '[':
    loop_start(function, &loop);
    tmp = jit_insn_load_relative(function, ptr, 0, jit_type_ubyte);
    jit_insn_branch_if_not(function, tmp, &loop->stop);

The condition the loop is the value pointed to by the ptr. We load that value and then use to decide whether we should branch on the loop, depending on whether it is 0 or not.

We then compile the JIT function and then call the function. The results of the benchmark by running the Mandelbrot code were really interesting:

Implementation                      Time
----------------------------------------
Mandelbrot (C Unoptimized)       22.343s
Mandelbrot (C Optimized)          1.241s
Mandelbrot (BF Interpreter)       8.304s
Mandelbrot (BF JIT)               3.918s

The unoptimized JIT is 2x faster that the optimizing interpreter. Though we are nowhere close to the optimized C code, but the gap can be narrowed by making some optimizations to the generated code.

Future work can be done in constructing an IR of the source and making an optimization pass, for example ++++ can be converted to +4 directly then, instead of +1 instruction 4 times.

Certain references that really helped are:

UPDATE:

I made a few optimizations to fuse the multiple increment/decrement and pointer movement operations into a single one. The benchmarks from my JIT is now much closer to that of the optimized C version. The latest benchmark results are:

Implementation                      Time
----------------------------------------
Mandelbrot (C Unoptimized)       22.343s
Mandelbrot (C Optimized)          1.241s
Mandelbrot (BF Interpreter)       8.304s
Mandelbrot (BF JIT)               1.609s

Maybe I should look at implementing these optimizations next.

Knocked out of Node Knockout

I had spent this Saturday participating in Node Knockout. I had planned for a little Travelogue web app called Mapvel, with which one can share his experience about the current location, hence other users can get what people think about a place. I was planning to make use of a person’s real location by using the HTML 5 Geolocation API.

My team name was Struggler, that shouldn’t be a surprise considering that I am making this post.

But then things went downhill from there. I got this idea around 10 hours into the competition. Then I realized that to store Geolocation and perform spatial queries, I would need to use MongoDB. But this was the first time I had even planned to use it. Then I thought, lets make people sign in with Twitter, oh well, this was the first time I was implementing OAuth stuff in Node.js. Hence most of my time was spent in reading the docs and playing around with these. The build part comes later.

Apart from that there were some awesome happenings in college (I am being sarcastic!) and I also have 4 project submission to do this week. Excuses aside, I sat Saturday evening and night and got a basic version of the app running. Twitter login worked, MongoDB worked, I started hating Jade even more. Today morning I woke up and decided to give up.

It was good experience, I was coding fast, and learning fast as well, I just implemented login with Twitter and was querying MongoDB in few hours. Maybe I’ll get back to completing this Mapvel some other time.

Fun with morse code

Few days back I sat down and cooked up something, an estoric language made only of Morse code characters: . and _. I won’t call it a full programming language per se, but then it can be used to make some fun stuff (without the codes making no sense by themselves).

Mind you, don’t try to develop anything useful with it, (it just has basic stack manipulations and arithmetic operators on integers). If you can make something with it, I would send you a cookie. :)

The docs are up on the website and source code is on GitHub.

In the meantime here is a morse “Hello” program.

_.. __.____
_.. __.__..
_.. __.__..
_.. __.._._
_.. _.._...
___.
___
___.
___
___.
___
___.
___
___.

Recollections from the Mozilla Summit

Couple of weeks back I was at Mozilla Summit at Santa Clara, USA – a grand get together of people who contribute to people. This was the first time i was meeting the first global Mozilla community, the first time I went outside India. It was a massive effort to bring the paid employees as well as the voluntary contributors at the same place. I got to meet and talk to people with whom I had only been talking on IRC.

Mitchell Baker’s keynote on the Nature of Mozilla, really set the mood for the Summit and it best defines why Mozilla exists and why we all gathered over the weekend to discuss the future goals and plans for Mozilla.

The event lineup was well thought of, to keep you interested and give you options to choose from the tracks going on at parallel. I met so many people I probably don’t remember the names of quite a few but some were Brendan Eich, Asa Dotzler, Brian Bondy, Brandon Benvie, Alon Zakai, David Herman and so many others. It was great to talk to Luke Wagner over the internals of SpiderMonkey, Mozilla’s JavaScript Engine and JITs. I also had a chat with Patrick Walton over Rust and Servo and both the projects really look promising.  Randomly bumping into new people while playing Guitar Hero and getting to talk to them is another great thing about these events.

It was very informative to see the demos and talks about the upcoming projects and products we are working on, advances with respect to performance of FirefoxOS, brainstorming on the different products and discussion about how we can improve the Mozilla ‘platform’ code, sessions about Servo, how to appreciate contributors and so many others. At Innovation Fair booths I could interact with all these people who are working on these projects, and it gave much better insight.

It was a great event, I felt a part of the common cause, of a shared vision — of an open web.

PS: Thank you Mozilla for the free passes to Great America, the amusement park was one experience I will never forget.