20 Jan 2010
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: 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.
18 Jan 2010
An excellent little performance optimization presentation that shows how
important memory layout is for today’s processors:
Pitfalls of Object Oriented Programming
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.)
18 Dec 2009
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.
26 Nov 2009
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.
26 Nov 2009
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.
25 Nov 2009
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
25 Nov 2009
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. :-) )
11 Nov 2009
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
07 Nov 2009
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!
07 Nov 2009
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.