Grammerjack

2011-10-16T07:56:00.000-07:00

I translated Alexander Boswell's toy REYES renderer from C++ to Google's new Dart programming language.

Here's what the output looks like:

Try It Yourself

If your browser supports the canvas tag and JavaScript, you can see the sphere being rendered here:

Render a REYES bumpy sphere in your browser.

And the source is here: http://code.google.com/p/reyes-dart/

Translating C++ to Dart

It was pretty easy to translate the original code from C++ to Dart.

The original code made use of classes and overloaded operators, both of which are also in the Dart language.
The original code used the SDL library to display output. It was easy to switch to the HTML5 CANVAS tag.

I used an early version of the "Dart Editor" IDE. The Dart Editor IDE was helpful because of the compiler warnings and errors.

Debugging

I used a variety of techniques to debug the code:

print() Dart has a built-in print function that logs to the JavaScript console. This was good for logging small amounts of data.
write() This is a utility function I wrote that appended the argument text to the document body of my HTML document. This has several advantages over "print":

Easier to see output during development.
Much easier to search and copy/paste large amounts of text.

Dumping 3D geometry as text. At one point I wanted to check whether or not my geometry was correct. The easiest way to check it was to dump the geometry out as a 3D text file using "write()", and then copy-and-paste that code into a file and view it in the blender3d.org Blender app.
Using Chrome to step through the compiled app.js code. This was pretty painful, but was occasionally useful. The stack crawls for exceptions usually gave good hits as to what was going wrong.

Dart Limitations

The Dart "dom" library is not yet complete. Currently it can't write to canvas imageData. As a work-around I draw each pixel of output as a little filled rectangle.

Dart Editor Limitations

I wish the Dart Editor would support:

Formatting code.
Stripping whitespace from ends of lines on save.
Converting tabs to spaces on save.

A script to upload files to Picasa Web Albums

2011-09-11T21:10:00.000-07:00

Today I backed up all my family pictures and videos to Picasa Web Albums.

For several months I have been thinking of ways to backup my pictures to somewhere outside my house. I wanted something simple, scalable and inexpensive.

When I read that Google+ users can store unlimited pictures sized <= 2048 x 2048 and videos <= 15 minutes long, I decided to try using Google+ to back up my media.

Full disclosure: I work for Google, which probably predisposes me to like and use Google technologies.

Unfortunately I had my pictures in so many folders that it wasn't very convenient to use either Picasa or Picasa Web Albums Uploader to upload them.

Luckily, I'm a programmer, and Picasa Web Albums has a public API for uploading images. Over the course of an afternoon, I wrote a Python script to upload my pictures and videos from my home computer to my Picasa Web Album account. I put it up on GitHub: picasawebuploader

Good things:

The Google Data Protocol is easy to use.
Python's built-in libraries made file and directory traversal easy.
OSX's built-in "sips" image processing utility made it easy to scale images.

Bad things:

The documentation for the Google Data Protocol is not well organized or comprehensive.
It's undocumented how to upload videos. Luckily I found a Flicker-to-Picasa-Web script that showed me how.

To do:

Use multiple threads to upload images in parallel.
Prompt for password if not supplied on command line.

What am I up to?

2011-08-20T10:23:00.000-07:00

I'm mostly posting on google+ these days, sorry!

Asynchronous directory tree walk in node.js

2010-12-20T07:08:00.000-08:00

I wrote an asynchronous directory tree walker in node.js. Note the use of Continuation Passing Style in the fileCb callback. That allows the callback to perform its own asynchronous operations before continuing the directory walk.

(This code is provided under the Apache Licence 2.0.)

// asynchronous tree walk
// root - root path
// fileCb - callback function (file, next) called for each file
// -- the callback must call next(falsey) to continue the iteration,
//    or next(truthy) to abort the iteration.
// doneCb - callback function (err) called when iteration is finished
// or an error occurs.
//
// example:
//
// forAllFiles('~/',
//     function (file, next) { sys.log(file); next(); },
//     function (err) { sys.log("done: " + err); });

function forAllFiles(root, fileCb, doneCb) {
    fs.readdir(root, function processDir(err, files) {
        if (err) {
            fileCb(err);
        } else {
            if (files.length > 0) {
                var file = root + '/' + files.shift();
                fs.stat(file, function processStat(err, stat) {
                    if (err) {
                        doneCb(err);
                    } else {
                        if (stat.isFile()) {
                            fileCb(file, function(err) {
                                if (err) {
                                    doneCb(err);
                                } else {
                                    processDir(false, files);
                                }
                            });
                        } else {
                            forAllFiles(file, fileCb, function(err) {
                                if (err) {
                                    doneCb(err);
                                } else {
                                    processDir(false, files);
                                }
                            });
                        }
                    }
                });
            } else {
                doneCb(false);
            }
        }
    });
}

Getting Old Educational Software to Run on OSX 10.6

2010-11-12T15:25:00.000-08:00

My kids' favorite piece of educational software is "Clifford The Big Red Dog Thinking Adventures" by Scholastic. We received it as a hand-me-down from their cousins. The CD was designed for Windows 95-98 and pre-OSX Macintosh. Unfortunately, it does not run on OS X 10.6. (I think it fails to run because it uses the PowerPC instruction set and Apple dropped support for emulating that instruction set in 10.6.)

After some trial and error, I found the most reliable way to run Clifford on my Mac was:

Install VMWare Fusion.
Install Ubuntu 10.10 32-bit in a Virtual Machine.
Install the VMWare Additions to make Ubuntu work better in the VM.
Install Wine on Ubuntu 10.10. (Wine provides partial Windows API emulation for Linux.)
Configure the audio for Wine. (I accepted the defaults.)
Insert the Clifford CD and manually run the installer.

The result is that the Clifford game runs full screen with smooth animation and audio, even on my lowly first-generation Intel Mac Mini.

You may scoff at all these steps, but (a) it's cheap, and (b) it's less work than installing and maintaining a Windows PC or VM just to play this one game.

(It's too bad there isn't a Flash, HTML5, Android or iOS version of this game, it's really quite well done.)

Eulogy for a PC

2010-09-05T19:42:00.000-07:00

This Labor Day weekend I decommissioned my tower PC.

If memory serves, I bought it in the summer of 2002, in one last burst of PC hobby hacking before the birth of my first child. It's served me and my growing family well over the years, first as my main machine, later as a media server.

But the world has changed, and it doesn't make much sense to keep it running any more. It's been turned off for the last year while I traveled to Taiwan. In that time I've learned to live without it.

The specific reasons for decommissioning it now are:

It needs a new CMOS battery.
It needs a year's worth of Vista service packs and security updates.
I don't use the media center feature any more.
After a year without a Windows machine I don't want to maintain one any more.
It's too noisy and uses too much energy to leave on as a server.

The decommissioning process

I booted it, and combed through the directories. I carefully copied off all the photos, code projects, email and documents that had accumulated over the years. Lots of good memories!

GMail Import

I discovered some old Outlook Express message archives. I wrote a Python script to import them into GMail. I didn't like any of the complicated recipes I found on the web, so I did it the easy way: I wrote a toy POP3 server in Python that served the ".eml" messages from the archive directory. Once the toy POP3 server was running, GMail was happy to import all the email messages from my server.

Erasing the disks with Parted Magic

Once I was sure I had copied all my data off the machine it was time to erase the disks. I erased the disks using the ATA Secure Erase command. I did this using a small Linux distro, Parted Magic. I downloaded the distribution ISO file and burned my own CD. Once the CD was burned, I just rebooted the PC and it loaded Parted Magic from the CD.

Parted Magic has a menu item, "Erase Disk". It lets you choose the disk and the erase method. The last method listed is the one I used. The other methods work too, but they don't use the ATA Secure Erase command.

It took quite a while to erase the disks. Each disk took about two hours to erase. (They took 200 GB per hour, to be precise.) Unfortunately, due to the limitations of my ATA drivers, I had to erase them one at a time.

While I think the ATA Secure Erase command is the fastest and most reliable way to erase modern hard disks, there is another way: Instead of having the drive erase itself, you can copy data over every sector of the drive. The advantage of this technique is that it also works with older drives. If you choose to go this route, one of the easiest way to do it is to use Darik's Boot and Nuke utility. This is a Linux distro that does nothing besides erasing all the hard disks of the computer you boot it on. You just boot the CD, then type "autonuke" to erase every disk connected to your computer.

Disposing of the computer

It's still a viable computer, so I will probably donate it to a local charity. The charity has a rule that the computer you donate must be less than 5 years old. I think while some parts of the computer are older than that, most of the parts are young enough to qualify.

Reflections on the desktop PC platform

Being able to upgrade the PC over the years is a big advantage of the traditional desktop tower form factor. Here's how I upgraded it over the years:

Initial specs (2002)

Windows XP
ASUS P4S533 motherboard
Pentium 4 at 1.8 GHz
ATI 9700 GPU
Dell 2001 monitor (1600 x 1200)
256 MB RAM
20 GB PATA HD
Generic case

Final specs (2010)

Windows Vista Ultimate
ASUS P4S533 motherboard
Pentium 4 at 1.8 GHz
ATI 9700 GPU
Dell 2001 monitor (1600 x 1200)
1.5 GB RAM
400 GB 7200 RPM PATA HD
300 GB 7200 RPM PATA HD
ATI TV Theater analog capture card
Linksys Gigabit Ethernet PCI card
Antec Sonata quiet case

I think these specs show the problems endemic to the desktop PC market. Although I didn't know it at the time, the PC platform had already plateaued. In eight years of use I wasn't motivated to upgrade the CPU, motherboard, monitor, or GPU. If I hadn't been a Microsoft employee during part of this time I wouldn't have upgraded the OS either.

What killed the PC for me wasn't the hardware wearing out, it was mission change. Like most people I now use the web rather than the local PC for most of my computer activity. Maintaining the local PC is pure overhead, and I've found it's easier to maintain a Mac than a PC.

It was nostalgic to turn on the PC again and poke through the Vista UI. It brought back some good memories. (And I discovered some cute pictures of my kids that I'd forgotten about.)

Thank you trusty PC. You served me and my family well!

An update on my car stereo

2010-08-29T08:47:00.000-07:00

It's been a year since I bought my fancy car stereo. I wanted to mention that I've ended up not using most of the fancy features.

The built-in MP3 player had issues with my 1000-song / 100 album / 4 GB music collection:

It took a long time to scan the USB storage each time the radio turned on.
It was difficult to navigate the album and song lists.
Chinese characters were not supported.
It took a long time to "continue" a paused item, especially a long item like a podcast.

The bluetooth pairing only worked with one phone at a time, which was awkward in a two-driver family.

Here's how I use it now:

I connect my phone using both the radio's USB (so the phone is being charged) and mini stereo plugs.
I use the phone's built-in music player.
I have the radio set to AUX to play the music from the stereo input plug.

It's a little bit cluttered, because of the two cables, but it gets the job done. The phone's music player UI is so much better than the radio's UI.

In effect I have reduced the car stereo to serving as a volume control, an amplifier, and a USB charger.

What I did on my Winter Vacation

2010-07-25T14:00:00.000-07:00

I just returned to the US after eight months living in Taiwan. The trip was great fun for me and my family. But more than that, it was a very productive time for me to learn new programming technologies.

Why was my trip so productive?

I think some of the reasons were:

I was away from my home computer set up (including video game consoles and a large TV). All I had was a Mac Mini (for the family to use), a MacBook Pro (for work) and a Nexus One phone.
I commuted by bus rather than car. While my commute time was longer, it was much more productive. Instead of having to concentrate on driving, I had 40 minutes a day of free time to think, web surf, and even code.
I didn't follow local politics, and USA politics were made less interesting by distance and time zone. I stopped visiting political web sites and obsessing over current events.
The timezone difference between Taipei and the US ment that email became a once-a-day event, rather than a continuous stream of interruptions.
It's more time-efficient to live as a guest in a city than as a home owner in the suburbs. For example, my mother-in-law cooked our meals, and I didn't have nearly as many household chores as I do in America.
Location-based internet blocks ment that some of my favorite time-wasting web sites (Pandora, Hulu) were unavailable.
Having to explain and defend my technology opinions to my Google Taipei coworkers. "Go is a cool language" I would say. "Oh yeah? Why?" they would reply. I would struggle to explain, and usually both of us would end up more enlightened.

Beyond that, I think being in a new environment, and removed from my home, helped shake me loose from my mental ruts. I was learning how to live in a new physical environment, and that transfered over to how I used the web as well.

What did I do?

I visited Hacker News frequently. It is a very good source of news on the startup business and new web technologies. Hacker News was where I first learned about Node.js and CoffeeScript, two of my current interests.
I entered the Google AI Challenge, a month long Game AI programming contest. I didn't place very high, but I had fun competing.
I gave two talks on the Go programming language. One at the Google Taiwan office, the other at the Open Source Developer Conference Taiwan OSDC.tw. Having to give a talk about a programming language helps increase one's understanding of that language.
An afternoon spent hanging out with JavaScript Mahatma Douglas Crockford. I worked with Douglas ages ago when we both worked at Atari. It was great to catch up with him and his work. (He was in town to give a speech at the OSDC conference.)
I joined GitHub, and started using it to host my new open source projects.

I wrote Taipei-Torrent, a Bit Torrent client written in "Go".
I started summerTorrent, a Bit Torrent client written in JavaScript, based on node.js

node.js - an interesting server-side JavaScript environment.
CoffeeScript - a JavaScript preprocessor that looks like a promising language.
PhoneGap - a cross-platform mobile JavaScript / HTML5 UI framework. I wrote a word scramble game using this framework.
DD-WRT routers. I bought four new DLink 300 routers (which are dirt cheap), installed DD-WRT on them, and used them to upgrade my Taiwan relatives' computer network.
My nephew bought a PS3, so I finally had a chance to see Little Big Planet and Flower, two games I had long wanted to know more about. I also got to see a lot of Guitar Hero being played. Unfortunately I didn't get a chance to actually play any of these games -- someone else always had a higher claim on the TV.

Keeping the Taipei Experience Alive

I'm back in the US, and am already starting to slip back into my old ways. Here are some ways I'm trying to keep my productivity up:

Cool side projects.

I'm going to continue to work on side projects to learn new things. I want to do something serious with CoffeeScript and Node.js.
iPad. I'm getting one in a few weeks, and looking to see if its a useful paradigm.

Get rid of distractions.

I'm selling off (or just closeting) distractions like my older computers and my media center.
I edited my /etc/hosts file to block access to all my top time-wasting web sites. Hopefully I won't just replace these with a new generation of web sites.

Working at home. My work office here in the US is just too noisy for me to concentrate in. I'm going to start spending as much time as possible working from a quiet room at home.
Regular exercise. I got a lot of walking done in Taiwan. I'm going to take up running again. (Easy to do now, we'll see how it goes when the weather gets rough.)

I may even get a pair of "Gorilla Shoes" for barefoot running.

ICFP 2010 contest is a bust for me

2010-06-18T05:54:00.000-07:00

The ICFP 2010 contest rules have been posted, and I am quite disappointed by this year's contest.

This year's contest is difficult to describe. It's too clever by half, and it depends too much on time, and too much on repeated interaction with the organizer's servers.

The conceit is that you're designing "car engines", and "fuel for car engines". A car engine is a directed graph with certain properties, and "fuel" is a directed graph with other properties that generates a set of coefficients that are fed to the engine.

Layered on top of that is an encoding puzzle (you have to figure out how the engine and fuel directed graphs are encoded for submission to the IFCP servers.)

Layered on top of that is an economy where you are encouraged to submit your own car engines and write optimal fuels for other people's car engines. There are benefits for finding better fuels for existing car designs. (You aren't provided the details of the other car designs.)

