Sub Ubi

During the last two weekends, along with some good help from Christian and Damian, I wrote a compiler.

The compiler takes a subset of the occam programming language, and compiles it to Transputer bytecode. SEQ, PAR, ALT, channel communication, and some basic arithmetic and logical expressions can be dealt with by this compiler. Written as “one to throw away,” the compiler was an exploration into some design decisions and their potential impact in a larger (full) compiler. Furthermore, it provides a starting point for the discussion of what languages and tools are most appropriate for authoring a compiler today.

A lab seminar and tech report on the compiler will follow shortly.

Related, but not quite, to this are a number of links I don’t want to loose track of. Mostly, they’re just the results of a Google search that this two-weekend project inspired. No doubt, they’ll inspire other searches as well.

• VHDL Tutorial
• SPARK: A parallelizing approach to the high-level synthesis of digital circuits
• Automatic compilation to a coarse-grained reconfigurable system-on-chip
• A quantitative analysis of the speedup factors of FPGAs over processors
• Hamburg VHDL Archive
• Maps: a compiler-managed memory system for raw machines
• Improving register allocation for subscripted variables

Lets do a little math today.

If I wanted to purchase a Zire 72 from the Palm UK store, it would cost £189. If I purchased the same product from Palm US, it would cost $300, minus a $50 rebate. Multiply $300 by .531276, and you get £159. Additionally, if you purchase in the US, you

• Receive a 128MB SD card with your purchase (free)
• Can mail in an old handheld for a $50 gift certificate
• Can get another $100 off the handheld by joining Audible for a year ($150 cost, so this is a net $50 loss)

That is, the Zire 72 in the US is $250 (£132), I can get a $50 gift certificate for the Zire 21 I paid $40 for at Amazon, and can consider paying $50 for a 1-year subscription to Audible.com, which is an MP3 audiobook download site.

Or, I can pay £189 in the UK for the same device.

(This is, of course, assuming I even decide to upgrade.)

So, I’m enjoying surfing the web for this. Given that I’ve flown twice in my life—once was a failed flight of a Kyosho Serenede, and the second was a powered foam delta wedge. In the second case, I had to claim I was an experienced flyer, but I did quite well, actually…

• The Mugi Evo is a twinwall craft. This is made out of twinwall plastic/sheeting, and it’s a cut/fold/glue operation to build the craft. So, the cost (outside of the radio/servos) is minimal. I’m guessing they’re unstable in the air, and not an ideal choice for a beginner. That is, they’re probably relatively fast flyers and unstable in strong winds.
• The Wattage Micro Flyer
  is just funny. It flies on an oversize capacitor (no doubt) for 6 minutes, and then you “recharge” it with the R/C transmitter/battery pack. Cute.
• The Indoor Flying Object is an interesting little craft. Made of flexed carbon fiber and… kevlar, this little craft looks like it could be fun and take a beating. Granted, I imagine that it’s not an easy beginner craft. As an “acrobatic slowflyer,” I suspect that means “dynamically unstable, even at low speeds.” However, cool looking little aircraft.
• A Carbon Falcon is an appealing style of craft in many ways—although, the rudderless design seems to imply some potentially dangerous flight behavior. It’s an appealing design because the carbon-fiber construction can be broken down and rolled up. As long as I’m living abroad, that has a certain appeal. That, and the kite-like construction is, apparently, nearly indestructible.
• Handlaunch gliders look fun—limited in scope, challenging to learn, and certainly don’t require much infrastructure. However, once I start looking at gliders, I find myself lusting after a 2m sailplane… Looking at a few handlaunches (the Zuni, for example) and DLGs (discus launch gliders, like the Osiris) I’m impressed with the minimalism of the construction. DLGs are especially appealing to me, I must admit, as I threw discuss for 7 years, through middle/high school and college. Lots of links here and here.

Ah. Fantasies of flight. And, after watching a few videos of sport gliders flying at 60-80 MPH, I know I don’t need one of those!

I think I’d like a toy. In particular, I think a remote control powered parachute would be very cool.

