Thursday, December 17, 2009

Tom Forsyth (Larrabee Dev) speaking at Stanford

I just noticed Tom Forsyth, aka tomf, is speaking at the Stanford EE CS Colloquium on January 6, 2010. The video will hopefully be posted on the web afterwards.

The topic is "To be announced", but is very likely to be Larrabee related.

Thursday, November 26, 2009

3D toolchain musings

I'm writing a skinning sample for a future Android SDK. This has prompted me to construct a toolchain to get skinned animated models into Android applications.

I'm really only just getting started, but so far I'm thinking along these lines:

Wings 3D -> Blender 2.5 -> FBX ASCII -> ad-hoc tool -> ad-hoc binary file -> ad-hoc loader.

For what it's worth, right now Blender 2.5 doesn't support FBX export, so I have to do Collada -> FBX Converter -> FBX. But Blender 2.5 support should be ready fairly soon.

You may wonder why I'm considering using the proprietary and undocumented FBX standard rather than the open source Collada standard. I'm doing it for the same reason so many other tool chains (e.g. Unity, XNA) do, namely that FBX is a simpler format that just seems to work more reliably when exchanging data between DCC applications.


Blender 2.5 alpha 0 is looking pretty good

The open-source Blender 3D DCC tool has long suffered from an ugly, non-standard, hard-to-learn UI. I'm very happy to see that the latest release, which just entered alpha status, has a much improved UI. It's not quite Modo quality, but it's starting to get into the same league as commercial DCC tools.

Wednesday, November 25, 2009

Two very good talks on ECMAScript 4, 5, and 6

Yahoo continues to be a source of excellent information on recent and future versions of JavaScript / ECMAScript. Here are two very good talks from November 2009 about the evolution of JavaScript from 2000 until now:

Tuesday, November 24, 2009

Prince of Persia Developer's blog

In the late 1980's Jordan Mechner single-handedly designed and programmed the original Apple II version of Prince of Persia and several other groundbreaking games. He published his development journals and technical design documents on his web site. The journals touch on:
  • The development of the stop-motion animation techniques used so effectively in PoP
  • The tension in Jordan's life between his two callings: game development and feature film scriptwriting / directing.
  • The difficulties involved in developing and selling a new game idea.
  • A view into the late 80's / early 90's pre-web game development business.
Although many games are now written by large teams of people, in the end, a lot of the business, artistic, and technical issues Jordan writes about remain relevant. I highly recommend these journals for anyone interested in an inside view of game development. (Or anyone interested in trying to break into Hollywood. :-) )

Tuesday, November 10, 2009

A Multi-threaded Go Raytracer


Above is the output of the raytracer. Below is a diagnostic mode showing which goroutines raytraced which section of the screen. Each goroutine has its own color to outline the pixels it traces:



I wrote a simple multi-threaded ray tracer in Google's new "go" language. It's an adaptation of Flying Frog Consultancy's Raytracer.

It runs single-threaded about 1/2 the speed of a comparable C++ version. I guess the C++ version benefits from a more optimizing compiler and the ability to inline small functions.

Compared to ordinary C/C++, the Go version was easier to multithread.

On my dual-core Macbook Pro I get an 1.80x speedup when running with GOMAXPROCS > 1:

$ GOMAXPROCS=1 time ./gotrace
1.52 real 1.50 user 0.01 sys
$ GOMAXPROCS=2 time ./gotrace
0.82 real 1.50 user 0.01 sys
$ GOMAXPROCS=3 time ./gotrace
0.81 real 1.50 user 0.01 sys

On an eight-core, 16 Hyperthread HP Z600 running Ubuntu 9.10, (with the source code changed to use 16 goroutines instead of the default 8 goroutines) I get a 5.8x speedup:

$ GOMAXPROCS=1 time ./gotrace
1.05user 0.01system 0:01.06elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+1544outputs (0major+2128minor)pagefaults 0swaps
$ GOMAXPROCS=16 time ./gotrace
1.32user 0.00system 0:00.18elapsed 702%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+1544outputs (0major+2190minor)pagefaults 0swaps

