Kernel Hacker's Bookshelf: The Practice of Programming

In The Mythical Man-Month, Fred Brooks observes that the productivity of experienced programmers frequently varies by a factor of 10 or more. What makes the 10x programmers so much better? Undoubtedly some of the difference is due to native facility with language or logic. But even with these advantages, no one is born writing beautiful, elegant, maintainable code; everyone goes through a learning process.

How do we learn to be good programmers? In many ways, the art of computer programming is still stuck in the era of the master-apprentice system. Some of us are lucky enough to learn to program in something like "the UNIX room" at Bell Labs, where you could shoulder-surf the likes of Ken Thompson and Dennis Ritchie. Occasionally someone practices pair-programming instead of just arguing passionately about it, and once in a very long while, a 10x programmer will actually teach another person how to program. Unfortunately, formal university education rarely teaches students about the practical aspects of programming, as any holder of a computer science degree will readily attest, and few programmers have the time, interest, or ability to write accessible books about programming. As a result, most programmers are doomed to a decade of re-inventing wheels by trial and error.

Brian Kernighan and Rob Pike are two 10x programmers who do have the time, interest, and ability to write a book about software engineering best practices. The Practice of Programming aims to fill the gaps in the training of most computer programmers. From the book:

This book probably won't make you ten times more productive, but it can easily make you twice as productive (and half as frustrated). If I could send one book to a programmer trapped on a desert island, this would be the book - and I'd send the same book to the new programmer who just joined my development team.

Overview

The Practice of Programming differs from most programming books in several enjoyable ways. Rather than promoting a particular new programming philosophy, Kernighan and Pike focus on three principles: simplicity, clarity, and generality. As you might guess from the title, the book is short on theory and long on practice. About one third of the ~250 page book is taken up by actual real-world example code, starting with the original dodgy code and showing the step-by-step evolution to better code. Most examples are in C, but the principles illustrated readily translate to other languages.

The writing style of this book is refreshingly practical and down-to-earth, without losing generality. The authors avoid stark black-and-white pronouncements, preferring to discuss why different techniques are useful under different conditions. Clarity is another hallmark of their style; they use as few words as possible to clearly state each point, and dismiss trivialities and side issues quickly and cleanly. A typical example of this approach is their advice on brace and indentation style: "The specific style is less important than its consistent application. Pick one style, preferably ours, use it consistently, and don't waste time arguing."

The book is organized into nine chapters, each covering a topic such as testing or debugging that usually requires an entire book on its own. The table of contents includes headings like "Test as You Write the Code," "Consistency and Idioms," "Strategies for Speed," "Other People's Bugs," and "Programs that Write Programs." I can't cover the whole book in this review, but I'll go into detail on two of my favorite chapters, "Performance" and "Notation."

Performance

The introduction of this chapter gives some very direct advice: "The first principle of optimization is don't." Computers are fast - go run lmbench on your desktop to update your sense of just how fast. For example, some system calls are now in the sub-microsecond range under Linux on modern hardware. Armchair optimization - the practice of making small theoretical optimizations as you code, at the expense of readability, portability, or correctness - is especially foolish in light of Donald Knuth's observation that 4% of the code typically accounts for more than half of the run-time of the program. Kernighan and Pike's first piece of advice is to write simple, clear, concise code, and optimize only when you have some tangible reason to do so.

The chapter begins with a real-world optimization problem: a spam-filter that worked well enough in testing but bogged down in production. The tangible reason for optimizing this program is that the mail queues were filling up with undelivered mail - a clear justification for optimization if there ever was one. The authors show the process they went through to optimize the spam-filter, step-by-step: profiling, analysis, a first attempt at optimization, re-factoring the problem, addition of pre-computation, and measurement of the results. This overview is welcome not only as a good programming war story but also because the overall flow of code optimization is non-obvious (otherwise, "How would you go about optimizing a program?" would not be such a common interview question).

