Robot Dreams

I think Mick makes a good point about the need to do careful optimizations and not put oneself in the trap of not doing optimizations until it's basically too late. But I think he misses on a more general, and more useful, optimization guideline Algorithmic Optimization. Like many programmers I worry about the usual inefficiencies in programs, some of which Mick mentions, like repeated memory allocations, hidden bottlenecks, bad in-lining, aliasing, RTTI, etc. But the optimization I think about most is the complexity of algorithms I'm implementing and of the complexity of libraries I'm using. Mick lists some optimizations that are obviously in the algorithm category: "AVOID PER FRAME CODE", and "AVOID ITERATIONS" which are more classically know as: use amortization algorithms, and use data structures to reduce complexity.

To help me in understanding the complexity of code I use a simple documentation trick. For each non-trivially complex function I write, I also add a comment indicating what I understand the complexity to be. This includes accounting for any interior calls made. For example one of the big operations in Thot is doing differences, the base algorithm of which is suffix arrays:

// O(E+6N+2NlogN), or O(E+5N+NlogN) without LCP sorting
void SuffixArray::build()
{
    // O(3N)+O(E)
    histogramSort();
    // O(NlogN+N)
    arraySort();
    // O(N)
    calculateLCP();
}
// O(3N)+O(E)
void SuffixArray::histogramSort();
// O(NlogN+N)
void SuffixArray::arraySort();
// O(N)
void SuffixArray::calculateLCP();

Which gives a clear idea of where one might optimize to get significant improvements. You might ask why I bother with constants. Simple; they may be constant but knowing that a function is 10N, and possibly in need of optimization, is a much better state than just saying it's N and having no idea why it's slow.

In the near future I'll talk about some specific algorithm optimizations that I've used in the past. And also on how to spot the hidden complexity in the plethora of Computer Science papers that claim incredible performance. Both John and I have some serious horror stories on that subject