Showing posts from 2010

Asynchronous directory tree walk in node.js

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 .

Getting Old Educational Software to Run on OSX 10.6

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 Mi

Eulogy for a PC

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 pro

An update on my car stereo

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 t

What I did on my Winter Vacation

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.

ICFP 2010 contest is a bust for me

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 o

Writing an Android application in JavaScript and HTML5

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 Androi

Google AI Challenge 2010

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 anoth

Looking at the original BitTorrent client

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

Some details on Xbox Project Natal

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?!

Wow, my Taipei-Torrent post made it to Hacker News and 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 par

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

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 chann

Objects vs. the L2 Cache

An excellent little performance optimization presentation that shows how important memory layout is for today's processors: 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.)