Hacker News Reader

Comment by londons_explore | Hacker News Reader

I'm waiting for the day someone manages to get AI to do the job of a compiler...

It's easy to find a sequence of instructions to implement a program, but the challenge is finding a good, small, fast sequence of instructions. The difference between current compilers and the best possible sequence is often 10x, and that difference is worth tens of billions of dollars - since you can reduce your CPU budget by 10x if all your programs run 10x faster.

Searching all possible sequences is infeasible, but it seems very practical to get AI to assist with some kind of directed search. Either additively (starting with an empty program and adding instructions till it correctly implements the programmers program), or subtractively (use a dumb compiler to make an inefficient program, and then use some ML model to decide how to adjust the instruction sequence to be smaller/faster, while remaining correct).

View on HN

There seems to be a lot of research into compiler optimizations guided by machine learning: https://github.com/zwang4/awesome-machine-learning-in-compil...

> starting with an empty program and adding instructions till it correctly implements the programmers program

This would require an algorithm to check if the output program and input program have identical behavior. However, this is impossible as per Rice's theorem.

> However, this is impossible as per Rice's theorem.

You moved a _little_ too quickly.

There exist program-pairs which can be proven equal, and those for whom no proof exists. You can organize the production of new programs into finite steps and organize the act of creating a proof-of-equivalence between the input and output into finite steps, then execute one step of creating a new program candidate followed by one step of finding the equivalence proof for each of the (finite number of) candidate programs created so far. In this way you are guaranteed to find an output program and its equivalence proof whenever such an (input-program, output-program, equivalence-proof) tuple exists.

Finding the equivalence proof is recursive enumeration—the same as creating the program candidates—but in some machine verifiable proofing language.

Speeding this up by leaving out syntactically incorrect programs and equivalent programs, as well as defining the proofing language and implementing the checker are left as an exercise to the reader.

Researches have been using machine learning to identify potential compiler optimizations for many years now. Naturally the problem with doing so is somehow ensuring, with a high degree of confidence, that such optimizations are correct wherever they are used.

Compilers have bugs of course, but I would be very surprised if any workload worth billions of dollars has a 10x problem. All the FAANGs spend millions of dollars on their respective compiler groups, and it is their job to profile and root out such problems.

Often they find fixes that improve this or that internal workload by 0.2% and consider that a big win.

If you have 5x orders-of-magnitude more computing power to stumble into constraints optimization solutions versus very good constraints optimizers. Go ahead and build it while being 10^5 slower and more expensive for no value.

Reply on news.ycombinator.com