Programming Pearls
Rate it:
Open Preview
Read between May 19 - June 08, 2019
1%
Flag icon
The pseudocode programs in the first edition of the book were all implemented, but I was the only person to see the real code. For this edition, I have rewritten all the old programs and written about the same amount of new code. The programs are available at www.programmingpearls.com The code includes much of the scaffolding for testing, debugging and timing the functions. The site also contains other relevant material.
Daniel Moore
https://web.archive.org/web/20000303195222/http://www.programmingpearls.com/
8%
Flag icon
The problem looks hard until you finally have the aha! insight: let’s view the problem as transforming the array ab into the array ba, but let’s also assume that we have a function that reverses the elements in a specified portion of the array. Starting with ab, we reverse a to get arb, reverse b to get arbr, and then reverse the whole thing to get (arbr)r, which is exactly ba.
8%
Flag icon
The reversal code is time- and space-efficient, and is so short and simple that it’s pretty hard to get wrong. Brian Kernighan and P. J. Plauger used precisely this code in their 1981 Software Tools in Pascal to move lines within a text editor. Kernighan reports that it ran correctly the first time it was executed, while their previous code for a similar task based on linked lists contained several bugs. This code is used in several text processing systems, including the text editor with which I originally typed this column. Ken Thompson wrote the editor and the reversal code in 1971, and ...more
12%
Flag icon
Dirty systems have hundreds of error messages scattered throughout the code, mixed in with other output statements; clean systems have them accessed through a single function. Consider the difficulty of performing the following requests under the “dirty” and “clean” organizations: produce a list of all possible error messages, change each “serious” error message to sound an alarm, and translate the error messages into French or German.
12%
Flag icon
Hypertext. In the early 1990’s, when web sites were numbered in the thousands, I was entranced by the reference books that were just coming out on CD-ROMs. The collection of data was stunning: encyclopedias, dictionaries, almanacs, telephone directories, classical literature, textbooks, system reference manuals, and more, all in the palm of my hand. The user interfaces for the various data sets were, unfortunately, equally stunning: every program had its own quirks. Today, I have access to all that data (and more) on CDs and the web, and the interface is usually the web browser of my choice. ...more
13%
Flag icon
While the stories in this column span several decades and a dozen languages, the moral of each is the same: don’t write a big program when a little one will do. Most of the structures exemplify what Polya calls the Inventor’s Paradox in his How to Solve It: “the more general problem may be easier to solve”. In programming this means that it may be harder to solve a 23-case problem directly than to write a general program to handle the n-case version, and then apply it to the case that n = 23.
23%
Flag icon
The expert debugger never forgets that there has to be a logical explanation, no matter how mysterious the system’s behavior may seem when first observed. That attitude is illustrated in an anecdote from IBM’s Yorktown Heights Research Center. A programmer had recently installed a new workstation. All was fine when he was sitting down, but he couldn’t log in to the system when he was standing up. That behavior was one hundred percent repeatable: he could always log in when sitting and never when standing. Most of us just sit back and marvel at such a story. How could that workstation know ...more
23%
Flag icon
A banking system built in Chicago had worked correctly for many months, but unexpectedly quit the first time it was used on international data. Programmers spent days scouring the code, but they couldn’t find any stray command that would quit the program. When they observed the behavior more closely, they found that the program quit as they entered data for the country of Ecuador. Closer inspection showed that when the user typed the name of the capital city (Quito), the program interpreted that as a request to quit the run!
23%
Flag icon
The best book I’ve seen on debugging is The Medical Detectives by Berton Roueché, published by Penguin in 1991. The heroes in the book debug complex systems, ranging from mildly sick people to very sick towns. The problem-solving methods they use are directly applicable to debugging computer systems. These true stories are as spellbinding as any fiction.
26%
Flag icon
I first learned the “Rule of 72” in a course on accounting. Assume that you invest a sum of money for y years at an interest rate of r percent per year. The financial version of the rule says that if r×y = 72, then your money will roughly double. The approximation is quite accurate: investing $1000 at 6 percent interest for 12 years gives $2012, and $1000 at 8 percent for 9 years gives $1999. The Rule of 72 is handy for estimating the growth of any exponential process. If a bacterial colony in a dish grows at the rate of three percent per hour, then it doubles in size every day. And doubling ...more
This highlight has been truncated due to consecutive passage length restrictions.
Daniel Moore
half a percent, π seconds is a nanocentury. Because the exponential program takes 107 seconds, we should be prepared to wait about four months.
27%
Flag icon
The output of any calculation is only as good as its input. With good data, simple calculations can yield accurate answers that are sometimes quite useful. Don Knuth once wrote a disk sorting package, only to find that it took twice the time predicted by his calculations. Diligent checking uncovered the flaw: due to a software bug, the system’s one-year-old disks had run at only half their advertised speed for their entire lives. When the bug was fixed, Knuth’s sorting package behaved as predicted and every other disk-bound program also ran faster.
27%
Flag icon
But before placing too much confidence in a twenty percent margin of error, consider Vic Vyssotsky’s advice from a talk he has given on several occasions. “Most of you”, says Vyssotsky, “probably recall pictures of ‘Galloping Gertie’, the Tacoma Narrows Bridge which tore itself apart in a windstorm in 1940. Well, suspension bridges had been ripping themselves apart that way for eighty years or so before Galloping Gertie. It’s an aerodynamic lift phenomenon, and to do a proper engineering calculation of the forces, which involve drastic nonlinearities, you have to use the mathematics and ...more
This highlight has been truncated due to consecutive passage length restrictions.
Daniel Moore
almost unique. “When Roebling was asked whether his proposed bridge wouldn’t collapse like so many others, he said, ‘No, because I designed it six times as strong as it needs to be, to prevent that from happening.’ “Roebling was a good engineer, and he built a good bridge, by employing a huge safety factor to compensate for his ignorance. Do we do that? I submit to you that in calculating performance of our real-time software systems we ought to derate them by a factor of two, or four, or six, to compensate for our ignorance. In making reliability/availability commitments, we ought to stay back from the objectives we think we can meet by a factor of ten, to compensate for our ignorance. In estimating size and cost and schedule, we should be conservative by a factor of two or four to compensate for our ignorance. We should design the way John Roebling did, and not the way his contemporaries did — so far as I know, none of the suspension bridges built by Roebling’s contemporaries in the United States still stands, and a quarter of all the bridges of any type built in the U.S. in the 1870’s collapsed within ten years of their construction. “Are we engineers, like John Roebling? I wonder.”
28%
Flag icon
Little’s Law states that ‘The average number of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.’ (And if there is a gross ‘flow balance’ of things entering and leaving, the exit rate is also the entry rate.) “I teach this technique of performance analysis in my computer architecture classes at Ohio State University. But I try to emphasize that the result is a general law of systems theory, and can be applied to many other kinds of systems. For instance, if you’re in line waiting to get into a popular ...more
29%
Flag icon
Physicists are well aware of this topic. After this column appeared in Communications of the ACM, Jan Wolitzky wrote I’ve often heard “back-of-the-envelope” calculations referred to as “Fermi approximations”, after the physicist. The story is that Enrico Fermi, Robert Oppenheimer, and the other Manhattan Project brass were behind a low blast wall awaiting the detonation of the first nuclear device from a few thousand yards away. Fermi was tearing up sheets of paper into little pieces, which he tossed into the air when he saw the flash. After the shock wave passed, he paced off the distance ...more
29%
Flag icon
Several readers commented that quick calculations are appropriately taught at an early age. Roger Pinkham wrote I am a teacher and have tried for years to teach “back-of-the-envelope” calculations to anyone who would listen. I have been marvelously unsuccessful. It seems to require a doubting-Thomas turn of mind. My father beat it into me. I come from the coast of Maine, and as a small child I was privy to a conversation between my father and his friend Homer Potter. Homer maintained that two ladies from Connecticut were pulling 200 pounds of lobsters a day. My father said, “Let’s see. If you ...more
33%
Flag icon
Chris Van Wyk and I chatted about code tuning early one afternoon; he then wandered off to improve a C program. A few hours later, he had halved the run time of a three-thousand line graphics program. Although the run time for typical images was much shorter, the program took ten minutes to process some complicated pictures. Van Wyk’s first step was to profile the program to find how much time was spent in each function (a profile of a similar, but smaller, program is shown on the next page). Running the program on ten typical test pictures showed that it spent almost seventy percent of its ...more
This highlight has been truncated due to consecutive passage length restrictions.
Daniel Moore
invoking the general storage allocator; this reduced the total run time of his program to 45 percent of what it had been previously (so the storage allocator now took 30 percent of the total time). An additional benefit was that the reduced fragmentation of the modified allocator made more efficient use of main memory than the original allocator.
38%
Flag icon
Fred Brooks observed the power of simplification when he wrote a payroll program for a national company in the mid 1950’s. The bottleneck of the program was the representation of the Kentucky state income tax. The tax was specified in the law by a two-dimensional table with income as one dimension, and number of exemptions as the other. Storing the table explicitly required thousands of words of memory, more than the capacity of the machine. The first approach Brooks tried was to fit a mathematical function through the tax table, but it was so jagged that no simple function would come close. ...more
40%
Flag icon
In another approach to sharing storage, Brian Kernighan wrote a traveling salesman program in the early 1970’s in which the lion’s share of the space was devoted to two 150×150 matrices. The two matrices, which I’ll call a and b to protect their anonymity, represented distances between points. Kernighan therefore knew that they had zero diagonals (a[i,i] = 0) and that they were symmetric (a[i, j] = a[j, i]). He therefore let the two triangular matrices share space in one square matrix, c, one corner of which looked like Kernighan could then refer to a[i,j] by the code c[max(i, j), min(i, j)] ...more
41%
Flag icon
The Apple Macintosh was an amazing machine when it was introduced in 1984. The little computer (128 kilobytes of RAM) had a startling user interface and a powerful collection of software. The design team anticipated shipping millions of copies, and could afford only a 64 kilobyte Read-Only Memory. The team put an incredible amount of system functionality into the tiny ROM by careful function definition (involving generalizing operators, merging functions and deleting features) and hand coding the entire ROM in assembly language. They estimated that their extremely tuned code, with careful ...more
42%
Flag icon
In the early 1980’s, Ken Thompson built a two-phase program that solves chess endgames for given configurations such as a King and two Bishops matched against a King and a Knight. (This program is distinct from the former world-computer-champion Belle chess machine developed by Thompson and Joe Condon.) The learning phase of the program computed the distance to checkmate for all possible chessboards (over the given set of four or five pieces) by working backwards from all possible checkmates; computer scientists will recognize this technique as dynamic programming, while chess experts know it ...more
This highlight has been truncated due to consecutive passage length restrictions.
Daniel Moore
records, which fit comfortably on a single (dedicated) disk. Even though Thompson knew there would be just one copy of his program, he had to squeeze the file onto one disk. Thompson exploited symmetry in data structures to reduce disk space by a factor of eight, which was critical for the success of his entire system. Squeezing space also reduced its run time: decreasing the number of positions examined in the endgame program reduced the time of its learning phase from many months to a few weeks.