Not Even My Wife Reads This

At PyCon, Maciej from the PyPy team asked for programs that the PyPy JIT did a really bad job on.

I have a directory full of over 200 little Python programs that attempt to solve Project Euler math problems. Only 186 of them get the right answer, and fewer of them run in a reasonable period of time. But this led me to concoct a quick benchmark comparing the Python implementations installed on my computer: CPython, CPython with Psyco, Unladen Swallow, and PyPy. (I haven't tested them with Jython or IronPython yet. Maybe someday.)

Basically, I just run all of euler*.py under four different Python implementations, record how long it took each implementation to run each program, and throw out the results for any programs that didn't work in all four versions of Python, or that didn't finish in 60 seconds or less on all of them.

Here are the results, for recent svn checkouts of PyPy and Unladen, CPython 2.6.4, and CPython 2.6.4 plus Psyco 1.6. (Don't get too obsessed with the exact results, since it's just a private benchmark and most of the code is unpublished. This is just background for the real information at the bottom of the post.)

So all the JITs are faster than CPython for this set of programs, but none is twice as fast. PyPy has the most wins, but Psyco has the lowest total time.

While PyPy does very well overall, it's an order of magnitude slower than all the others on 3 of the programs: 14, 135, and 174. If PyPy fixed whatever made those ones slow, it would definitely be the overall leader.

Here's my euler14.py

#!/usr/bin/env python

"""Project Euler, problem 14

The following iterative sequence is defined for the set of positive integers:

n -> n / 2 (n is even)
n -> 3n + 1 (n is odd)

Which starting number, under one million, produces the longest chain?
"""

def next_num(num):
    if num & 1:
        return 3 * num + 1
    else:
        return num // 2

MAX_NUM = 1000000

lengths = {1: 0}

def series_length(num):
    global lengths
    if num in lengths:
        return lengths[num]
    else:
        num2 = next_num(num)
        result = 1 + series_length(num2)
        lengths[num] = result
        return result

def main():
    num_with_max_length = 1
    max_length = 0
    for ii in range(1, MAX_NUM):
        length = series_length(ii)
        if length > max_length:
            max_length = length
            num_with_max_length = ii
    print num_with_max_length, max_length

if __name__ == "__main__":
    main()

Why is 14 so slow? My guess would be that it's because it heavily mutates a global dictionary.

Here's euler135.py:

#!/usr/bin/env python

"""Project Euler, problem 135

Given the positive integers, x, y, and z, are consecutive terms of an
arithmetic progression, the least value of the positive integer, n, for which
the equation, x**2 - y**2 - z**2 = n, has exactly two solutions is n = 27:

34**2 - 27**2 - 20**2 = 12**2 - 9**2 - 6**2 = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?
"""

"""
x**2 - y**2 - z**2 = n
y = z + d
x = z + 2 * d
d > 0
z > 0
(z + 2 d) ** 2 - (z + d) ** 2 - z ** 2 = n
(z**2 + 4dz + 4d**2) - (z**2 + 2dz + d**2) - z**2 = n
z**2 + 4dz + 4d**2 -z**2 - 2dz - d**2 - z**2 = n
-z**2 + 2dz + 3d**2 - n = 0
a = -1
b = 2d
c = 3d**2 - n
z = (-b +/- sqrt(b**2-4ac)) / 2a
z = (-2d +/- sqrt(4d**2+4(3d**2-n))) / -2
z = (-2d +/- sqrt(4d**2+12d**2-4n))) / -2
z = (-2d +/- sqrt(16d**2-4n))) / -2
z = (-2d +/- 2 sqrt(4d**2 - n)) / -2
z = (-d +/-  sqrt(4d**2 - n)) / -1
z = d +/- sqrt(4d**2 - n)
4d**2 - n >= 0
n <= 4d**2
4d**2 - n is a perfect square
"""

def main():
    limit = 1000000
    counts = limit * [0]
    for d in range(1, limit / 4 + 1):
        d24 = d ** 2 * 4
        if d24 < limit:
            start = 1
            counts[d24] += 1
        else:
            start = int((d24 - limit) ** 0.5)
        if start < 1:
            start = 1
        for root in xrange(start, 2 * d):
            n = d24 - root ** 2
            if n <= 0:
                break
            if n < limit:
                z = root + d
                y = z + d
                x = y + d
                #print "n", n, "d", d, "root", root, "x", x, "y", y, "z", z
                #assert x**2 - y**2 - z**2 == n
                counts[n] += 1
                if d > root:
                    z = d - root
                    y = z + d
                    x = y + d
                    #print "n", n, "d", d, "root", root, "x", x, "y", y, "z", z
                    #assert x**2 - y**2 - z**2 == n
                    counts[n] += 1
    total = 0
    assert counts[0] == 0
    for val in counts:
        if val == 10:
            total += 1
    print total

if __name__ == "__main__":
    main()

Why is PyPy so slow on this one? Well, maybe it's because all the work happens in one function, if PyPy doesn't JIT a function while it's still running. Or maybe it's the list with a million elements in it.

Finally, euler174.py:

#!/usr/bin/env python

"""Project Euler, problem 174

We shall define a square lamina to be a square outline with a square "hole" so
that the shape possesses vertical and horizontal symmetry.

Given eight tiles it is possible to form a lamina in only one way: 3x3 square
with a 1x1 hole in the middle. However, using thirty-two tiles it is possible
to form two distinct laminae.

If t represents the number of tiles used, we shall say that t = 8 is type L(1)
and t = 32 is type L(2).

Let N(n) be the number of t <= 1000000 such that t is type L(n); for example,
N(15) = 832.

What is sum(N(n)) for 1 <= n <= 10?
"""

from math import ceil
from collections import defaultdict

def gen_laminae(limit):
    """Yield laminae with up to limit squares, as tuples
    (outer, inner, squares)"""
    for outer in range(3, limit // 4 + 2):
        if outer & 1:
            min_min_inner = 1
        else:
            min_min_inner = 2
        min_inner_squared = outer ** 2 - limit
        if min_inner_squared < 0:
            min_inner = min_min_inner
        else:
            min_inner = max(min_min_inner, int(ceil(min_inner_squared ** 0.5)))
            if outer & 1 != min_inner & 1:
                min_inner += 1
        outer_squared = outer ** 2
        for inner in range(min_inner, outer - 1, 2):
            squares = outer_squared - inner ** 2
            yield (outer, inner, squares)

def main():
    squares_to_count = defaultdict(int)
    for (outer, inner, squares) in gen_laminae(1000000):
        squares_to_count[squares] += 1
    histogram = defaultdict(int)
    for val in squares_to_count.values():
        if val <= 10:
            histogram[val] += 1
    print sum(histogram.values())

if __name__ == "__main__":
    main()

Perhaps this one is slow because it heavily uses generators and a defaultdict?

Anyway, I'm not claiming any of these are great programs. I know others have much better solutions to these problems. And this code is certainly not optimized for PyPy. They're just examples of small programs that were originally written for CPython, and do work correctly on PyPy, but happen to be much slower on PyPy than on CPython.

Again, note these are the exceptions not the rule. PyPy runs most pure-Python code great. Just not these three programs.

PyCon was in Atlanta this year, which got me away from the record snow in the DC area.  Yay for winter conferences being in warm places.  (Nothing against Chicago, but Chicago conferences should be in the summer.)

Attendance was about 1100, a little more than last year, but nothing like the crazy growth PyCon saw when the economy was strong. I think that Python is still growing but travel and recruiting budgets are down.

The best talk I attended was Raymond Hettinger's.  It was about using the right container classes to solve computationally expensive problems.  He pointed out that every ordered dict implementation except the one he just added to Python 3.1 had O(n) deletes due to using a list for storing the order, while his had O(1) deletes because he used a linked list with a dict index.  I hung my head in shame because I've written odict twice (once at a former employer, again from scratch for Slugathon) and done it "wrong" both times.

The most useful thing I attended was the Twisted Open Space.   Because my employer really wants IPv6 in Twisted, and I've submitted a patch but not had it accepted because of reverse compatibility concerns.  Actually talking to most of the core Twisted team at once in person really helped clarify what we need to do to break the logjam and get the patch moving forward again.  That ten minutes probably justified the cost of sending me to PyCon this year.  (And I wish I could go to the sprints and maybe actually get this change into Twisted this week, but I can't.  Next year I really want to go to at least a couple of sprint days.)

Rackspace Cloud was there as a sponsor with a booth, which reminded me that I should have blogged about my experience using Rackspace Cloud.  Basically, they stood up a virtual small Ubuntu (they have other choices too) server for me in about 5 minutes, for about $12 per month (plus bandwidth, more money for more memory), and it just stinking worked.  I've since turned it off because Slugathon isn't done yet so I don't really need a dedicated game server yet, but I'll definitely be back when it is.  The only negative is that there's no way to setup a cap at which the server turns itself off, so if you get Slashdotted or DOS attacked you may get a high bandwidth bill.

Negatives:

Airline travel sucks.  You already know this.

Guido's keynote was just taking questions via Twitter, and the signal-to-noise ratio was awful.  (Yes, I'm an old Angry Unix Guy.  Get off my lawn and take your Twitter and your Facebook and your iPhone with you.)  If Guido doesn't want to do a real keynote, that's fine; why not let someone else have the slot?

