Besides counting steps, the program below also measures the amount of time that elapses between a moment shortly before a computer begins executing a given algorithm and a moment shortly after the algorithm terminates. Insight into an algorithm’s performance characteristics can certainly be gained by counting steps. However, several factors make it difficult to predict how programs will actually perform based on step counts alone.
When an algorithm is executed on a real computer, the individual steps of the algorithm can and often do get interleaved with the steps of other algorithms. And the low-level instructions produced by a compiler or interpreter might be significantly different, procedurally speaking, from the ones specified by a programmer in a high-level language. Furthermore, all steps are not created equal. Some instructions are more expensive than others, and this variable cost can vary from computer to another. Also, the actual performance of an algorithm can depend on instructions that were executed previously. Significant improvements in performance can be achieved by making predictions about the future using information from the past. Caches, pipelines, and branch predictors are examples of technologies that can affect actual program performance in ways not suggested by an analysis that only involves counting steps.
In short, there are good reasons for analyzing the theoretical and the actual performance of algorithms.
Algorithm X
Now let’s look at the specific algorithms that can be analyzed using the program below. At the beginning of Chapter 1, Knuth discusses the history and a definition of the word algorithm. He says we should consider the concept of an algorithm carefully, because it is basic to all of computer programming. On page 2, he presents “Euclid’s algorithm,” a procedure for finding the greatest common divisor of two positive integers, as an important historical example of an algorithm. The Java program below implements four variations of Euclid’s algorithm, including an implementation of the variation that Knuth calls “Algorithm E,” which he describes as follows:
Algorithm E (Euclid’s algorithm). Given two positive integers m and n, find their greatest common divisor, i.e. the largest positive integer which evenly divides both m and n.
E1. [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 ≤ r < n.) E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer. E3. [Interchange.] Set m ← n, n ← r, and go back to step E1. ▮
Gcd.methodE is a Java implementation of Algorithm E.
And Gcd.methodF is an implementation of the algorithm that Knuth gives as the answer to Exercise 3,
which appears on page 9 of Volume 1:
3. [20] Change Algorithm E (for the sake of efficiency) so that at step E3 we do not interchange values but immediately divide n by r and let m be the remainder. Add appropriate new steps so as to avoid all trivial replacement operations. Write this new algorithm in the style of Algorithm E, and call it Algorithm F.Knuth gives Exercise 3 a rating of 20, by which he means it is an average problem that tests basic understanding of the text material but which might take fifteen or twenty minutes to answer completely. You may wish to try solving the exercise yourself before looking at
Gcd.methodF or the answer given in Volume 1.
If you’ve already peeked at either one, you might be wondering how Algorithm F / Gcd.methodF
can be any better than Algorithm E / Gcd.methodE; if so, running the program below and studying the output
might help you understand the subtle difference.
The third method, Gcd.methodG, is more efficient than Gcd.methodE in the same way
that Gcd.methodF is more efficient, but not to the same extent. On the other hand, Gcd.methodG is similar to
Gcd.methodE in that it’s a little simpler than Gcd.methodF; certainly,
it consists of fewer lines of code.
Finally, Gcd.methodH, a recursive method, is composed of the fewest lines of code.
In fact, it could be written even more compactly, but that would be problematic. (Why?)
Exercises
- How do you think the performance of
Gcd.methodH, as measured by step counts, compares to the performance of the other three methods? Before performing any experiments, form a hypothesis and state it. Then design and perform an experiment to test your hypothesis. What was your prediction? How did you test it? What did you observe? What can you conclude from your observations? What further questions are raised as a result? - After performing the previous exercise, choose a follow-up question and study it using the same process.
- How do step counts relate to actual performance? Which of the types of steps counted by the program below (test, set, modulo, or jump) do you think is most expensive? Design an experiment to test your hypothesis. Describe your experiment. What did you discover?
- Study the following questions in the context of various boundary conditions. Describe the boundaries that you chose and what you learned.
Given a range of values for the integer variables m and n, what values of m and n have the smallest sum m + n and require the maximum number of steps to compute the greatest common divisor of m and n? What is the greatest number of distinct unordered pairs (m, n) that can satisfy these conditions for any range of inputs? How do you know? What is special about these values? What other interesting patterns can you spot?
- Design and implement a custom data type that can be used in place of the ArrayList
data type in the program below. Add your source code to the program and remove the import statement at the beginning of the program. Make additional changes to the rest of the program so that continues to function as originally designed. - In the program below, modify
AnalysisOfAlgorithms.outputso that it also prints a value labeled COST that is a sum of products where each term in the sum is the product of the number of steps counted for a given operation (test, set, modulo, or jump) and a weighting factor that represents the relative cost of that operation. Choose weights that are as realistic as possible. A smaller difference between the resulting COST value and the corresponding TIME value implies more realistic weights. - In the program below, modify
import java.util.ArrayList;
class Gcd {
private static Counter c;
public static void setCounter(Counter counter) { c = counter; }
public static int methodE(int m, int n) { c.mod(1); c.set(1);
int r = m % n; c.tst(1);
while (r != 0) { c.set(1);
m = n; c.set(1);
n = r; c.mod(1); c.set(1);
r = m % n; c.jmp(1); c.tst(1);
} c.jmp(1);
return n;
}
public static int methodF(int m, int n) { c.mod(1); c.set(1);
int r = m % n; c.tst(1);
while (r != 0) { c.mod(1); c.set(1);
m = n % r; c.tst(1);
if (m == 0) { c.jmp(1);
return r;
} c.mod(1); c.set(1);
n = r % m; c.tst(1);
if (n == 0) { c.jmp(1);
return m;
} c.mod(1); c.set(1);
r = m % n; c.jmp(1); c.tst(1);
} c.jmp(1);
return n;
}
public static int methodG(int m, int n) { c.mod(1); c.set(1); c.tst(1);
for (m = m % n; m != 0; m = m % n) { c.mod(1); c.set(1);
n = n % m; c.tst(1);
if (n == 0) { c.jmp(1);
return m;
} c.mod(1); c.set(1); c.jmp(1); c.tst(1);
} c.jmp(1);
return n;
}
public static int methodH(int m, int n) { c.mod(1); c.set(1);
m = m % n; c.tst(1);
if (m == 0) { c.jmp(1);
return n;
} c.set(2); c.jmp(2);
return methodH(n, m);
}
}
public class AnalysisOfAlgorithms
{
private static void output()
{
System.out.println(Team.aggregatorE.toString());
System.out.println(Team.aggregatorF.toString());
System.out.println(Team.aggregatorG.toString());
System.out.println(Team.aggregatorH.toString());
final ArrayList<Analyst> list = Team.highCountersE;
final int n = list.size();
for (int i = 0; i < n; i++)
System.out.println(list.get(i).id());
}
public static void main(String[] args)
{
final int lower = Integer.parseInt(args[0]);
final int upper = Integer.parseInt(args[1]);
for (int m = lower; m <= upper; m++)
for (int n = upper; n >= lower; n--)
for (int i : Sequence.ordered(4))
Controller.run(i, m, n);
output();
}
}
class Controller
{
private static void updateList(Analyst candidate, ArrayList<Analyst> highCountersList)
{
Analyst highCounter = highCountersList.isEmpty() ? candidate : highCountersList.get(0);
int result = candidate.device().compare(highCounter.device());
if (result > 0) highCountersList.clear();
if (result >= 0) highCountersList.add(candidate);
}
public static void run(int i, int m, int n)
{
Analyst analyst;
switch(i) {
case 1: analyst = Runner.runMethodE(m, n);
Team.aggregatorE.device().accumulate(analyst.device());
updateList(analyst, Team.highCountersE);
break;
case 2: analyst = Runner.runMethodF(m, n);
Team.aggregatorF.device().accumulate(analyst.device());
updateList(analyst, Team.highCountersF);
break;
case 3: analyst = Runner.runMethodG(m, n);
Team.aggregatorG.device().accumulate(analyst.device());
updateList(analyst, Team.highCountersG);
break;
case 4: analyst = Runner.runMethodH(m, n);
Team.aggregatorH.device().accumulate(analyst.device());
updateList(analyst, Team.highCountersH);
break;
}
}
}
class Runner
{
private static Analyst analyst;
public static Analyst runMethodE(int m, int n)
{
analyst = new Analyst("Gcd.methodE(" + m + ", " + n + ")");
Gcd.setCounter(analyst.device());
analyst.device().startTimer();
Gcd.methodE(m, n); /* Running Method E */
analyst.device().stopTimer();
return analyst;
}
public static Analyst runMethodF(int m, int n)
{
analyst = new Analyst("Gcd.methodF(" + m + ", " + n + ")");
Gcd.setCounter(analyst.device());
analyst.device().startTimer();
Gcd.methodF(m, n); /* Running Method F */
analyst.device().stopTimer();
return analyst;
}
public static Analyst runMethodG(int m, int n)
{
analyst = new Analyst("Gcd.methodG(" + m + ", " + n + ")");
Gcd.setCounter(analyst.device());
analyst.device().startTimer();
Gcd.methodG(m, n); /* Running Method G */
analyst.device().stopTimer();
return analyst;
}
public static Analyst runMethodH(int m, int n)
{
analyst = new Analyst("Gcd.methodH(" + m + ", " + n + ")");
Gcd.setCounter(analyst.device());
analyst.device().startTimer();
Gcd.methodH(m, n); /* Running Method H */
analyst.device().stopTimer();
return analyst;
}
}
abstract class Measurable
{
abstract public int size();
public int compare(Measurable right)
{
int lhs = this.size(), rhs = right.size();
return (lhs < rhs) ? -1 : (lhs == rhs) ? 0 : 1;
}
}
class Timer
{
private long startTime = 0;
public void start() { startTime = System.nanoTime(); }
public int stop() { return (int)(System.nanoTime() - startTime); }
}
class Counter extends Measurable
{
private int tst = 0, mod = 0, set = 0, jmp = 0;
public int tst(int stepSize) { return tst += stepSize; }
public int mod(int stepSize) { return mod += stepSize; }
public int set(int stepSize) { return set += stepSize; }
public int jmp(int stepSize) { return jmp += stepSize; }
public int tst() { return tst; }
public int mod() { return mod; }
public int set() { return set; }
public int jmp() { return jmp; }
public int size() { return tst + mod + set + jmp; }
}
class TimerCounter extends Counter
{
private final Timer t = new Timer();
private int totalTime = 0;
public void startTimer() { t.start(); }
public void stopTimer() { totalTime += t.stop(); }
public long totalTime() { return totalTime; }
public void accumulate(TimerCounter source)
{
this.tst(source.tst());
this.mod(source.mod());
this.set(source.set());
this.jmp(source.jmp());
this.totalTime += source.totalTime();
}
}
class Analyst
{
private final String id;
private final TimerCounter device = new TimerCounter();
public Analyst(String id) { this.id = id; }
public TimerCounter device() { return device; }
public String id() { return this.id; }
public String toString() {
String s = id;
s += "\n tst: " + device.tst();
s += "\n mod: " + device.mod();
s += "\n set: " + device.set();
s += "\n jmp: " + device.jmp();
s += "\n COUNT: " + device.size();
s += "\n TIME: " + device.totalTime();
return s + "\n";
}
}
class Team
{
public static Analyst
aggregatorE = new Analyst("Gcd.methodE(m, n)"),
aggregatorF = new Analyst("Gcd.methodF(m, n)"),
aggregatorG = new Analyst("Gcd.methodG(m, n)"),
aggregatorH = new Analyst("Gcd.methodH(m, n)");
public static ArrayList<Analyst>
highCountersE = new ArrayList<Analyst>(),
highCountersF = new ArrayList<Analyst>(),
highCountersG = new ArrayList<Analyst>(),
highCountersH = new ArrayList<Analyst>();
}
class Sequence
{
public static int[] ordered(int length)
{
int[] integers = new int[length];
for (int i = 0; i < length; i++)
integers[i] = i + 1;
return integers;
}
public static int[] shuffled(int length)
{
int[] integers = Sequence.ordered(length);
return Knuth.shuffle(integers);
}
}
class Knuth
{
private static int randomInt(int from, int to)
{
return from + (int)(Math.random() * (1 + to - from));
}
private static void swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static int[] shuffle(int[] array)
{
int k = array.length - 1;
for (int i = 0; i < k; i++) {
int j = randomInt(i, k);
swap(array, i, j);
}
return array;
}
}
