What’s the point? [1]

Let’s talk optimization today. It’s a contentious topic amongst programmers primarily because some are too eager to optimize while others are too lackadaisical. The former often results in code which is difficult to read and hard to maintain while containing more bugs than it otherwise would have, the latter results in programs which are unresponsive and often make the user wait. There are well known generic strategies for optimizing code which can be applied to improve perceived performance.

Caching is a common strategy which improves performance by remembering past answers to questions. You technically only have to compute a certain calculation once, for the answer to 4×31 will be the same tomorrow as it is today. There are only four considerations that matter with respect to caching, to wit:

1. Is the algorithm used to recompute a value a bottleneck in the overall scheme of things? In other words, if the computation is very fast to begin with, caching the result is probably not useful.
2. Is the time needed to retrieve the cached value less than the time needed to compute the value anew? Although it sounds like a rephrasing of bullet item #1, this is about the absolute performance gain rather than general merit.
3. Is the memory needed to store the cached value available? Optimization can apply both to processor performance and memory footprint and although the focus of this post is purely on performance, increased memory usage may make a certain optimization prohibitively expensive.
4. Is the cached value likely to be used ever again? There’s no point in caching the answer to a question that will only be asked once.

Lazy Evaluation is another common strategy which improves performance by delaying expensive computation till the utmost last moment. The basic idea is that if you never end up asking a specific question there’s no point wasting processor cycles on calculating —and caching— the answer. Lazy Evaluation improves the perception of performance in two ways:

1. It breaks potentially long computation times into smaller chunks that may not be noticeable to the user.
2. It eliminates processor cycles spend on calculating answers to questions that will never be asked.

Greedy Evaluation is the opposite of Lazy Evaluation and is —perhaps somewhat paradoxically— another common optimization strategy. Note that rather than talking about performance, I specifically prefixed it with the qualifier “perceived” in the opening paragraph of this post. When writing software for humans, what really matters is how people perceive the software rather than scientific metrics. It is a well known fact that the duration people are made to wait bears little correlation to how long people feel they had to wait. There are times when a delay will not bother people, for example when starting an application or entering a new game level. We expect to have to wait and will happily sit back for 3 seconds while the software performs its magic incantations. But make someone wait for half a second after selecting an object before you display the selected state and your software becomes all but unusable. Greedy Evaluation is the idea of calculating —and caching— lots of values during a period where the user is happy to wait, so that these values can then later be put to immediate use should the need arise.

Greedy Evaluation is sometimes also called Eager Evaluation, I assume to make it sound less negative and more like the opposite of Lazy Evaluation.

Multithreading improves performance by computing certain things in parallel. Almost all personal computers these days have more than one processor cores and certain computations can be performed simultaneously on different cores. Not all problems lend themselves to multi-threading, and often it is quite difficult to properly implement it. Breaking a process into smaller pieces is typically easy enough, but aggregating the results of each individual thread into a single final answer can be difficult. Especially with the arrival of Cell-processors and GPU-Multicores it is tempting to invest in multithreading as the performance increase can span two orders of magnitude.

But the above are all generic optimization strategies. Certain famous problems have a long history of people searching for specific optimizations and it is one of these I want to talk about in more detail. Up next: finding nearby points in large collections.