ICFP 2009 contest blog - Team Blue Iris

I just threw in the towel on the ICFP 2009 Programming Contest.

The problem this year was a set of 4 sub- problems related to orbital mechanics, plus a virtual machine spec. The virtual machine was used to enable the problems to be specified exactly, without worrying about differences in the order of math operations.

Implementing the virtual machine was easy and fun. Unfortunately, actually solving the final sub-problem required learning too much math and physics. I was able to solve problems 1 and 2, and make an entry for the lightning round. And I brute-forced a solution for problem 3. But now, 56 hours into the contest, I am giving up on problem 4.

I can see the general outline of how to solve it, but it would take sharper tools than I have now. For example, I’d like a way of solving Lambert’s equations, but I’m having trouble deriving the code on my own, and the best example I’ve found while searching the web is a 30-year-old NASA Space Shuttle Fortran program. Also, I’m pretty tired, and this is affecting my judgment. I don’t think it’s worth going on at this point.

Some fun things I did during the contest:

  • Learned Orbital Mechanics, the study of how bodies move in space.
  • Learned what a Hohmann Transfer Orbit is and why to use it.
  • Learned what Lambert’s Theorem is, and how to apply it to missile guidance.
  • Wrote a Python program that did efficient calculations by generating a C program, compiling it, and then running it and talking to it via a pipe.
  • Read a ton of Wikipedia articles, Google Books books and old NASA tech reports on orbit planning and course corrections.
  • Learned how old-school Q-system guided missiles work. Very clever use of ground-based computers to compute coefficient matrices that were fed into simple on-board analog computers for the duration of the flight.

Highlights of the contest:

  • Hanging out on IRC with 20 other contestants, trying to get the simulator to work.
  • Getting problems 1 and 2 to work.
  • Giving up on problem 3, then thinking of a brute-force way of solving it while in the parking lot, about to drive home. (Too bad I wasn’t further inspired to solve problem 4.)
  • Seeing the pretty pictures of the satellite orbits for problem 4.

Low-lights of the contest:

  • Wasting an hour or so due to bugs in the specification
  • Wasting an hour writing a Tkinter alternative to turtle graphics, then not being able to get a Tkinter window to show up, then realizing that Tkinter graphics are so limited that there’s no feature benefit over using the already-working turtle graphics.
  • The buggy scoring in problem 1 encourages people to program-to-the-scorer rather than solve the stated problem. I could probably increase my position in the standings by 10 places by hacking an “optimal” solution to problem 1 that uses all of the available fuel. But it seems like a waste of time.
  • Having to give up on problem 4.

My advice to (future) contest organizers:

  • Consider avoiding problems that require deep domain expertise. There’s only so much orbital mechanics and numerical methods one can learn in 72 hours.
  • Do whatever it takes to ensure that your VM machine spec is correct. In this case, just asking someone to spend a couple of hours implementing the spec would have exposed the show-stopping problems that everyone encountered.

Advice to myself for future contests:

  • Pace yourself on day two, to avoid burning out on day 3.
  • Be sure you understand the scoring system. For example problem 4 had partial credit, so a solution for problem 3 might have worked on problem 4.
  • Scheduling work and family life to enable a free weekend for the contest worked out very well.
  • Do more planning, and keep an eye on how the work is progressing, to avoid spending too much time on unnecessary work. “What’s the simplest thing that could possibly work”, and “you aint going to need it” are both good mottoes for this kind of contest.
  • Take a little time to refactor the code as you go along, to avoid slowing down due to barnacles. (Example, passing the problem number all over the place because it was one of the inputs to the simulation, rather than special-casing it and setting it once in the VM.)

Analysis of programming languages I used in the contest

I used Python and C. I actually completed the lightning round in pure Python.

Benefits of Python

  • Rapid development due to no compilation time, clean sparse syntax, well designed libraries, plenty of documentation and help available on-line.
  • Turtle graphics made it dead simple to display satellite orbits
  • The “struct” package made it dead simple to import and export binary data.
  • The “subprocess” package made it easy to start and control other programs.
  • Python 3.1’s exact printout of floating point values made it easier to tell what the math was doing. (Other projects ran into problems with almost-zero values printing as zero.)

