No Sane Compiler Would Optimize Atomics | Hacker News Reader

No Sane Compiler Would Optimize Atomics

github.com

65 pointsadamnemecek56 comments

Torvalds on memory ordering and clever compilers (http://yarchive.net/comp/linux/memory_barriers.html):

"Compiler people tend to think that people want smart compilers. I as a compiler power-user can emphatically tell you that that isn't true. People want _reliable_ compilers, and they want compilers that can be told to just get the hell out of the way when needed."

I guess I'm largely at the same side of the argument, on the theory that atomics etc. should be used very sparingly by people who know what they're doing and spend time to hand-optimize their code and think it through semantically (and these people aren't helped by the semantics of atomics becoming more complicated for the sake of optimization opportunities), as opposed to other language mechanisms which are used all over the place by everyone, and so with these mechanisms you do gain a lot from clever optimizations. But I understand the other side of this argument...

Torvalds' argument makes for a nice quote but reality tells a different story: If people just wanted a reliable compiler they would use the oldest compiler they could find which is able to compile their code. If it is old all bugs, problems and faults are known. You know how to work around them and nothing can surprise you anymore. The performance may not be great, it may be a bit of a pain to do some things, but you know it all, so it is not great, but reliable.

What people really want is something which is reliable and smart and fast and .. people love smart compilers/programs/whatever, only when those programs fail them they cry "why did you try in the first place? No one wants this"

There's a thin line between smart and crazy. Trying to be always on the right side is one of the hardest parts of software design.

I agree. Another proof is that the people like the -O3 optimization mode, when the -O0 optimization mode provides the same functionality with less compiling time (with the side effect of more run time).

I was under impression that, at least on gcc, everybody uses -O2 and -O3 is reserved for those who have the patience to verify that their software not only still works correctly, but even actually becomes faster.

FWIW, I once tried -O3 on some number crunching code few years ago and results were mixed. Improvements, if any, came from only one or few of the many -f flags enabled by -O3.

Oh, and I also tried -O3 on Gentoo. Some weird gtk crashes, had to rebuild back with -O2.

Of course, everyone wants the best of everything.

When someone says they prefer "reliable over smart," I assume that they mean they want as smart a compiler as possible under the constraint that it has to be reliable first.

And that's reasonable. Small (semantic) changes to code should result in small changes to performance.

> If people just wanted a reliable compiler they would use the oldest compiler they could find which is able to compile their code.

True, but not really possible. For a while, the Linux Kernel keep some support to be compiled with older versions of GCC (2.95 IIRC) because it was faster

However you need modern compilers to be able to support things like: support for modern processors, support for intrinsics, etc

I think that different elements of the language call for a different approach. I believe that everything related to mutable shared state calls for a very conservative compilation approach, because the potential benefits seem to me rather tiny while the potential drawbacks seem very large (since when it comes to race conditions, runtime testing is at its weakest when trying to find bugs in the code generated after a compiler upgrade.) To me it doesn't make sense economically. But this is not the case with a whole lot of other optimizations. I think that making this distinction is my modest attempt at being on the right side on this issue :-)

(So I agree that the original quote taken literally and out of the original context does become a nice talking point contradicted by reality; I think however that it's much more sensible in its original context - and the context of this discussion - this context being optimizing code working with mutable shared state.)

Linus was speaking in context of kernel development. See below and happy trails:

https://lwn.net/Articles/586838/

https://lwn.net/Articles/586957/ [edit: meat here]

Linus ideal memory model is 'DWIM'; to him it is obvious what the compiler should or shouldn't do. When people have asked him to write down exactly the rules he either refused or handwaved it. Unfortunately it is still pretty hard to write a compiler that would exactly replicate Linus thought processes and he also might not appreciate the brain dissection required to do so.

Paul wrote a memory model for Linux, with input from the Linux community: http://wg21.link/p0124r1

Yes, and Paul 'RCU' McKenney actively engaged with the C++ committee during the standardization process, even writing multiple papers, contrary to Linus which assumed that nothing good would ever come from it.

I love the WTF potential of this one:

Another interesting optimization is to use potentially shared memory locations (on the stack, heap and globals) as scratch storage, if the compiler can prove that they are not accessed in other threads concurrently. [..] For example the following transformation could occur:

  // Some code, but no synchronization.
  *p = 1; // Can be on stack, heap or global.

Becomes:

  // ...
  *p = RAX; // Spill temporary value.
  // ...
  RAX = *p; // Restore temporary value.
  // ...
  *p = 1;

Since we write to p and there is no synchronization operations, other threads do not read/write p without exercising undefined behavior. We can therefore use it as scratch storage.

I see no WTF here. Concurrent reads from * p have to be allowed to produce any possible value whatsoever, since if the variable is larger than a system word, the compiler may have to break up the write into multiple instructions (and some architectures don't even have instruction-level isolation).

The language doesn't give you any stricter concurrency guarantees just because a variable is sizeof(void* ). And that's good. It makes the language cleaner. No bullshit special cases that require you to know implementation details. You want atomic behavior, use std::atomic (or a lock), period.

This prevents debugging, probably does not really optimize (except 1% in useless microbenchmarks), and increases compiler complexity and the risk of bugs in it. A similar thing has already happen in the past: compiler started to introduce speculative writes on code pathes where the write did not occur in the source code, and this broke multithreaded programs -- IIRC there was no threading model at that time (the current one forbid to do that kind of thing, and it is probably impossible to get a sound threading model that does not forbid that) but instead of saying that they were technically allowed to do that compiler authors recognized that because it made multithreaded programs impossible to write, that they had to fix their shit.

In the C standard, crashing is not a specified behavior, so when an obscure architecture crashes on a specific construct, the standard has to technically say that this is undefined behavior. That compiler authors now interpret most of undefined behavior as a license to be stupid on ALL architecture instead using their brain and allowing non-portable programs to exist is not them being smart optimizing all our code-bases for free but just a proof they do not understand a part of what they are doing, including the standard they pretend to know so much.

So the position of "all the standard, nothing but the standard" is utter bullshit. Another example: the current published atomic specification is subtly unsound. Do compiler authors do the right thing instead of trying to implement the broken spec, while waiting for the spec to be fixed? On that point yes -- at least for now. So when, on other subjects, they introduce new bugs in compiled code compared to what all previously known compilers produced - and without proving this really improves performance like crazy to justify taking that kind of risk - they are just being dangerous asses. -O2 has shown to be able to be fast enough without (reasonable) code breaking behavior in the past. In most case you wants to keep the same behavior as -O0 built programs. An optimisation that does not preserve behaviors reasonably expected by skilled programmers and requires that every programmer knows the standard by heart at any point of their work under penalty of crashes and security holes is not an optimisation but a piece of crap. This is blurry but the C / C++ standards are blurry and their usage even more so -- and more importantly they do not forbid to stay safe and sane to begin with -- so trying to do formal logic instead of doing engineering by thinking about the whole picture and history is completely stupid.

In this case, the programmer cannot reasonably expect that a concurrent read produces a meaningful result.

There are good reasons to use clean, abstract formal logic over brutish "engineering" that results in a myriad of unmaintainable "if x, y, and z, do this, but not if also a or b, then we do that."

That said, I agree that compilers should not needlessly optimize based on undefined behavior in cases where a sensible architecture-specific behavior can be defined (but turning a "read can produce any value" into a "read can produce high 32 bits from old write and low 32 bits from new write" isn't even worth specifying).

> Another example: the current published atomic specification is subtly unsound.

Can you explain or point us somewhere?

'the current published atomic specification is subtly unsound'

Are you talking about memory_order_consume? Although I believe that correctness proofs have so far excluded memory_order_consume, I do not think the current spec has been shown to be unsound; it is just generally regarded as hard to implement and hard to use correctly. In practice most compilers (conformingly) just lower it to memory_order_acquire; even Linus has been considering doing away with all the dependent load trickery in the kernel and just convert all of them to explicit load acquires.

x86 and SPARC are TSO machines and have zero cost acquires, modern POWERs can also be run in a similar sane TSO mode and ARM64 has cheap explicit load acquire and store release (which I believe were added explicitly to allow simple mapping of the C and C++ memory model). Even Itanic has (I assume cheap) load acquire and store release operations.

Other insane architectures that actually require dependant loads for performance can go and have anatomically impossible sex with themselves.

edit: spelling

The latest on consume: http://wg21.link/p0190r0

The spec is pretty sound, but unimplemented because that's not how compilers work right now for the generality that consume wants. I think the above proposal is likely to work because it's more restrictive towards how consume works, but we need implementation experience.

Linux uses consume extensively for RCU, and I don't think it'll go away soon because of the benefits it provides to Power and ARM. It works through a gentleperson's agreement between Linux's RCU implementation in C and GCC.

There was a recent thread don lkml were after a long discussion on memory_order_consume, Linus wondered what would the cost be of replacing ACCESS_ONCE with a proper acquire. Someone run a test on arm64 and there was no measurable effect. Linus then actively considered the switch. I doubt it will happen right now or even the next few years, but it could happen soon.

IIRC you formally can't promote some memory orders without in some case introducing new behaviors. (You formally can't serialize in some cases, which is quite insane.)

But this is only anecdotal to my point.

What I'm especially against is situations like when we loose a behavior and a culture that was there for C programmers for something like 3 decades, that is rooted on experience on big project with an high number of regular programmers (and not just the Aristotelian idea of what a programmer should be according to (not even really existing) formal logic), and the justification is nothing else than lossy reading of a spec that in a lot of cases never had been written with the intent attributed to it by such compiler authors. Like I said; if you have an obscure arch (and/or mode) on which something results in an undefined behavior, the way the standard is constructed implies it has to call for undefined behavior. At the same time, it is hinted that you should provide stronger guarantee if you can. If e.g. you are considering a shift instruction on your target architecture I see nothing than more appropriate than to map the shift of the langage to such instruction to define the least astonishment behavior. You have no business in the programming langage area if you don't reason like that.

Again: "undefined behavior: behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements" and there even is a note that states: "Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). EXAMPLE An example of undefined behavior is the behavior on integer overflow."

Now the interpretation of those young clueless hippies is most of the time: just fuck the programmer, his program should be able to run on that DSP that does not exist anymore, so let's fuck it as well on x86 so it will crash faster where it ran flawlessly during 3 decades and each one of the hundreds of programmers who reviewed it at that time agreed on what it should do, because at least it will crash faster, and this is what we do now.

And honestly, the only reaction that kind of attitude inspire is: fuck them and that kind of bullshit. I have no confidence in people that even think for 1sec it could a good idea to discuss about how technically uint8_t is not mandated to alias everything, and to my horror I've witness that very thread... When you pretend to be a compiler author and get to that point, you should just change your career before you become too dangerous.

Now for practical purposes, if you want the list of options to get back a half-sane compiler behavior take a look at what Linux uses, because Linus is even less tolerant than I am to technical insanity and wicked default choices. Then triple check the current manpage of your exact version to see if you need to disable some extra "optimizations". Only then you (and your team) can start to program some general purpose stuff without putting your users in danger -- and you should still strive to be as compliant as possible BTW, but that's what of the thing real engineering is about: safety in depth.

> compiler started to introduce speculative writes on code pathes where the write did not occur in the source code, and this broke multithreaded programs

c.f. http://www.di.ens.fr/~zappa/readings/c11comp.pdf

> the position of "all the standard, nothing but the standard" is utter bullshit

I'm pretty sure that wasn't the point.

> the current published atomic specification is subtly unsound

Details? Batty has a few nits for C around memcpy, consume isn't implemented, out-of-thin-air is a theoretical problem, and forward progress guarantees will be added "soon". OTOH I can't think of anything else, but I'm sure I'm forgetting some. IMO none of these are interesting enough to be in the talk, but would make fine references.

> Do compiler authors do the right thing instead of trying to implement the broken spec, while waiting for the spec to be fixed?

Compiler authors are also fixing the spec.

> without proving this really improves performance like crazy to justify taking that kind of risk

That's untrue in most cases, especially when optimizing atomics.

> I see no WTF here.

Not WTF in itself, but has WTF potential. The way I read it is:

If you forget to put synchronization around accesses to global state, in addition to the usual problems, we will also overwrite your globals with random garbage.

Which sounds great when you think about debugging affected code.

> sizeof(void* )

You think that's equivalent to machine word? On 16-bit x86, for example, pointers can be either 16 or 32 bit ;)

> You think that's equivalent to machine word? On 16-bit x86, for example, pointers can be either 16 or 32 bit ;)

The 16bit x86 memory model is absolutely atrocious. And IDGAF what you call a "machine word" on x86, it's a 64 bit architecture grafted onto a historically grown 32 bit architecture grafted onto a historically grown 16 bit architecture grafted onto an 8 bit architecture.

And when Intel tried to do a clean reboot for the 64-bit part, the market chose the grafted-on abomination instead.

Also, you can have 128 bit atomic loads if you use an xmm register. But that's for the compiler to figure out when you declare an std::atomic of a 16-byte large type, not for you to assume on a plain variable, which was my point.

C/C++ language designers used to take the position that concurrency was an OS issue, not a language issue. That came unglued as processors did more and more out of order operations.

C/C++ language doesn't really understand concurrency. Even locking is iffy, because the language doesn't know what data is locked by a lock. Rust, and to a lesser extent Java, associate locks with data, which gives the compiler some info to guide what it can't optimize. C/C++ have a whole series of kludges - "volatile", "atomic", etc., which patch holes in race conditions but don't provide a coherent concurrency model. Which is why we see papers like this.

> C/C++ have a whole series of kludges - "volatile", "atomic", etc., which patch holes in race conditions but don't provide a coherent concurrency model.

Are you aware that C11/C++11 -- the language standards that added atomics -- also defined a coherent memory model?

Volatile is required for working with memory which is subject to change without notice. This is required for signaling that the value may be changed by a physical peice of hardware outside of your control. It's pretty useful.

Nowadays I look at UNIX (or POSIX) as the actual C runtime.

But even that doesn't change much, as the semantics are not consistent across implementations.

"C/C++ language designers used to take the position that concurrency was an OS issue, not a language issue"

That was the case until Bohem's 'Threads Cannot be Implemented as a Library' position paper, which lead the C++ Standard Committee to formally define the C++ memory model (whose correctness was also independently proven [1]). This standardization work was greatly inspired by the corresponding Java MM, and in a break from the past, it explicitly disallowed a few compiler optimizations and even made the C++ standard unimplementable on a few quirky older architectures for the sake of sanity.

Today there are no arguments on whether a concurrent algorithm (and compiler optimizations) is conforming or not, as there are both dynamic and static checkers that can verify it against the C++ memory model.

I wish that the same rigorous formalization work were to be done for the strict aliasing rules of the language, which are still a mess of underspecified, ambiguous and mutually contradicting rules scattered all over the standard document.

[1] the original drafts had in fact issues which were found when attempting the correctness proof; these flaws have been corrected, except there is a still standing issue with out-of-thin-air values; it is not believed to have any impact on code with current compiler and cpus, but there is an ongoing effort to correct it.

> to a lesser extent Java, associate locks with data

I'm not sure that's really true. Yes, monitors are attached to specific objects, but the ordering effects of acquisition and release of a lock apply to reads and writes to all objects, not just the one the lock is attached to.

The presentation is unreadable as it jumps all over the place and requires you to press keys to navigate.

What sane person would write a presentation like this. Horrible to try and read, particularly on a phone. Whatever his message was is lost on me.

A person that thinks compilers should optimize atomics?

A hipster one. Reveal.js presentations are everywhere nowadays.

It's reveal.js, a pox on the already poxy world of presentations.

Press space (as per some other comment there), but I agree

Someone forgot to install a space bar to my iphone

You can probably get around swiping down then right

Really?

There's one on my not-a-iphone.

Indeed. I just read the source at https://raw.githubusercontent.com/jfbastien/no-sane-compiler...

Wow, I was reading yours and others comments and thinking: "it can't possibly be that bad". Then I opened it, and immediately came to the conclusion that yes, it really could.

What's really fascinating is that the presentation isn't even broken. Someone actually designed that mess and thought it was a good idea. Then, someone else looked at it and said: "that's great, I am going to use this for my presentation". What is even worse, this even happened more than once.

It's like authors positively despise their readers, since they obviously don't want them to be able actually consume their content.

Wow that presentation format is precisely not the catastrophe I would expect from someone giving a talk pleading for sanity.

The frame rate and delay on a tablet is horrendous. On some slides I can swipe down and on others I have to swipe left, with no indication which directions are possible, some times I don't know of i can't swipe down or if the page is just loading. Is the presentation linear ot is it supposed to be a 2d grid? If you go to the right then down then left the left will go up instead of actually left.

(If it's not clear you need to navigate the presentation with both left/right and down keys)

You know what? This is getting pathological. It seems keywords are added to ensure serialization/atomicity, then compilers find a way to optimize it away/make it useless, then another thing "now it's the right way" gets added. Rinse, repeat

And most things that are added have some quirks and people trying to play it smart

We already have volatile for "yes, please do this as two separate increments, don't coalesce them". And atomics give you ordering guarantees and mappings to atomic instructions. And fence methods give you full fences where needed.

So we already have all those things you might need, they just got decomposed into different aspects that can be applied separately.

If you use <space> it'll go to the next slide, whether down or to the side.

>It seems keywords are added to ensure serialization/atomicity, then compilers find a way to optimize it away/make it useless

No, what happens is keywords (or more broadly, semantics) are added which provide certain guarantees given certain preconditions. Then, developers write code that depends on those guarantees and fails to meet the preconditions, but happens to work anyway. At some point, the implementation adds some optimization which -- while still providing the appropriate guarantees when the preconditions are met -- breaks that code.

I know C and C++ can be a royal pain in the ass sometimes, but I have little sympathy for developers who flip the "I know what I'm doing, please assume my code is right and make it run fast" switch, then get upset with the compiler when it turns out that their code actually _isn't_ right and the compiler performs an optimization they weren't expecting. If you don't want the compiler to reorder your memory access, then don't fuck around with the memory_order flags.

> Then, developers write code that depends on those guarantees and fails to meet the preconditions, but happens to work anyway.

This reminds me of the memcpy/memmove issue. You should use "move" when areas overlap, not memcpy

The real question is: why are there two versions? Checking if the memory overlap is very cheap compared to copying, let's say 16 elements. And if you're memcpy'ing smaller sizes you can probably do it manually

> I know C and C++ can be a royal pain in the ass sometime

Yes, they lack enough information to know what you are actually trying to do and have to guess a lot of things. Not sure how "C++ smart" are modern compilers. (Example: you pass an object by value, and only read one field, can it optimize this?)

I see they've finally changed the memcpy() specification to forbid overlapping memory areas completely.

Previously, it was defined to copy from low addresses to high addresses, which meant you could use this to fill an array:

    p[0] = 42;
    memcpy(&p[1], &p[0], sizeof(p)-sizeof(*p));

And people did.

The original 1989 ANSI C specification stated, in "4.11.2.1 The memcpy function":

If copying takes place between objects that overlap, the behavior is undefined.

So it has been this way in C since the first official standard. I don't have a first edition K&R so I can't see what that said, though.

Huh. You're quite right.

Well, it may have been undefined, but in practice the behaviour was standardised and couldn't be changed without breaking existing code... which is basically C in a nutshell.

Code like your example would have been broken by real standard library implementations very early in the piece, because even a forward-copying implementation that does word-at-a-time copies (a straightforward and obvious optimisation with real and significant benefits on many machines of the era) would have broken it.

> The real question is: why are there two versions?

Because long long ago, when CPU was slow, and compiler and stdlib were stupid, there were two versions.

> Example: you pass an object by value, and only read one field, can it optimize this?

Yes.

    struct S { int a,b; };
    void foo(int); // Some external function
    void bar(S s) { foo(s.a); }
    void baz() { bar(S{42, 55}); }

compiles the baz function to (-O2 on GCC 4.9)

    movl    $42, %edi
    jmp     _Z3fooi

Copying short non-overlapping chunks of memory is common in a lot of workloads (think manipulation of short strings) and it does happen in tight loops where an overlap check with two additions, two comparisons and two branches is a comparable amount of work to what memcpy() does.

Why should I have to manually implement memcpy() for small sizes when I know the memory won't overlap?

On that particular point of memory orders, this is true.

But on other points about how compiler optimize the simple alternative (-O0) is the binary to be painfully slow, while you still have a dozen of flag to make the binary both fast and safe, but the safe flags are not activated by default. The unsafe mode is activated by default when you compile with -O2. How is this useful? It is just crazy.

I haven't dealt with concurrency in C++ yet, but I definitely agree with the "don't write assembly, file bugs for the compiler instead" methodology. And not because I don't like ASM -- some of my favourite code consists of ASM hacks -- but because better compilers help everyone.

Reply on news.ycombinator.com