Programming Pearls, Second Edition

Column 6: Perspective on Performance

The next three columns describe three different approaches to run-time efficiency. In this column we’ll see how those parts fit together into a whole: each technique is applied at one of several design levels at which computer systems are built. We’ll first study one particular program, and then turn to a more systematic view of the levels at which systems are designed.

6.1 A Case Study

Andrew Appel describes “An efficient program for many-body simulations” in the January 1985 SIAM Journal on Scientific and Statistical Computing 6, 1, pp. 85-103. By working on the program at several levels, he reduced its run time from a year to a day.

The program solved the classical “n-body problem” of computing interactions ...