Drawbacks of Python

  • Slow. I had to switch the simulation to C to have it run fast enough for problems 3 and 4
  • Global Interpreter Lock (GIL) - meant I couldn’t use multiple calculation threads written in Python in one process. (And my machine’s got 8 hardware threads. :-) )
  • Lack of static type checking is frustrating when program run times are long: I had a half-hour period wasted debugging simple errors that only occurred after 2 minutes of simulation run-time that a static type checker would have caught immediately. To be fair, I could also have caught them with unit testing.

Benefits of C

  • Very simple to write code.
  • Runs really fast. :-)

Why My VM’s Cool

I wanted to explain how my VM implementation worked, because I think it probably ran faster than most other VMs.

I wrote a Python-based VM as a reference. Then I wrote a VM generator that would read a VM spec and generate hard-coded C to implement that specific spec. I used a “comparer” VM to compare the output of the two VMs to make sure that there were no bugs in the generated C version.

The hard-coded C VM was really hard coded to each problem. All the VM instruction interpretation overhead was removed. In addition, because the VM didn’t have any indirection, the “mem” array was replaced by hundreds of individual local variables. This allowed the C compiler to do a very good job of optimizing the code, because it could easily tell there was no aliasing.

I included a simple interactive shell in each generated hard-coded C program. The console let you set inputs, run “n” simulation steps, and read the outputs. This made it easy for me to control the simulation from Python. It also made it easy to hand-test the C simulation.

One feature I meant to add, but ran out of time/energy for, was to save and restore the state of the simulation. This would have been very helpful in solving problem 4.

How I solved the problems

Problem 1: Wrote Python VM. Implemented Hohmann transfers as described in a Wikipedia article.

Problem 2: Calculated the correct time to start the Hohmann transfer analytically. (I read about how to do this in a textbook I found through Google books.) Added simple brute-force docking code to match orbits exactly. No fancy “S” curves for me. (And wasted about an hour wondering why I didn’t score, because early versions of the contest problem spec didn’t say you had to turn off your engine for 900 seconds. I finally figured this out by disassembling the VM to see why the score wasn’t being set properly.)

Problem 3: Used my fast VM to compute a table of where the satellites would be over time, then wrote a set of nested for loops that tried various Hohmann transfers at various times looking for a solution. The precomputed tables meant I could just look up where the target satellite would be for any time in the future, rather than having to do complex elliptical math.

Problem 4: Only got as far as simulating and visualizing this one (boy the orbits are pretty!) Too tired to continue. I was planning on using a variation of the brute-force approach that solved problem 3, with save-and-restore of the simulator state, because I would have to recompute the table of locations for my rocket each time its orbit changed.


Upon reflection, I think that this particular contest, especially problems 3 and 4, is best suited to a C/C++ solution. This is due to the heavy reliance on numerical methods to calculate the optimal trajectories.

I liked that there were multiple versions of each problem. It made it easier to tell if we were making progress, and also allowed whole-program-level parallelization to make use of muticore machines to solve the problems in parallel.

While I expect the ultimate contest winners will code in a mutable- state static-type-checked compiled language like C/C++, I predict Haskell will do fairly well in the contest, due to its speed and the ease with which it handles math. However, the winners will probably have a good grasp of orbital mechanics, and it seems that someone who knows the math is more likely to be using C-like-languages.

Well that’s it, now I’m looking forward to next year!

P.S. Here’s a Wiki with other team writeups:

FUN Team ICFP 2009 Writeup / Wiki

Dandy in JavaScript

Dandy game

This weekend I wrote a JavaScript version of my old Atari 800 game Dandy.

Check it out: Web Dandy

It was my first JavaScript application. It was about as easy as writing the Python version. I have only tested it in two browsers so far (Firefox 3.0 and Chrome), and only on one platform, OSX. I have already run into differences between the two browsers: Firefox 3.0 for OSX seems to double-post keydown events.

No sound or multiplayer yet. Oh, and I use the CANVAS tag, so I think older browsers (like IE 7) won’t work.

