28 Jun 2009
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.
Conclusions
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
15 Jun 2009
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.
01 Jun 2009
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.
01 Jun 2009
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.
02 May 2009
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:
- Built-in trackpad.
- Built in volume control slider.
- Dedicated media transport controls.
- 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.
30 Mar 2009
###
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
27 Mar 2009
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.
25 Mar 2009
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!
06 Mar 2009
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.
17 Feb 2009
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.