4 ms·

Additionally, if a factor 2 improvement by the compiler on top of a factor 4 improvement by using better algorithms and data structures can give you an 8x impro

Additionally, if a factor 2 improvement by the compiler on top of a factor 4 improvement by using better algorithms and data structures can give you an 8x improvement overall, why would you not take it? Reading through the various comments asserting that optimizing compilers should not be necessary if you 'just use better algorithms' and whatnot, I'm kind of wondering why it has to be one thing or the another. Who wouldn't want to have both?

lmm 9y ago
Because using a better algorithm is more like a factor of 100 or 1000. Factors of 2 are just not worth bothering with; if the business is so marginal that a factor of 2 in the hardware requirements makes a noticeable difference then you don't want to be in that business in the first place.
- w0utert 9y ago
  That makes no sense at all. Only if you presume you are always going to start with some horrible piece of code that only uses the worst possible algorithms you may get that kind of speedup. And after you got your 100x to 1000x speedup, or if you start with a piece of code that already is quite efficient, it could still be 2x too slow to meet some hard realtime performance constraint. Or it could be fast enough, but you could potentially save 2x computing power that can be used for other tasks, just by letting the compiler optimize your code. If I tell my employer I'm not interested in getting a 2x speedup by flipping a compiler switch, but prefer to spend an uncertain time looking for or inventing this hypothetical algorithm that will give me 100x to 1000x speedup, I don't think they'll be very happy about that. For most of the code we deliver to our customers, a factor 'so marginal as 2x' could literally save them millions of dollars over the lifetime of the software. Two times faster saves a lot of computing time if you have jobs that run for 72+ hours. If only things were as easy as you pretend they are (we already have the 'marginal' 2x from the compiler optimizations, and we already have efficient algorithms)...
  - lmm 9y ago
    > Only if you presume you are always going to start with some horrible piece of code that only uses the worst possible algorithms you may get that kind of speedup If we're talking about algorithmic improvements we're usually talking about going from O(n^2) to O(n log n) or similar, which is easily a 100x-1000x or more speedup if your n is big enough to be bothering with performance at all. It's very easy to be accidentally quadratic and this causes a lot of performance bugs. Talking as though algorithmic speedups and optimization speedups are of a similar magnitude is really misleading. > it could still be 2x too slow to meet some hard realtime performance constraint Theoretically it could be, but that would take an incredible amount of luck. There's so much variation in runtime that the odds of getting within a factor of 2x are tiny; more likely you're thousands of times too slow, or thousands of times faster than you need to be. > Two times faster saves a lot of computing time if you have jobs that run for 72+ hours. Sure, if you've got jobs that run for 72 hours in your code (i.e. aren't spending those 72 hours doing something that's already highly optimized in a standard library e.g. linear algebra) and have already carefully optimized your choice of algorithms, then the rules are different. That's a pretty rare case though.
- bluGill 9y ago
  True, but that assumes a better algorithm exists that can give the 100x speedup. In a good language (most of them) the common algorithms are somehow implemented in the standard library and optimized - I just use them. Once I finished my degree I never wrote sort from scratch, I just looked up the syntax for calling the sort built into my language. Now it is possible that I can do better than the sort built in - but that is because I know my typical data and so I might be able to make a different compromise: we are not talking about a 100x speedup we are talking about a 1.0001x speedup (and that is only after several months of work to replicate tricks the built in sort already does) (technically I have implemented sort since my degree, but it was bogo sort: I obviously did it only for fun)
  - lmm 9y ago
    A 1.00001x speedup really isn't worth getting out of bed for unless you're working in a very specialised environment; your time is likely worth a lot more than whatever you saved.

lmm 9y ago

Because using a better algorithm is more like a factor of 100 or 1000. Factors of 2 are just not worth bothering with; if the business is so marginal that a factor of 2 in the hardware requirements makes a noticeable difference then you don't want to be in that business in the first place.

w0utert 9y ago
That makes no sense at all. Only if you presume you are always going to start with some horrible piece of code that only uses the worst possible algorithms you may get that kind of speedup. And after you got your 100x to 1000x speedup, or if you start with a piece of code that already is quite efficient, it could still be 2x too slow to meet some hard realtime performance constraint. Or it could be fast enough, but you could potentially save 2x computing power that can be used for other tasks, just by letting the compiler optimize your code. If I tell my employer I'm not interested in getting a 2x speedup by flipping a compiler switch, but prefer to spend an uncertain time looking for or inventing this hypothetical algorithm that will give me 100x to 1000x speedup, I don't think they'll be very happy about that. For most of the code we deliver to our customers, a factor 'so marginal as 2x' could literally save them millions of dollars over the lifetime of the software. Two times faster saves a lot of computing time if you have jobs that run for 72+ hours. If only things were as easy as you pretend they are (we already have the 'marginal' 2x from the compiler optimizations, and we already have efficient algorithms)...
- lmm 9y ago
  > Only if you presume you are always going to start with some horrible piece of code that only uses the worst possible algorithms you may get that kind of speedup If we're talking about algorithmic improvements we're usually talking about going from O(n^2) to O(n log n) or similar, which is easily a 100x-1000x or more speedup if your n is big enough to be bothering with performance at all. It's very easy to be accidentally quadratic and this causes a lot of performance bugs. Talking as though algorithmic speedups and optimization speedups are of a similar magnitude is really misleading. > it could still be 2x too slow to meet some hard realtime performance constraint Theoretically it could be, but that would take an incredible amount of luck. There's so much variation in runtime that the odds of getting within a factor of 2x are tiny; more likely you're thousands of times too slow, or thousands of times faster than you need to be. > Two times faster saves a lot of computing time if you have jobs that run for 72+ hours. Sure, if you've got jobs that run for 72 hours in your code (i.e. aren't spending those 72 hours doing something that's already highly optimized in a standard library e.g. linear algebra) and have already carefully optimized your choice of algorithms, then the rules are different. That's a pretty rare case though.
bluGill 9y ago
True, but that assumes a better algorithm exists that can give the 100x speedup. In a good language (most of them) the common algorithms are somehow implemented in the standard library and optimized - I just use them. Once I finished my degree I never wrote sort from scratch, I just looked up the syntax for calling the sort built into my language. Now it is possible that I can do better than the sort built in - but that is because I know my typical data and so I might be able to make a different compromise: we are not talking about a 100x speedup we are talking about a 1.0001x speedup (and that is only after several months of work to replicate tricks the built in sort already does) (technically I have implemented sort since my degree, but it was bogo sort: I obviously did it only for fun)
- lmm 9y ago
  A 1.00001x speedup really isn't worth getting out of bed for unless you're working in a very specialised environment; your time is likely worth a lot more than whatever you saved.