Living La Vida Linux at Work

Android system-level development can be done on either Linux or OSX. For the past few years I’ve been using OSX, but recently I’ve switched over to using Linux.

Why? Mostly for the higher performance. The full Android system build takes about 30% less time under Ubuntu 8.04 LTS than it does on OSX 10.5 on the same hardware. Not to mention that it’s much cheaper to buy a generic PC workstation than the equivalent Mac Pro.

I have had some early troubles:

It took me a while to get used to typing the “Ctrl” key instead of the “Command” key, and the ugly Linux fonts bothered me for a few days.

But since I’m mostly using the exact same programs on Linux as I was on OSX (FireFox, Eclipse, Android), after a few days everything clicked, and I think that I’m just as productive as I was before. And the faster builds and file system stuff (like grep) are wonderful.

It helped a lot to install the Blubuntu theme and some nice wallpaper to get away from the awful Ubuntu brown/orange color scheme.

Oh, and I’m using Chromium for Linux, which works pretty well, except that it doesn’t support Flash. I still fire up Firefox occasionally to watch Flash videos.

See, this is why we can't have nice things (Ubuntu 9.04 Intel Drivers)

A few years ago I tried Ubuntu and predicted it would become a serious challenger to Windows, in about 18 months.

Well, it’s about 18 months later, was I right?

Not exactly. Ubuntu seems to have stood still, if not actually gone backwards. In particular, the newer releases have much worse sound and video performance on my hardware (Intel CPU/GPU Mac Minis) than earlier releases.

The sound driver issue is because Linux, in its typical decentralized fashion, is trying to figure out how to provide a standard audio subsystem, and has two or three competing standards that are duking it out. Since they all suck it seems odd that people defend them so much. Just pick one already.

The video driver issue is because Intel decided to take several years to rewrite their Linux video driver stack, and Ubuntu decided to ship the new broken drivers rather than continue to use the old unbroken drivers. Very very lame on both Intel and especially Ubuntu’s part.

And Phoronix’s performance tests show that the performance of Ubuntu has gone downhill slightly over the last few releases. (With no offsetting user-visible feature improvements.) So we see the problem’s larger than just sound and video drivers.

It’s almost as if the Linux community doesn’t want to be successful.

Microsoft must be laughing all the way to the bank on this one.

The diNovo Edge is a nice keyboard for HTPC

I just bought a Logitech diNovo Edge Mac Edition keyboard for my Mac Mini HTPC. I bought the diNovo instead of the Apple Bluetooth keyboard because:

  1. Built-in trackpad.
  2. Built in volume control slider.
  3. Dedicated media transport controls.
  4. Nifty dock / recharger stand.

It’s my first Bluetooth device. So far I think Bluetooth works a lot better than IR, because you don’t have to point it at an IR receiver.

The diNovo does have some flaws:

  • No key backlighting, which makes it hard to use in the dark.
  • The mouse buttons below the trackpad are mushy and hinged at the outer edges, making them hard to press. (Happily tapping works and there is a separete left-mouse-button on the left edge of the keyboard. So for typical Mac usage you don’t need to use the mushy buttons.)
  • A skim of the Logitech support forums indicates that the function keys are not as programmable as some people wish. I don’t use function keys that much so this hasn’t been an issue for me yet.

My TV is a 40” LCD, and I sit about 15 feet away from it. At this distance the 1920 x 1280 desktop is just too high resolution for my eyes, so I reduced my screen resolution to 1366 x 720. That seems to work well for now. Apparently I need to get a bigger TV :-)

Using a keyboard/trackpad instead of a button- based remote control is nice. I like being able to use all the ordinary apps that I already know how to use, rather than have to learn a new set of apps and UI commands. I also like not having to switch input devices depending upon what I’m trying to do. (For example if I want to use a web browser to look up some fact about a video that I just watched, it just works.)

The diNovo is very smartly designed, so that it’s easy to use the mouse while holding the keyboard in two hands. Of course I’m a right hander. A left hander might have a different opinion, as the trackpad is located where it can be used easily with the right hand, but not the left hand.

