> The real question is, what makes it "premature"? When this principle has come up for me it's not so much about optimization, but about the cost you're paying

> The real question is, what makes it "premature"? When this principle has come up for me it's not so much about optimization, but about the cost you're paying to have that optimization: In particular, the cost in terms of code complexity. If you've already got generic code for a self-balancing red-black tree, and you can just plug your new data structure into it, and you're reasonably sure that your thing will get 10 nodes on occasion, then sure, use it, even if you don't know whether you'll ever get much larger than that. But if you don't have that code handy, then don't write a self-balancing red-black tree unless you have benchmarks to show that it will help. And don't use a self-balancing R-B tree if you don't know whether the number of nodes ever goes past 2. (Or, I mean, unless it's a personal project and you want to practice writing a self-balancing R-B tree; but at that point you're not optimizing, you're practicing / having fun, so the advice isn't applicable.) If code structure A and code structure B are both about equally comprehensible, and you think code structure A will be more effecient, go ahead and use it. But if structure A is extremely complicated, and will make the understanding and maintenance of the system more difficult and prone to error, then don't use it unless you know it's actually worth the cost.