Hurry up, someone is waiting on you for that

The title of this post is from a fortune cookie I received a few years ago. I keep it on my desk at work to remind me not to waste time.

So what does this have to do with this blog? Well, now that I have a nice high resolution graphical display for my Game of Life program I’d like to be able to have runs with large numbers of cells. To some degree I can. Using the time command in a Linux terminal (time python yourprogram.py) with a Core i7 processor for 500 iterations I measured the following times for each run with no display and no sleep time between iterations:

100 cells x 100 cells =  15 seconds
250 cells x 250 cells =  92 seconds
300 cells x 300 cells = 151 seconds
500 cells x 500 cells = 393 seconds

Not bad but not exactly what I had in mind for an Autoverse. So how can I make it faster? The first thing to do is find out why it’s slow. For that we need to profile the code and see where it spends most of its time. Fortunately there are some tools to make it simple.

cProfile is a profiler that watches the code while it’s running and measures how long it spends in different areas.

$ python -m cProfile -o output.file gol.py

This results in a file that can be read using the pstats method

$ python
>>> import pstats
>>> p = pstats.Stats('output.file')

some things you can do with it then:

>>> p.strip_dirs().sort_stats(-1).print_stats()

strips out all the directory information and prints the results.
You can also sort by the total time and print out the top 10 time suckers:

>>> p.sort_stats('cumulative').print_stats(10)

What’s really nice though is to use Gprof2Dot to get a graph of the data.

$ python gprof2dot.py -f pstats output.file | dot -Tpng -o output.png

This is what it gave me (click to enlarge):

No great surprises here. The most time is spent in the gol_defs updateState function indexing the neighbors to see who’s alive and who’s dead. For a 500 cell x 500 cell grid run for 50 cycles this is done approximately 200 million times. 35% of the execution time is spent here. Seems like a good place to start.