14
$\begingroup$

I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does anyone know the study or article?

$\endgroup$
  • 8
    $\begingroup$ Probably a better fit for cs.stackexchange. $\endgroup$ – Yuval Filmus Oct 11 '12 at 13:09
  • $\begingroup$ there is indeed a big paradigm shift within last few yrs wrt moores law, clock speeds, and parallelism & that has been covered in many articles/papers.... $\endgroup$ – vzn Oct 11 '12 at 15:40
8
$\begingroup$

this is an unintentionally complex question. this idea that software gains have outpaced hardware gains is apparently rooted in a real govt report but (as your question indicates) possibly approaching minor urban legend status due to being misunderstood or misinterpreted. the summary/sound-bite headlines do not really match the actual point being made in the report.

see [1] or [2] which states

A report by an independent group of science and technology advisers to the White House, published last December, cited research showing that performance gains in doing computing tasks that result from improvements in software algorithms often far outpace the gains attributable to faster processors.
...
But the White House advisory report cited research, including a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million. Of the total, a factor of roughly 1,000 was attributable to faster processor speeds, according to the research by Martin Grotschel, a German scientist and mathematician. Yet a factor of 43,000 was due to improvements in the efficiency of software algorithms.

but the issue of software vs hardware is very far from this one dimensional simplification, much more complex, and Lohrs blog has it more accurate— software and hardware form a sort of yin-yang symbiotic fusion and both have advanced very significantly, even staggeringly over the decades.

caveat/fine print: one cannot take individual gains in particular software algorithms, which in some cases have been very substantial, and generalize that across all algorithms.

the actual quote from the report is on page 71:

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.

so this government report is highly researched and polished, the basic claim of massive gains due to theoretical software advances in some areas is correct, and is promoting (theoretical/algorithmic) research partly on that basis.

however there are several other new/recent fundamental/massive phenomena/trends/shifts in recent years or what Intels Grove calls "inflection points" that are occuring in hardware vs software design. aka "gamechangers":

  • the rise of "Exascale" supercomputing may not be as readily achieved as "Petascale" due to hardware scaling constraints
  • clock speeds, a main drive of prior speed gains, have plateaued (partly due to heat/cooling constraints)
  • hardware is undergoing a massive shift toward less compute intensive, more energy efficient devices eg mobile, datacenters/virtualization/cloud etc
  • improving parallelism in software and hardware (eg "multicore") is therefore becoming more critical for performance improvements (where theory has a lot to say about how to parallelize algorithms)

[1] skeptic.se, does progress in algorithms beat progress in hardware

[2] Software progress beats Moores law NYT blog by Lohr

[3] REPORT TO THE PRESIDENT AND CONGRESS DESIGNING A DIGITAL FUTURE: FEDERALLY FUNDED RESEARCH AND DEVELOPMENT IN NETWORKING AND INFORMATION TECHNOLOGY Dec 2010

$\endgroup$
  • $\begingroup$ addendum. there are probably some good (counter)examples of important algorithms that have not advanced at all in efficiency of implementations over the decades. ideas? one candidate area might be matrix algorithms that are not parallelizable or other algorithms that seem to be inherently non-parallelizable... also, some algorithms have undergone theoretical improvements in lower bound complexity but the algorithms are not actually implemented or are not feasible for typical-sized inputs etc... eg matrix multiplication? $\endgroup$ – vzn Oct 12 '12 at 0:44
  • 1
    $\begingroup$ This is a great answer - full of details, nuance, and knowledgable discussion! $\endgroup$ – Joshua Grochow Jun 15 '16 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.