Lecture 19: Performance challenges

1 A Challenge Problem

Suppose you were given a binary tree, with numbers at the leaves. How could you design a method over that data to sum the values of all the leaves? Presumably, you’d use a simple recursive method:

class BinaryNode implements BinTree {
  ...
  public int sumValues() {
    return this.left.sumValues() + this.right.sumValues();
  }
  ...
}

class BinaryLeaf implements BinTree {
  ...
  public int sumValues() {
    return this.value;
  }
  ...
}

This works fine, up to a point. For data that is sufficiently large, and in particular, trees that are sufficiently deep, this code will fail with a StackOverflowException. Unfortunately, not all programming languages truly provide an unbounded notion of recursion, but limit it for implementation reasons. Modern computers implement function calls and returns by using a stack of memory dedicated to storing the function’s arguments and return values. When a function is called, its arguments are pushed onto the stack; when the function returns, its arguments are popped off the stack. But the memory devoted to the call stack is limited to a small fraction of the available memory on a system, and when it is exhausted, the program has no choice but to abort.1This is known as a leaky abstraction: we’re supposed to pretend like the call stack is unbounded, but details of the implementation leak through and shatter that illusion. So how can we rewrite our code to avoid this failure?

1.1 One solution: iterators

In Fundies 2, we defined an iterator over trees that would allow us to loop over all the nodes in a tree. In fact we defined two iterators: breadth- and depth-first versions. Those iterators used a Stack to store their state of which nodes had yet to be visited. We could then write our code as follows:

int sum = 0;
for (Integer n : myTree.iterator()) {
  sum += n;
}

2 A Harder Challenge

Suppose instead of summing all the numbers in our tree, we wanted instead to produce a new tree, all of whose numbers were twice as large as in the original tree. What can we do now? A simple iterator will not suffice, because we need to store the entire tree structure somehow.

3 Does this matter in practice?

This example is actually derived from a real-world problem faced in a compiler. The compiler needed to render arbitrarily large (i.e. deeply nested) data, in an environment where the call-stack was painfully small, and the rendering had to be faithful to the tree structure of the original data.

For another, subtler example of a real-world problem, consider hash tables. The defining feature of hash tables is that they provide basically constant-time insertion, update, and access operations. However, their performance can vary greatly depending on the order of operations performed on them. A recent blog post describes how, in a real implementation that was specifically designed by experts to avoid these kinds of problems, the act of copying one hash table into another wound up be quadratically expensive, instead of linear.

1This is known as a leaky abstraction: we’re supposed to pretend like the call stack is unbounded, but details of the implementation leak through and shatter that illusion.

2Called the heap, although this has nothing to do with the heap data structure, and ironic since we’re storing a Stack in it and not on the call stack...