Not that I imagine this in the immediate future, but… well, anyway.

This means it is time for bed.

And I quote:

“Dude, if your examiners ever find out you were surprised that O(n) operations, like indexing into a list, were slow, your PhD is totally revoked! ;-P”

In light of yesterday’s post, this is a fair comment, but let’s put it in context, yes? (Fear not, gentle reader: ninjas have already been dispatched to deal with the commenter. And, I think the commenter was just teasing me… but, the ninjas will torture that fact out of him at some point or another, no doubt.)

The Transterpreter project has, from the start, been intended to be as simple as it can be in execution and implementation. Our primary goal is to create a portable runtime that can be easily ported to any architecture we encounter. Therefore, throughout the development of the runtime, we have consistently made semantically clear but often computationally expensive choices.

Our architecture is, generally speaking, easily optimized locally, and in some cases globally. However, optimizing sooner (rather than later) is a good way to be left with code that A) you don’t understand, or B) is potentially inflexible or inappropriate in light of later extension. In the long run, our goal is to support an evolving programming language; how do you design tools to support that? Guy Steel gave a brilliant talk on this at Indiana while I was there, and this short article on the Sun website touches on some of the issues involved. In short, the number of factors involved in supporting a growing and evolving programming language are many, and complex.

So, no, we weren’t surprised as such that indexing into a list was expensive. Rarely have I written code where the time/space difference between referencing into a linked list is significantly different than indexing into a vector. If anything surprised me, it was the immediate and obvious disparity between the two, and how (as a Scheme programmer) I often completely forget about the underlying performance concerns. Put another way, I am more often concerned with correctness than performance, or am writing code that A) is evolving rapidly and B) has limited application. Therefore, a list (which is, in a dynamically-typed language like Scheme) becomes a “universal type” that gives me flexibility and freedom to evolve interfaces quickly and without large changes to my core program logic.

In the end, you could argue that we should have known better from the start. However, you could also argue that we’ve used appropriate tools in appropriate ways to get us quite far into a project that otherwise might have become bogged down in details long ago. It is flexible, runs most everywhere, and while it did have a 60x speedup lying around, that speedup took … two, three hours of time to realize fully? This implies that our design was simple and clear enough that we could pluck that 60x off the tree as low-hanging fruit, and not a major architectural overhaul. While some of our local choices may have been naive, our global, or architectural choices have been, I think, sound.

For over a year now, I’ve been collaborating with Christian on a lightweight and portable runtime for the occam programming language which we call the Transterpreter. This has been a fun project, because occam is a clean little language, and I enjoy architecting and writing compilers, interpreters, and similar kinds of software.

We wrote our first version of the bytecode interpreter in Scheme. Because we were reverse engineering the Transputer (a processor that ran compiled ocacm bytecodes) from a variety of sources, we felt that we had enough concerns without worrying about, say, memory management or pointer arithmetic. Our first version was slow, but it was clear, and the first version of the rewrite into C was almost a line-for-line translation.

Early in the project, Christian had written a Python script to clean up the bytecodes emitted by the existing compiler. It did the job, but with the rewrite into C we began thinking about the infrastructure for supporting a virtual machine that should be able to run anywhere. The occam compiler runs under any *NIX-like environment, and can be compiled for Windows using Cygwin or an old Borland toolchain, so any extensions to the toolchain should be at least as portable, if not more-so.

We considered a number of alternatives, but because of my experience programming in Scheme, we decided that PLT Scheme would be the implementation platform of choice. PLT Scheme (which encompasses MzScheme and DrScheme) runs damn near everywhere; there is excellent support for executing Scheme programs (interpreted or bytecode compiled with a run-time support library) on Windows, Mac (OS 9 and X), most flavours of *NIX, and even some PDAs. This way, the backend of our toolchain would be very portable, and let us program in a clean, well-understood and well-used language.

So, the slinker was born. Although, it is more than a linker—it’s like a compiler backend-ish, really. It started off with a 15-20 micropass (pipelined) architecture (inspired by this work), has grown in reasonable ways, currently needs some cleanup, but the architecture has proved to be flexible enough that we’ve been able to accommodate interesting additions without having to do ugly things like, say, scrap the codebase. We successfully designed for extension, and that’s good.

