Josh Haberman

Only when you develop cross-platform do you get the joy of using both the best profiler ever and the best memory debugger ever.

Scratch what I said the other day. Delivering a Gazelle IDE as a web application was this great attempt-to-be-forward-thinking dream that I clung to for a while. But yesterday in the wake of the news that Qt is going LGPL I gave it another look. And I have to say, the debate is over, the Gazelle IDE will be a standalone, cross-platform application written using Qt.

Why? Because it’s the answer to all the problems I posed before (of which there were many):

• The Gazelle compiler (wrtten in Lua) can run right there in-process, because the IDE can link in the Lua interpreter.
• The Gazelle runtime (written in C) can be linked in and run right there in-process, and be way faster than a JavaScript implementation would have been.
• Graphviz (written in C) can be linked in and run right there in-process.

It also answers several other problems I hadn’t even explicitly posed.

• Web applications don’t have access to the local filesystem. Desktop applications naturally do.
• Web applications are limited by the performance of JavaScript (a high-level, garbage-collected language). C++ applications have better performance (and I plan for the Gazelle IDE to have a lot of graphics going on).
• Qt has a really awesome support for, well, pretty much everything. Creating scene graphs that support hover, onClick, drag&drop, good drawing, animation, everything I was thinking about seems to be well-supported.

I’m still trying to be sure that Qt applications feel sufficiently “native” on Windows and Mac. But unless that’s a big disaster, Qt looks like the best path to my goals.

While I’m on a roll with these blog entries, I thought I’d share just one more secret that’s been kicking around in my head for a while. I desperately want to see a Gazelle development environment that runs in your web browser.

I first had this idea when I visited the excellent regular expression reanimator. It’s this beautiful little visualization that runs in your browser and shows you how a DFA transitions in response to text. And all you have to do to use it is click that little link!

My dream is that you can develop your grammars interactively. You type rules and as you type you see little graphs build themselves up, state by state. You add a kleene star and you see the extra transitions add themselves to the existing graph. You put some sample text in another textarea and watch it start syntax-highlighting itself as you add the rules to properly recognize its structure. Or you can develop your own syntax highlighting color schemes by typing syntax highlighting rules and again seeing them incrementally take effect on a block of sample text.

None of these ideas are brand-new. ANTLR of course has ANTLRWorks, which is an IDE for developing ANTLR grammars. But I feel that having this on the web would really lower the barrier to entry and make it accessible to more people. And despite how people poo-poo JavaScript and HTML, the web is not such a bad platform these days — especially now that SVG support is getting really good. SVG is the perfect tool for drawing graphs, styling the nodes in various ways, and having them do useful things when you hover/click on them.

So anyway, I really want this. But the hurdles to making this happen are great!

• Gazelle’s compiler is written in Lua. No real way to run Lua in a browser right now. Possible options for doing this in the future: a Lua -> JavaScript compiler, a Lua VM written in JavaScript, porting the Gazelle compiler to JavaScript, running the Lua interpreter inside NativeClent, and running the Lua interpreter inside Alchemy.
• Gazelle’s runtime is written in C. Possible options: port the runtime to JavaScript, run it inside Alchemy, or run it inside NativeClient.
• The Graphviz graph layout package is also written in C. Possible options are the same as the Gazelle runtime. I was seriously considering porting just the layout algorithms to JavaScript and had even started the port, but have recently been realizing how CPU-intensive these algorithms are even in C. In JavaScript they could only be slower. With Alchemy they would be slower than pure C, though it’s hard to say how much. With NativeClient they would run at native speed.

So it pretty much looks like I’m stuck waiting for either Alchemy or NativeClient to be prime-time. While I could always run all this software on the server and AJAX the results in constantly, I don’t think that would provide a smooth enough user experience (not to mention the load it would put on my server — these algorithms are kind of expensive).