Layered on top of that is that the instructions are not written very clearly. I had to read them multiple times to start to even begin to understand what was going on.

And finally, the contest registration / submission web site is returning 503 (Service Temporarily Unavailable) errors, either because it hasn't been turned on yet, or perhaps because hundreds of teams are trying to use it at once.

I suspect this contest is going to be difficult for teams with limited Internet connectivity. I also suspect the contest servers are going to be very busy later in the contest as people start hitting them with automated tools repeatedly in order to start decoding engines.

I salute the contest organizers for trying to get contestants to interact with each other during the contest, and for coming up with an original idea.

I fault them for designing a "write your program in _our_ language, not yours" puzzle. I want to enjoy programming in the language of my choice, not design graphs and finite state automata for creating fuel coefficients and engines.

I am going to punt this year -- the contest just doesn't sound very fun.

I hope next year's topic is more to my taste!

Writing an Android application in JavaScript and HTML5

2010-05-07T19:56:00.000-07:00

Happy Mother's Day everyone! This year I wrote an Android app for my wife for Mother's Day. How geeky is that?

The reason I wrote it is that my wife's favorite Android application, Word Mix Lite, recently added annoying banner ads. While the sensible thing to do might have been to switch to another app, or perhaps upgrade to the paid version of Word Mix, I thought it might be interesting to see if I could write my own replacement.

And as long as I was writing the app, I though I'd try writing it using JavaScript. Normally Android applications are written in Java, but it's also possible to write them in JavaScript, by using a shell application such as PhoneGap.

Why use JavaScript instead of Java? Well, hack value mostly. On the plus side it's a fun to write! Another potential plus is that it is theoretically possible to run the same PhoneGap application on both Android and Apple.

The drawback is that PhoneGap is not very popular yet, especially among Android developers, and so there is relatively little documentation. I ran into problems related to touch events and click events that I still haven't completely solved.

It took about three days to write the application. The first day was spent:

Finding a public domain word list.
Filtering the word list to just 3-to-6 character words.
Build a "trie" to make it fast to look up anagrams.
Output the trie as a JSON data structure.

The second day was spent writing the core of the word jumble game.

This was all done on a desktop, using Chrome's built-in Javascript IDE.

The third day was spent:

Porting to PhoneGap.
Debugging Android-specific issues.
Tuning the gameplay for the phone.

The project went pretty well.

JavaScript is a very easy language to work in.
CSS styling was fairly easy to learn.
Targeting a single browser made it relatively easy to use the DOM.
The Chrome JavaScript debugger was very helpful.
The web has a wealth of information on JavaScript and HTML / CSS programming information.

In the end there were unfortunately a few button-event UI glitches I couldn't solve in time for Mother's Day. When I get some spare time I'd like to revisit this project and see if I could use the JQTouch library to solve my UI glitches. I'd also like to make an open source release of a reskinned (non-Mother's Day themed) version of this app. And then who knows? Maybe I'll release it for the other phones that PhoneGap supports as well. :-)

Google AI Challenge 2010

2010-03-06T12:17:00.000-08:00

Team Blue Iris (that's me!) placed 77th out of 708 in the Google AI Challenge 2010 contest. The contest was to design an AI for a Tron lightcycle game.

My entry used the standard min/max approach, similar to many other entries. I guess that's why it performed similarly to so many other entries. :-) I didn't have any time to investigate better algorithms, due to other obligations.

In addition to my own entry (which was in C++), I also created starter packs for JavaScript and Google's Go language. These starter packs enabled people to enter the contest using JavaScript or Go. In the end, 6 people entered using Go, and 4 people entered using JavaScript. I'm pleased to have helped people compete using these languages.

I initially wanted to use JavaScript and/or Go myself, but the strict time limit of the contest strongly favored the fastest language, and that made me choose a C++ implementation. Practically speaking, there wasn't much advantage to using another language. The problem didn't require any complicated data structures, closures, or dynamic memory allocation. And the submitted entries were run on a single-hardware-thread virtual machine, which meant that there wasn't a performance benefit for using threads.

This contest was interesting because it went on for a long time (about a month) and because the contestants freely shared algorithm advice during the contest. This lead to steadily improving opponents. My program peaked at about 20th place early in the contest, but because I didn't improve it thereafter, its rank gradually declined over the rest of the contest.

The contest winner's post-mortem reveals that he won by diligent trial-and-error in creating a superior evaluation function. Good job a1k0n!

Congratulations to the contest organizers for running an interesting contest very well. I look forward to seeing new contests from the University of Waterloo Computer Club in the future.

Looking at the original BitTorrent client

2010-01-23T05:27:00.000-08:00

I wanted to learn more about how the original BitTorrent client implemented "choking", so I downloaded the source to the original Python-based BitTorrent client from SourceForge.

I was impressed, as ever, by the brevity and clarity of Python. The original BitTorrent client sources are very easy to read. (Especially now that I understand the problem domain pretty well.) The code has a nice OO design, with a clear separation of responsibilities.

I was also impressed by the extensive use of unit tests. About half the code in the BitTorrent source is unit tests of the different classes, to make sure that the program behaves correctly. This is a really good idea when developing a peer-to-peer application. The synthetic tests let you test things like your end-of-torrent logic immediately, rather than by having to find an active torrent swarm and wait for a real-world torrent to complete.

When I get a chance I'm going to refactor the Taipei-Torrent code into smaller classes and add unit tests like the original BitTorrent client implementation has.

And come to think of it, why didn't I check out the original BitTorrent client code sooner? It would have saved me some time and I'd probably have a better result. D'Oh! Oh well, live and learn!

Some details on Xbox Project Natal

2010-01-22T18:17:00.000-08:00

From Scientific American: Binary Body Double: Microsoft Reveals the Science Behind Project Natal

Short summary: They used machine-learning algorithms and lots of training data to come up with an algorithm that converts moving images into moving joint skeletons.

Given the huge variation in human body shapes and clothing, it will be interesting to see how well this performs in practice.

I bet people will have a lot of fun aiming the Natal camera at random moving object to see what happens. I can already imagine the split-screen YouTube videos we'll see of Natal recognizing pets, prerecorded videos of people, puppets and marionettes.

Oh, and of course, people will point Natal back at the TV screen and see if the video game character can control itself.

Great fun!

800 lines of code for a bencode serializer?!

2010-01-22T02:55:00.000-08:00

Wow, my Taipei-Torrent post made it to Hacker News and reddit.com/r/programming. I'm thrilled!

One comment on Hacker News was "800 lines for a bencode serializer?! It only took me 50 lines of Smalltalk!" That was a good comment! I replied:

A go bencode serialization library could be smaller if it just serialized the bencode data to and from a generic dictionary container. I think another go BitTorrent client, gobit, takes this approach.

But it's convenient to be able to serialize arbitrary application types. That makes the bencode library larger because of the need to use go's reflection APIs to analyze and access the application types. Go's reflection APIs are pretty verbose, which is why the line count is so high.

To make things even more complicated, the BitTorrent protocol has a funny "compute-the-sha1-of-the-info-dictionary" requirement that forces BitTorrent clients to parse that particular part of the BitTorrent protocol using a generic parser.

So in the end, the go bencode serializer supports both a generic dictionary parser and an application type parser, which makes it even larger.

In general, Taipei-Torrent was not written to minimize lines-of-code. (If anything, I was trying to maximize functionality per unit of coding time.) One example of not minimizing lines-of-code is that I used a verbose error handling idiom:

a, err := f()
if err != nil {
return
}

There are alternative ways to handle errors in go. Some of the alternatives take fewer lines of code in some situations. The above idiom is my preference because it works correctly in all cases. But it has the drawback of adding 3 lines of code to every function call that might return an error.

The go authors are considering adding exceptions to the go language. If they do so it will probably dramatically improve the line count of Taipei-Torrent.

A Taipei-Torrent postmortem: Writing a BitTorrent client in Go

2010-01-19T23:34:00.001-08:00

This is a BitTorrent client. There are many like it, but this one is mine.

-- the BitTorrent Implementer's Creed

For fun I've started writing a command-line BitTorrent client in Google's go programming language. The program, Taipei-Torrent , is about 70% done. It can successfully download a torrent, but there are still lots of edge cases to implement.

Go routines and channels are a good base for writing multithreaded network code. My design uses goroutines as follows:

a single main goroutine contains most of the BitTorrent client logic.
each BitTorrent peer is serviced by two goroutines: one to read data from the peer, the other to write data to the peer.
a goroutine is used to communicate with the tracker
some "time.Tick" goroutines are used to wake the main goroutine up periodically to perform housekeeping duties.

All the complicated data structures are owned by the main goroutine. The other goroutines just perform potentially blocking network I/O using channels, network connections, and []byte slices. For example, here's a slightly simplified version of the goroutine that handles writing messages to a peer:

func (p *peerState) peerWriter(errorChan chan peerMessage,

header []byte) {

_, err := p.conn.Write(header)

if err != nil {

goto exit

}

for msg := range p.writeChan {

err = writeNBOUint32(p.conn, uint32(len(msg)))

if err != nil {

goto exit

}

_, err = p.conn.Write(msg)

if err != nil {

goto exit

}

exit:

errorChan <- peerMessage{p, nil}

}

Good things about the Go language and standard packages for this project:

Even without IDE support it is easy to refactor go code. This ease-of-refactoring makes it pleasant to develop a program incrementally.
Goroutines and channels make networking code easy to write.
The log.Stderr() function makes debugging-by-printf fairly painless.
Go maps serve as pretty good one-size-fits-all collection classes.
I received very fast responses from the go authors to my bug reports.
The standard go packages are reliable and easy to use. I used the xml, io, http, and net packages pretty extensively in this project. I also used the source of the json package as a base for the bencode package.
gofmt -w is a great way to keep my code formatted.
Named return values, that are initialized to zero, are very pleasant to use.
The code writing process was very smooth and stress free. I rarely had to stop and think about how to achieve what I wanted to do next. And I could often add the next feature with relatively little typing. The feeling was similar to how it feels when I write Python code, only with fewer type errors. :-)
With the exception of using the reflect package I never felt like I was fighting the language or the compiler.

Minor Problems:

It was a little tedious to write if err != nil {return} after every function call in order to handle errors.
The standard go http package is immature. It is missing some features required for real-world scenarios, especially in the client-side classes. In my case I needed to expose an internal func and modify the way a second internal func worked in order to implement a client for the UPnP protocol. The good news is that the http package is open source, and it was possible to copy and fork the http package to create my own version.

What wasted my time:

Several hours wasted debugging why deserializing into a copy of a variable (rather than a pointer to the original variable) had no effect on the value of the original variable. I notice that I often make mistakes like this in go, because go hides the difference between a pointer and a value more than C does. And there're confusing differences in behavior between a struct (which you can pass by either value or reference) and an interface (which has reference semantics on its contents even though you pass the interface by value). When you are reading and reasoning about go code you must mentally keep track of whether a given type is a struct type or an interface type in order to know how it behaves.
Several hours wasted figuring out how to send and receive multicast UDP messages. This may be an OSX-specific bug, and it may already be fixed. I found the Wireshark packet sniffer very helpful in debugging this problem.
Several hours wasted with crashes and hangs related to running out of OS threads on OSX. This was due to my code instantiating time.Tick objects too frequently. (Each live time.Tick object consumes a hardware thread.)
Many hours spent trying to understand and use the reflect package. It is powerful, but subtle and mostly undocumented. Even now, some things remain a mystery to me, such as how to convert a []interface{} to an interface{} using reflection.

Project statistics:

Line count: Main program: 1500 lines, http package patches: 50 lines, UPnP support: 300 lines, bencode serialization package: 800 lines. Tests for bencode serialization: 300 lines
Executable size: 1.5 MB. Why so large? One reason is that go doesn't use shared libraries, so everything is linked into one executable. Even so, 1.5 MB seems pretty large. Maybe go's linker doesn't strip unused code.
Development time: ~8 days so far, probably 11 days total.
The source is available under a BSD-style license at: http://github.com/jackpal/Taipei-Torrent

Edits since first post:

Added error reporting to code example.
Added a link to the source code.
Give more details about the line count. I had mistakenly included some test code in the lines-of-code for the main program.
Add a statistic about program size.

Objects vs. the L2 Cache

2010-01-17T22:18:00.000-08:00

An excellent little performance optimization presentation that shows how important memory layout is for today's processors:

http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

The beginning of the talk makes the observation that since C++ was started in 1979 the cost of accessing uncached main memory has ballooned from 1 cycle to 400 cycles.

The bulk of the presentation shows the optimization of a graphics hierarchy library, where switching from a traditional OO design to a structure-of-arrays design makes the code run 3 times faster. (Because of better cache access patterns.)

Tom Forsyth (Larrabee Dev) speaking at Stanford

2009-12-17T22:33:00.000-08:00

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.

3D toolchain musings

2009-11-26T15:09:00.000-08:00

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

2009-11-26T15:01:00.000-08:00

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.

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

2009-11-25T00:33:00.000-08:00

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:

Doug Crockford on ECMAScript 4 /5

Brendan Eich on ECMAScript 4 / 5 and Harmony

Prince of Persia Developer's blog

2009-11-24T19:20:00.000-08:00

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

A Multi-threaded Go Raytracer

2009-11-10T19:44:00.000-08:00

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

How about that new Verizon Droid?

2009-11-07T11:37:00.001-08:00

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

2009-11-07T11:23:00.000-08:00

Man, the web really does change everything!

The company "Demand Media" has developed a Google-like business model for creating how-to videos:

Use data mining to figure out what people are searching for.
Use semantic database to figure out what their search queries mean. (e.g. "how to draw a gun" vs. "how to draw a flower".)
Find out how much advertisers are willing to pay for an ad that appears next to the video.
Look at how much content already exists to answer the question.
Use 1-4 to calculate the expected lifetime value of the how-to video.
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.)
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.

