CodeKata

Background

How do you get to be a great musician? It helps to know the theory, and to understand the mechanics of your instrument. It helps to have talent. But ultimately, greatness comes from practicing; applying the theory over and over again, using feedback to get better every time.

How do you get to be an All-Star sports person? Obviously fitness and talent help. But the great athletes spend hours and hours every day, practicing.

But in the software industry we take developers trained in the theory and throw them straight in to the deep-end, working on a project. It’s like taking a group of fit kids and telling them that they have four quarters to beat the Redskins (hey, we manage by objectives, right?). In software we do our practicing on the job, and that’s why we make mistakes on the job. We need to find ways of splitting the practice from the profession. We need practice sessions.

A week or so ago I posted a piece called CodeKata, suggesting that as developers we need to spend more time just practicing: writing throwaway code just to get the experience of writing it. I followed this up with a first exercise, an experiment in supermarket pricing.

Some sequences just keep turning up.

(This is a long one, but it does have a point…)

This all starts with the way RubLog does searching (but it isn’t an article about searching, or about bit twiddling. Trust me). Because I eventually want to use cosine-based comparisons to find similar articles, I build vectors mapping word occurrences to each document in the blog. I basically end up with a set of 1,200-1,500 bits for each document. To implement a basic ranked search, I needed to be able to perform a bitwise AND between each of these vectors and a vector containing the search terms, and then count the number of one-bits in the result.

I had a spare 45 minutes last night (I took Zachary to his karate lesson, but there was no room in the parent’s viewing area), so I thought I’d play with this. First I tried storing the bit vectors different ways: it turns out (to my surprise) that storing them as an Array of Fixnums has almost exactly the same speed as storing them as the bits in a Bignum. (Also, rather pleasingly, changing between the two representations involves altering just two lines of code). Because it marshals far more compactly, I decided to stick with the Bignum.

Then I had fun playing with the bit counting itself. The existing code uses the obvious algorithm:

      max_bit.times { |i| count += word[i] }

Just how slow was this? I wrote a simple testbed that generated one hundred 1,000 bit vectors, each with 20 random bits set, and timed the loop. For all 100, it took about .4s.

Then I tried using the ‘divide-and-conquer’ counting algorithm from chapter 5 of Hacker’s Delight (modified to deal with chunking the Bignum into 30-bit words).

     ((max_bit+29)/30).times do |offset|
       x = (word >> (offset*30)) & 0x3fffffff
       x = x - ((x >> 1) & 0x55555555)
       x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
       x = (x + (x >> 4)) & 0x0f0f0f0f;
       x = x + (x >> 8)
       x = x + (x >> 16)
       count += x & 0x3f
     end

This ran about 2.5 times faster that the naive algorithm.

Then I realized that when I was comparing a set of search times with just a few words in it, the bit vector would be very sparse. Each chunk in the loop above would be likely to be zero. So I added a test:

     ((max_bit+29)/30).times do |offset|
       x = (word >> (offset*30)) & 0x3fffffff
       next if x.zero?
       x = x - ((x >> 1) & 0x55555555)
       x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
       x = (x + (x >> 4)) & 0x0f0f0f0f;
       x = x + (x >> 8)
       x = x + (x >> 16)
       count += x & 0x3f
     end

Now I was seven times faster than the original. But my testbed was using vectors containing 20 set bits (out of 1,000). I changed it to generate timings with vectors containing 1, 2, 5, 10, 20, 100, and 900 set bits. This got even better: I was up to a factor of 15 faster with 1 or 2 bits in the vector.

But if I could speed things up this much by eliminating zero chunks in the bit-twiddling algorithm could I do the same in the simple counting algorithm? I tried a third algorithm:

     ((max_bit+29)/30).times do |offset|
        x = (word >> (offset*30)) # & 0x3fffffff
        next if x.zero?
        30.times {|i| count += x[i]}
      end

The inner loop here is the same as for the original count, but I now count the bits in chunks of 30.

This code performs identically to the bit-twiddling code for 1 set bit, and only slightly worse for 2 set bits. However. once the number of bits starts to grow (past about 5 for my given chunk size), the performance starts to tail off. At 100 bits it’s slower than the original naive count.

So for my particular application, I could probably chose either of the chunked counting algorithms. Because the bit twiddling one scales up to larger numbers of bits, and because I’ll need that later on if I ever start doing the cosine-based matching of documents, I went with it.

