3 ms·

I don't think the original paper by Knuth (https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640) supports this interpretati

by norir 3y ago

I don't think the original paper by Knuth (https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640) supports this interpretation. In the paper, Knuth describes how as one develops as a programmer one learns how to write in a style that is generally reasonably efficient. In particular, you should take note of hot loops, which are often quite obvious, and then write in the most readable style outside of the hot loops without too much thought about efficiency. By accepting some inefficiency, but writing in a generally efficient style, you can move much more quickly than if you are constantly bogged down in the details trying to squeeze out every possible cpu cycle. What people tend to miss in my view is that he is advocating writing in an efficient style, which may not be obvious to an inexperienced developer. For example, writing a linear algebra routine in which you traverse column wise in an inner loop when the data is laid out row wise is going to be very slow and a simple change of algorithm or restructuring of the data can lead to an enormous speed up. This should be done immediately if discovered. But a skilled programmer will also be unlikely to traverse in the wrong order anyway because they already know the data layout and have thought about the order of traversal as part of their thinking process. In other words, the "optimization" of traversing in the fast way is something they would just do naturally and has no influence on the development time. Conversely, they may also suspect that with some clever bit-twiddling hacks, they may be able to squeeze another 5-10% performance out of the routine. Unless you know that the code is being distributed at scale, this is almost certainly a waste of time. It will be hard to write as well as brittle and error prone. It deflects your attention from more important problems. It is evil both because of the opportunity cost of chasing these small efficiencies as well as the increased complexity that they often introduce for minimal gain.

HALtheWise 3y ago
I'm curious how this interacts with language selection. In particular, it looks like most of the programming languages in widespread use in 1974 were all relatively efficient compiled and statically typed languages (Fortran, cobol, C) with the notable exception of Basic. Would Knuth have considered choosing a performant language as "optimization" or just as part of "writing in an efficient style as any good programmer should do"? The distinction is a lot more important today with the ~100x speed and power consumption differences between Ruby/Python/etc and C++/Java/Go/Rust/etc.
- thom 3y ago
  Knuth makes this argument more clearly elsewhere, in Computer Programming as an Art: "Another important aspect of program quality is the efficiency with which the computer's resources are actually being used. I am sorry to say that many people nowadays are condemning program efficiency, telling us that it is in bad taste. The reason for this is that we are now experiencing a reaction from the time when efficiency was the only reputable criterion of goodness, and programmers in the past have tended to be so preoccupied with efficiency that they have produced needlessly complicated code; the result of this unnecessary complexity has been that net efficiency has gone down, due to difficulties of debugging and maintenance. The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming." If you have a holistic definition of efficiency, then it might make sense to use a performant language for the performance critical parts of a wider system, but more productive languages elsewhere. You might make a similar argument about languages that add some productivity overhead to achieve stronger guarantees of safety or correctness.
thom 3y ago
I'm pasting the famous passage below, and I don't know how to interpret it as anything other than a call to correctly identify the performance critical part of one's code before spending significant time on optimization. If you can intuit that, more power to you! If you can't, you must measure, and Knuth gives the suggestion that your compiler should do this automatically for you: "There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools or seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off." I certainly agree with the interpretation that the _cost_ is maintainability of prematurely optimised code and this is the evil he's describing. But this is also all in the context of efficiency as a virtue in itself - i.e. something you should be seeking, but seeking in the correct places.
fl0ki 3y ago
My problem is that people use this as an excuse not to consider optimization at all initially, because they think that once they have a working version, they can "just" profile and optimize the slowest few functions to get ideal performance. From the point of view of that singular task, yes, they achieved an optimization objective. From the point of view of overall performance vs what was possible given certain hardware, they could still be several orders of magnitude away from optimal. A profiler can't tell you that an entire operation would become completely unnecessary if you maintain a certain invariant elsewhere, and this can go as far out as you let it, e.g. entirely changing your in-memory data model to prepare it for the operations you know you'll be performing in the critical path. I know because I've been fortunate to work in environments full of seasoned experts writing world-scale software in C++ and Rust, that I was still able to optimize 100x-1Mx by zooming out and solving the same problem from a new perspective, something a profiler cannot help with. And I'm _nothing_ compared to the people that come around and make it another 10x faster with SIMD or some cutting edge computer science research I'm not across. (Remember when NFA regex was a breakthrough and now looks like a joke compared to DFA?). Even a profiler hinting that a hot function might benefit from SIMD can't tell you how you should arrange your overall data structures to fully benefit from SIMD, or cache locality for that matter. This isn't an attack on what you said, and what I'm saying is bordering on incoherent because there's so much more to the performance optimization iceberg than the "profiling" tip that most engineers are permanently stuck on. But no, every time aggressive holistic optimization conversations come up, more than half of the audience will dismiss it as "premature" or insist on just profiling and decline to learn anything. Then people like me have to inherit and rewrite their projects because they've ground our global scale to a halt.
- _a_a_a_ 3y ago
  > they could still be several orders of magnitude away from optimal I have a fair bit of experience in optimisation and this is ridiculously... optimistic, shall we say. The only way you can get literally orders of magnitude speed up is if some pillock put literally orders of magnitude of slowdown in originally, typically by combining a couple of O(n^2) operations, and even then only seen that a few times and it's easy to fix.

