Comment by jasode | Hacker News Reader

Comment by jasode | Hacker News Reader

The longer Knuth quote is “We should forget about small efficiencies, say about 97% of the time; premature optimization is the root of all evil”

In the inevitable meme transfer in the telephone game[1] and shortening of memes to smaller soundbites, the "small efficiencies" part is left out.

To me, "small efficiencies" was trying to "optimize" your old C code from...

  x = x + 1;

to...

  x++;

to...

  ++x;

... because you read/saw that a C compiler created tiny differences of assembly code based on post- vs pre- -increment operators which results in a 0.00001% runtime difference.

Knuth isn't talking about being ignorant or careless with choosing bubble sort O(n^2) vs quicksort O(log(n)). Or not placing an index on a lookup key of a 1 terabyte table (that's a 1-hour full table scan vs millisecond b-tree lookup). Those are not "small efficiencies".

If one leaves out the "small efficiencies" as a conditional, regurgitating the "premature optimization" is a cop out for not thinking.

[1]https://en.wikipedia.org/wiki/Chinese_whispers

> Is a cop out for not thinking

Commonly phrased in startup world as "It's OK, we're just building an MVP."

Which is wrong (and fails) mostly because the startup hasn't spent enough time verifying if a solution really solves a problem, and not that their MVP really required the extra performance.

> quicksort O(log(n)).

Quicksort is O(n log n) average case and O(n^2) worst-case.

Yes, I saw that error after the edit window closed so I couldn't fix the typo. There has to be an extra "n" because qs has to touch every element at least once so a baseline complexity of O(n) is unavoidable.

Hopefully, it didn't detract from the point that Knuth was talking about premature micro-optimizations and not design/architecture/algorithm optimization. Some inexperienced people are repeating "premature optimization" to try and win internet arguments instead of using it as nuanced advice to avoid wasting time.

>to try and win internet arguments

is pretty much the antithesis of

>to avoid wasting time.

It depends on how you implement median selection. You can get O(n log n) worst case if you want.

True, though it's usually not worth the hassle. Most production implementations of quicksort just drop down to heapsort for the current sub-array if the stack gets too deep.

https://en.wikipedia.org/wiki/Introsort

"premature optimization is the root of all evil"

-> I've found this super useful in projects. This doesn't mean you don't spend time on design or architecture, but it means many engineers have a strong tendency to jump on optimization opportunities too quickly (the more junior the stronger the tendency), AND this causes bad architecture choices that come to bite you hard later on. Keeping it simple and un-optimized is often better than early optimizing, not just because you save time and it's not worth it (hardware is cheap), but also because you keep your architecture elegant and the real bottlenecks will be different from what you thought they were and will come up later.

It's absolutely valid, and wisdom that's often hard earned.

Precisely - I think of this quote as more about how profiling and micro-optimizing your code should come last - but basic stuff like choosing the right data structure for the job should be something any programmer should jump at.

I had a friend once tell me he worried about double quotes vs single quotes b/c string interpolation checking. This would be the 97%.

Well, worrying about that is IMHO quite reasonable. Once. "Let's see how big an improvement that is...aha, near-nonexistent. Okay, moving on; perhaps use single quotes for new code if that still worries you."

In case anybody was wondering, your C compiler almost certainly will not generate different assembly code for ++x and x++. (This is easy enough to test if you have a compiler handy.)

Reply on news.ycombinator.com