Ubuntu 9.10 gets a clue!

2009-10-20T11:57:00.000-07:00

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.

I published my first Android app

2009-10-18T17:30:00.000-07:00

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.

GLES Quake - a port of Quake to the Android platform

2009-10-01T19:48:00.000-07:00

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:

That the game wants raw PC keyboard events, because it is in normal gameplay mode.
That it wants ASCII character events, because it is in menu / console mode.
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.

IDF 2009 Larrabee demo

2009-09-23T06:24:00.000-07:00

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.

ICFP 2009 contest final scores

2009-09-14T07:44:00.000-07:00

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!

And here's a video of the contest results presentation from ICFP.

Brick Break - a Javascript Breakout clone

2009-09-07T20:58:00.000-07:00

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

ICFP 2009 paper on Haskell in the Real World

2009-09-05T10:05:00.000-07:00

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.

Back to gnome

2009-09-03T20:04:00.000-07:00

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.

Technology Trends I'm Keeping an Eye On

2009-09-02T19:31:00.000-07:00

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

2009-09-02T19:12:00.001-07:00

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.

Nehalem machines are very fast

2009-07-23T10:56:00.000-07:00

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.

Too Many Words about Car Stereos

2009-07-18T07:09:00.000-07:00

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.

Using a Mac keyboard with Ubuntu Linux

2009-07-07T11:31:00.001-07:00

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.

ICFP 2009 contest blog - Team Blue Iris

2009-06-28T11:41:00.001-07:00

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

Dandy in JavaScript

2009-06-15T07:17:00.001-07:00

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

2009-05-31T20:56:00.000-07:00

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)

2009-05-31T20:43:00.000-07:00

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

2009-05-02T07:21:00.000-07:00

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.

Larrabee Instruction Set Talks

2009-03-30T02:53:00.000-07:00

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

Using XBMC on Mac Mini using both OSX and Linux

2009-03-27T08:23:00.000-07:00

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:

Installed rEFIt to allowing easy dual-booting between Mac and Linux
Installed Ubuntu 8.10 32-bit version.
Compiled XBMC from the tip-of-tree svn sources.
Installed the LIRC infrared remote control driver (apt-get install lirc) and used an old USB-based Windows Media Center remote control that I already had.

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

2009-03-25T14:37:00.000-07:00

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

2009-03-06T10:50:00.000-08:00

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:

I run the free SqueezeCenter program on my home machine to serve music.
I run the free Softsqueeze program on my work machine to listen to the music.
To keep the whole world from listening to my music, I set up an SSH tunnel.

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

2009-02-16T21:25:00.000-08:00

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.

"Pixar Quality Graphics" is 720 Gflops

2009-01-07T20:32:00.000-08:00

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.

Tech Talk on Wii security model (and breaking it)

2008-12-31T06:33:00.000-08:00

A very thorough talk describing the Nintendo Wii game console security model and the bugs and weaknesses that allowed the Wii to be compromised:
Console Hacking 2008: Wii Fail

In a nutshell, security is provided by an embedded ARM CPU that sits between the CPU and the IO devices, and handles all the IO. The two main flaws were (a) A bug in the code that compared security keys, such that it was possible to forge security keys, and (b) secret break-once-run-everywere information was stored un-encrypted in RAM, where it could be extracted using hardware modifications.

There's a nice table at the end of the presentation showing a number of recent consumer devices, what their security model was, and how long it took to break them.

The PS3 is the only console that's currently unbroken. The PS3's security model seems similar to the Xbox 360, but somewhat weaker. But it remains unbroken. This seems to due to the existence of an official PS3 Linux port, which means most Linux kernel hackers are not motivated to hack the PS3 security. (Only the ones who want full access to the GPU from Linux are motivated, and only to the extent that they can access the GPU.)

Larrabee papers from SIGGRAPH Asia 2008

2008-12-25T18:51:00.000-08:00

...as seen on the Beyond3D GPGPU forum, here are the presentations from the recent (December 12th 2008) "Beyond Programmable Shading" course:

SIGGRAPH Asia 2008: Parallel Computing for Graphics: Beyond Programmable Shading

There are good presentations from both GPU vendors and academics. My favorite presentations are the Intel ones on Larrabee, just because I'm so interested in that architecture:

Parallel Programming on Larrabee - describes the Larrabee fiber/task programming model.

Next-Generation Graphics on Larrabee - how Larrabee's standard renderer is structured, and how it can be extended / modified.

IBM / Sony missed a bet by not presenting here. That's too bad, because Cell sits between the ATI / NVIDIA parts and Larrabee in terms of programmability. And Cell's been available for long enough that there should be a number of interesting results to report.

Note to self: consider buying a PS3 and learning Cell programming, just to get ready for Larrabee. Heh, yeah, that's the ticket. Being able to play PS3-specific games like Little Big Planet and Flower would be just a coincidental bonus.

Fun with Git

2008-12-08T10:35:00.000-08:00

This weekend I reorganize my home source code projects. I have a number of machines, and over the years each one had accumulated several small source-code projects. (Python scripts, toy games, things like that.) I wanted to put these projects under source code control. I also wanted to make sure they were backed-up. Most of these little projects are not ready to be published, so I didn't want to use one of the many web-based systems for source-code management.

After some research, I decided to use replicated git repositories.

I created a remote git repository on an Internet-facing machine, and then created local git repositories on each of my development machines. Now I can use git push and git pull to keep the repositories synchronized. I use git's built-in ssh transport, so the only thing I had to do on the Internet-facing-machine was make sure that the git executables were in the non-interactive-ssh-shell's path. (Which I did by adding them in my .bashrc file.)

Git's ability to work off-line came in handy this Sunday, as I was attending an elementary-school chess tournament with my son. Our local public schools don't have open WiFi, so there was no Internet connectivity. But I was able to happily work away using my local git, and later easily push my changes back to the shared repository.

Microsoft New Xbox Experience Avatars

2008-11-19T10:17:00.000-08:00

I just tried creating an avatar on Microsoft's new Xbox dashboard. As you can see (at least when the Microsoft server isn't being hammered) on the left, they provide a URL for displaying your current Avatar on a web page.

The character creation system is not too bad. In some ways it's more flexible than Nintendo's Mii (for example more hair styles and clothing), but in other ways it's more limited (less control over facial feature placement).

My avatar looks better on the Xbox than it does here -- they should consider sharpening the image. For example, the T-shirt my avatar is wearing has a thin-lined Xbox symbol.

I think they do a good job of avoiding the Uncanny Valley effect. I look forward to seeing how avatars end up being used in the Xbox world.

In othe Xbox-related news I'm enjoying playing Banjo Kazooie Nuts & Bolts with my son. All we have right now is the demo, but it's great fun for anyone who likes building things. It's replaced Cloning Clyde as my son's favorite Xbox game.

Internals of the Azul Systems Multi-core Java processor

2008-11-19T05:24:00.000-08:00

I'm a big fan of CPU architectures. Here's a conversation between David Moon formerly of Symbolics Lisp Machines and Cliff Click Jr. of Azule Systems. They discuss details of both the Lisp Machine architecture and Azule's massively multi-core Java machine.

http://blogs.azulsystems.com/cliff/2008/11/a-brief-conversation-with-david-moon.html

The claim (from both Symbolics and Azule) is that adding just a few instructions to an ordinary RISC instruction set can make GC much faster. With so much code being run in Java these days I wonder if we'll see similar types of instructions added to mainstream architectures.

Can a comic strip make you more productive?

2008-10-20T00:54:00.001-07:00

This one can:

XKCD: Someone is Wrong on the Internet

--- this comic's punchline has saved me at least an hour of a week since it came out. That's more than I've saved by learning Python. :-)

Next gen video console speculation suggests we aim low

2008-09-30T10:01:00.000-07:00

The next generation of video game consoles should start in 2011. (Give or take a year). It takes about three years to develop a video game console, so work should be ramping up at all three video game manufacturers.

Nintendo's best course-of-action is pretty clear: Do a slightly souped-up Wii. Perhaps with lots of SD-RAM for downloadable games. Probably with low-end HD resolution graphics. Definately with an improved controller (for example with the recent gyroscope slice built in.)

Sony and Microsoft have to decide whether to aim high or copy Nintendo.

Today a strong rumor has it that Sony is polling developers to see what they think of a PlayStation 4 that is similar to a cost-reduced PlayStation 3 (same Cell, cheaper RAM, cheap launch price.)

http://forum.beyond3d.com/showthread.php?t=50037

That makes sense as Sony has had problems this generation due to the high launch cost of the PS3. The drawback of this scheme is that it does nothing to make the PS4 easy to program.

In the last few weeks we've seen other rumors that Microsoft's being courted by Intel to put the Larrabee GPU in the next gen Xbox. I think that if Sony aims low, it's likely that Microsoft will be foreced to aim low too, which would make a Larrabee GPU unlikely. That makes me sad -- in my dreams, I'd love to see an Xbox 4 that used a quad-core x86 CPU and a 16-core Larrabee GPU.

Well, the great thing is that we'll know for sure, in about 3 years. :-)

Woot! I'm 19th place in the ICFP 2008 Programming Contest

2008-09-24T07:46:00.000-07:00

Team Blue Iris (that's me and my kids!) took 19th place, the top finish for a Python-based entry!

Check out the ICFP Programming Contest 2008 Video. The winning team list is given at 41:45.

Will Smart Phones replace PCs?

2008-09-19T07:01:00.000-07:00

That's the question Dean Kent asks over at Real World Tech's forums. I replied briefly there, but thought it would make a good blog post as well.

I'm an Android developer, so I'm probably biased, but I think most people in the developed world will have a smart phone eventually, just as most people already have access to a PC and Internet connectivity.

I think the ratio of phone / PC use will vary greatly depending upon the person's lifestyle. If you're a city-dwelling 20-something student you're going to be using your mobile phone a lot more than a 60-something suburban grandpa.

This isn't because the grandpa's old fashioned, it's because the two people live in different environments and have different patterns of work and play.

Will people stop using PCs? Of course not. At least, not most people. There are huge advantages to having a large screen and a decent keyboard and mouse. But I think people will start to think of their phone and their PC as two views on the same thing -- the Internet. And that will shape what apps they use on both the phone and the PC.

And this switching will be a strong force towards having people move their data into the Internet cloud, so that they can access their data from whatever device they're using. This tendency will be strongest with small-sized data that originates in the cloud (like email), but will probably extend to other forms of data over time.

Peter Moore on Xbox

2008-09-19T06:55:00.000-07:00

Peter Moore on Xbox

I always liked Peter Moore, and I was sorry when he left Xbox for EA. He's given a very good interview on his time at Sega and Microsoft. (He ran the Xbox game group at Microsoft before moving on to Electronic Arts.) Lots of insight into the Xbox part of the game industry.

Here he is talking about Rare:

...and you know, Microsoft, we'd had a tough time getting Rare back – Perfect Dark Zero was a launch title and didn't do as well as Perfect Dark… but we were trying all kinds of classic Rare stuff and unfortunately I think the industry had past Rare by – it's a strong statement but what they were good at, new consumers didn't care about anymore, and it was tough because they were trying very hard - Chris and Tim Stamper were still there – to try and recreate the glory years of Rare, which is the reason Microsoft paid a lot of money for them and I spent a lot of time getting on a train to Twycross to meet them. Great people. But their skillsets were from a different time and a different place and were not applicable in today's market.

Pro tip: Try writing it yourself

2008-09-16T07:28:00.001-07:00

Sometimes I need to get a feature into the project I'm working on, but the developer who owns the feature is too busy to implement it. A trick that seems to help unblock things is if I hack up an implementation of the feature myself and work with the owner to refine it.

This is only possible if you have an engineering culture that allows it, but luckily both Google and Microsoft cultures allow this, at least at certain times in the product lifecycle when the tree isn't frozen.

By implementing the feature myself, I'm (a) reducing risk, as we can see the feature sort of works, (b) making it much easier for the overworked feature owner to help me, as they only have to say "change these 3 things and you're good to go", rather than having to take the time to educate me on how to implement the feature, (c) getting a chance to implement the feature exactly the way I want it to work.

Now, I can think of a lot of situations where this approach won't work: at the end of the schedule where no new features are allowed, in projects where the developer is so overloaded that they can't spare any cycles to review the code at all, or in projects where people guard the areas they work on.

But I've been surprised how well it works. And it's getting easier to do, as distributed version control systems become more common, and people become more comfortable working with multiple branches and patches.

Tim Sweeney on the Twilight of the GPU

2008-09-15T06:19:00.001-07:00

Ars Technica published an excellent interview with Tim Sweeney on the Twilight of the GPU. As the architect of the Unreal Engine series of game engines, Tim has almost certainly been disclosed on all the upcoming GPUs. Curiously he only talks about NVIDIA and Larrabee. Is ATI out of the race?

Anyway, Tim says a lot of sensible things:

Graphics APIs at the DX/OpenGL level are much less important than they were in the fixed-function-GPU era.
DX9 was the last graphics API that really mattered. Now it's time to go back to software rasterization.
It's OK if NVIDIA's next-gen GPU still has fixed-function hardware, as long as it doesn't get in the way of pure-software rendering. (ff hardware will be useful for getting high performance on legacy games and benchmarks.)
Next-gen NVIDIA will be more Larrabee-like than current-gen NVIDIA.
Next Gen programming language ought-to-be vectorized C++ for both CPU and GPU.
Possibly the GPU and CPU will be the same chip on next-gen consoles.

The Future of Graphics APIs

2008-08-12T07:48:00.000-07:00

The OpenGL 3.0 spec was released this week, just in time for SigGraph. It turns out to be a fairly minor update to OpenGL, little more than a codification of existing vendor extensions. While this disappoints OpenGL fans, it's probably the right thing to do. Standards tend to be best when they codify existing practice, rather than whey they try to invent new ideas.

What about the future? The fundamental forces are:

+ GPUs and CPUs are going to be on the same die
+ GPUs are becoming general purpose CPUs.
+ CPUs are going massively multicore

Once a GPU is a general purpose CPU, there's little reason to provide a standard all-encompasing rendering API. It's simpler and easier to give an OS and a C compiler, and a reference rendering pipeline. Then let the application writer customize the pipeline for their application.

The big unknown is whether any of the next-generation video game consoles will adopt the CPU-based-graphics approach. CPU-based graphics may not be cost competitive soon enough for the next generation of game consoles.

Sony's a likely candidate - it's a natural extension to the current Cell-based PS3. Microsoft would be very comfortable with a Larrabee-based solution, given their OS expertiese and their long and profitable relationship with Intel. Nintendo's pretty unlikely, as they have made an unbelievable amount of money betting on low-end graphics. (But they'd switch to CPU-based graphics in an instant if it provided cost savings. And for what it's worth, the N64 did have DSP-based graphics.)

Mac Min HTPC take two

2008-07-27T05:38:00.000-07:00

I just bought another Mac Mini to use as a HTPC (home theater PC). I tried this a year ago, but was not happy with the results. But since then I've become more comfortable with using OS X, so today I thought I'd try again.

Here's my quick setup notes:

I'm using a Mac Mini 1.83 Core 2 Duo with 1 GB of RAM. This is the cheapest Mac Mini that Apple currently sells. I thought about getting an AppleTV, but I think the Mini is easier to modify, has more CPU power for advanced codecs, and can be used as a kid's computer in the future, if I don't like using it as an HTPC. I also have dreams of writing a game for the Mini that uses Wiimotes. I think this would be easier to do on a Mini than an AppleTV, even though the AppleTV has a better GPU.
I'm using "Plex" as for viewing problem movies, and I think it may end up becoming my main movie viewing program. It's the OSX version of Xbox Media Center. (Which is a semi-legal program for a hacked original Xbox. The Plex version is legal because it doesn't use the unlicensed Xbox code.) The UI is a little rough. (Actually, by Mac standards it's _very_ rough. :-) ) Plex has very good codec support and lots of options for playing buggy or non-standard video files.
I connected my Mac Mini to my media file server using gigabit ethernet. This made Front Row feel much snappier than when I was using an 802.11g wireless connection.
I installed the Perian plugin adds support for many popular codecs to Quicktime and Front Row.
I set up my Mac Mini to automatically mount my file server share at startup and when coming out of sleep. Detailed instructions here. Synopsis: Create an AppleScript utility to mount the share, put the utility in your Login Items so that it's run automatically at startup, and finally use SleepWatcher to run the script after a sleep.
I added FrontRow to my Login Items (Apple Menu:System Preferences...:Accounts:Login Items) to start Front Row at startup.
I administer my Mini HTPC using VNC from a second computer. I don't have a keyboard or mouse hooked up to the HTPC normally. I disabled the Bluetooth keyboard detection dialog using Apple Menu:System Preferences...:Bluetooth:Advanced... then uncheck "Open Bluetooth Setup Assistant at startup when no input device present".

Things I'm still working on:

No DVR-MS codec support in Perian, and therfore none in Front Row. I have to use my trusty Xbox 360 or VLC to view my Microsoft Windows Media Center recordings.

ICFP 2008 post-mortem

2008-07-14T06:07:00.000-07:00

This year's ICFP contest was a traditional one: Write some code that solves an optimization problem with finite resources, debug it using sample data sets, send it in, and the judging team will run it on secret (presumably more difficult) data sets, and see whose program does the best. The problem was to create a control program for an idealized Martian rover that had to drive to home base while avoiding craters, boulders, and moving enemies.

I read the problem description at noon on Friday, but didn't have time to work on the contest until Saturday morning.

The first task was to choose a language. On the one hand, the strict time limit argued for an easy-to-hack "batteries included" language like Python, for which libraries, IDEs, and cross-platform runtime were all readily available. On the other hand, the requirement for high performance and ability to correctly handle unknown inputs argued for a type safe, compiled language like ML or O'Caml.

I spent a half an hour trying to set up an O'Caml IDE under Eclipse, but unfortunately was not able to figure out how to get the debuger to work. Then I switched to Python and the PyDev IDE, and never ran into a problem that made me consider switching back.

I realize that the resulting program is much slower than a compiled O'Caml would be, and it probably has lurking bugs that the O'Caml type system would have found at compile time. But it's the best I could do in the limited time available for the contest.

It was very pleasant to develop in Python. It's got a very nice syntax. I was never at a loss for how to proceed. Either it "just worked", or else a quick web search would immediately find a good answer. (Thanks Google!)

The main drawback was that the Python compiler doesn't catch simple mistakes like uninitialized variables until run time. Fortunately that wasn't too much of a problem for this contest, as the compile-edit-debug cycle was only a few seconds long, and it only took a few minutes to run a whole test suite.

The initial development went smoothly: I wrote was the code to connect to the simulation server and read simulation data from the server. Then I created classes for the various types of objects in the world, plus a class to model the world as a whole. I then wrote a method that examined the current state of the world and decided what the Martian rover should do next. Finally I wrote a method that compared the current and desired Martian rover control state, and sent commands back to the simulation server to update the Martian rover control state.

The meat of the problem is deciding how to move the rover. The iterative development cycle helped a lot here -- by being able to run early tests, I quickly discovered that the presence of fast-moving enemies put a premium on high speed movement. You couldn't cautiously analyze the world and proceed safely, you had to drive for the goal as quickly as possible.

My initial approach was to search for the closest object in the path of the rover, and steer around it. This worked, but had issues in complicated environments. Then I switched to an idea from Craig Reynolds' Not Bumping Into Things paper: I rendered the known world into a 1D frame buffer, and examined the buffer to decide which way to go. That worked well enough that I used it in my submission.

