+1

Ya that's a hilariously naive take (the quoted line not your response) given PGO, to say nothing of MLGO.

Pretty sure he means given a single compiler.

The compiler is deterministic - for the same inputs, you'll get the same outputs. Unless you've got memory corruption in it.

Many optimizers (and other algorithms used in compilers) can benefit from some random bits.

Though, of course, in practice you can use pseudo-random bits and fix the seed.

Having a compiler produce different code for the same source is a recipe for "I can't reproduce your bug and can't fix it".

Or unless you iterate over randomized hashtables to produce some output, e.g. function sections in an executable. Though that doesn't change the semantics and is basically rearranging coins in your pocket.

He probably meant that a compiler is a pure function for a given source file and a set of flags. Of course, if you change a compiler or flags, you can get something radically different, but you shouldn't get something radically different because it's Tuesday, midnight, your username starts with n, you have more than 3 hard drives, or because it reads some bytes from /dev/urandom.

It's bit of a stretch, sure, but I don't expect my performance problems to go away by recompiling stuff over and over again without changing either the code or flags and expecting the optimizer to make a better decision next time. It doesn't work that way.

Optimizing compilers often have budgets so you can get different outcomes if performance jitter happens to mean that it bails from some optimization stratagies.

The budgets I've seen have less been "if it's taken N seconds, bail" and more "if we've processed X million instructions, bail." At least in the compilers I work on, nondeterminism is considered a bug, although it can be harder to avoid nondeterminism than you'd think.

>and expecting the optimizer to make a better decision next time. It doesn't work that way

But in practice it does work exactly that way because of PGO and if we're precluding PGO then the observation is as banal as "programs that have no side-effects are pure". Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all.

> Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all.

It is actually a very useful picture especially to a beginner.

PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers. Someone learning to write a compiler does not need to think about PGO. And besides, a compiler with PGO is still a pure function of source + flags + profile.

>PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers.

Both clang and gcc support `-fprofile-generate`. Beyond that generic infrastructure, in my area (DL compilers) if you're not doing PGO/autotuning you're not serious.

>Someone learning to write a compiler does not need to think about PGO.

That's like saying someone learning to write a compiler doesn't need to think about optimization at all - sure maybe the first time. But then every time after that it should be at the forefront of your mind.

> Both clang and gcc support `-fprofile-generate`. Beyond that generic infrastructure, in my area (DL compilers) if you're not doing PGO/autotuning you're not serious.

How many binaries in a typical Linux distro are built with PGO for example? The answer is approximately zero.

Your point? Because your first goalpost was "most compilers don't even support PGO". And now the goalpost is Linux distros? How about this one - how many binaries at FB/G are built with PGO? Answer: a great deal (llvm/bolt is a FB project and MLGO is a G project).

My point is that the view of a compiler as a series of transformation passes from a source program to machine code, implemented as pure functions, is an entirely appropriate way to describe how they work in a random introductory blog post?

Congratulations on your recent PhD in quantum machine learning or whatever -- I hope you find some way to speed up FB/G's ad serving algorithms by 1% and land that promotion. I'm sure you're very smart.

>My point is that the view of a compiler...

Your point in bringing up Linux was to reiterate your original point? Interesting.

> I hope you find some way to speed up FB/G's ad serving algorithms by 1% and land that promotion. I'm sure you're very smart.

lol

I don't remember using PGO like ever. And even if you do use it, isn't it like breaking compilation into two phases that are themselves deterministic?

It is pretty useful picture in my eyes, because that's what I've been observing since like forever. Non-deterministic compiler would be pretty hard to test or reason about.

It might be a banal observation, but an important one if you want to contrast a compiler with something like an OS kernel or most modern programming projects that interact heavily with outside world. When you throw hardware, network traffic, or users into the mix, it gets crazy.

* * *

There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%:

- Bug in your program? Could be a dependency of a dependency built wrong, better do a full clean and rebuild.

- All of your pre-release tests passed? The code you shipped doesn't work, because you hit that unlucky 1%. Imagine how bad this would be back when software was released on CDs...

- Have 70 dependencies which are like this (not hard in the webscale era)? Now your CI needs to retry every build up to 10 times, because every build has a ~63.4% chance of failing. And there's still ~1% chance your CI fails anyways because you got 10 unlucky builds in a row.

I'm sure there are more stories of these kinds of issues...

> There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%:

That's not the only kind of non-determinism, you know?

Lots of algorithms benefits from access to random bits, too.

The context is

> for each input, there is one and only output

A randomized algorithm which uses non-determinism but produces the same output is OK.

Also, psuedo-randomness is OK as long as the same program compiled in the same version of the compiler always gets the same seed.

But if the algorithm can produce different output causing the same program to compile to different assembly, that's a problem. Unless you can formally prove that every possible variation will have the same behavior, but formal methods + non-determinism is hard, so it usually isn't worth it.

Even random hash order in hashmaps can create problems: see https://github.com/rust-lang/rust/issues/84447 and https://github.com/rust-lang/rust/pull/82272#issuecomment-82..., though this is a very small issue in the diagnostic reporter and not a case of 2 valid programs with different semantics.

If you are using something like a SAT solver to produce code, non determinism might be unavoidable. Like, say the solver is heavily multi threaded for perf reasons (these things are slow right?). Or I guess, any FPGA compiler would fit that mold also.

Or anything that compiles a corpus into a model, though we typically call that training rather than compilation :).

Parallel computing can still produce deterministic outcomes, if you are careful.

Having said that, most people are not careful, and most languages make it very hard to be careful.

The keyword is 'deterministic parallelism', if you want to look into the research. See eg https://www.well-typed.com/blog/2012/12/deterministic-parall...

Deterministic parallelism has a non-trivial cost that can negate the perf you were hoping to gain by using multiple cores (or even GPU cores) in parallel.

> Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%

Nondeterministic doesn’t mean random. Consider how NFAs relate to DFAs and then realize the same applies to nondeterministic TMs.

So, the downvotes and replies warrants a follow-up comment.

I support deterministic compilers due to deterministic builds. For a given input source code, compiler executable, and command-line flags, it should always produce the same binary, regardless of the time of day, random number generator, I/O, threading, environment, etc.

My refutation of the article is that he made it sound like a compiler is like computing Fibonacci numbers - here are all the valid inputs, here is how each one maps to its one and only correct output answer, so fill in the code to accomplish that.

Also in the previous paragraph he wrote:

> Because the most basic compiler architecture is standard, you have limited boundaries and degrees of freedom when designing one. This might sound restricting, but actually, it's freeing because you get to play in a predictable sandbox.