What about Linux?

I have been able to use the same keyboard with both Mac and Kubuntu 9.04. With Kubuntu there were some issues around the initial pairing: You need a working keyboard and mouse in order to pair a new Bluetooth device. You even need to reboot once, and answer one final dialog box using a working keyboard / mouse, before the new device pairing is complete.

A second issue for HTPC use is that the Mac Mini video driver on Kubuntu does not have the flexability to slightly lower the resolution of the screen. I blame Intel for this, as they are in the middle of converting to a new driver model and their current drivers are pretty bare bones.

One final issue for dual booting Mac systems is that it seems to take a while for the keyboard to reconnect after a restart. This is an issue if you have reFit installed and you’re trying to send keystrokes to reFit during the reboot. I found I had to press multiple keys multiple times until reFit started recognizing keys, after which the keyboard acted normally.

Larrabee Instruction Set Talks


Here’s the first public version of the slides from Tom Forsyth and Michael Abrash’s GDC 2009 talks on Larrabee’s instruction set, by way of Japanese magazine PC Watch, as seen on Beyond 3D’s Forums. (You have to manually click on each of the little thumbnails of each slide.):

Larrabee Instruction Set

Hopefully Intel (or GDC) will release a better version of these slide decks sometime soon.

Say, was it just me, or was blogging really light about GDC this year? In past years I was a lot more technical writeups than I saw this year. I wonder if blogging is down in general? Is everyone on Facebook and Twitter now? I can’t imagine Twitter being very useful for reporting technical information.

Here’s Michael Abrash’s Doctor Dobbs Journal article on the Larrabee instruction set.

Dr. Dobbs Larrabee

Here’s the Intel GDC 2009 Larrabee talks:

Rasterization on Larrabee: A First Look at the Larrabee New Instructions (LRBni) in Action SIMD Programming on Larrabee: A Second Look at the Larrabee New Instructions (LRBni) in Action

Using XBMC on Mac Mini using both OSX and Linux

The Xbox Media Center (XBMC) is a nifty open-source application for watching videos. It was originally designed for use on modified Xbox video game consoles, but has more recently become popular for Intel-based Home Theater Personal Computers. It has been ported to Windows, Mac, and Linux. It has no PVR features, instead it concentrates on displaying streaming and downloaded videos. Its big advantage over using the Xbox 360’s similar application is that it handles a much wider variety of streaming video sources and downloaded video codecs.

I’ve been running Plex, an OSX- specific version of the Xbox Media Center, on my Mac Mini for several months now. Overall it’s a good product, but I had some issues for my application. I wanted Plex to serve as a consumer electronic device that my mother-in-law (who doesn’t use computers and can’t read English) could use by herself to watch videos. The system I put together didn’t work very well for her. The problems we ran in to were:

1) The integration with the 6-button Apple Remote Control into the Plex/XBMC UI leaves a lot to be desired. The XBMC UI was designed to be used with a full-featured remote, and the Apple Remote mapping is just too hard to use. My mother-in-law would end up in the weeds of some obscure corner of the Plex UI, without knowing how she had gotten there or how to get back. The Plex software contributed to this problem by having a very sluggish interface to the Apple Remote, that frequently missed clicks. When you couple this with the overloading of “short” and “long” presses to try and give the Apple Remote more logical buttons, it became quite difficult (even for me) to reliably drive the UI. Even a task as simple as backing out of a playing video was difficult to do reliably.

2) OSX (and Plex) have trouble running in consumer-electronics mode, without a keyboard or mouse. OSX and Plex both liked to bring up modal dialogs to report errors or software updates. I was always having to drag out a keyboard and mouse to dismiss these dialogs.

Now, a sensible person would work around these issues by buying a Bluetooth keyboard and mouse, and software like “Remote Buddy” that enables the use of a full-featured remote. A somewhat more ambitious person might have rescripted the Plex UI to work better with the Apple Remote, or even dug into the sources to try and fix the sluggish event problem. But I’m restless, and wanted an excuse to try out Linux on the Mac Mini anyway. So this week I decided to see if the Linux version of XBMC worked any better.