Source code gotracer.zip


Saturday, November 7, 2009

How about that new Verizon Droid?

I've been working part time on the "Droid" project for the last year, and it finally shipped today. I wrote some of the graphics libraries.

At first I was skeptical of the industrial design. The early prototypes looked very much like a 1970's American car dashboard. But Motorola really improved the industrial design in subsequent versions. I like the high-grip rubber on the battery cover. It makes the phone very comfortable to hold.

The phone hardware is very fast, and the high resolution screen is beautiful. I think people will enjoy owning and using this phone.

My favorite feature is the turn-by-turn navigation software. My second favorite feature is the "Droooid" default notification sound. Oh, and the camera flashlight is very nice too!

Wired article about Demand Media's automated How To videos

Man, the web really does change everything!

The company "Demand Media" has developed a Google-like business model for creating how-to videos:
  1. Use data mining to figure out what people are searching for.
  2. Use semantic database to figure out what their search queries mean. (e.g. "how to draw a gun" vs. "how to draw a flower".)
  3. Find out how much advertisers are willing to pay for an ad that appears next to the video.
  4. Look at how much content already exists to answer the question.
  5. Use 1-4 to calculate the expected lifetime value of the how-to video.
  6. Automate the process of matching freelance writers, videographers, editors, and fact checkers to create the video as inexpensively as possible. (In the $30 per video range.)
  7. Host the resulting videos on Youtube (and other video sites) and monetize with ad keywords.
They say that the algorithm produces lifetime values about 5 times higher than human editors do.

These guys have basically automated the "How to" video market. Amazing! I wonder if they will move up the video food chain into music videos, TV shows or movies? It might work for low budget children's programming.

Or even for casual games. Hmm.



Tuesday, October 20, 2009

Ubuntu 9.10 gets a clue!

I was pleasantly surprised to see that the latest version of Ubuntu, 9.10 b1, comes with a nice selection of desktop backgrounds. This makes a huge difference in how beginners perceive the product, at very little cost to Ubuntu.

The new dark-brown default color scheme is also an improvement over the older schemes.

Sunday, October 18, 2009

I published my first Android app

Now that the Android Native Development Kit has been released, I was finally able to publish the sources and binary to my Android Terminal Emulator. It's a fairly plain Digital Equipment Corporation VT-100 terminal emulator, with some features from newer terminals (like colors.)

This is my first application in the Android Market. There are at least 10 other terminal emulators in the market; we'll see how this one is received.

A bit of history: This was my first Android application. I wrote it for the original "Sooner" Android devices, and have kept it updated for the successive generations of devices. It requires native code because there's no public Android Java APIs for dealing with PTYs.

A bit of ancient history: I wrote two terminal emulators for the Atari 800 back in the day: Chameleon, in 6502 assembly, and a version of Kermit in the excellent "Action!" programming language. Kermit was one of my first "open source" programs. If you poke around on the web you can still find it here and there.



Thursday, October 1, 2009

GLES Quake - a port of Quake to the Android platform

I've just published the source code to a port of Quake to the Android platform. This is something I did a while ago as a internal test application.

It's not very useful as a game, because there hasn't been any attempt to optimize the controls for the mobile phone. It's also awkward to install because the end user has to supply the Quake data files on their own.

Still, I thought people might enjoy seeing a full-sized example of how to write a native code video game for the Android platform. So there it is, in all its retro glory.

(Porting Quake II or Quake III is left as an exercise for the reader. :-)

What's different about this particular port of Quake?

Converted the original application into a DLL

Android applications are written in Java, but they are allowed to call native languge DLLs, and the native language DLLs are allowed to call a limited selection of OS APIs, which include OpenGL ES and Linux File I/O.

I was able to make the game work by using Java for:
  • The Android activity life-cycle
  • Event input
  • View system integration
  • EGL initialization
  • Running the game in its own rendering loop, separate from the UI thread
