4 ms·

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;

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.
  - Robotbeat 7y ago
    Thank you for providing better examples. I'm not a computer scientist but a physicist.

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.
- Robotbeat 7y ago
  Thank you for providing better examples. I'm not a computer scientist but a physicist.