5 ms·

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 inevita

by jasode 11y ago

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 https://en.wikipedia.org/wiki/Chinese_whispers

blowski 11y ago
> Is a cop out for not thinking Commonly phrased in startup world as "It's OK, we're just building an MVP."
- dack 11y ago
  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.
hn9780470248775 11y ago
> quicksort O(log(n)). Quicksort is O(n log n) average case and O(n^2) worst-case.
- jasode 11y ago
  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.
  - cossatot 11y ago
    >to try and win internet arguments is pretty much the antithesis of >to avoid wasting time.
- zeroonetwothree 11y ago
  It depends on how you implement median selection. You can get O(n log n) worst case if you want.
  - pjscott 11y ago
    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 https://en.wikipedia.org/wiki/Introsort
ultramancool 11y ago
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.
- randall 11y ago
  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%.
  - Piskvorrr 11y ago
    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."
pjscott 11y ago
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.)
petervandijck 11y ago
"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.

by jasode 11y ago

blowski 11y ago

> Is a cop out for not thinking Commonly phrased in startup world as "It's OK, we're just building an MVP."

dack 11y ago
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.

hn9780470248775 11y ago

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

jasode 11y ago
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.
- cossatot 11y ago
  >to try and win internet arguments is pretty much the antithesis of >to avoid wasting time.
zeroonetwothree 11y ago
It depends on how you implement median selection. You can get O(n log n) worst case if you want.
- pjscott 11y ago
  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 https://en.wikipedia.org/wiki/Introsort

ultramancool 11y ago

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.

randall 11y ago
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%.
- Piskvorrr 11y ago
  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."

pjscott 11y ago

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.)

petervandijck 11y ago

"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.