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.