<p>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.</p>

<p>see [1] or [2] which states</p>

<blockquote>
  <p>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.<br>
  ...<br>
  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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>the actual quote from the report is on page 71:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>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":</p>

<ul>
<li>the rise of "Exascale" supercomputing may not be as readily achieved as "Petascale" due to hardware scaling constraints</li>
<li>clock speeds, a main drive of prior speed gains, have plateaued (partly due to heat/cooling constraints)</li>
<li>hardware is undergoing a massive shift toward less compute intensive, more energy efficient devices eg mobile, datacenters/virtualization/cloud etc</li>
<li>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)</li>
</ul>

<hr>

<p>[1] skeptic.se, <a href="https://skeptics.stackexchange.com/questions/9011/does-progress-in-algorithms-beat-progress-in-hardware">does progress in algorithms beat progress in hardware</a></p>

<p>[2] <a href="http://bits.blogs.nytimes.com/2011/03/07/software-progress-beats-moores-law/" rel="nofollow noreferrer">Software progress beats Moores law</a> NYT blog by Lohr</p>

<p>[3] <a href="http://www.whitehouse.gov/sites/default/files/microsites/ostp/pcast-nitrd-report-2010.pdf" rel="nofollow noreferrer">REPORT TO THE PRESIDENT
AND CONGRESS
DESIGNING A DIGITAL FUTURE:
FEDERALLY FUNDED RESEARCH
AND DEVELOPMENT IN
NETWORKING AND INFORMATION
TECHNOLOGY</a> Dec 2010</p>

CC BY-SA 3.0
2012-10-12T00:44:14.623Z
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?
vzn
CC BY-SA 3.0
2016-06-15T03:50:07.813Z
This is a *great* answer - full of details, nuance, and knowledgable discussion!
Joshua Grochow
CC BY-SA 3.0
2012-10-11T18:30:01.907Z
2012-10-11T18:30:01.907Z
2017-04-13T12:46:46.700Z
vzn
<p>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?</p>

CC BY-SA 3.0
2012-10-11T13:09:19.850Z
Probably a better fit for cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2012-10-11T15:40:56.493Z
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....
vzn
<ds.algorithms><reference-request><big-picture><ar.hardware-architecture>
Speedup from algorithmic advances vs. hardware
John
# Speedup from algorithmic advances vs. hardware

(Asked by: username_0 on 2012-10-11)

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?

**Tags:** ds.algorithms, reference-request, big-picture, ar.hardware-architecture

> **Comments:**
> **username_1**: Probably a better fit for cs.stackexchange.  
> **username_2**: 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....  

---

## 1 answers

### Answer by username_2 on 2012-10-11. Score: 9 | Accepted answer

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](https://skeptics.stackexchange.com/questions/9011/does-progress-in-algorithms-beat-progress-in-hardware)

[2] [Software progress beats Moores law](http://bits.blogs.nytimes.com/2011/03/07/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](http://www.whitehouse.gov/sites/default/files/microsites/ostp/pcast-nitrd-report-2010.pdf) Dec 2010

> **Comments:**
> **username_2**: 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?  
> **username_3**: This is a *great* answer - full of details, nuance, and knowledgable discussion!  

---

