3 ms·

"Avoid Premature Optimization" Does Not Mean "Write Dumb Code"

54 points by fogus 15y ago

mahmud 15y ago
His "non-dumb" code converts colors from a vector-space to a laundry list. The tuple representation of colors has algebraic qualities absent from the simplistic lookup-table he proposes (in fact, he's inadvertently taking us back from full color to "indexed" palettes common in the 80s) I prefer the tuples better; at least they can be logically extended to include alpha & depth information, and can be efficiently packed into a machine word.)
- ZeroGravitas 15y ago
  I think the colors are still tuples and there's still a lookup either way, it's just that instead of having an expressive human-readable name like "Tomato" they have an opaque code number like "0".
- secoif 15y ago
  If you read the last part of the article you will find he is, in fact, proposing the tuple method and is aghast at the debugging issues/readability of the lookup table, vs arguable speed increase.
  - mahmud 15y ago
    The exposition could be better, imo. Nevertheless, nice to know we agree.
cpt1138 15y ago
My understanding of the "premature" part is the fact that without profiling your application in some way, you have no idea apriori where the bottlenecks are. This "optimization" is premature in that its cost in w/e metric you want (readability, etc.) is payed and you have no idea about its relative performance cost. For example, after performing this "optimization" you save a few milliseconds but the Mnesia sync between two instances is orders of magnitude more time.
- onemoreact 15y ago
  You can profile and application without running it. That's the whole point of BigO notation. The type of profiling your thinking of is a great place to look for less obvious improvements. AKA my N is probaly above 50,000 so (N^N) not worth looking into.
  - Locke1689 15y ago
    Big O is often somewhat useless in practice. Yes, if you have an O(2^n) algorithm that's slow -- don't do that unless you can't approximate and your problem is NP-complete. In most other cases (AKA a good developer usually tries to find O(n)/O(nlog n) algorithms for everything possible) you're really talking about problems due to memory and network. These can never be represented accurately by big-O, so usually it's more accurate to ask in the beginning, "How many RPCs am I doing here?" because that's what's really going to kill you in production.
    - onemoreact 15y ago
      I have seen plenty of developers create websites using a lot of O(n^2) code when O(n log n) was an option. Often its simple questions like should I sort this before I do some manipulation and working though which is faster can literally take a few seconds of thought. That's not to say you need to always write optimized code, just avoid writing dumb code when you know it's going to be a problem ahead of time.
      - wanorris 15y ago
        If it's the same amount of work and readability is not sacrificed, consistently using O(n log n) is a good practice for that situation. If the result is more effort or less readable, then an understanding of what n is going to be like is probably worthwhile. For the love of all that's holy, please do not optimize access to a collection of days of the week that is accessed infrequently.
  - chc 15y ago
    Big-O tells you the behavior of your running time as the dataset increases. It does not tell you what parts of your program are actually fast or slow. For example, an O(n^n) algorithm is actually fine if it will never be applied to more than six elements and each operation takes two microseconds, and is vastly better for that case than an O(1) algorithm that takes half a second.
elmindreda 15y ago
...because what he really means is "use good taste," but the Tao that can be blogged about is not the true Tao.
colomon 15y ago
It seems like it is very simple to me: You should always code with your performance requirements in mind. But you shouldn't do detailed optimization until you have some sort of profiling feedback. You have to do your basic coding with your performance requirements in mind, because it is all too easy to come up with code that can never meet your performance requirements, no matter how much you profile and optimize it. Case in point: http://strangelyconsistent.org/blog/p1-best-way-to-multiply-a-chain-of-matrices http://strangelyconsistent.org/blog/p1-best-way-to-multiply-... . My solution (http://strangelyconsistent.org/p6cc2010/p1-colomon/ http://strangelyconsistent.org/p6cc2010/p1-colomon/) was quite elegant, IMO, setting up things so I simply generated all the all the possible solutions, and then took the min with respect to the number of multiplications. But it was also appallingly inefficient. Generating all the possible solutions is completely the wrong approach, and no amount of optimizations to my algorithm would ever be sufficiently efficient for non-trivial problems. The only possible approach is to start over from scratch: http://strangelyconsistent.org/p6cc2010/p1-moritz/ http://strangelyconsistent.org/p6cc2010/p1-moritz/ So if I had properly considering my performance requirements, I would have come up with a much better solution. (Or just failed: dynamic programming is not really in my programming toolbox. I need to get around to remedying that!) But at the same time, worrying about how to most efficiently represent my Ordering object would have been completely pointless. That's what "avoid premature optimization" means, IMO. It's not an excuse ignore performance. It's about not sweating the small details until you're certain they're important.
- abecedarius 15y ago
  I only glanced at this, but usually when a recursive solution can be improved upon by dynamic programming, you can make a comparable improvement by memoizing instead, without needing a full rewrite. In this case using stacks instead of recursion appears to have gotten in the way of that and might count as premature optimization. (I might be completely barking up the wrong tree as far as your particular code goes, again, but code described as generating all possible solutions could be made efficient without much change.) For example, the memoized word-splitting code at http://norvig.com/ngrams/ http://norvig.com/ngrams/ compared to the recent discussion here on HN of doing it with dynamic programming (as an interview problem).

54 points by fogus 15y ago

His "non-dumb" code converts colors from a vector-space to a laundry list. The tuple representation of colors has algebraic qualities absent from the simplistic lookup-table he proposes (in fact, he's inadvertently taking us back from full color to "indexed" palettes common in the 80s) I prefer the tuples better; at least they can be logically extended to include alpha & depth information, and can be efficiently packed into a machine word.)

ZeroGravitas 15y ago
I think the colors are still tuples and there's still a lookup either way, it's just that instead of having an expressive human-readable name like "Tomato" they have an opaque code number like "0".
secoif 15y ago
If you read the last part of the article you will find he is, in fact, proposing the tuple method and is aghast at the debugging issues/readability of the lookup table, vs arguable speed increase.
- mahmud 15y ago
  The exposition could be better, imo. Nevertheless, nice to know we agree.

cpt1138 15y ago

My understanding of the "premature" part is the fact that without profiling your application in some way, you have no idea apriori where the bottlenecks are. This "optimization" is premature in that its cost in w/e metric you want (readability, etc.) is payed and you have no idea about its relative performance cost. For example, after performing this "optimization" you save a few milliseconds but the Mnesia sync between two instances is orders of magnitude more time.

onemoreact 15y ago
You can profile and application without running it. That's the whole point of BigO notation. The type of profiling your thinking of is a great place to look for less obvious improvements. AKA my N is probaly above 50,000 so (N^N) not worth looking into.
- Locke1689 15y ago
  Big O is often somewhat useless in practice. Yes, if you have an O(2^n) algorithm that's slow -- don't do that unless you can't approximate and your problem is NP-complete. In most other cases (AKA a good developer usually tries to find O(n)/O(nlog n) algorithms for everything possible) you're really talking about problems due to memory and network. These can never be represented accurately by big-O, so usually it's more accurate to ask in the beginning, "How many RPCs am I doing here?" because that's what's really going to kill you in production.
  - onemoreact 15y ago
    I have seen plenty of developers create websites using a lot of O(n^2) code when O(n log n) was an option. Often its simple questions like should I sort this before I do some manipulation and working though which is faster can literally take a few seconds of thought. That's not to say you need to always write optimized code, just avoid writing dumb code when you know it's going to be a problem ahead of time.
    - wanorris 15y ago
      If it's the same amount of work and readability is not sacrificed, consistently using O(n log n) is a good practice for that situation. If the result is more effort or less readable, then an understanding of what n is going to be like is probably worthwhile. For the love of all that's holy, please do not optimize access to a collection of days of the week that is accessed infrequently.
- chc 15y ago
  Big-O tells you the behavior of your running time as the dataset increases. It does not tell you what parts of your program are actually fast or slow. For example, an O(n^n) algorithm is actually fine if it will never be applied to more than six elements and each operation takes two microseconds, and is vastly better for that case than an O(1) algorithm that takes half a second.

elmindreda 15y ago

...because what he really means is "use good taste," but the Tao that can be blogged about is not the true Tao.

colomon 15y ago

It seems like it is very simple to me: You should always code with your performance requirements in mind. But you shouldn't do detailed optimization until you have some sort of profiling feedback. You have to do your basic coding with your performance requirements in mind, because it is all too easy to come up with code that can never meet your performance requirements, no matter how much you profile and optimize it. Case in point: http://strangelyconsistent.org/blog/p1-best-way-to-multiply-a-chain-of-matrices http://strangelyconsistent.org/blog/p1-best-way-to-multiply-... . My solution (http://strangelyconsistent.org/p6cc2010/p1-colomon/ http://strangelyconsistent.org/p6cc2010/p1-colomon/) was quite elegant, IMO, setting up things so I simply generated all the all the possible solutions, and then took the min with respect to the number of multiplications. But it was also appallingly inefficient. Generating all the possible solutions is completely the wrong approach, and no amount of optimizations to my algorithm would ever be sufficiently efficient for non-trivial problems. The only possible approach is to start over from scratch: http://strangelyconsistent.org/p6cc2010/p1-moritz/ http://strangelyconsistent.org/p6cc2010/p1-moritz/ So if I had properly considering my performance requirements, I would have come up with a much better solution. (Or just failed: dynamic programming is not really in my programming toolbox. I need to get around to remedying that!) But at the same time, worrying about how to most efficiently represent my Ordering object would have been completely pointless. That's what "avoid premature optimization" means, IMO. It's not an excuse ignore performance. It's about not sweating the small details until you're certain they're important.

abecedarius 15y ago
I only glanced at this, but usually when a recursive solution can be improved upon by dynamic programming, you can make a comparable improvement by memoizing instead, without needing a full rewrite. In this case using stacks instead of recursion appears to have gotten in the way of that and might count as premature optimization. (I might be completely barking up the wrong tree as far as your particular code goes, again, but code described as generating all possible solutions could be made efficient without much change.) For example, the memoized word-splitting code at http://norvig.com/ngrams/ http://norvig.com/ngrams/ compared to the recent discussion here on HN of doing it with dynamic programming (as an interview problem).