In literature class, we all learned the notion of close reading, a disciplined approach to really studying and really understanding a work of literature.
Although program code is (usually) not literature, the techniques of close reading apply there, too.
Last winter, John Regehr's Nibble Sort Programming Contest inspired a number of truly wonderful close readings of code:
- Nibblesort: Adventures in Optimization
I decided to enter the contest because I don’t usually work on low-level optimization, either writing hand-tuned code or working on compiler transformations to make “normal” code execute in a more efficient way. I eventually submitted an entry that did pretty well (top half of the non-SIMD entries), and learned several “morals” about optimization along the way.
- Parallel Nibble Sort
I chose to implement the sort using a sorting network. I used the following minimum-depth network to sort 16 items, which was designed by David C. Van Voorhis.
- Nibble Sort
Being susceptible to nerd sniping, this problem stuck in my head and I ended up spending two Saturday afternoons trying to implement a fast solution.
Of the three essays, I liked Jordan Rose's the best, although all three are nice.
Let's hear it for close reading of code!
Oh, and lastly: I particularly enjoyed that the prize for the competition was a copy of Hacker's Delight, perhaps the most unusual and most wonderful, if most challenging, computer textbook ever written. I have the first edition of Warren's incredible book on my reading stand, and every so often I crack it open at a random page and disappear into half an hour of reverie...
Too bad I was never a compiler writer; I suspect I would have enjoyed it.