Exactly. And not only being able to pick the correct data structure for the problem, (and possibly the correct implementation), but being able to know what is going to need attention even before a single line of code is written.

Most of my optimization work is still done with pencil, paper and pocket calculator. Well, actually, most of the time you won't even need a calculator.