Why Programmer-Specified Aliasing Is a Bad Idea (2004) [pdf] | Hacker News Reader

Why Programmer-Specified Aliasing Is a Bad Idea (2004) [pdf]

citeseerx.ist.psu.edu

39 pointstjalfi26 comments

It's interesting to note that the hesitant adoption of "restrict" in C has affected rust's use of the LLVM implementation of that feature.

In rust, technically almost every pointer is non-aliasing, so you could enable "restrict" (or rather its equivalent down in the LLVM layer) by default for almost every pointer. However, this uncovered many unexercised corner cases where LLVM's restrict implementation appeared broken:

https://stackoverflow.com/questions/57259126/why-does-the-ru...

Scroll down to the answer to see how often noalias was enabled and disabled.

It just got reenabled again.

Are you aware of any interesting benchmarks? I’m curious what the performance difference is in different kinds of applications.

The cited figure is a ~5% performance drop the first time rustc disabled noalias

Note that that's an "up to" 5% drop. Some benchmarks were unaffected, some were only lightly affected.

Until the next miscompilation bug is found, how many times it has been reenabled thus far?

The SO answer has the entire list (Shep' apparently updates it regularly). In stable it had to be disabled twice, though both times it remained disabled for a long while, and the first re-enable was a mayfly (lasted all of 18 weeks):

* initially enabled

* disabled in 1.8

* enabled in 1.27

* disabled in 1.30

* enabled 1.54 (because an issue blocked enabling it in 1.53 which pretty much guarantees there's still a bunch lurking)

(submitter)

Here’s the abstract.

The ISO C standard C99 has added a special keyword, named restrict to allow the programmer to specify non-aliasing as an aid to the compiler’s optimizer and to thereby possibly improve performance. However, it is the programmer’s responsibility to ensure that the annotations are correct. Therefore, in practice, restrict will be useful only when the programmer’s effort is rewarded with noticeable performance improvement. To assess the performance potential of the restrict annotation, we automatically generated best-case restrict annotations for SPEC CPU2000 benchmarks by using pointer profiling. However, even though we used the best possible restrict annotations, we found an average program speedup of less than 1% on average when using two state-of-the art optimizing compilers that implement the restrict pragma. Since the typical performance benefits do not warrant significant user effort and potential errors, we conclude that having the programmer specify non-aliasing is a bad idea.

Apparently the Rust compiler saw a 5% improvement (on average) when they enabled automatic aliasing information (they are now working with LLVM to get it back on).

Note that it is very program dependent, a friend got a 30% improvement on a very specialized numerical simulation.

Yeah, it's highly workload dependent. I've used restrict in anger to accelerate particle systems and we saw a significant speed boost.

Even a 5% speed increase is nothing to discount give that it's "free" once they have LLVM handling it correctly. I agree with the conclusion that if you have to manage the aliasing manually it's very limited in scenarios where you would want to deploy that given the failure modes of getting it wrong.

> Apparently the Rust compiler saw a 5% improvement (on average) when they enabled automatic aliasing information (they are now working with LLVM to get it back on).

For now, it should be part of the next release (1.54).

It was originally slated for 1.53, but then a new miscompilation was discovered during the 1.53 release cycle, so it stayed off.

1.54 landed just the other day, and I didn’t see any mention of noalias in the release notes. I’m curious to see if some of my microbenchmarks improve. And idea what’s going on with it? 1.55 maybe?

https://blog.rust-lang.org/2021/07/29/Rust-1.54.0.html

In Rust 1.54 the option known as `-Z mutable-noalias` is now on-by-default if you're using an LLVM version >= 12 (which includes the LLVM that ships with the official Rust distribution). I suspect it was overlooked in the release notes since the patch enabling it landed a few releases ago, and the patch was never reverted on nightly, only on beta/stable.

The downside is that it's totally out of your control. One small change to your program in a seemingly unrelated area, and suddenly your 5% or 30% improvement may vanish ...

That's the case with tons of compiler optims.

In Rust, that's not true at all. The aliasing information flows out of the type system, which you control. If a reference is marked mutable, the compiler is free to treat it as unaliased, and an unrelated change elsewhere cannot change that.

It goes further- immutable/shared references get the same treatment as they will not change out from under you either.

The thing that disables it is interior mutability- types like `Mutex` or `Cell` that can be mutated through shared references fall back to something like C without TBAA.

`Mutex` (and `RwLock`) should not since they grant exclusive access, should they? As long as the aliasing information doesn't live across lockings, but that doesn't seem like it would happen: each locking would hand out a different guard, and thus a different reference the optimiser wouldn't see relating at all to the previous locking.

Right, you should get noalias optimizations within a particular locking, but not on the outer `&Mutex` references.

The upside is that it doesn't get a consultant calling a functions unaware of its restrict specification and triggering UB, much worse than losing those 5% or 30% improvements.

I'm very curious what interaction there is with compiler-imposed strict aliasing. I can't determine from a scan of the paper what they expected the compiler to do in this regard. I.e., was some equivalent of either `-fstrict-alias` or `-fno-strict-alias` in effect?

I do wonder if there's a chicken and egg issue here, in that it not being used very much means not much effort has been put into optimisations that take advantage of it.

(though by "I wonder" I do not in any way suggest I'm qualified to have an opinion on the compiler internals themselves)

Highly dependant on the actual workload too.

It's worth pointing out that compiler optimizations are not written as a lump of symbolic logic which then automatically goes and finds speed, there does have to be some human written code directing the transformations, so there likely is a chicken and egg here.

One complication is that in situations where aliasing is unlikely but very harmful some compilers already check for aliasing then use an optimized routine rather than a slow one that has to handle aliasing - that means user specified alias hints could only yield the elision of a branch and some instructions rather than a dramatic increase in throughput.

In ClickHouse there is 1.6 times performance improvement after simply adding __restrict in aggregate functions:

https://github.com/ClickHouse/ClickHouse/pull/19946#issuecom...

These low-level things are hardware dependent.

SPARC and Itanium are dead, and these two are the only platforms being benchmarked in the article.

This makes the article useless, we only care about AMD64 and ARM these days.

This is my probe to disable broken restrict implementations

https://github.com/rurban/autoconf-archive/commit/91625ebef2...

Reply on news.ycombinator.com