And then I use C++ for the rest. The interface between Java and C is pretty simple. There are calls for:
  • initialize
  • step - which does a game step, and draws a new frame.
  • handle an input event (by setting variables that are read during the "step" call.)
  • quit
The Java-to-C API is a little hacky. At the time I developed this game I didn't know very much about how to use JNI, so I didn't implement any C-to-Java calls, preferring to pass status back in return values. For example the "step" function returns a trinary value indicating:
  1. That the game wants raw PC keyboard events, because it is in normal gameplay mode.
  2. That it wants ASCII character events, because it is in menu / console mode.
  3. That the user has chosen to Quit.
This might better have been handled by providing a series of Java methods that the C code could call back. (But using the return value was easier. :-))

Similarly, the "step" function takes arguments that give the current screen size. This is used to tell the game when the screen size has changed. It would be cleaner if this was communicated by a separate API call.

Converted the Quake code from C to C++

I did this early in development, because I'm more comfortable writing in C++ than in C. I like the ability to use classes occasionally. The game remains 99% pure C, since I didn't rewrite
very much of it. Also, as part of the general cleanup I fixed all gcc warnings. This was fairly easy to do, with the exception of aliasing warnings related to the "Quake C" interpreter FFI.

Converted the graphics from OpenGL to OpenGL ES

This was necessary to run on the Android platform. I did a straightforward port. The most difficult part of the port was implementing texture conversion routines that replicated OpenGL functionality not present in OpenGL ES. (Converting RGB textures to RGBA textures, synthesizing MIP-maps and so forth.)

Implemented a Texture Manager

The original glQuake game allocated textures as needed, never releasing old textures. It relied upon the OpenGL driver to manage the texture memory, which in turn relied on the Operating System's virtual memory to store all the textures. But Android does not have enough RAM to store all the game's textures at once, and the Android OS does not implement a swap system to offload RAM to the Flash or SD Card. I worked around this by implementing my own ad-hoc swap system. I wrote a texture manager that uses a memory mapped file (backed by a file on the SD Card) to store the textures, and maintained a limited size LRU cache of active textures in the OpenGL ES context.

Faking a PC Keyboard

Quake expects to talk to a PC keyboard as its primary input device. It handles raw key-down and key-up events, and handles the shift keys itself. This was a problem for Android because mobile phone devices have a much smaller keyboard. So a character like '[' might be unshifted on a PC keyboard, but is shifted on the Android keyboard.

I solved this by translating Android keys into PC keys, and by rewriting the config.cfg file to use a different set of default keys to play the game. But my solution is not perfect, because it is essentially hard-coded to a particular Android device. (The T-Mobile G1). As Android devices proliferate there are likely to be new Android devices with alternate keyboard layouts, and they will not necessarily be able to control the game effectively using a G1-optimized control scheme.

A better approach would be to redesign the game control scheme to avoid needing keyboard input.

A Few Words about Debugging

I did the initial bring-up of Android Quake on a Macintosh, using XCode and a special build of Android called "the simulator", which runs a limited version of the entire Android system as a native Mac OS application. This was helpful because I was able to use the XCode visual debugger to debug the game.

Once the game was limping along, I switched to debugging using "printf"-style log-based debugging and the emulator, and once T-Mobile G1 hardware became available I switched to using real hardware.

Using printf-style debugging was awkward, but sufficient for my needs. It would be very nice to have a source-level native code debugger that worked with Eclipse.

Note that the simulator and emulator use a software OpenGL ES implementation, which is slightly different than the hardware OpenGL ES implementation available on real Android devices. This required extra debugging and coding. It seems that every time Android Quake is ported to a new OpenGL ES implementation it exposes bugs in both the game's use of OpenGL ES and the device's OpenGL ES implementation.

Oh, and I sure wish I had a Microsoft PIX-style graphics debugger! It would have been very helpful during those head-scratching "why is the screen black" debugging sessions.





