|Re: failure due to compiler? firstname.lastname@example.org (1996-07-04)|
|Randomized compilation order (was: failure due to compiler?) email@example.com (1996-07-13)|
|Re: Randomized compilation order (was: failure due to compiler?) firstname.lastname@example.org (Darius Blasband) (1996-07-24)|
|Re: Randomized compilation order (was: failure due to compiler?) email@example.com (Matthew B Grice) (1996-07-26)|
|Re: Randomized compilation order (was: failure due to compiler?) firstname.lastname@example.org (1996-07-31)|
|From:||email@example.com (David Keppel)|
|Date:||31 Jul 1996 19:25:02 -0400|
|Organization:||Computer Science & Engineering, U of Washington, Seattle|
|References:||96-07-041 96-07-172 96-07-181|
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
Search the comp.compilers archives again.