Re: Randomized compilation order (was: failure due to compiler?)

The moderator wrote (regarding an aparant randomizing MULTICS compiler):
>[Any idea why they made a non-deterministic compiler?]


I spoke recently with a sometimes compiler writer who said he wrote an
optimizer phase that used randomization to "prime" a heuristic optimization
pass. It would try optimizing N times, each time with a different random
seed, and then select the "best" code by some metric and discard the rest.
The goal was to use a heuristic that was good in big-O and sometimes good in
code quality; the problem was that small (irrelevant) changes in the input
could also cause the heuristic to (quickly) produce rotten output. He said
the result of using the random seeding was a fast compiler that produced
good code and was horrible to debug.


>[I'd be suprised if pruning the worst behavior was intractible.]


I didn't ask about the alternatives. I'm certainly willing to believe there
were better alternatives but that "it seemed like a good idea at the time".
Likewise, the MULTICS compiler (has anybody asked on any of the newsgroups?)
used randomization even though there were good alternatives; for example,
the original author might have been unfamiliar with them. The above example
shows that non-determinism has been done.


;-D on ( Alternative ego ) Pardo
--

Return to the comp.compilers page.
Search the comp.compilers archives again.