Program Performance

Once a program has been correctly implemented, the next task is to ensure it's performing adequately.

Andrew's notes state the order of developing a program should be the following:

  1. Design the program well
  2. Implement the program well
  3. Test the program well
  4. Only after you're sure it's working, measure performance
  5. If (and only if) performance is inadequate, find the "hot spots"
  6. Tune the code to fix these
  7. Repeat measure-analyse-tune cycle until performance ok

Programs to Analyse Performance

  • Valgrind
    • (e.g. valgrind '—tool=cachegrind' could be used to analyse caching for array modification)
  • Gcc -p/gprof (to find out where execution time is being spent)
    • run gcc -p -o blah blah.c and then run gprof blah to see a split of the time


Language Choice

More important even than optimisations is the initial choice of language. A C program may run faster than shell/perl/python, but likely take much longer to write and be much harder to debug.


Caching is one of the most useful tools for improving performance. Instead of having a function calculate the same input over and over again, store the result in an array. Then it can check there first, and afterwards place the result there.
Perl has a package memoize that does this:

use Memoize;
sub fib($);
printf "fib(%d) = %d\n", $_, fib($_) foreach @ARGV;
sub fib($) {
    my ($n) = @_;
    return 1 if $n < 3;
    return fib($n-1) + fib($n-2);