Progress In Algorithms Beats Moore's Law

Relic of the Future writes "Seen on the blog 'Algorithmic Game Theory,' a report to congress and the president about past and future advances in information technology notes that, while improvements in hardware accounted for an approximate 1,000 fold increase in calculation speed over a 15-year time-span, improvements in algorithms accounted for an over 43,000 fold increase."

Comments

But we made up in ...

[sourcerror]

more bloated GUI libraries (bling), and comfier runtimes (different VMs).

Re:But we made up in ...

[betterunixthanunix]

Well, the real question is, are users better off as a result? Personally, I found that most of the computationally intensive graphics were not actually helping me get my work done any faster, switched to a more minimal window manager and did all that I could to reduce the amount of CPU time spent on rendering the GUI (disabling special effects wherever I saw them), and discovered that, in fact, I was correct: none of those effects were actually helping me get my work done.

On the flip side, people tend to be turned off when they see what my screen looks like. It has gotten to the point where I do not mention that this is "Linux," because I do not want new users to get scared. In the end, looking pretty winds up being more important than how efficiently you use computational resources.

1000 fold

[MichaelSmith]

Thats an interesting figure because when the alpha came out DEC were predicting 1000 fold improvement in speed over about the same period. They split the improvement over factors of ten: clock speed, parallelism in the CPU and multiple cores were each expected to deliver a factor of ten improvement.

Now while our algorithms might be getting better our programmers definitely are not. A lot of those improved algorithms must be in our APIs. Like the way its easy to use a Hashtable in java now but in the last you might have just searched a linear array.

Re:1000 fold

[jc42]

Now while our algorithms might be getting better our programmers definitely are not.

Sometimes this is intentional. One of the more fun software competitions I've run across is to write the slowest sorting algorithm. Trivial programming tricks such as do-nothing loops that just run a counter to use time disqualify you, obviously. The judging is solely on the algorithm, by comparing the O(N) functions. One of the winners in the early years was a sort that generated a random permutation of the data, and tested it for sortedness, repeating if it wasn't sorted. And it turns out that there are several progressively worse variants of this, depending on how ridiculous your random-permutation algorithm is.

I should go find this contest again, and see what sorting atrocities they've come up with in the past couple years ...

(I did once read a suggestion that such contests not be widely publicised, out of fear that managers will find them and declare the winning algorithms the new company standards. ;-)

What Good Lord Giveth ...

[140Mandak262Jamuna]

What the Good Lord Algorithmic Efficiency Improvements giveth, the Evil Lord Real-Time-Virus-Scanner taketh away.

Transistor increase with software?

[F.Ultra]

So how did they magically increase the number of transistors using software? Oh whait, someone didn't know what Moore's law was...

Not so much

[kasperd]

When hardware gets faster it applies more or less uniformly to all algorithms you run on that hardware. When an algorithm is improved it applies to just one specific problem. For some problems we already knew close to optimal algorithms 15 years ago, in those cases there was no way algorithmic improvements could have achieved such a speedup. And in fact the article mentions just one specific problem where algorithmic improvements made it about 43.000 times faster on one specific input. In other words, this number is not nearly as general as the summary makes it sound. The are algorithms that were not speeded up nearly as much, and for any algorithms that were bad enough to begin with, there could have been an even larger speedup - without anybody making a fuss about it.

Re:Not so much

[QRDeNameland]

Mod parent up. If this claim were true in any generic sense, we'd see newer software generally running ever faster on older hardware, and it wouldn't seem that every generation of hardware improvement goes mostly towards visual eye-candy and anti-virus.

The problems the author cites, notably speech recognition, are cases that are notorious for *not* scaling to CPU power, that is, throwing brute force cycles at the problem only yields marginal benefits. While processing power doubles every 18 months, speech recognition only gets slightly better despite both better hardware and algorithmic advances.

45 years later

[zeroRenegade]

Moore's law is based more on economics than technology. He was just a hands on executive who had a clear vision of what the future would bring. Anybody who actually has read his original paper would realize this. The fact that his theory has held up this long is incredulous.

Re:First post algo

[bersl2]

Doubles and higher-order tuples are an ongoing topic of research, much less mature than research on first posts.

Actual text of statement on relative improvements

[jthill]

Progress in Algorithms Beats Moore’s Law

Everyone knows Moore’s Law – a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.

Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor den- sity into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.

Even more remarkable – and even less widely understood – is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.

The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time. In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later – in 2003 – this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algo- rithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.

The design and analysis of algorithms, and the study of the inherent computational complexity of prob- lems, are fundamental subfields of computer science.