The biggest issue I have with premature optimization is stuff that really doesn't matter.

For example, in Java I usually use ConcurrentHashMap, even in contexts that a regular HashMap might be ok. My reasoning for this is simple: I might want to use it in a multithreaded context eventually and the performance differences really aren't that much for most things; uncontested locks in Java are nearly free.

I've gotten pull requests rejected because regular HashMaps are "faster", and then the comments on the PR ends up with people bickering about when to use it.

In that case, does it actually matter? Even if HashMap is technically "faster", it's not much faster, and maybe instead we should focus on the thing that's likely to actually make a noticeable difference like the forty extra separate blocking calls to PostgreSQL or web requests?

So that's the premature optimization that I think is evil. I think it's perfectly fine at the algorithm level to optimize early.

I can fully understand "bickering" about someone sprinkling their favourite data type over a codebase which consistently used a standard data type before. The argument that it might be multithreaded in the futurure does not hold if the rest of the code base clearly was not writen with that in mind. That could even be counter productive, should someone get the misguided idea that it was ready for it.

Make a (very) good argument, and suggest a realtistic path to change the whole codebase, but don't create inconsistency just because it is "better". It is not.