Most active commenters
  • jcranmer(3)
  • jcalvinowens(3)

←back to thread

Tree Borrows

(plf.inf.ethz.ch)
572 points zdw | 15 comments | | HN request time: 1.27s | 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 #
1. 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 #
2. 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 #
3. jcalvinowens ◴[] No.44515813[source]
That's really interesting, thanks.
4. 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 #
5. saagarjha ◴[] No.44517065{3}[source]
Because they require changes in thousands or millions of lines of code.
6. jcalvinowens ◴[] No.44517072[source]
> Take anything Linus says about compilers with a grain of salt

I think he's making an argument about CPU behavior here more than about compilers: if we call loads and stores which aliasing optimizations might remove "redundant", he's saying that modern machines with big caches and store buffers make those "redundant" operations so cheap they don't matter in practice for most workloads.

Of course, it's admittedly an oversimplification to reduce aliasing optimizations to simply eliminating loads and stores, you described things which go beyond that.

However, I just ran a silly little test where I added `-fno-strict-aliasing` to CFLAGS and rebuilt the world on one of my gentoo build machines, it only got 1.5% slower at compiling an allmodconfig linux kernel (gcc-14):

    Before: 14m39.101s 14m42.462s 14m41.497s 14m44.540s
    After:  14m54.354s 14m54.415s 14m55.580s 14m55.793s
That's on a shiny new znver5.
replies(1): >>44519944 #
7. kunley ◴[] No.44517943[source]
Maybe Linus by writing kernels, not compilers, has even more to say, because his use-case is much more practical than anything that compiler designers could imagine.
replies(2): >>44520924 #>>44534425 #
8. 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.
9. sapiogram ◴[] No.44519944[source]
Very cool benchmark, thanks!
10. jcranmer ◴[] No.44520924[source]
That's kind of a rude thing to say, suggesting that compilers aren't real programmers. Nevertheless, it is the case that most optimizations in the compiler are motivated by real issues with somebody's code, as opposed to compiler engineers thinking up optimizations in their heads.
replies(1): >>44523330 #
11. 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.
12. kunley ◴[] No.44523330{3}[source]
So, if my sentence is rude, and "take anything Linus says about compilers with a grain of salt" isn't, then I definitely quit this discussion.
replies(2): >>44524193 #>>44527040 #
13. jcranmer ◴[] No.44524193{4}[source]
I'm suggesting that Linus isn't the best person to be used as an expert in compilers because his field isn't in compilers.

You're suggesting that someone who works on compilers shouldn't be used as an expert in compilers because their field is in compilers.

There is a difference between those two statements, and that difference is what makes one rude where the other isn't.

14. dwattttt ◴[] No.44527040{4}[source]
Your statement

> by writing kernels... his use-case is much more practical than anything that compiler designers could imagine.

States that compiler designers cannot even imagine the practicalities needed to write kernels. Which is quite a blanket statement to try to make and defend.

15. tomjakubowski ◴[] No.44534425[source]
Compilers are practical too, software tools used all the time. They're just as fundamental to building software as an operating system kernel is to running software. I don't know what point you're trying to make.