This question is as relevant in 2025 as it was in 2009.

1. The first question you should ask is this: what are my constraints?
2. The second question is: given these constraints, what performance characteristics do I need?
3. The third question is: do I need additional optimization beyond the simplest implementation to meet these performance characteristics?

Premature optimization is the root of all evil mainly refers to skipping one or more of these steps, and proceeding to optimize anyway.

Optimizations should be done early in a project's lifecycle mainly refers to optimizing early based upon known constraints and performance characteristics.

Both philosophies can lead one to making the wrong decisions early on, which creates additional work down the road. Following either in isolation may lead you to make either more type 1 errors or type 2 errors than you need to: https://en.wikipedia.org/wiki/Type_I_and_type_II_errors

Ask those 3 questions early to help make the right decisions. Sometimes, you just don't know what you need early on and need to assess as the project moves forward, in which case it may be worthwhile to create a simple prototype/proof-of-concept. That gives you a chance to assess bottlenecks, then re-write a fuller implementation with those bottlenecks in mind. Done well, this just means you're spending the time you need to on these questions.