Thursday, January 29, 2009

Optimal Optimizing Program

create a program that reads a program in machine language and does some periphery optimizations on it wherever it can, even if they're a little expensive

run the program on itself, then modify the program slightly so that, with its improved speed, it can afford to make some more serious optimizations

run the program on itself again, repeat cycle until your program completely refactors machine code to make it better.

the ideal goal would be to make a program that takes a program as input, and gives the most optimal possible program that does the exact same thing. that, per se, may not be practical, but it would be nice to see how far we can go with the idea.

once we have a pretty good optimizing program, we can run it once for a given program, even on a supercomputer if necessary, and then disseminate the result to all the end users.

there probably is not an optimal optimizing program that creates the best possible optimization in earthly time, because even if it had come up with clever ways to make specific kinds of optimizations, it could never *prove* that the result is the best possible optimization, in the most general case, without iterating through every possible program to verify. so a program that does *perfect*, per se, optimization, may not be a useful thing to aim for, that is by trying to optimize a program that originally *does* iterate through every possibility.
that same idea applies if we were to make the best sound compression software, etc.

No comments: