Programming Pearls

1The fifteen-minute phone call (and the bitmap)

A programmer calls Bentley: how do I sort a disk file? Bentley starts sketching a disk-based merge sort, about 200 lines and a week of work. Then he asks questions. The file: at most 10 million toll-free phone numbers, 7-digit integers, no duplicates, no attached data, and "about a megabyte" of free memory. Suddenly the problem is not "sort a file"; it is "sort 10 million distinct small integers in 1 MB".

The answer: represent the data as 10 million bits. Bit i is 1 if number i is in the file. Read the input, set the bits, then walk the bitmap once and write the numbers back out, sorted for free. A few dozen lines, a few hours of work, about ten seconds of run time. "The programmer told me about his problem in a phone call; it took us about fifteen minutes to get to the real problem and find the bitmap solution" (Column 1). And the moral, in one line: "defining the problem was about ninety percent of this battle". Saint-Exupéry gets the last word: perfection is reached when there is nothing left to take away.

2Aha!: the hand flip and the sorted signature

Column 2 collects problems whose solutions feel like magic tricks. Rotating an array by d positions in place, in linear time? Reverse the first part, reverse the second, reverse the whole thing; done. Doug McIlroy demonstrated it with his hands: flip the left hand, flip the right hand, flip both together.

Finding every anagram family in a 230,000-word dictionary? Brute force is hopeless (comparing all pairs of words costs around 15 hours). The aha fits in one function: give each word a signature by sorting its letters.

signature = lambda word: "".join(sorted(word))
signature("deposit")   # → "deiopst"
signature("dopiest")   # → "deiopst"  ← SAME signature: they're anagrams

Then just sort the words by signature: anagrams land next to each other. A three-stage Unix pipeline, and by the 2nd edition the whole dictionary runs in 18 seconds. The lesson under the magic trick: a good representation does the work for you.

3The back of the envelope

The most reusable column of the book teaches estimating before building. The rules fit on one slide: "two answers are better than one" (estimate the Mississippi's flow via cross-section × speed, then via watershed × rainfall; if they agree, trust them), check dimensions, and keep rules of thumb handy. The gem: "π seconds is a nanocentury", accurate to half a percent. Let's unroll it on the brute-force anagram count:

# how long for 10²¹ operations at ~1 billion/second?
10²¹ ops ÷ 10⁹ ops/s        = 10¹² seconds
# rule of thumb: π × 10⁷ seconds ≈ 1 year
10¹² s ÷ (3.15 × 10⁷ s/yr)  ≈ 30,000 years   # verdict known before lunch

The anecdote that justifies the whole column: an engineering manager, reviewing a proposed system at the Olympics, times a one-character message round trip on a napkin and concludes the design works only if there are "at least a hundred and twenty seconds in each minute". Design rejected; the system shipped a year later worked flawlessly. The humbling appendix: a ten-question estimation quiz where you give 90% confidence ranges; most people get 3 to 6 right instead of the expected 9. We are all overconfident, measurably.

The anecdote that justifies the whole column: an engineering manager, reviewing a proposed system at the Olympics, times a one-character message round trip on a napkin and concludes the design works only if there are "at least a hundred and twenty seconds in each minute". Design rejected; the system shipped a year later worked flawlessly. The humbling appendix: a ten-question estimation quiz where you give 90% confidence ranges; most people get 3 to 6 right instead of the expected 9. We are all overconfident, measurably.

4The TRS-80 that beats the Alpha

One problem (the maximum-sum contiguous subsequence), four algorithms, from cubic to linear. The book then stages the fight nobody forgets: the cubic algorithm, compiled C, on a 533 MHz Alpha workstation, against the linear algorithm, interpreted BASIC, on a 1970s TRS-80 running at 2 MHz. Past n ≈ 10,000, the museum piece wins. At n = 1,000,000: 19 years for the Alpha, 5.4 hours for the TRS-80.

The 2nd edition's epilogue adds a wink: rerunning the 1st edition's measurements 14 years later, Bentley found his Pentium II "almost exactly one thousand times faster than the venerable VAX", with nearly identical algorithmic coefficients. Machines change by powers of ten; the math does not move.

5Binary search was published in 1946. A correct one took much longer.

Column 4 opens on a trap question: "the first binary search was published in 1946; when was the first correct search published?" The gap is measured in years. The most famous bug hides in one innocent-looking line:

lo = 0; hi = n - 1;
while (lo <= hi) {
  mid = (lo + hi) / 2;       // ✗ lo + hi OVERFLOWS the integer on large arrays
  mid = lo + (hi - lo) / 2;  // ✓ same value, no overflow (fixed in 2006!)
}

Bentley uses this "simple" algorithm to teach verification: write the loop invariant first (what must be true at every turn, here "if x exists, it's between lo and hi"), and derive the code from it, instead of patting the code until the tests pass.

Column 5 completes the method with scaffolding: a throwaway test harness around the function, assertions that document what must hold, and automated timing. The companion code ships nine versions of binary search, one of them deliberately wrong, to make the harness prove its worth. It is TDD's grandfather, twenty years early, in K&R C.

6Debugging is an exercise in disbelief

The debugging section (5.10) is a short anthology of impossible bugs that all had boring explanations. The programmer who could log in sitting down but not standing up: two keycaps swapped, and he typed differently when standing. The Chicago banking system that crashed when a customer typed "Quito": the terminal read it as a quit command. The system that "worked once, twice": a variable initialized at load time and never reset.

The professional attitude, from Rick Lemons: the best debugging lesson he ever had was watching a magic show. The dove did not really appear out of thin air, and your bug is not really impossible; in both cases you watched the wrong hand. "Debugging is usually unbelieving" (Column 5): refuse the supernatural explanation and the logical one surfaces.

7Strings of pearls: the Bible, the Iliad and the grandfather of LLMs

The column added in 2000 plays with big text. Counting the King James Bible's words (789,616 of them, 29,131 distinct; "the" alone appears 62,053 times) becomes a benchmark: a 30-line hand-rolled hash table beats the C++ STL map by an order of magnitude. A suffix array (sort all suffixes of the text, neighbors share prefixes) finds the longest repeated passage of the Iliad's 807,503 characters in 4.8 seconds: a full sentence Juno speaks and Minerva repeats word for word.

Then the showstopper: generate fake text by following word statistics from a source, a Markov chain. Trained on the book itself, order-2 produces eerily plausible technical prose, and Bentley notes that "for purposes of parody, order-2 text is usually juiciest" (Column 15). Predicting the next word from the previous ones, trained on a corpus: in 2000 it was a 50-line party trick; scale it by a few billion and you get the assistants we type to all day. The pearl aged into a pension fund.

8The rules that remain

Both epilogs are fictional interviews where Bentley grills himself ("people who interview themselves shouldn't criticize writing styles"). Out of them and the appendices come the book's distilled rules:

• the design checklist of the first epilog: work on the right problem, look at the data, use the back of the envelope, build prototypes, keep it simple, strive for elegance;
• Tom Duff's law, quoted as the best answer to "library or hand-rolled?": "whenever possible, steal code". In 2026 it's called npm install, Composer and Stack Overflow; the reflex hasn't aged a day, only its name changed;
• the line that summarizes the whole book's taste: "the cheapest, fastest and most reliable components of a computer system are those that aren't there";
• 27 code-tuning rules (Appendix 4), with measured gains and a warning attached: measure first, on YOUR machine; the cost models show a malloc of 12 bytes really consuming 48.