I spent about fourteen hours on the contest: Two hours reading the problem and getting the IDE together, ten hours over two days programming and debugging, and about two hours testing the program on the Knoppix environment and figuring out how to package and submit the results.

Things I wish I had had time to do

My rover is tuned for the sample data sets. The organizers promised to use significantly different data sets in the real competition. Unfortunately, I didn't have time to adapt the program to these other data sets, beyond some trivial adjustments based on potential differences in top speed or sensor range.
I model the world at discreet times, and don't account for the paths objects take over time. I can get away with this because I'm typically traveling directly towards or away from important obstacles, so their relative motion is low. But I would have trouble navigating through whirling rings of Martians.
I don't take any advantage of knowledge of the world outside the current set of sensor data. The game explicitly allows you to remember the world state from run to run during a trial. This could be a big win for path planning when approaching the goal during the second or later trials.
I don't do any sort of global path planning. A simple maze around the goal would completely flummox my rover.

I very much enjoyed the contest this year. I look forward to finding out how well I did, as well as reading the winning programs. The contest results will be announced at the actual ICFP conference in late September.

Getting ready for ICFP 2008

2008-07-09T03:47:00.000-07:00

The rules for this year's ICFP contest have just been posted. Although the actual problem won't be posted until Friday July 11th, the rules themselves are interesting:

Your code will be run on a 1GB RAM 4GB swap 2GHz single-processor 32-bit AMD x86 Linux environment with no access to the Internet.
You have to submit source code.
You may optionally submit an executable as well (useful if for example you use a language that isn't one of the short list of languages provided by the contest organizers.)
Teams are limited to 5 members or less.

I have mixed feelings about these rules. The good news is:

It should be possible for most interested parties to recreate the contest environment by using the contest-provided Live CD. A computer capable of running the contest could be purchased new for around $350.
It seems that the focus will be on writing code in the language of the contestant's choice, rather than writing code in the language of the contest organizer's choice. This wasn't the case in some previous year's contests.
It provides a level playing field in terms of CPU resources available to contestants.
It ensures that the winning entry is documented. (A few years ago the contest winner never wrote up their entry, which was quite disappointing.)

The bad news is:

It penalizes contestants with low Internet bandwidth. The Live CD image is not yet available for download, and I anticipate some contestants will have difficulty downloading it in time to compete in the contest.
It penalizes non-Linux users, who are forced to use an alien development environment and operating system.
It penalizes languages too obscure to make the contest organizer's list. That goes against the whole "prove your language is the best" premise of the contest.
The target system is 32 bits and single core, which is at least five years out of date, and does little to advance the state of the art. This penalizes many languages and runtimes. For example OCaml has a harsh implementation limit on array size in 32 bit runtimes that is relaxed in 64-bit runtimes.
It seems as if there won't be any during-the-contest scoring system, so we will have to wait until the ICFP conference to find out how the contestants did.

Still, I'm hopeful that the contest itself will still be enjoyable. I look forward to reading the actual programming problem on Friday.

Network Attached Storage Notes

2008-06-28T12:03:00.000-07:00

I just bought a Buffalo LinkStation Mini 500GB Networked Attached Storage (NAS) device. It's a very small fanless Linux file server with two 250 GB hard drives, 128 MB of RAM, a 266 MHz ARM CPU and a gigabit Ethernet port.

My reasons for buying a NAS

I wanted to provide a reliable backup of family photos and documents, and I was getting tired of burning CDs and DVDs.
I wanted a small Linux-based server I could play with.

My reason for buying the LinkStation Mini

It's fanless.
It's tiny.
Buffalo has a good reputation for NAS quality.
There is a decent sized Buffalo NAS hacking community.
Fry's had it on sale. :-)

Setting it up

Setup was very easy -- I unpacked the box, pluged everything in, and installed a CD of utility programs. The main feature of the utility program is that it helps find the IP address of the NAS. All the actual administration of the NAS is done via a Web UI.

To RAID or not to RAID

The LinkStation Mini comes with two identical drives, initially set up as RAID0. This means that files are split across the two drives, which means that if either drive fails all your files will be lost. Using the Web UI, I reformatted the drives to RAID1, which means that each file is stored on both drives. This of course halves the amount of disk space available to store files, but I thought the added security was worth it. This process of switching over was fairly easy to do, but it erases all the data on the drives and it takes about 80 minutes.
RAID1 is more secure than RAID0, but it is not perfectly secure. There's still a chance of losing all the data if the controller goes bad, or if the whole device is stolen or destroyed. So for extra security I will probably end up buying a second NAS (or USB 2.0 drive), and setting up an automatic backup of the backup device. The Mini can be set to perform periodic automatic backups to a second LinkStation for this very reason. Once I do that, I'll probably reformat my NAS's drives back to RAID0 to enjoy the extra storage space.

Getting Access to Linux root

There is a program called acp_commander, that enables you to remotely log in as root on any Buffalo LinkStation Mini on the same LAN as your PC. Once logged in as root you can read and write any file on the NAS. You can use this power to install software and reconfigure your system.

Yes, this is a security hole -- it means anyone with access to your local LAN can bypass all the security on the file server. Very advanced users can patch the security hole by following the instructions at this web forum. I think it's extremely negligent of Buffalo to configure their NAS devices in this way. Imagine the uproar if Microsoft shipped a product with this kind of security hole.

Playing with Linux

Once I obtained root access to the Mini I was able to install additional software. I installed the Optware package system, which gives access to a wide variety of precompiled utility programs, as well as tools for writing new programs.
(Yeah, I know, it's crazy to run software on a file server that's supposed to be backing up important data. Right now I'm just having fun playing with my new toy, but eventually I'm going to have to get serious about making it work reliably.)

From looking at what other people have done, I am thinking that I might set up a small web server, or perhaps a media server for streaming music and video.

Thinking of the Future

There's an active LinkStation hacking community at buffalo.nas-central.org. Unfortunately the Linkstation Mini is so new that nobody in the NAS hacking community knows much about it. Right now it seems to be similar to a LinkStation Pro Duo, but only experience will show if this is true.
The Mini comes with a USB 2.0 port, to which you can attach a printer and/or a hard disk. While the hard disk isn't part of a RAID array, it could be used to back up the RAID array, providing an additional layer of security.

Alternatives

There must be 20 different NAS vendors, although many of them just repackage reference designs made by the SOC vendors. SOC mean System on Chip. Marvell seems to be the dominant player in the NAS SOC market these days. A good overview of available NAS products can be found by visiting Small Net Builder. Some brands like Revolution, QNAP and Synology cater to enthusiasts who are interested in using the NAS as a mini Linux server. The only thing that stopped me from buying those brands is that (a) they're more expensive, and (b) they don't currently have fanless RAID1 form factors.
The Revolution brand is actually owned by Buffalo. They add hardware daughter boards to standard Buffalo products. The daughter boards have extra flash chips and I/O connectors. It's possible that there will be a Revolution "Kuro box" version of the Mini some day.

The venerable (out-of-production, but still available in stores) Linksys NSLU2 product is fanless and cheap, and very popular with hackers, but you need to add hard drives, and I don't think its networking performace is very good compared to more recent products.

Another approach is to use a PC, either running a regular OS like Windows XP, Windows Server, OSX or Linux, or a special-purpose stripped-down NAS version. I do have an old PC currently running Windows Media Center that I could use for this purpose, but I didn't seriously consider this option because I wanted something small, low-power, and quiet. (And I was looking for an excuse to learn how to administer a Linux system anyway.)

Apple makes NAS products too. Their the Airport Extreme and Time Capsule products both look OK, but neither one supports RAID1. And there doesn't seem to be a software hacking community around these products. There is a software hacking community around the AppleTV, which you could make into a NAS by adding some USB 2.0 hard drives.

Some routers (like the Apple Airport Extreme mentioned above) have USB 2.0 ports, but I think they avoid advertising themselves as NAS products because they don't have enough RAM (or CPU) to act as both routers and file servers. As a result, these products tend to have relatively low NAS performance.

Some people would laugh at a NAS that has only 240GB of storage. They are more interested in the high-end NASes that use four or five 1GB disks. When formatted in RAID5 configuration those NASes have 3GB of usable space. But they also cost $600 plus the cost of the drive ($160 each). Which is much more than I wanted to spend. Besides the cost, another drawback is that these products are nearly as large and noisy as regular PCs. Still, if you've got a lot of video (or are anticipating generating a lot of video in the future) the larger NASs are the way to go.

A NAS in Every Garage?

While all my friends and I are setting up file servers to store their family's videotapes, I'm not sure if the product will become universally popular. I think it will depend on how people's secure storage needs evolve.
We're already seeing small files (email, photos, low-res videos) being stored in the cloud. It seems like it's just a matter of time before everything is. Unless people suddenly come up with compelling new applications that use dramatically more data (holographic TV perhaps?), it seems likely that people's personal storage needs are going to top out in the next decade. If disk capacity and network bandwidth keep growing at a rapid pace for several decades beyond that, then it seems inevitable that cloud storage will eventually take over.

In any event, by the time this happens my little Mini will long since have been retired. (I remember paying $100 apiece for 1GB Jaz disks back in the day. It's amazing how far and how fast storage prices have fallen.) If all goes well, my my family's photos and other important documents will still be around!

I saw the original Spacewar! on a PDP-1 today

2008-06-07T20:14:00.001-07:00

I went to the Computer History Museum today. I saw the Visual Storage exhibit, which is a collection of famous computers, the Babbage Difference Engine, which is a very elaborate reproduction of a never-actually-built Victorian era mechanical calculator, and the PDP-1 demo. This last demo was very special to me, because I finally got to play the original Spacewar! game, and meet and chat with Steve Russell, the main developer. (Perusing Wikipedia I now realize that Steve was also an early Lisp hacker. D'Oh!, I was going to ask a question about Lisp on the PDP-1, but I got distracted.)

There's a Java Spacewar! emulator, but it doesn't properly convey the look of the PDP-1 radar-scope-based display. The scope displays individual dots, 20,000 times per second. Each dot starts as a fuzzy bright blue-white dot, but then fades quickly to a dim yellow-green spot, which takes another 10 seconds to fade to black. This means that dim yell0w-green trails form behind the ships as they fly around. These trails add a lot to the game's distinctive look. (In addition, due to time multi-plexing, the stars of the starfield are much dimmer than the space ships or the sun.) The fuzzyness of the dots means that the spaceships look much smoother on the PDP-1 scope than they do in the Java simulator.

According to Steve Russel and the other doscents, the Java version also runs faster than a real PDP-1.

I also got to see serveral other cool PDP-1 hacks, including the original Munching Squares, 4-voice square-wave computer synthezed music, and the famed Minskeytron. The author of the music synth program, Peter Sampson, was present, and explained how he carefully patched into four of the console lights to make a four-voice D/A converter to get music out of the machine.

They keep all the hacks loaded into the PDP-1 core at the same time, and just use the front panel to decide which one to jump to. The core memory is non-volitile. The PDP-1 even booted in a few seconds -- just the time it took the power supply to come up to speed.

The PDP-1 demo is given twice a month, on the second and fourth Saturdays. I highly recommend it for adults and children over 12. (It's 45 minutes long, so younger kids might get bored.)

Thoughts on In-Flight Entertainment systems

2008-06-05T13:34:00.000-07:00

I recently spent a lot of time using two different in-flight entertainment systems: one on Eva Air, and another on Virgin Atlantic. For people who haven't flown recently, I should explain that these systems consist of a touch-sensitive TV monitor combined with a remote-control-sized controller. The systems typically offer music, TV, movies, flight status, and video games.

I believe both systems were based on Linux. I saw the Eva system crash and reboot, and the Virgin Air system has a number of Linux freeware games.

The GUI frameworks were pretty weak -- both systems made poor use of the touch screen and had obvious graphical polish issues. The Virgin system was much higher resolution, and was 16:9 aspect ratio. I expect it was running on slightly higher-spec hardware.

Both systems worked pretty well for playing music and watching TV or movies. The media controls were pretty limited - neither system allowed seeking to a particular point in a movie, or even reliably fast forwarding. Both systems provided enough media to entertain your average customer for the duration of the flight.

One cool feature of the EVA system was backwards compatibility mode with the older "channel" music system from the 70's. The controller came with the traditional "channel" UI. If you used the channel buttons, the system simply acted like the old system, cycling through a limited number of preset channels. One nice difference from the old channel system is that these new virtual channels always started when you switched to them, rather than having to join the looping presentation at whatever point it happened to be in.

The game portions of both sysetems were very weak. None of the games were very good. Perhaps the best game was a port of the shareware Doom game on the Virgin Atlantic system. (I used an in-flight entertainment system on Singapore Air many years ago that had Nintendo games. It was more fun.)

The Virgin system allowed you to order food and drink, which was nice. Both systems had credit card swipers, and offered some for-pay options. Both systems allowed you to make in-flight phone calls. EVA allowed you to send SMS messages and emails.

Both systems allowed you to create "play lists" of music tracks that would then be played while you did other tasks. I enjoyed this, but I suspect it's not used much, as anyone with the sophistication and interest to use this UI would probably have their own MP3 player.

The Virgin system had two other very nice features: 1) laptop power in most seats (although only two plugs for every three seats), and 2) Ethernet connections. Unfortunately the ethernet connections were not yet active.

Virgin allowed you to "chat" between seats. I didn't try this, but it seems like it would be fun for some situations (e.g. when a high school class takes a trip.) I expect that the Doom game can play between seats as well, but didn't investigate.

Virgin also had normal mini stereo headphone plugs, which I think was a good idea. Eva had two kinds of audio plug, but neither one was the normal mini stereo plug. I tried using "Skull candy" noise-canceling headphones with the Virgin system, and while they helped suppress the airplane noise, they didn't eliminate it completely.

It will be interesting to see how these systems evolve over time. I think that once in-plane internet access becomes practical people will prefer to surf the Internet to using most of the other services. (besides movie watching) And with the in-seat power, I think many people will prefer using their own laptop to the in-seat system. On the other hand, the in-seat system is very space efficient. There's a chance people will use it as a remote display for their own laptop or mobile phone, which could then remain tucked away in the carry-on luggage.

Wii long term strategy

2008-05-31T17:20:00.000-07:00

Here's a very long, quite good post on Nintendo's strategy with the Wii:

http://malstrom.50webs.com/birdman.html

The thesis is that the mainstream video game market arms race of every-more-complicated games ended up overshooting enough of the potential game market to allow an opening for simpler "down-market" games, and that Wii was able to exploit this opening. The article predicts that Nintendo will now move up-market, producing more complicated games over time, pushing PS3 and Xbox 360 into very up-market niches. Sort of how consoles took over from PC games.

OS X will hang if your VPN connection is flakey

2008-05-14T00:04:00.000-07:00

OS X is by and large a good OS, but once you get past the sexy UI you find a lot of rough edges.

For example, this month I've been working remotely over a flakey DSL connection. I ran into a very frustrating problem: if you're using a PPTP-based VPN, and your network connection is poor quality, the whole Apple UI will frequently freeze up with the "Spinning beachball" cursor for minutes at a time.

Luckily for me the work-around is to reboot my DSL modem. But it seems like poor system design for the VPN packet performance to affect the UI of non-networked applications.

Yegge's rant on dynamic languages

2008-05-13T20:29:00.000-07:00

Another superb rant by Steve Yegge on dynamic languages:

http://steve-yegge.blogspot.com/2008/05/dynamic-languages-strike-back.html

The comment section's good too -- especially the long comment by Dan Weinreb of Lisp / ITA software fame.

Steve's got the same problem some of my self-taught friends do (hi Bob, hi Jim!): he'll say something in a strongly opinionated way, without giving supporting evidence. I think that makes people think he doesn't know what he's talking about. So people tend to write him off. But if you talk with him, it almost always turns out his strong opinions are backed by some pretty deep experience and insight. I've learned to give Steve (and my self-taught friends) the benefit of the doubt.

Wow, TVs are complicated

2008-04-18T09:53:00.001-07:00

Check out this teardown of a Sony OLED TV. It looks like Sony has a standardized architecture for their TVs, which makes sense, but which also means that some TVs have unused capabilities (such as a multi-core CPU powerful enough to run a web browser. I wish an enterprising hacker would figure out how to download code and run them on the TVs -- my understanding from reading Sony's GPL web site is that they already have Linux and busybox installed. Oh well, maybe GPL 3.0 will force Sony to make their TVs user-upgradable in the future.

It's significant that Sony's not using the Cell CPU in their TVs. That was part of the justification for spending so much on Cell. I assume this means that Cell's just not cost-effective for TVs.

Tom Forsyth on Larrabee

2008-04-18T09:49:00.000-07:00

Tom Forsyth, who recently left RAD to work at Intel on the Larrabee project, has posted to his tech blog explaining that Larrabee is going to be primarily a traditional OpenGL/DirectX rasterizer, not some crazy raytracer:
Larrabee and Raytracing

Dusty Decks

2008-04-06T10:56:00.000-07:00

Back in the '90s I had a home page where I posted some of my code hacks and articles. If you want to see what I was doing 10 years ago, check out:

Jack's Hacks

(Mostly Java and Anime. Both of which were leading-edge back then, but are kind of main-stream now.)

ThinLisp

2008-03-30T00:23:00.000-07:00

Some notes on ThinLisp, a dialect of Lisp for real-time systems. Thin Lisp was written by Gensym Corporation in the '90s. The general idea is that you develop your program using a subset of Common Lisp, and then compile it into efficient C. Garbage collection is avoided by using object pools, arenas, and similar tricks familiar to advanced C programmers.

The current home of ThinLisp seems to be Vladimir Sedach's Code Page . Vladimir seems to have used it for "one small OpenGL" project before abandoning it. He seems to be happily hacking ParenScript (a Lisp to Javascript translator) these days.

The Scheme guys have similar, but more modest, sysems: Schelp, and PreScheme (part of Scheme48).

One year at Google!

2008-03-26T08:10:00.000-07:00

Happy Anniversary to me! Google's automated HR script just emailed me its congratulations.

Although I miss my friends and former colleagues at Microsoft, and I miss the games industry, overall I'm still glad I made the switch. I'm enjoying the new work, and learning all the cool Google technologies. Now if only the stock price didn't keep going down. :-)

Some things I like:

Switching from Window to Macintosh. It took me six months to get used to the subtle differences, but as a user I'm just happier with the Mac. It's easier for me to use. Now, to be fair, at home I still maintain a Windows Vista machine for the excellent Windows Media Center, but for everything else I use the Mac.
Better corporate politics. There seems to be less infighting between groups. And while my overall compensation is about the same as it was at Microsoft, the way it's managed and delivered makes it seem less competitive than MS. Perhaps it's an illusion, but it feels better.
Better equipment. I love using a 30" LCD monitor and a high-end laptop, and I love the "we'll just give it to you" technical support. At MS sometimes I felt that I had to fight to justify minor hardware purchases.
Fancier food in the cafeterias. I usually eat lunch and diner at work, so the tasty and relatively healthy food is much appreciated. Interestingly enough, I think Google Seattle uses the same food caterer as Microsoft does. I guess we just asked them to cook different food.
More connected to the Web / Valley culture. Microsoft's pretty insular. It was good to get closer to the Silicon Valley culture again.
Able to use open-source projects. Sometimes the open-source projects are the best way of doing something. But Microsoft's not able to use it, due to a combination of pride, loyalty to its own products, and fear of viral licenses. For example, using Linux for embedded devices is much better than Windows CE. I also find I liked using non-Microsoft technologies like Java, Python and Ruby.

Since you may be wondering, what do I miss from Microsoft?

I miss the Xbox project. Right now my old team is probably starting to plan the next generation of Xbox, and it would have been a blast to have been a part of that process.
I miss the free game betas, and using beta software in general. (I'm a sucker for new features!)
I miss some of the Microsoft-specific technologies like C# (still better than Java), Visual Studio (still better than Eclipse), and F#.
Surprisingly, I don't miss my old single-person office very much. It's true that a group office is distracting. But it's also helpful for sharing ideas and for keeping focused on the project.

Well, that's it, better get back to work!

Insomniac Games Shares Technology

2008-03-18T09:44:00.000-07:00

One very nice habit of Western game companies is that many of them share their technical knowledge with competitors. Insomniac Games is a very good third party console game developer that has concentrated mostly on the PlayStation platform. Their recent games include the shooter "Resistance Fall of Man" and the action platform Rachet and Clank series.

At this year's GDC they announced the "Nocturnal" initiative. It's not a whole game engine, but rather a collection of useful utilities. Things like logging code, C++ object serialization, and a cross-platform performance monitor. Some of the utilities are Playstation 3 specific, but most are applicable to any modern game platform.

Much of this code would be right at home in a "Game Gems" book, but it's even better to have it freely available, on the web, with a BSD-style license. Good for you Insomniac!

Insomniac also publishes technical papers in a GDC-presentation-like format on their Game R & D Page.

Why do so many game companies share information like this? I think it's for a number of mutually supportive reasons:

It's a form of advertising, to show off how smart and competent the developers are. This is helpful in attracting job applicants and impressing publishers and game reviewers.
It educates all game developers, some of whom will eventually end up working for the original developer.
It encourages other developers to share their technology, which benefits the original game developers.
It reduces the value of middleware, driving down the cost of middleware.

Game developers can give away source code because, unlike other kinds of software, the major intellectual property in the game is in the copyrighted and trademarked art assets, (the data) rather than in the code. Yet, at the same time, game quality is directly tied to the performance of the code. This creates a unique economy in which it is profitable for game developers to exchange performance tips with their competitors.

And it's a lot of fun for armchair developers like me. Now if only we can get Naughty Dog to open-source their GOOL and GOAL Lisp-based game engines. :-)

TaxCut 2007 vs. Case-sensitive file systems

2008-03-15T22:08:00.000-07:00

OS X allows you to format your file system as case-insensitive (the default) or case sensitive (like Linux.) I use case-sensitive, to simplify porting and working on Linux software.

Unfortunately, H&R Block's TaxCut 2008 program won't work if installed on a case-sensitive file system. It fails because it can't find files, probably due to differences between the case of the file name used by the programmer and the actual case of the file name on disk.

A work-around is to use the Disk Utility program to create a case-insensitive image, and install Tax Cut on the image. I used a 600 MB image, so that I can store all my tax forms there too, and eventually burn the whole thing to CD to archive it.

Tim Sweeney Too - DX 10 last relevant graphics API

2008-03-15T22:03:00.000-07:00

A good, three-part interview with Tim Sweeney (the other FPS graphics guru):

Part 1: http://www.tgdaily.com/content/view/36390/118/
Part 2: http://www.tgdaily.com/content/view/36410/118/
Part 3: http://www.tgdaily.com/content/view/36436/118/

His main thesis is that soon GPUs will be come so programmable that you won't bother using a standard Graphics API to program them. You'll just fire up a C compiler.

I think he's right.

Carmack speaks on real next-gen graphics

2008-03-12T15:53:00.000-07:00

John Carmack is experimenting with a "sparse octree" data structure for accelerating 3D graphics rendering:

http://www.pcper.com/article.php?aid=532&type=overview

Best quote:

"The direction that everybody is looking at for next generation, both console and eventual graphics card stuff, is a "sea of processors" model, typified by Larrabee or enhanced CUDA and things like that, and everybody is sort of waving their hands and talking about “oh we’ll do wonderful things with all this” but there is very little in the way of real proof-of-concept work going on. There’s no one showing the demo of like, here this is what games are going to look like on the next generation when we have 10x more processing power - nothing compelling has actually been demonstrated and everyone is busy making these multi-billion dollar decisions about what things are going to be like 5 years from now in the gaming world. I have a direction in mind with this but until everybody can actually make movies of what this is going to be like at subscale speeds, it’s distressing to me that there is so much effort going on without anybody showing exactly what the prize is that all of this is going to give us."

Second-best quote is that he wants lots of bit-twiddling operations-per-second to traverse the data structures rather than lots of floating-point-operations-per-second. Must be scary for the Larrabee and NVIDIA CPU architects to hear that, this late in their design cycles.

Hopefully John will come up with a cool demo that helps everyone understand whether his approach is a good one or not. Hopefully the Larrabee / NVIDIA architectures are flexible enough to cope. (Interestingly, no mention of ATI -- have they bowed out of the high-end graphics race?)

ForumWarz - a game about the web forum culture

2008-03-09T10:46:00.000-07:00

This is an interesting role-playing-game set in current-day web forum culture:

http://www.forumwarz.com/

It's somewhat not-safe-for-work, and the humor is pretty low-brow. But what's neat is that you play it through your browser, and it recreates the look-and-feel of web forum culture perfectly. It wouldn't surprise me if the authors just captured the HTML for various real-world forums to create the resources for the game. (Or alternately, created their own fictional forums using web tools, and then captured the HTML from those fictional forums.)

The actual game didn't hold my interest for very long, but it's free and it's fun for a few days.

Good web site for following the Microsoft / Yahoo Merger

2008-02-21T08:44:00.000-08:00

Silicon Alley Insider seems to have the best coverage of the Microsoft / Yahoo Merger.

But for the grumpy inside-Microsoft point-of-view you can't beat Mini-Microsoft .

We write for posterity

2008-02-21T06:38:00.000-08:00

The Google Analytics numbers for this blog are dismal. (Hi Mom! Hi Friends!) I think it's because right now I don't have much to say that's both unique and interesting. Partly this is because so much of my life is off limits: I don't want to talk about the joys & cares of raising a family, and I musn't talk about the joys & cares of raising a new product. What's left are comments on the general state of the web, and essays on general topics like this one.

Why write then, and who am I writing for? I write because something inside me compells me to, and because it helps me think to get my ideas down in written form. Who do I write for? From my Analytics numbers it's clear that I'm writing primarily for search engines (Hi Googlebot!) rather than people. And that's something interesting to think about: Baring a world-wide disaster or cultural revoloution, what I write today will persist for thousands and probably even millions of years, and will be read countless times by search engines, and only occasionally, if at all, by people.

My words will be torn apart and merged with other web pages from other authors, becoming a mulch out of which new insights will be gleaned. (Hmm, not unlike how my body will be recyled when I die, its atoms used to make new things.)

Perhaps the last time my essay will ever be read by a live human is in some far distant future when some graduate student is writing an essay on early-web-era civilization, and is trying to find out what those poor benighted souls thought of the future. (Hi posterity!)

No doubt my words will be automatically translated from 21st-century English into whatever language wins the world-wide language wars. Perhaps my essay will even be automatically annotated, with a description of who I was, and a best guess at what I looked like, from searching the world's photo archives. There will be footnotes and links to explain the archaic topics I'm referencing. "Search engine" - they used to store data in seperate computers, and brute-force building the search index. How primitive! How quaint!

And no doubt the grad-student-of-the-future will glance over my words, then move on to the hundreds of other essays on similar themes. (Good luck with your own essay, future-guy!)

Hey, Paul Graham's arc programming language is out!

2008-01-29T19:24:00.000-08:00

I just noticed (while reading the 4chan prog forum for the first time) that Paul Graham has put up a web site for his minimal Lisp language Arc:

http://arclanguage.org/

The language looks like a nice quiet Scheme-like Lisp dialect. And it has a nice tutorial, as you would expect from a Paul Graham language.

3dMark price/performance charts

2008-01-25T18:54:00.000-08:00

3DMark is a GPU/CPU benchmark used by PC gamers to measure system performance. Here are some great charts showing

What GPU/CPU/RAM/OS/Screen size gamers have, and how it's changed over time

The best bang-per-buck for GPUs and CPUs

My home computer system is very weak compared to these charts, except in one dimension, which is that my 1600 x 1200 display puts me in the top 10% of gamers. Woot!

While many people (myself included) have switched to laptops and/or all-in-ones, if you're planning on building a new desktop, check out the Ars Technica system guide. The guide does a good job of speccing out a "Budget Box", a "Hot Rod", and a "God Box", and it's updated every quarter.

Languages that look interesting

2008-01-24T21:36:00.000-08:00

Currently I'm reading up on the following computer languages:

Python - fun, easy to learn, batteries included
Boo - fun like Python, but with macros and type declarations so that it can run fast.
Erlang - very brief code. I'm impressed by how concise the Wings3D source code is.
Typed Scheme - Scheme with type checking. (Could in theory run fast.)

I may try implementing my old "Dandy" game in these languages to see how they feel.

Darwin Ports issue with "patch"

2008-01-24T21:25:00.000-08:00

Ever since I've upgraded to Apple Macintosh OS X 10.5 Leopard, I've run into problems using the Darwinports "port" command to install new software.

The problem is that for some reason the version of GNU "patch" that I have installed in /usr/bin/patch is version 2.5.8, and it doesn't operate the way that Darwin ports expects. A typical error message is:

---> Applying patches to erlang
Error: Target org.macports.patch returned: shell command " cd "/opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_release_ports_lang_erlang/work/erlang-R12B-0" && patch -p0 < '/opt/local/var/macports/sources/rsync.macports.org/release/ports/lang/erlang/files/patch-toolbar.erl'" returned error 2
Command output: Get file lib/toolbar/src/toolbar.erl from Perforce with lock? [y]
Perforce client error:
Connect to server failed; check $P4PORT.
TCP connect to perforce failed.
perforce: host unknown.
patch: **** Can't get file lib/toolbar/src/toolbar.erl from Perforce

Error: Status 1 encountered during processing.

The work-around is to define the environment variable POSIXLY_CORRECT=1 , as in:

POSIXLY_CORRECT=1 sudo port install erlang

Now, I've done some web searching, and I haven't seen anyone else complaining about this problem, so perhaps there's something odd about my setup.

Web scraping in Java, F#, Python, and not Lisp

2008-01-07T06:13:00.001-08:00

Yesterday I wrote a web scraper. A web scraper is a program that crawls over a set of web pages, following links and collecting data. Another name for this kind of program is a "spider", because it "crawls" the web.

In the past I've written scrapers in Java and F#, with good results. But yesterday, when I wanted to write a new scraper, I though I'd try using a dynamically-typed language instead.

What's a dynamically-typed language you ask? Well, computer languages can generally be divided into two camps, depending on whether they make you declare the type of data that can be stored in a variable or not. Declaring the type up front can make the program run faster, but it's more work for the developer. Java and F#, the languages I previously used to write a web scraper, are statically typed languages, although F# uses type inference so you don't actually have to declare types very often -- the computer figures it out for you.

In order to scrape HTML you need three things:

a language
a library that fetches HTTP pages
a library that parses the HTML into a tree of HTML tags

Unless you're using Mono or Microsoft's Common Language Runtime, the language you choose will restrict the libraries that you can use.

So, the first thing I needed to do was choose a dynamic language.

Since I just finished reading "Practical Common Lisp", an excellent advanced tutorial on the Lisp language, I though I'd try using Lisp. But that didn't work out very well at all. Lisp has neither a standard implementation nor a set of standard libraries for downloading web pages and parsing HTML. I did some Googling to try and find some combination of parts that would work for me. Unfortunately, it seemed that every web page I visited recommended a different combination of libraries, and none of the combinations I tried worked for me. In the end I just gave up in frustration.

Then, I turned to Python. I had not used Python much, but I knew it had a reputation as an easy-to-use language with a lot of easy-to-use libraries. And you know what? It really was easy! I did some web searches, copied some example code, and voila, I had a working web spider in about an hour. And the program was easy to write every step of the way. I used the standard CPython implementation for the language, Python's built-in urllib2 library to fetch the web data, and the Beautiful Soup library for parsing the HTML.

How does the Python compare to Java and F# for web scraping?

Python Benefits:

Very brief, easy to write code
Libraries built in or easy to find
Lots of web examples
I didn't have to think: I just used for loops and subroutine calls.
Very fast turn-around.
Easy to create and iterate over lists of strings.

Python non-issues for this application:

Didn't matter that the language was slow, because this task is totally I/O bound.
Didn't matter that the IDE is poor, using print and developing interactively was fine

F# Benefits:

Good IDE (Visual Studio)
Both URL fetching and HTML parsing libraries built in to CLR

F# Non-issues:

Small community, few examples. (A non-issue because there is an example of how to write a multi-threaded web scraper!)

F# Drawbacks:

The CLR libraries for URL fetching and HTML parsing are more difficult to use than Python. It takes more steps to complete similar operations.
Strong typing gets in the way of writing simple code.
odd language syntax compared to Algol-derived languages.
Hard-to-understand error messages from the compiler.
Mixed functional/imperative programming is more complicated than just imperative programing.
The language and library encourages you to use advanced concepts to do simple things. In my web scraper I wrote a lot of classes and had methods that took complicated curried functions as arguments. This made the code hard to debug. In retrospect perhaps I should have just used lists of strings, the same as I did in Python. Since F# supports lists of strings pretty well, maybe this is my problem rather than F#'s. ;-)

Java benefits:

Good debugger
Good libraries
Multithreading

Java drawbacks:

Very wordy language
Very wordy libraries

Lisp drawbacks:

No standard implementation
No standard libraries

Looking to the future, I'd be interested in writing a web scraper in IronPython, which has good IDE support, and in C# 3.0, which has some support for type inference.

In any event, I'm left with a very favorable impression of Python, and plan to look into it some more. In the past I was put off from it because it was slow, but now I see how useful it is when speed doesn't matter.

[Note: When I first wrote this article I was under the impression that CPython didn't support threads. I since discovered (by reading the Python in a Nutshell book) that it does support threads. Once I knew this, I was able to easily add multi-threading to the web scraper. CPython's threads are somewhat limited: only one thread is allowed to run Python code at a time. But that's fine for this application, where the multiple threads spend most of their time blocked waiting for C-based network I/O. ]

Hot Chips Conference archives

2007-12-29T10:32:00.000-08:00

Curious about the internal designs of GPUs, CPUs, and game consoles? Tired of lame articles full of uninformed speculation and fanboy rants? Then check out the archives of the "Hot Chips" conference, an annual conference where computer chip designers get together to brag about their latest chips. The conference presentation slides are all online, and they're full of good technical information on GPUs, CPUs. and even game consoles. Of course, presenters often gloss over any technical problems with their chips, so you won't get the full picture. But these presentations offer a detailed technical look inside otherwise secret system architectures.

(For what it's worth the web site is poorly organized, and many links are broken -- you sometimes have to edit the URLs slightly to find the correct links.)

Some highlights:

Reality Co-Processor, Ken Hayes (Silicon Graphics, Inc.) - All about the Nintendo 64.

Gekko: A PowerPC compatible processor supporting high-performance 3D Graphics - Gamecube CPU

Multiple Cell Papers (PS3)

Xbox 360 System Architecture

Nintendo Wii security defeated by the Tweezer Attack

2007-12-29T10:10:00.000-08:00

According to a presentation at the 24th Chaos Communication Congress, hackers have apparently been able to defeat the Nintendo Wii game console's security system using tweezers to bypass the hardware memory protection.

The way it works is that the Wii runs in two modes: a GameCube emulation mode, which has access to just 1/8th of the total memory, and Wii mode, that has access to all the memory.

Hackers had already figured out how to run their own code in GameCube mode. So the trick was to run their code in GameCube mode, then use the tweezers to short out the address lines to allow the hacker's code to access parts of rest of the memory. By shorting different address lines different portions of memory were made available. By collecting enough shards they eventually mapped all of memory.

Apparently the Wii operating system keeps its digital signature keys in this protected memory, and once the digital signatures were found it was possible to sign and run homebrew code on the Wii.

It is not clear to me whether the attack is a per-machine attack or a break-once-run-everywhere attack.

Searching for old web pages: The Wayback machine is cool!

2007-12-29T09:28:00.000-08:00

I was searching for information on LINJ, a Lisp language that compiles into human-readable Java code. Unfortunately, the LINJ web site http://www.evaluator.pt/linj.html, is currently offline.

Luckily, it turned out that the Internet Archive Wayback machine had cached both that page, and the download files that that page had pointed to. Very cool!

Similarly, I was looking for the source to the Windows CE port of Quake 3, and found that the project's web site http://www.noctemware.com/q3ce.html had been abandoned and taken over by spammers. Luckily the Wayback machine had cached both the original web page and the downloads.

Let this be a lesson to you aspiring open source developers out there: It's better to store small open-source projects in a large "won't-ever-go-away" source repository like SourceForge or Google Code than to use your own vanity domain hosting. Of course, even using a large popular repository is not failure-proof. Some large code repositories from the early days of the Internet, like DEC's ftp site, have gone away after their owning company was bought by another company. Perhaps some sort of distributed system of discoverable git repositories is the answer.

In the case of Quake 3 for Windows CE, I've contacted the author, Christien Rioux, and with his kind permission I've set up a code.google.com project so that other people can more easily find the sources (and binaries): http://code.google.com/p/q3ce .

Why the Farmers won

2007-12-27T19:51:00.000-08:00

I've been thinking about Lisp lately. A powerful language, with many excellent features, but not hugely successful. And I thought of one reason why:

The excellent book Guns, Germs and Steel hypothesizes that agriculture displaced hunting and gathering because people who practiced agriculture stayed in one place, and were able to have one child per year, as opposed to the hunter-gatherers, who had to wait until their children were old enough to walk before having another child. This reproductive rate difference was amplified by the ability for a given unit of land to support more farmers than hunters. As a result, agriculture displaced hunting even though individual hunters were far healthier (as seen by their skeleton height) than the farmers that displaced them.

So it is possible for a poorer technology to displace a better one, if it has compensating advantages. And I think that's what's hit Lisp. C and Java, which are each less powerful and more wordy than Lisp, are more successful for reasons other than power and brevity. Perhaps because both languages allow lots of reusable code to be written by ordinary programmers. Maybe Lispers are like healthy hunters, being displaced by hordes of sickly farmers.

Well, no doubt the Lispers will take some comfort in the Java and C programmers being displaced in turn by whatever language next becomes even more successful, just as hunter-gatherers may take pleasure in the trend that farmers are gradually being displaced by urban dwellers. (Come to think of it, Lispers have already seen their original competitor Fortran displaced by C/C++, and in turn much of C++ has been displaced by Java and C#.)

I think something similar is happening in productivity applications, as a generation of not-very-good-but-web-based productivity applications is displacing the Microsoft Office suite. (For example, I am typing this blog entry into a simple and ugly HTML-based web form rather than a beautiful Word document.)

Back to Mac

2007-12-23T03:57:00.000-08:00

This week I converted my family's main computer from Vista to OS X. (It's a Mac Mini).

We pretty much use it for web surfing, web email, really old DOS children's games, and photo editing. Macs do that pretty well.

I still have a Vista machine that I use for the excellent Windows Media Center -- love the record-by-keyword feature and the free programming guide.

But for day-to-day use we're back to the Mac.

Alternative language blues

2007-12-23T03:50:00.000-08:00

I've spent roughly 4 years of midnight-engineering time looking into the cool languages to see if they would make game programming easier or more fun. Haskell, Ocaml, F#, Erlang, Scheme, Lisp, D, Factor, Scala, Python, I've looked at them all.

F# held my attention for quite a while, but now my platform-of-choice has moved away from F#'s design center. (I'm into Linux-based mobile platforms now.) And to be honest, I'm still happier in a C-like language.

I'm depressed. Sure, I learned a lot about fancy language features, but I could have written quite a few games in plain-old-C++ (or C#, or Java or Flash or Basic) in the same time.

P.S. Someone else has done this more impressively than I have. Do a Google Groups search for Brandon van Every, who has had a five year odyssey to find the perfect non-C++ game programming language. I corresponded with him back when we were both interested in O'Caml. Since then he's managed to annoy pretty much everyone by harping on their favorite language's shortcomings. In the end (at least as of six months ago) he'd given up and gone back to C++. I look forward to seeing what he does next.

Lisp Hacking and Science Fiction

2007-12-23T03:13:00.000-08:00

I've been poking around with Lisp and Scheme again, and am reminded of some of my favorite science fiction books (warning, plot spoilers follow):

Verner Vinge's "A Fire Upon the Deep" begins with a group of scientists mining an ancient civilization's web archives. They need to build interpreters for the ancient civilization's programs. All goes well until they reconstitute a malevolent AI that they spend the rest of the book fighting.
Piers Anthony's Macroscope involves a group of people trying to decode an Extra-Terestrial message, that other ETs are trying to jam. Over the course of the book your opinion as to which group of ETs has humanity's best interests at heart changes back and forth several times.
Any number of SF stories are set in the far future where people poke around in the ruins of a once-great civilization. (See Gene Wolfe, Cordwainer Smith.)

Working with Lisp reminds me of these books. Lisp's a seductive, ancient, powerful language that has been worked on for years by very smart, very motivated hackers. Pretty much everything one can think of to do with Lisp has been done, multiple times, by really smart people.

For example, I want to have a system where I can interactively write a game, changing code on the fly while the game is running. I want to be able to use macros and garbage collection and free serialization and inspection and all that cool stuff that Lisp provides.

And Naughty Dog had all that, in GOAL, for the PS2. Their implementation was apparently much better (more efficient, less buggy, more features) than one I could cobble together out of open-source-Lisp parts. And they had used it to successfully write two or three games. But they they walked away from it. Gave it up. Went back to C++.

They said it was because they had a lot of pressure from their parent company to make their engine more reusable. But I think it's also because the results they were getting just weren't that much better than the results that all the other developers, who use C++-and-some-cheap-scripting-language-like-Lua, were getting.

I think Lisp is like a powerful alien technology that may not be in your best interests to use.

More evidence that garbage collection is expensive

2007-12-04T09:58:00.000-08:00

As seen on Lambda the Ultimate.org

Quantifying the Performance of Garbage Collection vs. Explicit Memory Management

We compare explicit memory management to both copying and non-copying garbage collectors across a range of benchmarks, and include real (non-simulated) runs that validate our results. These results quantify the time-space tradeoff of garbage collection: with five times as much memory, an Appel-style generational garbage collector with a non-copying mature space matches the performance of explicit memory management. With only three times as much memory, it runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%. When physical memory is scarce, paging causes garbage collection to run an order of magnitude slower than explicit memory management.

The Economics of Selling a MacBook on Craig's List vs. Ebay

2007-12-04T08:31:00.000-08:00

I just sold my MacBook over the web. I sold it on Craig's List. I also considered using eBay, but Craig's List turned out to be a better deal, for both buyer and seller.

The reason is that listing and selling on Craig's List is free, while selling on eBay is expensive, especially for items priced higher than $500. First, there's the listing fee of $0.20, then the Final Value fee of $0.50 + 3.25% * price. But wait, there's more: EBay all-but-requires you to use their PayPal service to settle transactions, and PayPal in turn requires you to use a "Premier" account if you receive more than $500 in eBay payments in one month, which you automatically would if the item you're selling is more than $500. Using a "Premier" account requires that you pay PayPal 2.9%+$0.30 per transaction, even for cash transactions. (The processing fee is less if you are doing a high volume of business through them.)

So the total eBay selling cost is in the range of 6.15%. That's $50 on a $800 item.

You could avoid accepting PayPal, but since accepting PayPal is the norm on eBay, it's very likely that your auction will be shunned, and you will receive a lower price.

Besides the hefty fees, using PayPal is riskier for the seller than using cash. This is because it is possible for a disgruntled buyer to reverse the transaction. (Of course this same ability is a plus for the buyer, as is the ability to use credit cards.)

Even without using eBay to sell the product, it makes sense to use eBay as a price setter. eBay makes this easy to do by reporting the final price for closed auctions that you are "watching". Since auctions last between 3 and 10 days, and an auction must be active in order for you to watch it, you will need at least a week to track enough auctions of similar items to make a fairly accurate estimate of the market price.

Xbox 360 Fall 2007 update adds DIVX/MP4 video support

2007-11-30T10:27:00.001-08:00

The Fall 2007 Xbox 360 dashboard update (coming December 4th) will add support for DivX and MP4 playback.

Video FAQ

This is great news for Xbox 360 owners who want to watch video encoded in these formats. I'm surprised that Microsoft did this, because these formats compete with Microsoft's own WMV format. While the benefit to consumers is obvious, I'm not sure what the benefit is to Microsoft. I'm guessing they did this to both improve the "watch your PC's videos on your Xbox" story, and also to match an existing PS3 feature.

Game resolution issues

2007-11-21T12:39:00.000-08:00

This morning I fired up Mario Galaxy 64 on my new Wii for some early-morning platforming. I happened to sit closer to the screen than I normally do. Yuck! The jaggies were suddenly very apparent and very distracting. But when I moved back to my normal viewing distance, the jaggies were gone, blurred out by my poor vision.

It's no wonder that HDTV and HD gaming in general is not taking off as quickly as consumer electronics companies hoped -- the benefits are just not that apparent to normal eyes at normal viewing distance.

Jaggies aside, Mario Galaxy 64 is great fun! A very smooth difficulty curve, and gorgeous graphics. Right now I'm working my way through the candy level. (I have seven stars.)

Had brunch at Salty's

2007-11-21T12:34:00.000-08:00

I had a very nice birthday brunch at Salty's on Alki.

Here's a variety of different ways of linking to Salty's on Google Maps:

Search Result
Search Result with traffic

A place that isn't Salty's at all

My initial Wii impressions

2007-11-12T03:34:00.001-08:00

I finally got a Nintendo Wii this weekend. Wii's are in fairly short supply right now, so I couldn't find one at a reasonable price on-line. If you live in the Seattle area, here's my Wii-finding tip: Fred Meyer stores get deliveries on Wednesdays, Fridays, and Sundays, meaning that calling a Fred Meyer store at 7am on Sunday morning to check if they received a new shipment is a good way to find a Wii.

The total cost, with tax, an extra controller, and a component video cable was around $350.

I've got Wii Sports, Wii Play, and will be picking up Mario Galaxy this week. The primary users will probably be my kids, although I am very interested in trying out Mario Galaxy.

As a former Xbox 360 developer, I couldn't help comparing the Wii to the Xbox 360. So far I give the Wii high marks for:

It's small and quiet.
It starts up quickly.
The dashboard UI is very clean and pleasant.
The low-res (480p component) graphics are quite good. I did occasionally see jaggies, for example on the edges of the bowling pins during close-ups in Wii bowling. But the Wii encourages you to play fairly far away from the screen, which masks the lower resolution.
The Wii remotes are great! I love the new gesture "verbs" that are available for game play, and I found it much easier to enter text with the Wii than with an Xbox controller.
The TV station metaphor for the top-level UI is a good metaphor. It makes it easy to take in the available options at a glance. And the Wii remote makes it low-effort to pick the channel you want.
Having built-in wireless was a nice touch.
The Mii avatars are pure genius. Both the fun of designing them and then having them appear in the sports-style games. This is something that the other consoles should copy, and I'm surprised they haven't. Maybe it's patented in some way that makes it difficult to copy.
I thought it was a nice touch that I could name my console, but I didn't see the name used anywhere.
My two three-year-old daughters were strongly attracted to the Wii dashboard and games' graphics and sounds, saying things like "pretty!" and "I like it!" They never said this about the Xbox 360 dashboard or games.
My five-year-old son really got into acting out the moves in the baseball game. And he has not yet played real-world baseball. It will be interesting to see how he does when he starts playing real-world baseball next spring.
The UI of the Wii online store is very good. The Mario themed downloading bar is pure genius -- you know you have a good UI when people _enjoy_ watching the download progress bar.

Some things I didn't like about the Wii:

The UI for pairing a second wireless controller to the console was hard to discover. (I will give Nintendo big props for pre-pairing the in-the-box controller with the console. I'm sure that adds cost to manufacturing, but it makes for a great out-of-box experience.)
The network connection UI gave very little feedback on why the network connection failed. When you test network connectivity you get a 20 second "testing" animation, followed by a cryptic five-digit error code. I had to make two changes to my router configuration to get networking to work. I would have preferred the Xbox 360's UI, that gives more step-by-step information about network connectivity issues.
My three-year-olds can't handle the Wii controller very well. There are too many buttons to accidentally press, and the required gestures are too complicated for them.
No downloadable games demos. And very few downloadable games at all.
The walled-garden Internet channels are pretty weak, especially the Everybody Votes channel.
Not many current or upcoming games that I want to play. After Mario Galaxy, I don't know what my next purchase will be. Luckily, the current games should keep my kids happy for quite a while. (My son's been working his way through Cloning Clyde on Xbox 360 for the past year, I can only imagine how much fun he's going to have with Mario Galaxy!)

In conclusion, I'd have to rate the Wii as a much better "family" console than either the Xbox 360 or the PS3. And by family I mean "small children". I'm lucky that I like the Wii's UI and game style, because I have a feeling I'll be hearing and seeing a lot of it over the next few years. As for my trusty 360, I suspect it will be mostly relegated to "Media Center Extender" status. (Although I am definitely looking forward to Alan Wake and I have high hopes for the next Banjo game. And I might get "The Orange Box" -- Portal and Team Fortress 2 look like a lot of fun.)