As far as Alchemy vs. NativeClient: Alchemy will be slower (2-10x according to them) since it compiles your C/C++ to the Flash VM instead of to machine code, and it will require the Flash plugin. NativeClient will run at roughly native speeds, but will require a plugin download (most people will have flash already) and one that has potentially scary security implications if the NativeClient guys made any mistakes.

Time to play with Alchemy and see if I can get it to work! And hope that NativeClient makes a lot of progress in no time!

For no reason in particular I decided to dig into LLVM today. I decided to try out its assembly language by writing a line count program in it (I chose this problem since I had previously written an optimized x86 version using SSE). This was of course significantly trickier than I initially expected and took me several hours to figure out.

SSA took some getting used to. I understood the basic idea before but had never worked with it. The surprising thing is that you don’t get registers, which means that to do something as simple as the “i++” of a for loop you have to:

  %current_i_val = load i32* %i
  %new_i_val = add i32 %current_i_val, 1
  store i32 %new_i_val, i32* %i

In this example, “%i” is the address of a stack variable where “i” lives. I have to load the current value, increment it, and store it again.

This load/modify/store business made me uncomfortable because it felt really inefficient. You just have to trust that when LLVM does register allocation that it’s smart enough to know that it doesn’t actually have to do the load/store each time.

I was also surprised that LLVM assembly language is more strict that real assembly languages about the structure of each function. Each function has a series of “code blocks” and each code block must begin with a label and end with a “termination instruction.” As an example, here’s a function definition and the first two blocks in that function:

