December 30, 2004

The Ramble Chronicles: Efficient Matrices

This post concerns serious low-level software geekery; if you're interested in how Ramble develops as a game, but not in the underlying software, you can safely skip it.

I'm implementing Ramble in Tcl/Tk for several reasons. It's my favorite language; I can accomplish things in moments in Tcl that would take me hours in C. It's got a cross-platform GUI toolkit; I'm developing Ramble on an Apple Macintosh, but it should run just fine on a Windows PC or a Linux box--and that means that if I can switch to a different platform (as I did a couple of years ago, when I bought the Mac PowerBook on which I'm typing at the moment) without throwing away my personal programming projects.

On the other hand, Tcl is slow compared to C, and certain aspects of a game like Ramble--generating random levels, for example--are computationally intensive. That means that I can't ignore efficiency when designing my internal algorithms and data structures.

The most basic data structure in a tile-based game is the matrix of tiles. Almost every algorithm in the game operates on that matrix somehow, so it needs to be efficient. Now Tcl, like other scripting languages (Perl, Awk, etc.) doesn't have matrices as such; what it has are hash tables, sometimes called associative arrays. Each index in an associative array is a string used as a hash key. It's easy to represent a rectangular matrix using an associative array; here's an example that creates a 4*4 multiplication table:

for {set i 1} {$i <= 4} {incr i} {
    for {set j 1} {$j <= 4} {incr j} {
        set matrix($i,$j) [expr {$i*$j}]
    }
}

puts "3*4 = $matrix(3,4)"

The important thing to note is that although it looks like I'm accessing a two-dimensional matrix, I'm not. It's really a one-dimensional array with keys that look like "1,1", "1,2", and so on. This had certain advantages, and it's the usual Tcl solution. But it's not as fast as it could be.

The other important Tcl data structure is the list. In some languages with a built-in list type, lists are implemented as linked lists; in Tcl, however, the list is in fact a fast one-dimensional vector--it's roughly equivalent to a one-dimensional C array, except that it's automatically extensible. As a result, accessing a list element is much faster than accessing an associate array element. And because a list element can be anything, including another list, it's possible to implement a matrix as a list of lists--or, really, a vector of vectors. Which, as it happens, is more or less how it's done in C. For example:

set matrix {matrix {row 0 0 0 0}
                   {row 0 0 0 0}
                   {row 0 0 0 0}
                   {row 0 0 0 0}}

for {set i 1} {$i <= 4} {incr i} {
    for {set j 1} {$j <= 4} {incr j} {
        lset matrix $i $j [expr {$i*$j}]
    }
}

puts "3*4 = [lindex $matrix 3 4]"

Here we see that the variable matrix contains a list consisting of the word "matrix" and four rows, each of which is a list containing the word "row" and four numeric values. If you know Tcl, you might be wondering why I didn't represent the matrix without the extra words, e.g.,

set matrix {{0 0 0 0}
            {0 0 0 0}
            {0 0 0 0}
            {0 0 0 0}}

Tcl lists are indexed starting at 0; but mathematically, matrix rows and columns are numbered 1 to M and 1 to N respectively. I've gone back and forth on this several times (as a C programmer, zero-based arrays are deeply engrained in my psyche), but on the whole, I've decided that starting at 1 is better, at least for my uses. The words "matrix" and "row" occupy the zero slot, which means that [lindex $matrix 1 1] gets the correct item.

In addition, it makes arrays easier to read when printed out, without requiring any special formatting.

I'll admit that the lset/lindex syntax is a bit clunky compared with normal array notation; but in my benchmarks it's at least an order of magnitude faster than the associative array implementation. The tricky bit is creating matrices to begin with. It's easy enough to type them in, as I did above, when the matrix is small, but it's much less pleasant when the matrix is large. What we need is a helper function. Here's the one I use:

proc ::matrix::new {m n args} {
    array set opts {
        -init {}
        -type matrix
    }
    array set opts $args

    set mat $opts(-type)
    set val $opts(-init)

    for {set i 1} {$i <= $m} {incr i} {
        set row {row}
        for {set j 1} {$j <= $n} {incr j} {
            lappend row $val
        }
        lappend mat $row
    }

    return $mat
}

set matrix [matrix::new 32 32 -init 0]

The routine ::matrix::new creates a new matrix of arbitrary size. By default, each element of the matrix is just the empty string; in the example, I use the -init option to specify the initial value. If I'm creating a matrix of a particular type, i.e., to hold a particular kind of data, I can use the -type option; this specifies a string to replace the word "matrix" in the top-level list.

Here are some additional matrix utilities: mrows returns the number of rows in the matrix, and mcols returns the number of columns:

proc ::matrix::mrows {matrix} {
    expr {[llength $matrix] - 1}
}

proc ::matrix::mcols {matrix} {
    expr {[llength [lindex $matrix 1]] - 1}
}

I don't have any special commands for setting and getting the elements in a matrix; lindex and lset do the job perfectly well. Anything I'd define would just be slower.

And speaking of slower, I hate the Tcl syntax for looping over the elements of an array. It's ugly, and cumbersome to type. Tcl's an outstanding language, though, and one its many graces is that you can define your own syntax when you need to. I spent a fair amount of time at this, trying to come up with something more concise, and there were a number of solutions I liked quite a bit. Here I define a simpler version of for that just loops from one integer to another:

fori i 1 4 {
    fori j 1 4 {
        # Do something with $i, $j
    }
}

Here I try a combined loop: I specify the limits for i and j both, and it does both loops:

forij i 1 4 j 1 4 {
    # Do something with $i, $j
}

Here I use a function that returns a list of integers, and iterate over the list. I wrote the function so that it caches the list, and doesn't need to create a new one each time:

foreach i [range 1 4] {
    foreach j [range 1 4] {
        # Do something with $i, $j
    }
}

However, all of these solutions had one major thing in common--they were all a lot slower than the normal Tcl syntax I use above. I think something like fori would be a nice addition to Tcl...but it would have to be implemented as a C extension.

Posted by Will Duquette at December 30, 2004 04:39 PM

Michael A. Cleverly said:

Will,

Great stuff! Regarding your fori implementation that is a lot slower--how much slower is it?

I've played around a bit with various fori implementations. My initial (naive) approach was almost 10x slower than [for] itself. I've improved to where I've now got a version that only takes 1.5x as long (on a range of 1-1000 my [fori] takes 1514 microseconds compared to 1007 microseconds for [for]).

Happy New Year.

Will Duquette said:

Hey, Michael! Happy New Year yourself.

I've tried a couple of fori approaches, and both have been a little over 10x slower than the standard for loop on my benchmark, which is iterating over and summing the elements of a 4*4 matrix (as defined in this post). I'm very curious to see your implementation.