The rest of the chapter talks about best practices for each step of optimization. The first topic is timing and profiling, as it should be. All too often, even good programmers measure performance by "feel" - if you don't believe me, search LKML. Sometimes no easy tool exists to measure what is being optimized, but it's still better to write some kind of measurement tool, no matter how clunky or approximate. Human perception and judgment are heavily influenced by preconceptions and the vast majority of theoretical optimizations have negligible effects on performance. A more subtle piece of advice is to turn performance results into pictures or graphs. Chris Mason's seekwatcher is an excellent example; it turns block traces into graphs - and even movies!

The authors cram a surprisingly complete demonstration of profiling into less than two pages, using prof on their spam-filter as the example. They show how to identify hot spots and do basic sanity checking on the results - e.g., match up the number of times a function call shows up in the profile with the number of iterations of the main loop. While they include some caveats on trusting profiling results, I wish they had spent some time on the design of profiling tools to show the kinds of biases and errors that so often make profiling results misleading. Perhaps it's because I work on systems software, but I've found that I really have to know the details of whether the profiler is using a periodic timer, hardware counters, includes time spent sleeping for IO in the kernel, how many events are dropped or missed, etc. A useful technique to demonstrate, and one in keeping with their minimalist, do-it-yourself philosophy, would be manually bisecting the code with timers to find hot spots when normal profiling tools fail.

The discussion on rewriting code goes beyond "find the top function and optimize it" - it also addresses eliminating calls to hot functions entirely and doing modest amounts of pre-computation. A fair portion of the section on code tuning has been superseded by improved compilers which can do, e.g., loop-unrolling automatically, but it still teaches valuable lessons about how to read code and understand its true cost and complexity.

Notation

The chapter on notation unfolds elegant, beautiful solutions one by one, turning normally painful problems into fun coding exercises. Each technique - little languages, special-purpose notation, programs that write programs, virtual machines - is accompanied by a concrete demonstration of how to implement the bare minimum of the technique to get the job done. The suggestion to "write a new language" seems absurd in the face of most day-to-day programming problems, but writing a very small, very specialized language can save the programmer much time and many bugs, even when replacing only a few hundred lines of conventional code. Their first example, after printf() format specifiers, is a notation for packing and unpacking network packets. I recently implemented this technique and can report that it worked beautifully, repaying the time I invested in it within days of completion.

Another exercise in minimalism is their demonstration of how to write a basic grep in around 100 lines of C, without relying on external libraries. Most of us will never need to re-implement regular expressions from scratch, but we may encounter a problem best solved by writing a small general purpose pattern matcher.

Another example demonstrates the power (and danger) of keeping a variety of scripting languages and data processing tools at your fingertips. The authors implement a crude text-only web browser with about 50 lines of Awk, Tcl, and Perl, again using only built-in language support and no external libraries or modules. Here as elsewhere, Kernighan and Pike refuse to make hard and fast assertions about the One True Scripting Language; they'd rather you used the right language for the right job. From the book:

It can be argued that this approach is less justified now, given the modern plethora of scripting languages written specifically to address the limitations of earlier scripting languages. However, their argument still rings true for me, as someone who has never settled down into one scripting language. I have a decade of experience using a hodge-podge of random scripting languages, and when I do write in one scripting language, I end up spending a lot of time contorting language features to fit situations they were not designed for.

The section on virtual machines shows how to implement a minimal special purpose virtual machine (the Z-machine for Zork comes to mind immediately). The remaining sections cover programs that write programs, using macros to generate code (a common technique in Linux header files), and just a little taste of run-time code generation.

Summary

The Practice of Programming embodies its own principles: simplicity, clarity, generality. First published in 1999, it has aged well due to its focus on general principles of good programming rather than language-specific tricks and tips. The book has something to offer to programmers at all levels of experience; beginners will benefit most but experienced developers will appreciate the more advanced and subtle techniques in the later chapters. Of all the books on the Kernel Hacker's Bookshelf, this one should never be missing.

A friend of mine collected and analyzed statistics on a six-month crash project involving some
500 programmers.  At project end, fully half the code delivered had been written by just one
of them.  This programmer, whom I shall call Per because that's his name, is humble about his
skills, because he knows someone else who codes ten times as fast, and wears out two keyboards
a year.