Wednesday, September 23, 2009

IDF 2009 Larrabee demo

Intel showed their new Larrabee GPU publicly for the first time at their annual developer conference. They showed Larrabee running a ray tracer that was rendering QuakeWars geometry.

The enthusiast scene (e.g. beyond3d) was not impressed by this demo, because, frankly, it wasn't very impressive at an emotional level. The scene was static, no people in it, just waves and a few very small helicopters. It's strange that they didn't even move the camera, which is something that a ray tracing engine should easily be able to to. The camera angle they chose was effective for showing dynamic reflections, but keeping the camera locked down meant a much less interesting demo.

For the same amount of effort they could have come up with a much more visually and emotionally interesting demo. For example, a cascade of brightly colored chrome balls tumbling down a staircase, which would show off both physics and ray tracing.

That they didn't use this early opportunity to sell Larrabee indicates that they don't know how to market add-on GPUs to consumers. Which makes sense, since it has been many years since they've needed to do this.

Their current demos are all targeted to (a) test out Larrabee features, and (b) educate developers as to the potential strengths of Larrabee. They are similar to Microsoft DirectX samples. But I think Intal also needs to develop showy "AMD/ATI Ruby" style demos to win the hearts of enthusiasts.

Groo at semiaccurate.com suggests that the IDF demo was shown on early, barely functional Larrabee silicon. If true, that could help explain why the demo was so limited. But by this time in the GPU's lifecycle there should be more marketing -- even if totally pre-rendered -- showing what the GPU will do. So far the bland GDC2009 meteor demo is the only thing we've seen. I think Larrabee needs more sizzle, like this early Sony Playstation 2 demo reel. (Sony also had some great interactive tech demos of things like feathers and pollen particles, but I haven't been able to find online videos in my limited searching.)

Intel's current marketing approach seems to indicate that they are not serious about competing for the enthusiast add-on GPU market. Perhaps they are just waiting until it's closer to the time Larrabee is available for market, but my guess is that they just don't understand how to play the game. It would be a shame if Larrabee is a technical success but a sales failure due to poor marketing execution.

Monday, September 14, 2009

ICFP 2009 contest final scores

Final scores are out, and my team Blue Iris scored 80 out of 328 in this year's ICFP contest. Not as good as last year, ah well. :-) Next year: More sleep!

Monday, September 7, 2009

Brick Break - a Javascript Breakout clone


This weekend I wrote a Javascript clone of the old Atari "Breakout" game. Thanks to the "Canvas" tag it was very easy to write, but I did run into a few problems:

Javascript math is always floating point, so I had to use the "Math.floor" function to convert the results of a division to an integer. This was in the brick collision detection logic, where I am converting the ball's (x,y) coordinates to the bricks that the ball might be hitting.

I was evaluating document.getElementById too early in the document lifecycle, before the corresponding elements existed. This took me a long time to diagnose -- I ended up just moving the getElementById calls to their run-time use, rather than trying to cache the results.

Jack's Brick Break Breakout clone

Saturday, September 5, 2009

ICFP 2009 paper on Haskell in the Real World

Here's a good paper on using Haskell to write a commercial application. The authors are practical commercial programmers who tried Haskell to see if it was a more effective language than Ruby:

Experience Report: Haskell in the “Real World”
Writing a Commercial Application in a Lazy Functional Language


Of special interest is the "Problems and Disadvantages" section. It seems that space leaks which are a continuing source of trouble in the authors' application.

Reading this paper reminds me of Tenerife Skunkworks Haskell vs Erlang Reloaded. In that experiment a developer found that Erlang was much better than Haskell for real-time programming.

Thursday, September 3, 2009

Back to gnome

Well, 8 hours using wmii was enough for me. Too many apps didn't quite work right. So I'm back to plain-old-boring-but-familiar Gnome.

Wednesday, September 2, 2009

Technology Trends I'm Keeping an Eye On

In no particular order, here's what I've been studying lately:
  • Javascript. I've avoided this language over the years because of its low speed and shoddy reputation. But the language implementations seem to be getting faster and the available libraries seem to be getting more interesting. I've just watched all of Doug Crockford's YUI lectures on JavaScript, and I'm thinking about trying to use the language in some toy projects.
  • git gui - this git command, available in recent builds of git, make Git changes pretty easy to author.
  • The Undercover Economist - this is a great book about economic theory. It's pretty easy to read while shaving, or waiting for compiles. Lots of good anecdotes and tools for modeling the behavior of consumers and firms. I took 3 economics classes in college, and they didn't teach me as much practical information as I've learned from reading this book.
  • Hacker News - this link voting site has replaced alterslash and reddit programming as my daily comp-sci news site. I like the emphasis on start-up news.
  • wmii - yet another tiling window manager. I tried a bunch of tiling window managers, and this one seemed to "click" with me. I found that I could customize it easily, and it mostly "just worked" the way I wanted it to. We'll see if I stick with it or go back to Gnome. [Follow-up. I went back to Gnome (and then to OSX). Oh well.]
  • Chrome - now that the Linux and OSX versions have Flash support, Chrome has become my default web browser. I like its clean UI.

Dual XHD7714 Road Trip Report

After a month of using the Dual XHD7714, during which my family and I took a 4000 mile road trip, I have to say it's a pretty nice system. We used it almost exclusively as an MP3 player, rather than an HD Radio or a CD player. I loaded 800 songs from our home music collection onto an 8GB memory stick. It was great introducing my kids to some new music. By the end of the trip their favorite songs were Shock the Monkey and The Magical Mr. Mistoffelees.

Some problems specific to the Dual XHD7714:

Bluetooth issues:
  • Bluetooth headset mode only syncs with one phone at a time. This seems to be a common limitation of low-end bluetooth car stereos, but it's quite frustrating for two-driver families like mine.
  • Bluetooth audio streaming mode doesn't sound very good on this radio. However, I didn't experiment with this very much, so it may have been source-material related.
USB MP3 player issues:
  • It takes about 5 seconds per GB to index USB stick music each time it starts up.
  • It only recognizes US-ASCII characters. If any non-ASCII characters are present in the album or song name the entire name is replaced with the string "Not supported". We had a lot of Chinese-language tracks that displayed that way, making them very difficult to navigate.
  • It can't fast-forward or rewind through MP3s.
  • When you turn on the radio, it does remember where in the current MP3 it is playing, _but_ it takes a long time to resume playing an MP3 in the middle. So it's awkward listening to long podcasts.
Still, even with all these flaws, I'm quite happy with the radio. We really enjoyed being able to conveniently listen to so many different songs during our trip.

Thursday, July 23, 2009

Nehalem machines are very fast

I've just had a chance to use a Nehalem HP Z600 workstation with 2 Xeon E5520 CPUs. The machine has 8 cores, 16 hardware threads, and an absurd 12 GB of RAM.

It's very fast. It's about 2.5 times as fast (when building the Android sources) as the previously fastest machine I'd used, which was an HP xw6600 with a single Xeon E5420 CPU.

The machine's relatively small, no larger than an ordinary ATX tower. One way that HP kept the case small is by making the motherboard an odd shape: it is "C" shaped, with a cutout that leaves room for the DVD drive.



Saturday, July 18, 2009

Too Many Words about Car Stereos

The other day my wife said to me, "Jack, we're going on a road trip soon. Is there any way we could hook up our MP3 player to the car stereo, so that the kids could listen to their favorite songs during the trip?"

Twenty hours of web research and $250 later we've got a new car stereo. It's a Dual XHD7714 from Crutchfield. I'm getting it installed by Best Buy tomorrow. Let's hope their AV installers do a good job!

First, why did I get a new stereo at all? Well, all I wanted to do was hook up an MP3 player. But there was no easy way to do that. My 2005 minivan came with a factory installed stereo that didn't have an auxiliary input. There are cheap FM transmitter systems that work with any radio, but they look clunky and the sound quality is supposed to be poor. A lot of web searching turned up some aftermarket accessories that allow hooking up either an audio input jack ($75 + $50 installation = $125) or an MP3 player and/or iPod ($125 + $50 = $175.) But the for just a little more money I was able to get a a whole new radio with lot of additional features.

Why this particular model? It was well reviewed and relatively inexpensive. The features I was interested in were:
  • MP3 player / USB memory stick player.
  • Hands-free bluetooth calling with a built-in microphone.
  • Streaming audio from a bluetooth phone.
  • Charging USB devices.
  • HD radio.
  • Good fast text UI for navigating a MP3 player.
  • Play MP3s stored on CDs.
  • Wireless remote control for "back seat DJs"
General thoughts on the car stereo market
  • Crutchfield is a good place to research and buy car stereos. For research purposes they have a wide selection, and they have very good information, especially in the form of user reviews. For buying they offer free shipping and more importantly a free installation and wiring kit. They also seem to offer very good telephone help for do-it-yourself installers.
  • The add-on car stereo market is in long-term decline. I think that in the next few years the car stereo will become little more than a mobile phone docking station. People will keep their music collection on their phone, or stream it from the internet.
  • Car stereo makers are not going down without a fight. They are experimenting with iPhone-inspired full-screen touch-screen UIs and built-in internet radios. While very creative, I don't think people will buy them. They will just use their phones instead.
  • Many people want to connect their iPods to their car stereo. In the short term Apple is making this difficult by changing their communication protocols with every generation of iPod. In the long term iPods are going to be replaced by iPhones, which will probably be forced to support bluetooth stereo streaming.

Tuesday, July 7, 2009

Using a Mac keyboard with Ubuntu Linux

I frequently switch between Mac and Linux, and it's been troublesome to remember to type Command-whatever on the Mac, but Control-whatever on Linux. (For copy-and paste, for example.)

I did a quick web search and found out that it's easy to make Ubuntu Linux recognize the Command keys as an extra set of control keys:

Choose menu: System : Preferences : Keyboard
Select the Layouts tab
Choose "Layout Options"
Open the "Alt / Win Key Behaviour" tab
Check the "Control is mapped to the Win-keys" checkbox.

Sunday, June 28, 2009

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.

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

Monday, June 15, 2009

Dandy in JavaScript



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.

Sunday, May 31, 2009

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.

Saturday, May 2, 2009

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.

Monday, March 30, 2009

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.):

http://pc.watch.impress.co.jp/docs/2009/0330/kaigai498.htm

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.

http://www.ddj.com/hpc-high-performance-computing/216402188

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



Friday, March 27, 2009

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.

Wednesday, March 25, 2009

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!

Friday, March 6, 2009

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.

Monday, February 16, 2009

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.

Wednesday, January 7, 2009

"Pixar Quality Graphics" is 720 Gflops

For at least 10 years GPU vendors have been talking about "Pixar Quality" graphics. But what does that mean? Well, according to this lecture on The Design of Renderman, the original goals for the REYES architecture were
  • 3000 x 1667 pixels (5 MP)
  • 80M Micropolygons (each 1/4th of a pixel in size, depth complexity of 4)
  • 16 samples per pixel
  • 150K geometric primitives
  • 300 shading flops per micropolygon
  • 6 textures per primitive
  • 100 1MB textures
That's a shading rate of 80M * 300 * 30 Hz = 720 Gflops. (They were probably more concerned about 24 Hz, but for games 30Hz is better.)

In comparison I think the peak shader flops of high-end 2008-era video cards are in the 1 TFlop range. (Xbox 360 Xenos is 240 Gflops, PS3 is a bit less.). Now, GPU vendors typically quote multiply-accumulate flops, because that doubles the number of flops. So it's more realistic to say that 2008-era video cards are in the 500 Gflop range. So we really are entering the era of "Pixar Quality" graphics.