Hacker News Reader

Comment by tadeegan | Hacker News Reader

Compilers have soooo many heuristics. And a lot of it looks like a chess or Go game: You have a list of 100s of AST optimization passes (possible moves) that preserve the semantics of the program but you have limited compute with which to run iterations of these passes. What order and combination of these should you use?

View on HN

This is known as the "phase ordering problem". Despite the super-exponential (even unbounded, because phases can be repeated) space, I think this is more tractable for certain subsets. For example, in sea of nodes compilers, like HotSpot, Graal, and TurboFan, forward dataflow analyses that do reductions (i.e. always make the graph smaller and/or cheaper) can be combined into one mega-pass where they positively interact each other. The problem is that some problems are not forward data flow problems and some transformations are not simple reductions. Also, some phases make use of type information which can be destroyed or obscured by lowering.

In general, every heuristic in systems programming --- kernels z compilers, databases, whatever --- is an opportunity to substitute an ML system.

today, learned heuristics have a couple of pitfalls that make them hard to add to such systems

1. they are usually hard to run efficiently

2. they are usually hard to explain

The former is definitely changing with low precision formats like fp16 and useful coprocessors that can do matrix multiplications efficiently (M1, Intel). The latter hasn't been developed much and unless you're just training a model to memorize the entire space the heuristic operates in, it can be scary to trust it on unseen data.

From my work, I've found it's really simple and straightforward to apply.

1. Choose a parameter for your compiler, xxx.

2. Have your ML model "choose compiler config parameter yyy." After the ML model "chooses" the config parameters, work backwards.

3. Determine why yyy is a better config parameter than xxx.

It might not be!

This system works, brilliantly. Cyborg intelligence, a combination of the human being and the ML model, is the future of society.

The key is the ML "suggests." ML must keep "suggesting."

Never have ML choose a parameter autonomously.

That's exactly how you get self driving cars running over children.

> Choose a parameter for your compiler, xxx

Most interesting cases don't really look like this. The heuristic is applied to the user's code; it's not a one-time knob in the compiler. If it were, then you would likely be able to afford an exhaustive search to pick it & wouldn't need ml.

Depends on the domain.

The analogy I'm making doesn't especially apply to compilers, which have human defined defaults in the first place.

What I've found is that it's important to not run the ML model then use its output as the default state. Have a human, heuristic choice as the default state.

Also, they are not stable. I.e, if you have a fast program and you change a tiny detail, it is not guaranteed that the program remains fast. Also between versions of the compiler.

Which you should use are often unknowable because it's often about how the code is driven by the data - you need to know the characteristics of the data to know how the code will behave, only then can you meaningfully talk about picking a 'better' heuristic.

Analogy: otherwise you're just optimising the design of a car. But optimising it for what? speed, efficiency, reliability, price, weight, carrying capacity... You first need to know how it's expected to be used.

I guess local inlining might sometimes be an unconditional win, but even then only under specific circumstances.

(disclaimer: I know something but am not an expert)

Profile guided optimisation is a thing.

You are quite right, I should have stated that.

Well, in this case, TFA:

> Better code optimization can significantly reduce the operational cost of large datacenter applications

They’re aiming to spend a bit more time compiling models, to reduce the scaled operational costs moving forward.

Reply on news.ycombinator.com