I've encountered many people who are dogmatically against anything which can be considered "optimization" in the general English-language sense of the word, and they very often quote verbatim the (partial) quote "premature optimization is the root of all evil" as a justification for their stance, implying that they interpret whatever I'm talking about to be "premature optimization". However, these views are sometimes so ridiculously entrenched that they dismiss pretty much any kind of algorithmic or data-structure deviations from the purest "naive" implementation… or at least any deviations from the way they've done things before. How can one approach people like this in a way to make them "open their ears" again after they shut down from hearing about "performance" or "optimization"? How do I discuss a design/implementation topic which has an impact on performance without having people instantly think: "This guy wants to spend two weeks on ten lines of code?"
Now, the stance of whether "all optimization is premature and therefore evil" or not has already been covered here as well as in other corners of the Web, and it has already been discussed how to recognize when optimization is premature and therefore evil, but unfortunately there are still people in the real world who are not quite as open to challenges to their faith in Anti-Optimization.
Previous attempts
A few times, I've tried supplying the complete quote from Donald Knuth in order to explain that "premature optimization is bad" ↛ "all optimization is bad":
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
However, when supplying the entire quote, these people sometimes actually become more convinced that what I'm doing is Premature Optimization™ and dig in and refuse to listen. It's almost as if the word "optimization" scares them: On a couple of occasions, I was able to propose actual performance-improving code changes without them being vetoed by simply avoiding the use of the word "optimiz(e|ation)" (and "performance" as well — that word is scary too) and instead using some expression like "alternative architecture" or "improved implementation". For this reason, it really seems like this truly is dogmatism and not them in fact evaluating what I say critically and then dismissing it as not necessary and/or too costly.
Best Answer
It seems you are looking for shortcuts not to try out the "purest naive implementation" first, and directly implement a "more sophisticated solution because you know beforehand that the naive implementation will not do it". Unfortunately, this will seldom work — when you do not have hard facts or technical arguments to prove that the naive implementation is or will be too slow, you are most probably wrong, and what you are doing is premature optimization. And trying to argue with Knuth is the opposite of having a hard fact.
In my experience, you will either have to bite the bullet and try the "naive implementation" first (and will probably be astonished how often this is fast enough), or you will at least make a rough estimation about the running time, like:
"The naive implementation will be O(n³), and n is bigger than 100.000; that will run some days, while the not-so-naive implementation will run in O(n), which will take only a few minutes".
Only with such arguments at hand you can be sure your optimization is not premature.
There is IMHO only one exception from this: when the faster solution is also the simpler and cleaner one, then you should use the faster solution right from the start. The standard example is the one of using a dictionary instead of a list to avoid unnecessary loop code for lookups, or the usage of a good SQL query which gives you exactly the one result record you need, instead of a big resultset which has to be filtered afterwards in code. If you have such a case, do not argue about performance - the performance might be an additional, but most probably irrelevant benefit, and when you mention it, people might be tempted to use Knuth against you. Argue about readability, shorter code, cleaner code, maintainability - no need to "mask" anything here, but because those (and only those) are the correct arguments here.
To my experience, the latter case is rare - the more typically case is one can first implement a simple, naive solution which is better understandable and less error prone than a more complicated, but probably faster one.
And of course, you should know the requirements and the use case well enough to know what performance is acceptable, and when things become "too slow" in the eyes of your users. In an ideal world, you would get a formal performance spec by your customer, but in real world projects, required performance is often a grey area, something your users will only tell you when they note the program behaves "too slow" in production. And often, that is the only working way of finding out when something is too slow — the user feedback, and then you do not need to cite Knuth to convince your teammates that their "naive implementation" was not sufficient.