Optimization: Basics

CS 301 Lecture, Dr. Lawlor, 2005/10/28

Often our programs don't run fast enough, and we'd want them to run faster.

Examples of programs you'd want to run fast:

Anything that deals with big datasets (Google, social security department, IRS) that need to be processed semi-interactively. Speeding up a program by 20% might save somebody *hours* of waiting.
Anything that moves pixels around. A 1600x1200 display has 1.92 million pixels. At 60fps, that's over 100 million pixels per second. Think GUIs, 3D games, movie encoders/decoders, etc.
Anything that happens in real time: audio processing (44KHz audio == 44,000 samples per second), network processing (fast ethernet can deliver >=20,000 packets per second), hardware control.

If it only happens once, as long as it's within reason (under a second), it doesn't matter how fast it is:

Code run at program startup
Code run when an error occurs
Code to handle weird unlikely exceptions (as long as they really are unlikely!)
Code to process small datasets

Why is my program slow?

The only trick to optimization is figuring out why the program is running slowly, and then speeding it up.

To answer the "why" question, you can use:

Profiling tools, like UNIX "gprof" and Intel's Windows "vtune".
Operating system process profilers, like UNIX "top" or the Windows Task Manager (just press ctrl-alt-delete to see it. Really!)
Standard timing routines, like "gettimeofday" and "time", to measure wall-clock time. Timers are tricky to use because they're "quantized" (inaccurate), so you've got to make sure what you're timing takes long enough (by looping), and also repeat the measurements several times.

Good timers are built into NetRun, and accessible with the "Time" checkbox (which times the foo routine), and "print_time" (which times a subroutine of your choice).