So what’s the point of all this?

Yesterday I posted a blog entry about the importance of verbs. It said "Often the true value of a thing isn’t the thing itself, but instead is the activity that created it." Chad Fowler picked this up and wrote a wonderful piece showing how this was true for musicians. And Brian Marick picked up of Chad’s piece to emphasize the value of practice when learning a creative process.

At the same time, Andy and I had been discussing a set of music tapes he had. Originally designed to help musicians practice scales and arpeggios, these had been so popular that they now encompassed a whole spectrum of practice techniques. We were bemoaning the fact that it seemed unlikely that we’d be able to get developers to do the same: to buy some aid to help them practice programming. We just felt that practicing was not something that programmers did.

Skip forward to this morning. In the shower, I got to thinking about this, and realized that my little 45 minute exploration of bit counting was actually a practice session. I wasn’t really worried about the performance of bit counting in the blog’s search algorithm; in reality it comes back pretty much instantaneously. Instead, I just wanted to play with some code and experiment with a technique I hadn’t used before. I did it in a simple, controlled environment, and I tried many different variations (more than I’ve listed here). And I’ve still got some more playing to do: I want to mess around with the effect of varying the chunk size, and I want to see if any of the other bit counting algorithms perform faster.

What made this a practice session? Well, I had some time without interruptions. I had a simple thing I wanted to try, and I tried it many times. I looked for feedback each time so I could work to improve. There was no pressure: the code was effectively throwaway. It was fun: I kept making small steps forward, which motivated me to continue. Finally, I came out of it knowing more than when I went in.

Ultimately it was having the free time that allowed me to practice. If the pressure was on, if there was a deadline to delivery the blog search functionality, then the existing performance would have been acceptable, and the practice would never have taken place. But those 45 pressure-free minutes let me play.

So how can we do this in the real world? How can we help developers do the practicing that’s clearly necessary in any creative process? I don’t know, but my gut tells me we need to do two main things.

The first is to take the pressure off every now and then. Provide a temporal oasis where it’s OK not to worry about some approaching deadline. It has to be acceptable to relax, because if you aren’t relaxed you’re not going to learn from the practice.

The second is to help folks learn how to play with code: how to make mistakes, how to improvise, how to reflect, and how to measure. This is hard: we’re trained to try to do things right, to play to the score, rather than improvise. I suspect that success here comes only after doing.

So, my challenge for the day: see if you can carve out 45 to 60 minutes to play with a small piece of code. You don’t necessarily have to look at performance: perhaps you could play with the structure, or the memory use, or the interface. In the end it doesn’t matter. Experiment, measure, improve.

Practice.

This kata arose from some discussions we’ve been having at the DFW Practioners meetings. The problem domain is something seemingly simple: pricing goods at supermarkets.

A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers.

This Kata is straightforward. Implement a binary search routine (using the specification below) in the language and technique of your choice. Tomorrow, implement it again, using a totally different technique. Do the same the next day, until you have five totally unique implementations of a binary chop. (For example, one solution might be the traditional iterative approach, one might be recursive, one might use a functional style passing array slices around, and so on).

Rough estimation is a useful talent to possess. As you’re coding away, you may suddenly need to work out approximately how big a data structure will be, or how fast some loop will run. The faster you can do this, the less the coding flow will be disturbed.

So this is a simple kata: a series of questions, each asking for a rough answer. Try to work each out in your head. I’ll post my answers (and how I got them) in a week or so.

Martin Fowler gave me a hard time for KataTwo, complaining that it was yet another single-function, academic exercise. Which, or course, it was. So this week let’s mix things up a bit.

Here’s an exercise in three parts to do with real world data. Try hard not to read ahead—do each part in turn.

There are many circumstances where we need to find out if something is a member of a set, and many algorithms for doing it. If the set is small, you can use bitmaps. When they get larger, hashes are a useful technique. But when the sets get big, we start bumping in to limitations. Holding 250,000 words in memory for a spell checker might be too big an overhead if your target environment is a PDA or cell phone. Keeping a list of web-pages visited might be extravagant when you get up to tens of millions of pages. Fortunately, there’s a technique that can help.

Back to non-realistic coding this week (sorry, Martin). Let's solve some crossword puzzle clues.

The last couple of kata have been programming challenges; let’s move back into mushier, people-oriented stuff this week.