←back to thread

Tree Borrows

(plf.inf.ethz.ch)
565 points zdw | 6 comments | | HN request time: 0.752s | source | bottom
Show context
jcalvinowens ◴[] No.44513250[source]
> On the one hand, compilers would like to exploit the strong guarantees of the type system—particularly those pertaining to aliasing of pointers—in order to unlock powerful intraprocedural optimizations.

How true is this really?

Torvalds has argued for a long time that strict aliasing rules in C are more trouble than they're worth, I find his arguments compelling. Here's one of many examples: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... (the entire thread worth reading if you find this sort of thing interesting)

Is Rust somehow fundamentally different? Based on limited experience, it seems not (at least, when unsafe is involved...).

replies(11): >>44513333 #>>44513357 #>>44513452 #>>44513468 #>>44513936 #>>44514234 #>>44514867 #>>44514904 #>>44516742 #>>44516860 #>>44517860 #
jcranmer ◴[] No.44514867[source]
Take anything Linus says about compilers with a grain of salt--he writes OS kernels, not compilers, and those are pretty different domains.

Alias analysis is extremely important for getting good performance these days--but it should also be remembered that the biggest benefits accrue from the simplest heuristics (like two loads that use the same SSA value as the pointer must alias each other). In LLVM terms, that's BasicAA: a collection of very simple heuristics that primarily amounts to "if we can track down the allocation sites of objects, we can definitively resolve these alias queries; otherwise, we don't know."

The real question that you're trying to ask, though, is what is the value of alias analyses that go beyond the most basic, obvious tests. At the point where the alias queries are no longer trivial to solve, then it's generally the case that what you can do as a result of those queries also shrinks dramatically, pretty much to looking for code motion hazards, and the benefits you get from that are much reduced. One of the experiments I would like to do is measure the total speedup you'd get from a theoretically perfect alias analysis, and my guess is that it's somewhere in the 20% range even on non-HPC code like the Linux kernel [1].

[1] This doesn't account for the heroic optimizations, such as data-layout transformations, that you wouldn't attempt to write without a very high-quality alias analysis. But since we already know that alias analysis doesn't exist in practice, we're not going to attempt those optimizations anyways, so it's not worth including such stuff in prospective speed gains.

replies(3): >>44515164 #>>44517072 #>>44517943 #
1. oconnor663 ◴[] No.44515164[source]
Here's another data point: https://lobste.rs/s/yubalv/pointers_are_complicated_ii_we_ne...

> I spoke to Apple folks when their compiler team switched the default to strict aliasing. They reported that it made key workloads 5-10% faster and the fixes were much easier to do and upstream than I would have expected. My view of -fstrict-aliasing at the time was that it was a flag that let you generate incorrect code that ran slightly faster. They had actual data that convinced me otherwise.

replies(4): >>44515813 #>>44516893 #>>44518168 #>>44522183 #
2. jcalvinowens ◴[] No.44515813[source]
That's really interesting, thanks.
3. naniwaduni ◴[] No.44516893[source]
The counterpoint to this is that if you're willing to accept patching upstream as an option to make "key workloads" (read: partial benchmarks) perform better, what's stopping you from adding the necessary annotations instead?

The answer is basically that you were never going to, you're just externalizing the cost of making it look like your compiler generates faster code.

replies(1): >>44517065 #
4. saagarjha ◴[] No.44517065[source]
Because they require changes in thousands or millions of lines of code.
5. ralfj ◴[] No.44518168[source]
OTOH we have https://web.ist.utl.pt/nuno.lopes/pubs/ub-pldi25.pdf which shows that on a range of benchmarks, disabling all provenance-based reasoning (no strict aliasing, no "derived from" reasoning, only straight-forward "I know the addresses must be actually different") has a much smaller perf impact than I would ever have expected.
6. SleepyMyroslav ◴[] No.44522183[source]
I don't understand how they convinced him that code with limited set of aliasing patches remained 'correct'. Did they do 'crash ratio' monitoring? Disclaimer I had to do that in gamedev on 'postlaunch' for couple of projects. Pretty nasty work.