; Returns the number of newlines found in a buffer.
define i32 @count_newlines(i8* %buffer, i32 %bufsize) {
  ; Local variables.
  %i = alloca i32
  %num_lines = alloca i32

  store i32 0, i32* %i           ; Initialize to zero.
  store i32 0, i32* %num_lines   ; Initialize to zero.
  br label %loop  ; can't just fall through to %loop

loop:
  %i_val = load i32* %i
  %is_done = icmp uge i32 %i_val, %bufsize
  br i1 %is_done, label %done, label %continue_loop

So you can’t just put labels anywhere willy-nilly, you only get one label at the beginning of the block. The termination instructions are mostly branches of various sorts. Basically this means that you can’t just “fall through” to the next label without branching — if you want to proceed to the next block you have to explicitly end your current block by branching to the next one. So in this sense the order of the blocks as you write them in the file is insignificant — the only significance is the first one, which is automatically run when you enter the function.

Once you write your LLVM assembly language, you can assemble it with llvm-as, and then either run it with “lli” (which will JIT+run it) or compile it to x86 assembly with “llc” and then assemble it with gcc.

$ llvm-as wc.ll
$ lli wc.bc < /usr/share/dict/american-english-huge
638818
$ llc wc.bc
$ gcc -o wc wc.s
$ ./wc < /usr/share/dict/american-english-huge
638818

In a comment to a previous entry, Emmanuel Castro asks:

You chose the LLVM bitcode format for Gazelle instead of Google Protocol Buffer.

Is there any reason, or was it just because you made the choice before Protocol Buffer was available.

Protocol Buffer seems to have a better language support (C , Java, Python).

This is a good question. The easy answer is that I chose LLVM Bitcode before Protocol Buffers were available. But the harder questions are “would I make the same choice today?” and “should I port Gazelle at some point to use Protocol Buffers (or something else) instead?”

Being quite familiar with both formats (I’ve implemented both), I thought I should take a moment to compare/contrast the two. These two formats target a really similar use case (compact, binary encoding of arbitrary data) but have some significant differences.

Data Definition/Schema:

With protocol buffers, you lay out your schema in a .proto file that looks something like this:

message Person {
  required string name = 1;
  required int32 id = 2;
  optional string email = 3;

  enum PhoneType {
    MOBILE = 0;
    HOME = 1;
    WORK = 2;
  }

  message PhoneNumber {
    required string number = 1;
    optional PhoneType type = 2 [default = HOME];
  }

  repeated PhoneNumber phone = 4;
}

Having a formal schema means that generic protobuf tools can generate code with nice classes/structures that mirror the schema. Generic tools can also pretty-print Protocol Buffers given the .proto file.

With Bitcode, on the other hand, there is no formal schema. Schemas are informally specified in some mixture of documentation (here’s LLVM’s and here is Gazelle’s) and code. This means that generic Bitcode tools have much less information to go on for things like code generation or pretty-printing.

The lack of a schema system isn’t inherent to Bitcode, and one could easily be added. But given the status quo of it not having one, Protocol Buffers are the clear winner here.

Space efficiency

Both Protocol Buffers and Bitcode are quite concerned with space efficiency, but Bitcode is a bit more extreme about it. Specifically:

1. Bitcode files are considered a stream of bits rather than a stream of bytes. Bitcode is the absolute only format I have ever encountered that does this. This leads to greater space efficiency (since you can encode a boolean value using only 1 bit, for example), but is more expensive to encode/decode since you have to be shifting and masking a lot. I don’t have any data about how significant this is.
2. Bitcode allows you to define “abbreviations”, which allow you to define bit-by-bit what your records will look like. You can define an abbreviation that says: “a 1-bit integer (a boolean) followed by a five-bit integer followed by a variable-bit-rate integer where each chunk is four bits.” Using this facility you can optimize your records to use exactly as many bits as they need, with none wasted! But it takes a lot of work and foresight on the application developer’s part to get the most of this.

So the general idea is: Bitcode is smaller, but probably takes more CPU and more work on the application developer’s part. But unfortunately I have no measurements about how much smaller or how much more CPU or how much more work.

Data Model

The Protocol Buffer data model is: each protocol buffer is a series of key/value pairs. Any of the values can itself be a protocol buffer, which provides hierarchy. The values can be any of 10 integer types, float, double, boolean, UTF-8 string, or raw bytes. Any of the keys can repeat if the .proto file says they can.

person {
  name: "Harry"
  age: 42
  likes_color: "blue"
  likes_color: "green"
  vehicle: {
    make: "Toyota"
    model: "Prius"
  }
}

The Bitcode data model is: files are a series of data records, and data records can be nested inside blocks to provide hierarchy. Each data record has a code and a series of integers:

[DataRecord code=5, 3, 9]
(this next record might be ASCII values for "Hello",
 but there's no string type so we don't know)
[DataRecord code=8, 72, 101, 108, 108, 111]
[block id=9]
  [DataRecord code=4, 6, 5]
  [block id=10]
    [DataRecord code=8, 8, 1]
  [/block]
[/block]

Clearly there is less semantic information at the Bitcode level, which means that generic Bitcode tools can’t show you as much. Most notably, Bitcode has no notion of a string. And since there are no keys to the records in Bitcode, everything is dictated by the order of the records in the file and the order of the integers within the records. This means that Bitcode will be more space-efficient if all of your records have the same set of fields. On the other hand, if your records have a large number of possibly optional fields but each actual record uses only a few, then Protocol Buffers will be more space efficient.

Both formats are capable of seeking over sub-records/blocks that you aren’t interested in parsing.

Adoption/support

I haven’t been following the spread of Protocol Buffers too closely (which is a shame since I keep meaning to finish my C implementation), but it’s almost certainly more widely adopted than Bitcode, which has never really been marketed at anything other than LLVM. This is definitely a concern, because I ended up having to implement Bitcode myself. This ended up being a significant diversion for me — it took me many weeks and a lot of frustration, and despite being only about 1000 lines of code, it was subtle and difficult to get right. I would have much rather used an existing library, but LLVM’s Bitcode library was C++ and I wanted to stay 100% C.

Conclusion

So on every count except space efficiency Protocol Buffers seem to be a win. If I was doing it again I might choose Protocol Buffers instead. I’d still like to see the degree to which Bitcode is more space-efficient, because space-efficiency is quite important to me.

I still have a half-implemented C protocol buffer library sitting around, and hope that someday I’ll get around to finishing it. Once I have that, I may consider porting Gazelle’s bytecode to use protocol buffers instead.