Installing Linux XBMC

Installing Linux is alot like the old pre-Windows 95 days of DOS. I spent a lot of time trying different things and fiddling with hardware issues. Here’s what finally worked for me:

So far (one day) this has worked well. The full-functioned remote control make a big difference in usability.

Some issues I ran into

Ubuntu 9.04 beta problems with OpenGL accelleration for the Mac Mini

The Ubuntu 9.04 beta Intel 945 OpenGL driver does not hardware accelerate as many features of OpenGL as in older versions of Ubuntu. XBMC’s user interface runs very slowly. This is not XBMC-specific. Try using apt-get to install the “amoeba” OpenGL demo. It runs smoothly on Ubuntu 8.10, but is a 2-frame-per-second slide-show on Ubuntu 9.04 beta. I hope this regression gets fixed in future versions of Ubuntu 9.04, as it otherwise looks like a good system.

The prebuilt “PPA” XBMC binaries will crash on Ubuntu 8.10 when pausing video

I had to build XBMC from the subversion sources in order to fix a bug where pausing a video would immediately cause XBMC to crash. (I used a build from Thursday March 26th. I’m sorry but this is the first time I’ve used subversion, so I don’t know how to figure out which revision number I’m synced to.) This is a bug that’s been reported several times in the XBMC forums. It seems to be solved by compiling from source, without making any other changes. I’m suspicious that this may be due to some subtle difference between the libraries that you install to compile and the libraries that are installed when you install the prebuilt binary. (But that’s just a guess. The real reason may be something completely different.)

Well, after all this the system seems to work pretty well for my application. Too bad my mother-in-law’s finished her visit with us and gone back home. At least now I’ve got plenty of time to work out the bugs before her next visit.

[Revision notes]

3/27/09 - Updated for Ubuntu 9.04 beta.

Intel describes Larrabee instruction set

Perhaps in preparation for Friday’s GDC talks by Michael Abrash and Tom Forsyth, Intel has described the Larrabee instruction set:

Prototype Primitives Guide

Intel includes a C source file that implements their new instruction set, so people can play around with the instructions before Larrabee ships.

The instruction set looks alot like a typical GPU shader instruction set. Lots of “log” and “rsqrt” type instructions. But there are also some interesting variations on MADD, such as MADD233_{PI,PS}, which I assume help shave cycles off of inner loops. The compress and expand instructions also look very useful. I look forward to reading code examples from Abrash and Forsyth in the near future!

Listening to my home music at work with SqueezeCenter and Softsqueeze

For some time I’ve wanted to listen to my home music collection on my computer at work. I tried a bunch of different approaches, and finally came up with one that works pretty well:

The resulting system works pretty well. In case you’re wondering, the SqueezeCenter program’s main use is to serve music to the Squeezebox brand of internet radios. The ability to use it with a regular computer, without purchasing a Squeezebox internet radio, is a nice gesture on the part of the Logitec company that makes and sells Squeezebox internet radios.

Future GPU.org for cryptic Larrabee news

Phil Taylor, a long-time Microsoft graphics and gaming evangelist is now working for Intel on graphics tools evangelism. He started a blog, called Future GPU, where he drops hints and links about Larrabee development. He also tells Microsoft war stories for people in the mood for inside-baseball information about Microsoft’s DirectX and game groups.

Back when I was working at WebTV and just learning about the 3D graphics world, Phil was nice enough to give me and a few of my WebTV co- workers tickets to the super-desirable GDC DirectX party. These parties were intended for external developers, so it was very hard for non-DirectX Microsofties to attend. Thanks Phil!!! :-)

From reading Phil’s blog it sounds like Intel’s developing a set of graphics debugging tools that they’re going to announce at GDC. Could it be PIX-for-Larrabee?

I found Phil’s site through a “Google Alert” that I set up for Larrabee news. It does a weekly search for Larrabee news. The web’s so big and sparsely connected that I’m finding that I’ve never heard of any of the web sites that the Alert is dredging up. Most of the sites mentioned in the Google Alert are not worth visiting, but a few (like Phil’s site) are very interesting indeed.