Thanks so much for the comprehensive (and quick) reply! Point by point:
Yes, constants are calculated at compile time, and the compiler is pretty good at recognizing things like the fact that (128 / 16) is the same as (128 >> 4) so will implement the fast bit shift instead of doing the division.
I'm not sure I understand: if it's calculated at compile time, then why does efficiency matter (other than compile speed)? If what ends up in the code is a constant regardless, why does it matter if it was calculated using division or a bit shift?
Looking at code size alone doesn't tell you anything about performance. In the same way as looking at the size of a car does not tell you how fast it can go, it's what's under the hood that counts.
That's what I guessed, regarding the code size - obviously loops and functions can decrease code size, but not execution time.
A good way to optimise code is to look at the assembler output from the compiler. But this is only helpful if you invest the time to learn to read and understand the assembler code.
I'm more than willing to do this; somewhat eager, in fact. I programmed a bit in assembler back in High School, and quite enjoyed it. Can you (or anyone else) suggest any good resources for learning about AVR assembler? Also, any tools for making examining the code easier (especially on OS X, but any *nix would be OK)?
...if you can take the code out of the ISR and run it in the loop of a sketch, you may be able to measure how changes to the code speed up or slow performance. Particularly if you measure over thousands or millions of iterations.
This has generally been my strategy for determining speed, but, of course, it has its limitations, which is why I'd like a less brute-force method.