Sunday, October 11, 2015

Moore's Law of Code Optimization

An early version of Moore's law is as follows:

HARDWARE: The number of transistors on an integrated circuits doubles every 18 MONTHS.

Moore's law is  often used to refer to the following:

SPEED: The speed of computers due to hardware doubles every 18 MONTHS.

There are other versions as well. I've heard that some versions of it are no longer working  (it couldn't go on forever). But what about the gains made NOT by hardware? Is there a Moore's Law of Code Optimization?

There is! Its called  Proebstring's law

SPEED: The speed of computers due to code opt doubles every  18 YEARS.

The paper pointed to gives evidence for this law.
So is Code Opt worth it? I've heard the following:

1) Some of the Code Opts eventually go into the hardware, so its not quite fair to say that Code Opts improve speed that slowly.

2) Any improvement is worth having.

3) Being forced to think about such issues leads to other benefits.


  1. By code optimization, you mean compiler optimization. What is the cost (including lost opportunity cost) of employing researchers to add such optimizations to compilers? What is the benefit? Even if compiler optimizations improve performance by only 3-4% a year, that can be a huge benefit in terms of time and energy saved. Not to mention the benefits in development time and security from using higher-level constructs, e.g., garbage collection and type safety.

  2. They all suffer from the law of diminishing returns.

  3. There's also the "Full employment theorem for compiler writers": proving programs equivalent is undecidable in general, so no compiler can optimize all programs optimally. (I first heard of it in a compilers class, unsurprisingly :/)

    Hardware designers seem to use automated tools for verification (SAT solvers, solvers for quantified boolean formulas) more than programmers, and there are competitions for improving that kind of program. It may be easier to agree on a standard for Boolean formulas, than programs, so maybe that's part of it. Also, chip designers may have been more careful, because they had to be: producing a new kind of chip is expensive. (I guess it's possible they'll be less careful, as chip fabrication gets easier.)