4 ms·

>can we further improve the practical performance of general computation by innovation alone? we can improve the performance of average programs by a factor of

>can we further improve the practical performance of general computation by innovation alone? we can improve the performance of average programs by a factor of ~100x simply by more careful software engineering. Don't use python or javascript, optimize code for cpu cache hits, use more cores effectively, etc. However games, maybe only 2x if anything.

segfaultbuserr 7y ago
I was referring to the computational capabilities that hardware can provide, not the performance of an average program. The parent article talks about semiconductor manufacturing, you can save your rants on inefficient and useless programs for another HN article.
- BubRoss 7y ago
  It's not a 'rant'. This is exactly why speeding up CPUs is more difficult, even with billions of transistors. People expect to write whatever they want and have it run faster. 1% of the transistors in a CPU are actually running instructions, the other 99% are trying to keep it busy.
  - segfaultbuserr 7y ago
    > gameswithgo: Don't use python or javascript It is clearly a rant to me! Don't get me wrong, I'm not a huge fan of JavaScript, but discussing about useless programs is simply not what I'm asking here. I'm not interested in how Google Chrome can be 1000% faster. > People expect to write whatever they want and have it run faster. 1% of the transistors in a CPU are actually running instructions, the other 99% are trying to keep it busy. I agree, now, your perspective makes the talk on software interesting. Recently I've seen an article C Is Not a Low-level Language (https://queue.acm.org/detail.cfm?id=3212479 https://queue.acm.org/detail.cfm?id=3212479), in the article the author argued that the in-order, synchronous, sequential execution model from the PDP-11 heyday is outdated. However vast majority of programs (i.e. C programs) are still written based on this model, so a CPU must use a lot of resources to dispatch these sequential code and introduce countless transparent optimizations (e.g. ILP), to make existing sequential code faster, on the other hand, the compilers are becoming monsters because they must be as intelligent as possible to understand the algorithms in a program and rewrite them automatically for optimum performance on a modern CPU. As a result of this disparity, the capabilities of what the hardware can actually provide is often underutilized. The author purposes that we should try discarding the PDP-11's classical "in-order, synchronous" view of a program, and try developing new programming languages and models that designed with the capabilities of modern hardware in mind, such as low-level parallelism to eliminates this disparity. So the CPUs can focus on what they are good at with less overhead of dispatching the instructions.
- dang 7y ago
  Personal attacks will get you banned here, regardless of how wrong or off topic some other comment is. Would you mind reviewing https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and using this site as intended? We'd appreciate it.
mjburgess 7y ago
I'd guess the downvotes are for exaggeration. Your basic point is correct. We have actually got 20%+ of speed ups in the last 30 years from better algorithms; not just better hardware. Many programs are I/O limited and wouldn't see 100x from more effective CPU use (eg., Word). Others need complete re-writes (eg., browsers) and are typically heavily optimized already. I'd say we could squeeze another generation of Moore's Law just from software design; and another still from algorithm research.
- Robotbeat 7y ago
  For many classes of algorithms, the speed-up is actually better than Moore's Law. I don't think it's really an exaggeration to say that optimization of the programs can lead to 100x performance improvements. Sorting algorithms, for instance, improved dramatically from the first computer algorithms in the early 50s (yay Bubblesort) to QuickSort in the 1960s to newer algorithms in the 1980s/90s like Melsort, and even algorithms being written today, like Neatsort: https://arxiv.org/abs/1407.6183 https://arxiv.org/abs/1407.6183 And the thing about algorithms is that for certain problems and large n, they can quickly blow up. Something with just a slightly better big-O could easily mean a 100x better performance at large n.
  - mjburgess 7y ago
    Well, specific tasks in some programmes are sensitive to these improvements. But since only a fraction of their run time is typically spent in them, the overall improvement wouldnt be 100x.
    - kragen 7y ago
      Occasionally this is true, but often it is not; see the examples in my comment above.
  - kragen 7y ago
    Radix sort predates the 1950s (perhaps it dates from the 1890 US census?), and mergesort (linearithmic, like quicksort) dates from at least the 1950s, if not earlier. I'm not sure when the linear-time variants of radix sort were discovered; it might have been later. I agree that many problems have experienced super-Moorean algorithmic speedups, but the examples I'd point to might be solving large linear systems (successive over-relaxation), integer factorization, suffix-array computation, and all kinds of search problems, especially including SAT and SMT, rather than sorting of records.
bluGill 7y ago
Of course with optimization the question is always is it worth it. Make Word 1000% faster and it won't make a difference to me as most of the time word is waiting for me to press the next key. Of course this is a reflection of me: I don't use Word much and when I do I'm not using even 2% of what it can do. I'm sure Microsoft knows of areas that if they could improve it would make a difference to power users.
hindsightbias 7y ago
In my average view, Knuth was wrong about optimization. Not technically, but because the vast majority of people writing software took "premature optimization is the root of all evil" to be "optimization is the root of all evil." I have a long list of encountering software doing things like reading a billions of rows with getline() in C++. That can be a problem [1]. It doesn't matter how good a heapsort is if it's blocked on some architectural primitive and we'd do better to teach to that optimization in CS 101 than sorting. 1. https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/ https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/
tracker1 7y ago
It depends on what you are doing... Modern desktop, and most mobile devices are just fine running CRUD apps written in JS. Same goes for a lot of server processes. That's not to say anyone should be using it for intense algorithmic processes. A lot of what is currently in Python for ML will likely move on to another language, or we may see better AOT and other optimizations for Python itself. As with all things, it depends on what your needs are and what you are doing. Modern hardware is pretty damned good, and most apps don't need more than what we already have. Or have had for a decade or more at this point.

segfaultbuserr 7y ago

I was referring to the computational capabilities that hardware can provide, not the performance of an average program. The parent article talks about semiconductor manufacturing, you can save your rants on inefficient and useless programs for another HN article.

BubRoss 7y ago
It's not a 'rant'. This is exactly why speeding up CPUs is more difficult, even with billions of transistors. People expect to write whatever they want and have it run faster. 1% of the transistors in a CPU are actually running instructions, the other 99% are trying to keep it busy.
- segfaultbuserr 7y ago
  > gameswithgo: Don't use python or javascript It is clearly a rant to me! Don't get me wrong, I'm not a huge fan of JavaScript, but discussing about useless programs is simply not what I'm asking here. I'm not interested in how Google Chrome can be 1000% faster. > People expect to write whatever they want and have it run faster. 1% of the transistors in a CPU are actually running instructions, the other 99% are trying to keep it busy. I agree, now, your perspective makes the talk on software interesting. Recently I've seen an article C Is Not a Low-level Language (https://queue.acm.org/detail.cfm?id=3212479 https://queue.acm.org/detail.cfm?id=3212479), in the article the author argued that the in-order, synchronous, sequential execution model from the PDP-11 heyday is outdated. However vast majority of programs (i.e. C programs) are still written based on this model, so a CPU must use a lot of resources to dispatch these sequential code and introduce countless transparent optimizations (e.g. ILP), to make existing sequential code faster, on the other hand, the compilers are becoming monsters because they must be as intelligent as possible to understand the algorithms in a program and rewrite them automatically for optimum performance on a modern CPU. As a result of this disparity, the capabilities of what the hardware can actually provide is often underutilized. The author purposes that we should try discarding the PDP-11's classical "in-order, synchronous" view of a program, and try developing new programming languages and models that designed with the capabilities of modern hardware in mind, such as low-level parallelism to eliminates this disparity. So the CPUs can focus on what they are good at with less overhead of dispatching the instructions.
dang 7y ago
Personal attacks will get you banned here, regardless of how wrong or off topic some other comment is. Would you mind reviewing https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and using this site as intended? We'd appreciate it.

mjburgess 7y ago

I'd guess the downvotes are for exaggeration. Your basic point is correct. We have actually got 20%+ of speed ups in the last 30 years from better algorithms; not just better hardware. Many programs are I/O limited and wouldn't see 100x from more effective CPU use (eg., Word). Others need complete re-writes (eg., browsers) and are typically heavily optimized already. I'd say we could squeeze another generation of Moore's Law just from software design; and another still from algorithm research.

Robotbeat 7y ago
For many classes of algorithms, the speed-up is actually better than Moore's Law. I don't think it's really an exaggeration to say that optimization of the programs can lead to 100x performance improvements. Sorting algorithms, for instance, improved dramatically from the first computer algorithms in the early 50s (yay Bubblesort) to QuickSort in the 1960s to newer algorithms in the 1980s/90s like Melsort, and even algorithms being written today, like Neatsort: https://arxiv.org/abs/1407.6183 https://arxiv.org/abs/1407.6183 And the thing about algorithms is that for certain problems and large n, they can quickly blow up. Something with just a slightly better big-O could easily mean a 100x better performance at large n.
- mjburgess 7y ago
  Well, specific tasks in some programmes are sensitive to these improvements. But since only a fraction of their run time is typically spent in them, the overall improvement wouldnt be 100x.
  - kragen 7y ago
    Occasionally this is true, but often it is not; see the examples in my comment above.
- kragen 7y ago
  Radix sort predates the 1950s (perhaps it dates from the 1890 US census?), and mergesort (linearithmic, like quicksort) dates from at least the 1950s, if not earlier. I'm not sure when the linear-time variants of radix sort were discovered; it might have been later. I agree that many problems have experienced super-Moorean algorithmic speedups, but the examples I'd point to might be solving large linear systems (successive over-relaxation), integer factorization, suffix-array computation, and all kinds of search problems, especially including SAT and SMT, rather than sorting of records.

bluGill 7y ago

Of course with optimization the question is always is it worth it. Make Word 1000% faster and it won't make a difference to me as most of the time word is waiting for me to press the next key. Of course this is a reflection of me: I don't use Word much and when I do I'm not using even 2% of what it can do. I'm sure Microsoft knows of areas that if they could improve it would make a difference to power users.

hindsightbias 7y ago

In my average view, Knuth was wrong about optimization. Not technically, but because the vast majority of people writing software took "premature optimization is the root of all evil" to be "optimization is the root of all evil." I have a long list of encountering software doing things like reading a billions of rows with getline() in C++. That can be a problem [1]. It doesn't matter how good a heapsort is if it's blocked on some architectural primitive and we'd do better to teach to that optimization in CS 101 than sorting. 1. https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/ https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/

tracker1 7y ago

It depends on what you are doing... Modern desktop, and most mobile devices are just fine running CRUD apps written in JS. Same goes for a lot of server processes. That's not to say anyone should be using it for intense algorithmic processes. A lot of what is currently in Python for ML will likely move on to another language, or we may see better AOT and other optimizations for Python itself. As with all things, it depends on what your needs are and what you are doing. Modern hardware is pretty damned good, and most apps don't need more than what we already have. Or have had for a decade or more at this point.