When the difference between a mediocre programmer and the best is three orders of magnitude,
it argues for (1) paying way more for somebody closer to the latter, and (2) figuring out some
way to identify him or her.  Fortunately, our distinguished author, Ms. Henson has identified
herself for us.  Others working in Free Software distinguish themselves, to varied but
measurably visible degrees, in their public work.  

Curiously, the pay scale seems to be logarithmic; it is vanishingly rare to find a star
programmer of Per's or Val's caliber paid more than three times as much as an ordinary
programmer.  I take that as evidence that software development management has not yet attained
a stone-age level of sophistication.

By extension, if a programmer should implement something requiring 
algorithms more complex than can be explained in three lines of crude 
pseudocode, such that a random monkey pulled off the street can't 
understand them in five minutes, it's the fault of the person who 
implemented that algorithm.

(I get this all the time. I ignore it. The proposed replacement 
algorithms, if any are provided, are invariably brittle, slow, and don't 
work.)

In Finland, we have the concept of "donkey's bridge" which means a way to move discussion to
(un)related topic across a method that might superficially seem related but in reality is not.
I do not know where it is coming from, and I digress.

I feel like pointing out a man called Steve Yegge who tends to have useful bits of information
in his blog, especially for programmers. Give it a try, maybe his style works for you.

> In Finland, we have the concept of "donkey's bridge" which means a way to 
> move discussion to (un)related topic across a method that might 
> superficially seem related but in reality is not. I do not know where it 
> is coming from, and I digress.

http://en.wikipedia.org/wiki/Pons_asinorum

That's not special to programming. It goes for all creative problem-solving skills. More true
the more creative, more analytical the work is though.

A skilled person will clean a room in half the time, and the result will be better.

But a skilled mechanic will sometimes listen to a car-engine for 10 seconds, twist one screw,
listen to it again, and know what the problem is, whereas a clueless one might spend a day
searching for the problem.

It's rare that pay scales with performance. And it'd probably be a bad thing for society
overall if it did. It should probably differ MORE than it does though, but that would require
management to be able to actually recognize skill, which is a tricky proposition.

Why does it follow that a steep pay scale is somehow more sophisticated?

I would believe that is a dangerous path. As soon as you measure productivity as a one
dimensional variable (the pay rate) you open for all sorts of possibilities to cheat. Lines of
code? Easy, write bad code. Bugs? Easy, write nothing. Fixed bugs? Easy, write buggy code in
the first place. As soon as you reduce productivity to a single value you will start getting
results reflecting that.

Measuring productivity has been a hot topic since the seventies and so far nothing of value
has been produced by doing it. It's just not that simple. If it were, your boss should also be
compensated according to his/her abilities, and how do you measure THAT? And even if you pull
off this impossible stunt, I believe you would find that the best creative people in this line
of work require a lot more complex incentive than money.

Absolutely!

I can't believe I forgot to mention that one.  Programming Pearls should definitely be on any
programmer's bookshelf.

I read Rob Pike's "Notes on Programming in C" way back in the day, and it is still one of the
very best essays on programming style I've ever read.  I credit this with almost
single-handedly banging me upside the head and causing me to consider my code more like a
novel than a flowchart: how can I write my code so that its structure and intent can be easily
SEEN and UNDERSTOOD by the reader?  How can I make it obvious which things are important and
which are incidental, just by the way I write the code?  This is catnip to a naturally
anal-retentive person like myself.

Of course I've read "The C Programming Language", and I also had an opportunity to hear Brian
Kernighan speak at Carnegie Mellon in the 80's, about C++ (although back then it wasn't clear
this would be the name!)

If these guys are giving advice, I'm buying!

Agreed to all said, one cannot praise this book enough; I was always telling to my students
that if they want to work on improving their programming skills, that this is the book to
read.

I'd like also to point to the "Unix Programming Environment" book of same authors that is IMO
still, after all those years, the best quick introduction into the topic.

The German translation is called "Programmierpraxis. Prinzipien zur effizienten
Programmierung", ISBN 3827315832. But don't try to find it, it is sold out and since this
morning, no longer available at any online used book store |-/

