Q:

Optimizing Code

You are given a heap of code in your favorite language which combines to form a rather complicated application. It runs rather slowly, and your boss has asked you to optimize it. What are the steps you follow to most efficiently optimize the code? 
What strategies have you found to be unsuccessful when optimizing code?
Re-writes: At what point do you decide to stop optimizing and say "This is as fast as it'll get without a complete re-write." In what cases would you advocate a simple complete re-write anyway? How would you go about designing it?

A:

Profile before attempting any optimisation. 
9 times out of 10, the time won't be consumed where you might guess it is.
The usual unsuccessful strategy is micro-optimisation, when what is actually required is the appropriate algorithm.
Obligatory Donald Knuth quote:

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"

A:

Steps:

Measure
Analyze
Decide
Implement
Repeat

First get a profiler to measure the code. Do not fall into the trap of assuming you know where bottlenecks are. Even afterwards, if your assumptions prove to be correct, do not think that you can skip the measurement step the next time you have a similar task.
Then analyze your findings. Look at the code, identify the bottlenecks you can do something about that will have an effect. Try to estimate how much of an improvement this will be.
Decide if you want to go down this path, based on your analysis. Will the gains be worth it? Is a rewrite warranted? Perhaps you find that though it runs slow, it's as good as it is going to get or that you're close to the top of the performance curve where the work needed to eek out a miniscule improvement isn't warranted.
Implement your changes, do the rewrite if necessary, or refactor the code if that's the path you've gone down. Do it in small steps so that it becomes easy to measure if your change gave what you wanted or if you need to backtrack a step and try a different route.
Then go back to the start and measure, analyze, decide, implement, etc.
Also, on the note of refactoring code. The first things you should change are the big algorithm-level approaches. Things like replacing a sort algorithm with another that performs better, etc. Do not start with line-level optimizations, like how to get a line that increments a value to go slightly faster. Those are last level optimizations and usually not worth it, unless you're running in extreme performance conditions.

A:

Don't even bother to try anything  without some sort of profiling, I can't stress this enough! Unfortunately, all the profilers I know either suck or are expensive (Yay for business costs!) so I'll let others make recommendations there :).
You know you need a re-write when your data tells you that you need a re-write, which sounds recursive, but really just means the the cost of your current architecture or software stack is enough by itself to push you over the performance cliff, so nothing you do in local changes can fix the overall problem. However, before you get out the File->New... command, make a plan, build a prototype and test the prototype does better than the current system for the same task: it's amazing how often there is no noticable difference!

