Optimisation Links

Optimisation Links:

Krishna Kunchithapadam's Efficient Programming

Summary of techniques for accelerating code. It's good, but is couched in general terms - I'm looking for more examples.

Improving Protein Database Search Sensitivity

An as yet unwritten article, based on experience of using the optimised 'diff' algorithm. The article concentrates on modifications to the algorithm that improved its sensitivity by taking account of common patterns in protein sequences. This page gives an idea of the kind of knock on effects that follow from writing a very fast implementation.

Rick Booth

Including this link is really an excuse for me to mention Rick Booth's superb book - "Inner Loops", Addison Wesley, ISBN 0-201-47960-5 on optimising code on the current generation of 32 bit processors. This book describes in detail how on-chip caches affect performance and how to use the dual pipeline architecture. You won't find a lot at the web site, not at the moment anyway, but the book is in my view essential reading.

FFT

An as yet unwritten article on how the Fast Fourier Transform algorithm could have been discovered. The basic idea is that the Fourier transform algorithm can quite naturally be formulated as a (rather inefficient) recursive algorithm. If however the tie up between recursion and dynamic programming described in the article 'DP is recursion with a cache' is exploited, the efficiency lost is more than regained. The FFT is then seen to be a Dynamic Programming implementation of the Fourier Transform.

Othello

An as yet unwritten article on how a change in board representation accelerated a 6502 based Othello playing program.