I'm no longer in favor of invited talks, because one of them was just content-free pattern metababble that never would have been accepted if the speaker had had to do a proposal.  (But, in fairness, all the other invited talks I attended were excellent.)

There were several talks that I really enjoyed and thought were great fun, but where I didn't really learn anything.  So they validated my existing opinions but didn't stretch my brain at all.  (Larry Hastings actually pointed out before his talk about micro-optimizations that it was just nerd porn and that it would be entertaining but nobody would learn much.  I applaud him for his honesty.)  I guess that's natural when you've been doing something for a long time and have attended the same conference a bunch of times.  I need to attend fewer talks and spend more time just talking to people.

The board game social wasn't as awesome as last year because there wasn't a huge pile of games to pick from.  (I think last year a game store donated some games, and you can't expect that to happen every year.)  So I will bring at least one game next year.

My 7-year-old laptop lost its WiFi connection whenever things got crowded.  The networking people do their best, but 1000 laptops crammed into a small area means the newer stronger ruder WiFi cards will crowd out the older weaker more-polite ones, no matter how many access points there are.  I plugged into a switch when I could, and lived without WiFi when I couldn't.  My laptop is heavy and has poor battery life anyway, so I think it's time to retire it in favor of a netbook.

I've been working on Slugathon on-and-off (but mostly off) since 2003. The bare minimum feature set that I consider necessary to do a serious alpha release is almost done. (Release early, release often; but if you release before you actually do anything useful you might just leave a bad first impression and scare off your potential users.) So I've been thinking about installers, and portability to MacOS and Windows, and whether my current hosting solution (svn and Trac provided for free to open source Python projects by WebFaction; thanks WebFaction) would cut it when I had users and possibly more contributors.

I like Trac, a lot. I now strongly prefer Git to Subversion. You can use Git and Trac together with the GitTracPlugin, but it's hard to find a host that has it installed. (SourceForge, for example, now offers both Git and Trac, but not together.) So I decided to go with github. They're the most popular Git host, their paid hosting business seems to be solid enough that they're unlikely to go away anytime soon, they offer free hosting for open source projects, and they have a wiki and an issue tracker.

So this morning I experimentally moved everything from Subversion+Trac to github. I've administered both Svn/Trac and Git/Trac installations at work, so I knew how to do this on a local machine where I had control, but doing things locally is different from doing things on a remote hosting service.

Here's what I did on github:

1. Signed up for an account. (I've poked around github plenty of times, and cloned other people's repositories there to my local box, but I never needed to register until I actually wanted to move my own repository there. Which is exactly the way it should work.)

2. Uploaded an ssh key. I already know ssh so it was just a matter of posting ~/.ssh/id_rsa.pub into a web form.

3. Re-cloned my Subversion repository to my local box, using git-svn, using the –no-metadata option to remove all the ugly "git-svn-id" blobs in the log. I'd done this before when we switched from Subversion to Git at work, but I didn't remember the exact syntax. Luckily it was right there on Github's help page so I didn't even need to check a Git man page.

4. Uploaded my new local Git repository to Github.

5. Realized that I'd forgotten to use the –authors-file option to convert the author metadata from Subversion format (bare username) to Git format (firstname lastname email). Oops, this was also on github's help page but I'd been in too much of a hurry. I poked around github until I found out how to delete a repository, deleted the one I'd just made, redid the git-svn clone with the missing option, and re-uploaded my repository.

6. Basically cut-and-pasted my wiki pages (there were only 8 of them) from Trac to Github's wiki. I did a little tweaking to convert formatting from Trac format to the Textile format that Github uses, but didn't obsess about getting every little format perfect. One thing that github's wiki doesn't support well is images; they let you link to external images, but not post attachments directly into the wiki. So for now the thumbnail screenshots are there, but they don't link to the larger versions.

7. Manually ported all my Trac tickets to github issues. I had 62 tickets, 30 closed and 32 open. Both Trac and the github issue tracker share the same #number format for referring to issues, and I mention ticket numbers inside commit messages, so I thought it was necessary to add all the already-closed issues for historical reasons. I also changed any references to Subversion commit numbers to Git commit ids inside the issues. This was an annoying data entry task, but with only 62 tickets it was faster to just do it by hand than to write some awesome Trac to github conversion script. (Which would require either cooperation from github, or advanced web scraping, since github is a rather fancy web site with JavaScript everywhere.)

8. Changed Slugathon's SourceForge page to point at github rather than WebFaction. (I'm keeping a SourceForge presence for the project because they offer useful things that Github does not, like project mailing lists. Also, if SourceForge ever integrates Git and Trac and I become dissatisfied with Github's new and fairly minimal issue tracker, I might move everything to SourceForge.)

9. Changed the main wiki page at WebFaction to point to github, too. (I will eventually ask WebFaction to delete the project, but first I want to make sure that the move was a good idea. And give Google enough time to cache the version of the page that shows the redirect to github, so people don't think the project just disappeared.)

10. Created a static web page using the instructions at pages.github.com. This feels somewhat redundant with the github wiki, but it gave me a place to park my images.

My conclusion so far: I still like Git a lot more than Subversion. I like github's wiki and issue tracker less than Trac, but they seem to be good enough.

I have a TrendNet TE100-P1P print server. It's a little $30 gizmo with an Ethernet jack on one end and a parallel printer port on the other, so that you can turn a printer into a network printer without hanging it off a computer. Bought it because my new motherboard didn't have a parallel port. The other benefit is that now the printer works when my main desktop computer is off.

Anyway, we had a power failure, and the printer stopped working. No "lexmark" found in local DNS. No DHCP lease for the TrendNet gizmo.

The gizmo was still there, but I couldn't find it. There's no UI on the device, just the network jack. So I wrote a little script (below) to portscan my LAN for anything that answered on port 631. That found it.

Turns out that when the power goes out, the print server reconfigures its network settings from DHCP to fixed. It keeps its last network settings, but the DHCP / DNS server no longer has any record of them, so you can't find it unless you remember what its last IP was.

Here's the script. Because I had 700+ addresses to check, and it sometimes takes a few seconds for a failed socket connection to timeout, I used 250 threads to make it faster. (I initally tried using a separate thread for each IP, but I hit an OS limit at 255 threads, and decided to use a fixed-size pool and two shared work queues.)

#!/usr/bin/env python

"""Hunting for the TrendNet print server"""

import socket
import threading
import Queue

socket.setdefaulttimeout(5)

port = 631
num_threads = 250

class ConnectThread(threading.Thread):
    def __init__(self, in_queue, out_queue):
        threading.Thread.__init__(self)
        self.in_queue = in_queue
        self.out_queue = out_queue
        self.setDaemon(True)

    def run(self):
        while True:
            ip = self.in_queue.get()
            try:
                sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
                sock.connect((ip, port))
            except socket.error:
                self.out_queue.put((ip, False))
            else:
                self.out_queue.put((ip, True))
            self.in_queue.task_done()

def main():
    job_queue = Queue.Queue()
    result_queue = Queue.Queue()
    count = 0
    for net in range(3):
        for addr in range(1, 255 + 1):
            ip = "192.168.%d.%d" % (net, addr)
            count += 1
            job_queue.put(ip)
    for unused in xrange(num_threads):
        ConnectThread(job_queue, result_queue).start()
    job_queue.join()

    for unused in xrange(count):
        ip, status = result_queue.get()
        if status:
            print ip

if __name__ == "__main__":
    main()

Someone on the PyGTK mailing list just asked which is faster for drawing rectangles, GDK or Cairo.

I wasn't sure, so I wrote a silly little test program.  Note that it's not quite apples-to-apples as the Cairo rectangles have variable transparency while the GDK rectangles are opaque.

On my box, running Gentoo Linux and the latest stable versions of everything, the Cairo version draws 500 rectangles in about 0.01 to 0.03 seconds, while the GDK version takes about 0.13 to 0.14 seconds.  So Cairo is faster.

To run this, just cut-and-paste into an editor window, save the file as rectangles.py, and run "python rectangles.py"

#!/usr/bin/env python

"""GTK rectangle drawing speed test, GDK vs. Cairo

David Ripton 2008-12-03
MIT license
"""

import time
import random

import gtk

NUM_RECTS = 500

handle_id = None

def main():
    window = gtk.Window()
    window.connect("destroy", gtk.main_quit)
    window.set_default_size(800, 600)
    vbox = gtk.VBox()
    window.add(vbox)
    area = gtk.DrawingArea()
    vbox.pack_start(area)
    gdk_button = gtk.Button("GDK")
    gdk_button.connect("clicked", on_gdk_button_clicked, area)
    vbox.pack_start(gdk_button, expand=False)
    cairo_button = gtk.Button("Cairo")
    cairo_button.connect("clicked", on_cairo_button_clicked, area)
    vbox.pack_start(cairo_button, expand=False)
    window.show_all()
    gtk.main()

def on_gdk_button_clicked(button, area):
    global handle_id
    if handle_id is not None:
        area.disconnect(handle_id)
    handle_id = area.connect("expose-event", on_area_exposed_gdk)
    area.queue_draw()

def on_cairo_button_clicked(button, area):
    global handle_id
    if handle_id is not None:
        area.disconnect(handle_id)
    handle_id = area.connect("expose-event", on_area_exposed_cairo)
    area.queue_draw()

def on_area_exposed_gdk(area, event):
    t0 = time.time()
    width, height = area.window.get_size()
    colormap = area.get_colormap()
    gc = area.get_style().fg_gc[gtk.STATE_NORMAL]
    for ii in xrange(NUM_RECTS):
        r = random.randrange(0, 65535 + 1)
        g = random.randrange(0, 65535 + 1)
        b = random.randrange(0, 65535 + 1)
        gc.foreground = colormap.alloc_color(r, g, b)
        x = random.randrange(0, width)
        y = random.randrange(0, height)
        w = random.randrange(0, width - x)
        h = random.randrange(0, height - y)
        area.window.draw_rectangle(gc, True, x, y, w, h)
    t1 = time.time()
    print "gdk drew %d rectangles in %f seconds" % (NUM_RECTS, t1-t0)

def on_area_exposed_cairo(area, event):
    t0 = time.time()
    cr = area.window.cairo_create()
    width, height = area.window.get_size()
    for ii in xrange(NUM_RECTS):
        r = random.random()
        g = random.random()
        b = random.random()
        a = random.random()
        cr.set_source_rgba(r, g, b, a)
        x = random.randrange(0, width)
        y = random.randrange(0, height)
        w = random.randrange(0, width - x)
        h = random.randrange(0, height - y)
        cr.rectangle(x, y, w, h)
        cr.fill()
    t1 = time.time()
    print "cairo drew %d rectangles in %f seconds" % (NUM_RECTS, t1-t0)

if __name__ == "__main__":
    main()

Rant: It is way too hard to post code with Wordpress. First I tried the "code" button, but all my indentation was destroyed (bad for any code, fatal for Python). Then I tried the "b-quote" button; same effect. Then I switched to HTML mode and hand-inserted a "pre" tag, which preserved the indentation. But Wordpress then proceded to vandalize my code with "smart" quotes. (Have you ever seen anything with "smart" in its name that actually was?) Luckily it was simple to find and install the wpuntexturize plugin, a few lines of PHP that eradicate Moron Quotes. But why the hell are they there in the first place, let alone enabled by default, let alone enabled by default inside a "pre" tag?

Stephen Waterbury added a WxPython client to my AmpChat example program. (Mentioned earlier in this post.)

His Mercurial repository is here.

This is still just example code, but now it's an example of multiple things:

• how to use Twisted AMP
• how to use Twisted with PyGTK (trivial because gtk2reactor rocks)
• how to make WxPython's mainloop run in parallel with Twisted's using threads
• how to write the same simple GUI program in both PyGTK and WxPython
• how to use Mercurial to contribute to a project without commit rights in the original repo

Anyone want to contribute a PyQT or Tk version?

I've been running Python 2.6 (released October 1) as the only Python on my Gentoo desktop for a few weeks. In most ways, it's the Best Python Ever. It's got per-user site-packages. It's got the multiprocessing module so you can use lots of CPU cores without thinking too hard. It's got abstract base classes. It's got binary literals. It's got ast.literal_eval, so you can safely evaluate static dicts without worrying about security. It's got other cool stuff that you can read about here.

But it constantly spews annoying deprecation warnings like this:

dripton@al ~/src/Slugathon/slugathon $ ./Connect.py
/usr/lib/python2.6/site-packages/twisted/internet/_sslverify.py:4: DeprecationWarning: the md5 module is deprecated; use hashlib instead
import itertools, md5


Or this:
dripton@al ~/src/projecteuler $ py.test test_euler86.py
===================================== test process starts =====================================
executable: /usr/bin/python (2.6.0-final-0)
/usr/lib/python2.6/site-packages/py/process/cmdexec.py:27: DeprecationWarning: The popen2 module is deprecated. Use the subprocess module.
import popen2
using py lib: /usr/lib/python2.6/site-packages/py


or even this:
dripton@al ~/src/Colossus-git/Colossus $ ant
/usr/lib/python2.6/site-packages/java_config_2/EnvironmentManager.py:15: DeprecationWarning: the sets module is deprecated
from sets import Set
/usr/lib/python2.6/site-packages/java_config_2/EnvironmentManager.py:15: DeprecationWarning: the sets module is deprecated
from sets import Set
/usr/lib/python2.6/site-packages/java_config_2/EnvironmentManager.py:15: DeprecationWarning: the sets module is deprecated
from sets import Set
/usr/lib/python2.6/site-packages/java_config_2/EnvironmentManager.py:15: DeprecationWarning: the sets module is deprecated
from sets import Set
Buildfile: build.xml
...
BUILD SUCCESSFUL
Total time: 5 seconds


If you're reading carefully, you'll notice one important fact: none of those warnings were in my code. I imported twisted, and got warnings because twisted used md5. I ran py.test, and got warnings because py.test used popen2. I ran ant, which last time I checked was a Java program, and got warnings because some Python script wrapped around the Java used sets.Set.

Of course, there's a good reason for these warnings. Python 3.0 is coming, and many of the features that trigger deprecation warnings in 2.6 will be gone in 3.0. (Well, no important functionality will truly go away, but where there are two ways to do something, sometimes they'll pick one and axe the other.) This is useful and important, but will cause pain. And the pain has already started.

Of course, I know how to silence the warnings. Temporarily:
dripton@al ~/src/Slugathon/slugathon $ python -Wignore Connect.py

Or permanently:
$ sudo vim /usr/lib/python2.6/sets.py
#import warnings
#warnings.warn("the sets module is deprecated", DeprecationWarning,
# stacklevel=2)


But it's annoying to have to do that. Especially when you didn't even realize you were running a Python program, as in the ant example above.

I predict lots of whining about this when 2.6 goes more mainstream (say, when it becomes default in Ubuntu).

I started Colossus in December 1997, almost 11 years ago. Yesterday I turned over leadership of the project to Clemens Katzer. That's a long time to maintain a software project, and it feels weird to me that I finally quit.

Colossus was my first large game project, my first large Java program, my first large GUI program, my first experience working on a complex game AI, and my first time managing a significant multi-programmer software project. Somehow it worked out pretty well, for the first few years. We had a pretty full-featured, stable Titan game, with somewhat dumb but working AI, and support for lots of cool variants. We had a rotating team of up to half a dozen developers at a time working on the game, and it was fun.

But then I added network play, and I didn't do a very good job. At the time there were no Java remote method libraries that had the features we needed, so I wrote everything myself with a simple string socket protocol, with lots of receiver threads. But I wasn't rigorous enough with thread synchronization, which meant walking the line between deadlock and corrupted game data. And gaining acceptable performance meant that a lot of logic that existed on the server side needed to be reproduced on the client side, but excessive coupling in the code base meant this couldn't be done cleanly and a lot of code got duplicated. I tried and tried to fix the mess, but couldn't put Humpty-Dumpty together again.

I finally decided to start over, in a better programming language (Python), with a better networking framework (Twisted), with a better overall design paradigm (game events flowing from the server to the client, using the Observer pattern to reduce coupling and allow complete reuse of the core game logic between the client and server) and with safe sane single-threaded code. Thus was born Slugathon. Unfortunately, as a new father I didn't have nearly as much free time as I did back when I started Colossus, and so Slugathon still isn't finished.

With Slugathon unfinished I felt obligated to keep maintaining Colossus, but I didn't really have my heart in it. I figured my job was to keep the project alive until a successor showed up to take it over. We had several guys on the team who were technically qualified to take over, but none seemed likely to put in the necessary amount of time on a consistent basis. Then Clemens joined, and not only submitted code for his pet features (the fun part that everyone wants to do) but started watching the bug tracker like a hawk, and talking to users about their bugs, and making special test builds so that users could test that their obscure hard-to-reproduce bugs were fixed, and adding documentation of which features went into which releases, and all the other not-fun crap that 90% of small volunteer open source projects can't find anyone to do. Around the same time, longtime contributor Peter Becker did a giant refactoring that reduced the amount of code duplication from disgusting to merely gross. And Clemens switched the server side from listener threads to NIO, reducing the total thread count from insane to merely scary.

Which meant I was no longer needed on Colossus. So I'm committing to releasing a stable, network-playable version of Slugathon by the end of 2008. And hoping that the Colossus team can continue cleaning up the mess I left them. Hopefully someday soon we'll have two stable networked Titan games instead of zero.

(By the way, I played a couple of four-human 2-AI networked Abyssal6 Colossus games this morning. It was great fun, even though both games had technical difficulties.)

My desktop computer, which runs Gentoo Linux, has a 120 GB drive (used for my / and /boot and swap partitions) and a 480 GB drive (used for /home).  I decided to add another drive for backups.  Ended up with a 720 GB drive, which is bigger than the others combined with room to spare, and only cost me about $100.

(Backing up to another hard drive on the same box is easy, and fast, and protects from a single drive failing, but does not protect against the computer being stolen or the house burning down.  So I still need to push really important stuff, like source code, offsite.)

I mount the new drive as /mnt/backup.  I use rsync to backup everything, minus a few excluded directories, to /mnt/backup/{TIMESTAMP}.  I tell rsync to use hard links when a file is the same as the file in the previous backup.  That way I have a full backup tree per day, but the incremental hard disk space used is only equivalent to the size of the files that actually changed that day.

I control the backup with this Python script (sh or perl would work too, but I like Python), which lives at /usr/local/bin/backup.py:

#!/usr/bin/python

"""Backup most of a filesystem to a backup disk, using rsync."""

import subprocess
import time
import os

SOURCE = "/"
DESTINATION = "/mnt/backup"
EXCLUDES = [
    "/proc",
    "/sys",
    "/lost+found",
    "/mnt",
    "/media",
    "/tmp",
    "/var/tmp",
    "/var/run",
    "/var/lock",
]
RSYNC = "/usr/bin/rsync"

def find_latest_destdir():
    latest = 0
    for fn in os.listdir(DESTINATION):
        if fn.isdigit() and len(fn) == 14:
            timestamp = int(fn)
            latest = max(timestamp, latest)
    if latest:
        return str(latest)
    return None

def main():
    cmd = [RSYNC]
    cmd.append("-ab")
    for exclude in EXCLUDES:
        cmd.append("–exclude=%s" % exclude)
    latest = find_latest_destdir()
    if latest:
        cmd.append("–link-dest=%s" % (os.path.join(DESTINATION, latest)))
    cmd.append(SOURCE)
    timestamp = time.strftime("%Y%m%d%H%M%S")
    cmd.append(os.path.join(DESTINATION, timestamp))
    print cmd
    returncode = subprocess.call(cmd)

if __name__ == "__main__":
    main()

And here's the crontab line that runs it every night at 3 a.m, added with "sudo crontab -e":

0 3  * * *      /usr/local/bin/backup.py

Automated nightly backups are now so easy (thanks to tools like rsync, and the cheapness of hard drives) that there's really no excuse not to do them.

The previous benchmark was too fast, and mostly only measured startup time. Here's a slower one. Project Euler Problem 10

Basically, find the sum of all primes up to a million. Best of 5 runs for each Python version.  Basically the standard Sieve of Eratosthenes in a loop.

python2.4 13.131s
python2.5 12.67s
python2.6 11.517s
python3.0 13.764s
jython2.2.1 11.542s
pypy-c (r56024, translate.py –gc=hybrid –thread targetpypystandalone –faassen –allworkingmodules), 12.774s
python2.5 with psyco: 1.926s
python2.5 using gmpy.is_prime 2.441s
python2.5, psyco, gmpy.is_prime 1.762s

So on this one all the Python versions are pretty close, with a nice steady improvement from 2.4 to 2.5 to 2.6. Jython and pypy are both in the same ballpark.  psyco makes it run about 6 times as fast. Using gmpy's is_prime function (written in C) instead of my Python sieve has a similar result.