Unfortunately, when we started running the CG test suite, we suffered; the slinker was taking as much as 20-30 minutes on some tests. The compiler took seconds, the slinker took half-an-hour, and then running the test took a few seconds. This was, we agreed, bad, but optimization takes time, and we didn’t have that. We did have machines laying around that could run the test suite over night, which was good enough.

An exercise in optimizing Scheme

Yesterday, we started optimizing. Now, I learned some interesting things (I should have known) about PLT Scheme in the process. For example, we had a loop that looked like

(while (

This code was killing us. Slaughtering us. On 150,000 element lists, we would run for 200,000ms or more (and this was a large, but not huge, bytecode array). All the other passes in the slinker ran in 0 to 60 ms, and the DrScheme profiler was really quite clear that our problem was buried in this loop---not elsewhere.

This unrolled to a 'named let' in Scheme, which should be every bit as efficient as a for in most other languages, so we assumed our loop was not a problem. Or, put another way, we had perfectly fast code elsewhere that used the same macro, so that wasn't the problem.

Immediately, I decided the consing to build a list was certainly a problem. So, we got rid of that. To find out what was a good structure to use, I wrote a little "benchmarking" script to test insertions into vectors and hash-tables. It was faster to do an insert into vectors, so the structure build-up was modified.

(while (

Now, this code ran faster. We got a barely perceptible speedup at this point. This struck me as odd, as we had just benchmarked this, and clearly we should have seen a large speedup.

So, that wasn't the bottleneck. Keep in mind now, we only have a few things going on in this loop:


The test (,

A vector-set!
A list-ref on the bytecode list
A variable increment (the set! on pos)

Lets eliminate a few things right now. First, the increment on the variable is not the source of the problem. The vector-set! had just been benchmarked, and we revisited our benchmarking script to verify, but decided that we certainly were OK on the vector insert. The test, also, isn't a problem: even with dynamic typing, the check to see if one integer is smaller than another is still fast. Which left our list lookup.

We achieved a 5x speedup by changing one data structure and one function call in our code above.

(while (

See it? vector-ref instead of list-ref. Why? I haven't looked at the MzScheme source yet (I will, as I'd like to know what's going on) but I have a good idea as to why this accounted for a massive speedup in our code. Vectors are probably treated as contiguous locations in memory, and so the entire structure is allocated on the heap in one big chunk. When you operate on it, and in particular, reference into a vector, it's a simple index into memory from the head pointer.

Lists in Scheme are different; they're a bunch of cons pairs (or, they can be). I suspect that MzScheme handles lists very differently from vectors, and when we build a list with 150,000 elements, the cons pairs end up all over the heap. Referencing into the list is certainly not a constant-time operation; in fact, we were being badly, badly abused by our references into the list. I have no idea how many trips out to main memory had to be made to reference into element 126449 of our list... perhaps dozens.

This morning, Christian worked on a few other passes that we suspected had similar ugliness---as they, too, took many minutes to run. Now, our largest test case, which previously took 30 minutes to link, now links in approximately 30 seconds. That's a 60x speedup.

Lessons learned
I don't think we've done anything wrong here; we wrote simple, clean code to start that allowed for flexibility while developing. When we finally reached a good place to stop and look at the entire project, we made some key optimizations that, perhaps, could have been implemented from the start. However, early in the project, speed didn't didn't matter. Good design and sound implementation mattered. The software worked. And, we think, it continues to prove itself as extensible and maintainable.

And, now, we see that our linker is easily optimized as well. Our entire compiler test suite of several thousand cases runs in 30 minutes, and perhaps even less before the day is over. A few days ago, we had to run it overnight because it took so long; now you can start a run before going to lunch, and have results when you get back. Sweet
But yes. I believe it's true: premature optimization continues to be the root of all evil. 
(PS. I'll drop a note here when I take some time out to look at how MzScheme handles vectors vs. lists; that was an interesting revelation.)