Why aren't whole program optimizations more prevalent now?

Main question: Why aren't general or even specialized whole program optimizers part of our daily lives?

I started thinking about this after reading SuperCompilers, LLC's White paper, which discusses their method of "supercompiling" or metacompiling a program's source to (generally) achieve a faster version that does the same functionality as the original program. Essentially they step through a program's execution and recompile to the same target language. By doing this, natural optimizations occur; for instance, a general binary search function might be specialized to binary search an array of 100 items, if the input program uses arrays of 100 items frequently.

Partial Evaluation is a perhaps a more narrow type of whole program optimization, where the program's source is reduced/evaluated based on some fixed set of input while leaving unknown input open to be evaluated at runtime. For instance, a general function x ^ y, if given that y = 5, can be reduced to x ^ 5 or perhaps something like (x * x) * (x * x) * x.

(I apologize for my crude descriptions of these two techniques)

Historically whole program optimizations such as the two above would be too memory intensive to perform, but with our machines have gigs of memory (or using something like the cloud), why haven't we seen lots of open source partial evaluators and the like spring up? I have seen some, b开发者_StackOverflowut I would have thought this would be a regular part of our tool chain.

• Is it fear (programmer fearing the transformation of their code introducing bugs)?
• Is it just not worth it (i.e. for web apps the bottleneck is I/O, and this kind of optimization seems to be saving CPU time)?
• Is this kind of software just that difficult to write?
• Or, is my perception of this just wrong?

I think it's mostly that your perception is wrong. Most compilers support "whole program" (interprocedural) optimizations, and profile-guided optimization to guide the optimizer based on actual use.

The main reason most people haven't noticed is that in the end, these rarely make enough difference to really notice are care much about. General availability of such tools also happened around the time that they just didn't matter a lot for most purposes. CPUs are now so fast that nobody thinks twice about having code running on a java virtual machine, which is itself running inside something like a VMWare virtual machine (and it wouldn't even be particularly rare to have a third virtual machine layer).

That adds overhead that dwarfs the improvement you can typically expect from global optimization. For most people, speed differences have to be quite large to matter at all anymore (and improvements from global optimization rarely qualify).

Thanks for asking what I consider a deep question, and please forgive my flame...

Partial Evaluation is a beautiful concept whose beauty has been totally lost in the seemingly endless desire to build clever but brainless tools to take things out of the hands/minds of programmers. That's why it hasn't done much.

Whenever you write a program A that writes a program B (which is a basic skill that every programmer (in my opinion) should know how to use, and when to use) you are doing partial evaluation. Since some of the input data is known early and does not change often, there's no need for the program to keep testing what it is all the time. You can take the information that hardly ever changes and pass it as input to A, and have A print out the program B that simply "knows" the static input, so all it has to do is handle the unpredictable dynamic input.

But as soon as somebody tries to write a tool to do partial evaluation, they are taking the programmer's brain out of the loop, and that's what kills it.

The same goes for optimization in general. When the programmer surrenders his/her judgement to a tool, very little results, because there is no tool (yet, at least) that can comprehend the code the way the programmer does.

It is certainly worthwhile to try to make tools that understand the code as well as the programmer does, but it is silly to assume that it has been done.

My guess is that it is a chicken egg problem, let me explain this.

With Supercompilation (SC) the programmer can write more abstract code without paying the runtime costs (for the release build, it may be impractical to do it for every debug build).

So if there (today) no SC's are around, programmers write "low level" code, so nobody writes better code and needs SC's to do the heavy lifting.

The only thing which may prevent SC in the real world is the need for a (very) high level of intelligence for whole program supercompilation. OpenCog or any other AGI-ish AI may be a great help to solve this last problem. This is not the case if only small parts should be SC'ed (like single methods).

Another reason, that SC isn't today common, is that it is relativly new (compared to much older compilation technology), SC was developed in the 70's and the compilation costs scale nonlinear, so its not a target of the big compiler vendors.

With more abstract code I mean

• ability to write datatype independent code, so it would in the end make templates/generics obsolete (for the most part)
• the programmer can invoke at any point any kind of a interpreter, the SC should be in the most cases be able to optimize it completly away so the end result looks like a handcrafted version of the code the programmer has in mind. Without the need to do the manual "unrolling" and a much higher productivity (because the programmer doesn't need to modify the "low level" code, he can work on a much higher level