by norir 3y ago

HALtheWise 3y ago

I'm curious how this interacts with language selection. In particular, it looks like most of the programming languages in widespread use in 1974 were all relatively efficient compiled and statically typed languages (Fortran, cobol, C) with the notable exception of Basic. Would Knuth have considered choosing a performant language as "optimization" or just as part of "writing in an efficient style as any good programmer should do"? The distinction is a lot more important today with the ~100x speed and power consumption differences between Ruby/Python/etc and C++/Java/Go/Rust/etc.

thom 3y ago
Knuth makes this argument more clearly elsewhere, in Computer Programming as an Art: "Another important aspect of program quality is the efficiency with which the computer's resources are actually being used. I am sorry to say that many people nowadays are condemning program efficiency, telling us that it is in bad taste. The reason for this is that we are now experiencing a reaction from the time when efficiency was the only reputable criterion of goodness, and programmers in the past have tended to be so preoccupied with efficiency that they have produced needlessly complicated code; the result of this unnecessary complexity has been that net efficiency has gone down, due to difficulties of debugging and maintenance. The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming." If you have a holistic definition of efficiency, then it might make sense to use a performant language for the performance critical parts of a wider system, but more productive languages elsewhere. You might make a similar argument about languages that add some productivity overhead to achieve stronger guarantees of safety or correctness.

thom 3y ago

I'm pasting the famous passage below, and I don't know how to interpret it as anything other than a call to correctly identify the performance critical part of one's code before spending significant time on optimization. If you can intuit that, more power to you! If you can't, you must measure, and Knuth gives the suggestion that your compiler should do this automatically for you: "There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools or seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off." I certainly agree with the interpretation that the _cost_ is maintainability of prematurely optimised code and this is the evil he's describing. But this is also all in the context of efficiency as a virtue in itself - i.e. something you should be seeking, but seeking in the correct places.

fl0ki 3y ago

My problem is that people use this as an excuse not to consider optimization at all initially, because they think that once they have a working version, they can "just" profile and optimize the slowest few functions to get ideal performance. From the point of view of that singular task, yes, they achieved an optimization objective. From the point of view of overall performance vs what was possible given certain hardware, they could still be several orders of magnitude away from optimal. A profiler can't tell you that an entire operation would become completely unnecessary if you maintain a certain invariant elsewhere, and this can go as far out as you let it, e.g. entirely changing your in-memory data model to prepare it for the operations you know you'll be performing in the critical path. I know because I've been fortunate to work in environments full of seasoned experts writing world-scale software in C++ and Rust, that I was still able to optimize 100x-1Mx by zooming out and solving the same problem from a new perspective, something a profiler cannot help with. And I'm _nothing_ compared to the people that come around and make it another 10x faster with SIMD or some cutting edge computer science research I'm not across. (Remember when NFA regex was a breakthrough and now looks like a joke compared to DFA?). Even a profiler hinting that a hot function might benefit from SIMD can't tell you how you should arrange your overall data structures to fully benefit from SIMD, or cache locality for that matter. This isn't an attack on what you said, and what I'm saying is bordering on incoherent because there's so much more to the performance optimization iceberg than the "profiling" tip that most engineers are permanently stuck on. But no, every time aggressive holistic optimization conversations come up, more than half of the audience will dismiss it as "premature" or insist on just profiling and decline to learn anything. Then people like me have to inherit and rewrite their projects because they've ground our global scale to a halt.

_a_a_a_ 3y ago
> they could still be several orders of magnitude away from optimal I have a fair bit of experience in optimisation and this is ridiculously... optimistic, shall we say. The only way you can get literally orders of magnitude speed up is if some pillock put literally orders of magnitude of slowdown in originally, typically by combining a couple of O(n^2) operations, and even then only seen that a few times and it's easy to fix.