I don't know if you tried this before, but with great reviews like this, I'd have no problem
clicking a "Place order with Amazon" or something like that, giving you some referral money.

Maybe have a few options to differing parts of the world, i.e., I can't use the American
amazon.com, because I'd have to pay both American and European taxes then, so I always use
amazon.co.uk (I'm from Denmark).

Actually, after reading a few lines of the article (including the author's name), I went
straight to amazon.fr and ordered the book.

I always find Val Henson's articles excellent, and the comments above just seem to
confirm her high opinion of the book. I'll soon have my own opinion of it ;-)

Thanks Val and all LWN commentators for such a great knowledge and experience
sharing. How can one live without LWN?

bookzilla in germany (append .de) doesnt hand out referral money, but 
donates a good deal of money to the free software foundation europe.

I don't buy from Amazon since the one-click patent, but the link may be useful for the more
tolerant.

A fantastic book, and a fantastic article.  I look forward to more of this type of content
from LWN in the future!

A previous incarnation of the "The Practice of Programming" is Kernighan and Plauger's "The
Elements of Programming Style". This was a book that was a must read when I was in college*
and covers most of the items that "The Practice of Programming" does.. However it does it in
Fortran (and yes it shows how to program cleanly with style in Fortran.. and if you can do
that you can do it in any language (probably even Haskell :)).

* the John Shipman List of Books:
Kernighan and Plauger: The Elements of Programming Style
Kernighan and Pike: The Unix Programming Environment
Kernighan and Ritchie: The C Programming Language
Brooks: The Mythical Man-Month
Knuth: The TeXbook
...

I think there were 3-4 other books (but I forget them).. and there were a couple of other ones
added over the years. But those were the basics you had to know if you were going to get into
senior year of CS.

I would also cite this book as that which most improved my code. Anything by Donald Knuth,
also (not just the TeXbook, but any of his software engineering writings). He has a wonderful
code style (if not to everyone's taste).

May be out of place considering you are talking specifically about kernel programming, however
the claim that programmers range from 1x to 10x was published in 1975, 33 years ago.

Now we have Java which is by design for average programmers. There is plenty of average
programming to be done -- more software is coded for in-house than best of breed. The very
first programmers were recruited from chess grandmasters since programmers didn't exist back
then. A lot has changed since then, and I'd like to see how well this 10x claim holds up now.

Also the claim that projects are like pregnancy, throwing more workers at the problem will not
speed things up seems to be in disagreement with the industry practice of death marches. If
Fred Brooks is still correct then why do industries do death marches (e.g. video games)?

...who claimed that the ratio is more recently closer to 50x. I see no reason to disbelieve
him.

While a simple *doubling* of productivity and clarity could easily be gained through the
insights of any of the great books mentioned, one should not interpret these ratios to mean
"10x or 50x more lines of code" (and I would be suspicious of programmers who 'wear out
keyboards'. If you are doing more typing than thinking, you're on irc, not writing great
code.)

Any old programming fart (guilty) will cite Dijkstra's observation that a line of code is a
liability, not an asset. So real productivity gain must be through leverage, tool-building,
and paradigm shifts - and reuse, not reinventing wheels.

The fact that industry does something proves nothing except possibly
mismanagement.

The idea of less people, more skilled more productivity is cross industry
sectors. Smart construction people know that, and many a foreman has made a
name and career for himself by choosing a small competent crew, feeding them
the necessary support and materials, and outperforming other crews with far
more people.

The real problem is determining skill level and productivity, and getting
used to the idea that the company's future is dependent on a few key
individuals that don't sit in the executive suite.

Derek

About paying for productivity -- Paul Graham (Hackers and Painters) made a wonderful point --
"you need to be good to see who is good".

Very few people are good.

Most management of large projects looks for interchangable parts.

About 25 years there was a number of Programmer Productivity workshops/papers -- and the
conclusions were facinating...In some
controlled tests they gave a number of programmers a problem to solve.

a) There were as ~10x difference in productivity, code size and performance.
b) All good things came together (smaller, faster, tigher code written quicker).

The sample sizes were small (on the order of several dozen) -- with large
samples I would expect the differences to be even greater.