Well, think of it this way, if you're not into compilers wouldn't you expect your code to run as written? Especially if you put a breakpoint in there and you can see each step happening sequently. I don't really think people that don't know these things should be viewed as ignorant because the compiler tends to be doing some very unintuitive things. IMO everyone would be better off if somehow the tooling or the compiler could report some of these things in an easy to visualize not-super-verbose way.
But the possible and actual interleavings aren't written in the program - so how can I guess what the user needs from what's written?
When trying to reason about code, finding somethings that looks like a bug but isn’t can result in a lot of wasted effort.
That's like synchronised in Java or any other kind of atomic block or serialising block - that's already a thing.
You set the direction not me! You asked me 'would you like some way to be informed that [the interleaving is] impossible'. Yes... and the user gives me that information through a synchronised block. If they don't tell me they want an interleaving to be impossible then why should I not make it possible? There are countless other interleavings I make impossible or possible when I do any trivial compiler task such as scheduling. Should I consult the user on all of them? I don't think you'd like all the questions you'd get!
Or they could program against the spec and not worry.
That's not a guess - the user didn't put anything in between them so we know they haven't required them to be separate.
Keeping them separate would be making the guess - a guess that they need them to be separate. Why should we invent that constraint when the user never wrote it?
> Not guessing would mean generating the code as specified.
We are generating it as specified - nothing in the specification says atomic actions have to be run independently. Why should I invent extra constraints that don't exist in the specification?
Why do you expect that? Nobody ever promised you that. If you expect something you weren’t promised then that’s on you.
> If I end up with one, they werent really "atoms" were they?
Atomic has a technical definition - it means either applied fully or not at all. That doesn’t preclude combining.
> what you are doing is undeniably changing the meaning of the program
It doesn’t! According to the spec we’re both working off. If you think the spec is wrong then change it. But I can’t guess what you want unless you tell me using the spec.
Because I wrote it?
> Nobody ever promised you that.
I just assumed that compiler writers had empathy for humans, my bad.
> It doesn’t! According to the spec we’re both working off. If you think the spec is wrong then change it. But I can’t guess what you want unless you tell me using the spec.
How big is the spec and how many working programmers do you think are super intimately familiar? Do you think this article would be on the front page if this information wasn't surprising? Are you building a compiler for humans, or are you just chasing metrics and getting the smug satisfaction of telling users "I told you so" when shit doesn't work in an intuitive way?
If you want to beat me over the head with "the spec says", you win, master language lawyer. I build things for a living and I like it when the code I specify is the code that's generated. You can blame users all you want, but maybe after the trillionth zero day exploit because nobody gets these things right you might consider empathy and developer ergonomics.
Okay, then specify -O0 and enjoy your dumpster fire performance.
But you aren't specifying it!
You're asking me to follow extra constraints that you haven't written down and we haven't agreed. Don't you think it's unreasonable when you say it out loud like that?
If you want extra constraints on top of what is already agreed in the spec then we can do that, but you have to ask for it and you have to bring me a workable spec. You want me to 'intuit' but really you want me to read your mind and follow a lot of unwritten rules!
And frankly, here's the thing: I don't care that much about most of your optimizations. If I'm making my code fast, what I'm fretting about is designing my data structures to fit in cache, or using SIMD instructions, or offloading work to the GPU or other coprocessors. Screwing with the meaning of my code just makes my life harder.
- Does my data fit in cache
- Can I make it fit in cache?
- Have I packed my memory efficiently?
- Am I using the right algorithm?
"Can the compiler inline this" is like 5000 on my list of things I care about. Compiler optimizations are mostly only useful to people who werent paying attention in the first place.
Okay, you're definitely severely underestimating how much slower everything would be if compilers weren't allowed to optimize anymore.
The problem is you don't understand the meaning of what you've written. You think the language has extra meaning that it doesn't. You can already get the meaning you want through existing constructs like volatile and yield and memset_s.
This is the problem with the attitude of compiler writers. Of course there are bugs. Nobody perfect. Pobodys nerfect? If I accidentally left a sign overflow in the code, or something of that nature, I think any (human) reading the code would understand what I meant, but the compiler is like "'Lets get weird!'". Yes I CAN get the meaning through the existing construct. That, however, is not my point. I am perfectly skilled and capable of doing this. What I'm questioning is why tool vendors think it's useful or practical to take advantage of users mistakes. I'd rather have a diagnostic of "why are you adding these numbers multiple times?" then have the compiler silently rewrite something I did on purpose.
I'm not writing this in the abstract, I'm writing this because things like this have hurt me in the past. It's super annoying. I don't care about your optimization to make things five percent faster if I spend three days debugging why the release build crashes if the window is full screen, but the debug build runs fine 100% of the time. The code has a bug, I own this, but I don't see how the attitude of "if your code has a bug, we will turn it into fucking dragons" is even remotely useful. Usually it's not even my code I'm fixing, it's someone elses. I just want people to stop breaking things to meet a dumb benchmark.
Two problems.
1. Your definition of "exact" is not exact. It is exact in your mind, but it isn't going to be precisely the same across all developers and compiler authors cannot reasonably develop hard requirements from this. This is especially true when targeting different machines. Operations on a uin64_t aren't going to look the same on a 32 bit machine, for example.
2. Attempting to do this makes your programs slow as hell. You can claim that compiler optimizations don't matter... but you are free to deploy debug builds if you really think this. C and C++ especially aim to provide a sort of ambient performance where everything is fast rather than just providing speed for hot loops. People complain nearly daily about modern applications being slow and then turn around and say we should throw away decades of compiler optimizations.
Well then it's a pretty bad name no? Considering what the word atomic means.
You seem to want "atomic" to mean "the data that corresponds to the instruction cannot be divided" but it means "the execution of the instruction cannot be divided", those aren't the same thing.
That’s just not true. Intel models will reorder reads and other processors will even reorder writes - and I’m talking about observably.
Perhaps you're thinking of a simple abstract CPUs used in "introduction to computers" courses instead of the real-life silicon used in most applications?
Simple example: if you declare a structure that is 14-bytes in size, declare variables foo and bar of that type, and then write
foo = bar;
The compiler will instead do something different. It might call memcpy, it might copy 8 bytes first, then 4 more, then the last 2, it might copy the first 8, then the last 8 (copying the two center bytes twice), etc.
Similarly, if you declare an int named i and do
i += 1;
Also, a literal interpretation of “as written” requires spilling the result of every statement back to memory; a strict literal interpretation even forbids using registers (if you don’t write “copy i into a register, add 1, write the result back to i”, the compiler can’t do that if it has to run your code “as written”)
But yes, it would be awesome if somehow the tooling or the compiler could report some of these things in an easy to visualize not-super-verbose way.
Unfortunately, that isn’t possible. Modern languages and their compilers are just too far abstracted away from modern hardware.
Um, no. I use a compiler to generate code that would otherwise be very tedious to write. I do not expect it in any way to abstract away the CPU. I do not want it to abstract away the CPU. If I did I would write Java or python. I'm using C++. I am very aware of the CPU. What I'm not aware of is whatever silly transformations the optimizer thinks it can do to my carefully crafted program because I didn't read page 783 of the spec.
I can, however, see an argument that people want a C like language which is a macro assembler. I am lost again when people start asking for a C++ like macro assembler. The features that C++ brings over C are not concepts that exist on any mainstream CPU.
[0] Unless you decide to build a concrete machine (either in bare metal, or as a VM).
Put "360 assembler macros" in your search engine and you'll find lots of information.
This is a good place to start: https://www.ibm.com/docs/en/zos/2.1.0?topic=language-macro-i...
"Assembly language for the PC"
https://archive.org/details/assemblylanguage00soch
"TASM Reference"
https://archive.org/details/bitsavers_borlandturemblerVersio...
"Structured Assembler Language For IBM Microcomputers"
https://archive.org/details/structured-assembler-language-fo...
Or just go to MASM documentation, you will find plenty of directives that look like an high level language
https://docs.microsoft.com/en-us/cpp/assembler/masm/directiv...
There is no definitive start point for C, as it grew fairly organically out of B and began as a living language. However, a reasonable approximation for C 1.0 is The C Programming Language (Kernighan and Ritchie, 1978) [0], commonly known as K&R C.
The language they describe is much simpler than modern C. Notably for this discussion, it contains no synchronization mechanisms.
There is nothing in that book that suggests C was a macro assembler. On the contrary, its description of C precludes it from being a macro assembler for the reasons I talked about in a parent comment:
> Although C matches the capabilities of many computers, it is independent of any particular machine architecture, and so with a little care it is easy to write "portable" programs, that is, programs which can be run without change on a variety of hardware. . It is now routine in our environment that software developed on UNIX is transported to the local Honeywell, IBM and Interdata systems. In fact, the C compilers and runtime support on these four machines are much more compatible than than the supposedly ANSI standard versions of Fortran.
> Because the data types and control structures provided by C are supported directly by most existing computers, the runtime library required to implement self-contained programs is tiny. On the PDP-I1, for example, it contains only the routines to do 32-bit multiplication and division and to perform the subroutine entry and exit sequences.
Notice the way this paragraph frames the issue. Since the features of C are supported by most machines, it can be implemented with a small runtime library. It does not say that C must use those features directly. In fact, it explicitly anticipates that C could provide some of its primitives in ways other then directly leveraging a corresponding capability of the hardware. The feature here is efficiency and a small runtime.
If C were a macro assembler the following things would be true of it, most likely:
- types would have fixed bit sizes (ie. uint32_t would be the norm)
- you'd be able to do various 'normal' things for assembly like rotate left and right.
- inline assembly would probably be.. you know.. standard instead of something that compiler vendors only started putting in in like the 80s.
[1] Ever wondered why `int` is so fuzzily defined in C? It's because in B there was only one type and it was always word sized. That's also why various things are typed `int` by default if you don't specify.
History: C was essentially PDP11 macro assembler. There are so many assumptions in C that basically came from the PDP11. C was originally a very utilitarian language to make writing unix easier. That it became massively popular was more of a happy accident.
And in fact, as gizmo86 pointed out, one of the explicit goals of C in terms of "making unix easier to write" was, afaik, that it would allow the code to be more portable to other architectures, because as the 11 in the name implies, the history that led to the creation of unix was not short on new architectures, and one of the key weaknesses of Multics was, afaik, the fact that it was rigidly written specifically for one specific architecture.
By this logic nearly every programming language is just a macro assembler at a certain level of (non-)complexity. All compilers do is translate syntax (macros?) into machine code (assembly?). So, is pascal also a macro assembler?
Anyways here is a list of instructions on the pdp11 that you can't directly represent even in the earliest versions of C to my knowledge:
ROR
ROL
SWAB
SXT
ADC
SBC
BVC
BVS
BCS
MARK
HALT
WAIT
RESET
MTPD
MTPI
MFPD
MFPI
MTPS
MFPS
MFPT
CLC
CLV
CLZ
CLN
CCC
SEC
SEV
SEZ
SEN
SCC
I'd be really happy to see some code from one of the code archives of unix' history that proves me wrong there, though, if you have it.
C was especially designed to do that! https://stackoverflow.com/questions/53100198/what-is-the-pre...
> Also, a literal interpretation of “as written” requires spilling the result of every statement back to memory; a strict literal interpretation even forbids using registers (if you don’t write “copy i into a register, add 1, write the result back to i”, the compiler can’t do that if it has to run your code “as written”)
If you don't make a pointer to a variable then it's allowed to be in a register, isn't it? There's even a 'register' keyword, however obsolete it may be.
Using an interpreter seems to be the best option to abstract away the CPU. Write the interpreter once, get enough eyeballs onto it, test it 'till death and use it for predictability.
Even if you write assembly these days, there is all sorts of ambiguity around. Even the underlying hardware we use can fail.
I used to believe that computers did as they're told, they could do no mistakes, all mistakes were human-made. Now I see that there is no such thing as error-free. We are basically living on chance, much is uncertain.
I trust my eyes and ears more and more instead of the machine.
As examples of merging, if you do
s = sin(x)
c = cos(x)
If you do
typedef struct s { char a; char b; }
s c;
[…]
c.a = 3;
c.b = 6;
*(short *)(&c) = 0x0603;The hard part is that programmers don't imagine the code to be executed in a naive unoptimized way, but still expect it to be reasonably well optimized (converted to "obviously" equivalent assembly), except where optimizations combine into a result they haven't thought of.
Ideally we test our applications on all hardware, with all configuration permutations etc. etc. In practice we do rely on our compilers translating our intent accurately and sometimes such edge cases matter.
Compatibility is a tricky thing. It's kind of like the argument whether adding optional arguments to a function breaks BC. It doesn't break BC if you don't pass those parameters. But if for some reason you were passing extra parameters hoping they'd be ignored (for example as a handler some other place) then adding optional parameters WILL break BC and cause your software's behavior to be undefined.
If you are a compiler or library writer, one solution is to avoid having useful properties that are not part of the spec. For instance, Go does not guarantee any particular iteration order for hashmaps; so they go out of there way to randomize the iteration order, thereby preventing developers from writing code that depends on a deterministic order.
In the case of threading, what you would need to do is essentially have a compiler/runtime that goes out of its way to order and time operation in a random/adversarial manner.
I've seen research that looks into doing this in a VM environment; which would be inhibited by the type of compiler optimizations being discussed. And others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order.
Ultimately, fuzzing and testing can only give you confidence that what is being tested is mostly correct. It can never give you confidence that what is written is entirely correct. If you want confidence in the latter, you need to invest in some form of static analysis (which could either be built into the language, such as a type system, or be an external analysis tool). Ultimatly, writing even a moderately complicated program (by modern standards) with full confidence in its correctness would involve advancing the state of the art of the field by decades (if not longer).
For the most part, the field just doesn't care about programs being fully correct; and accept it as a fact of life that going onto new/untested platforms and configurations will introduce/expose bugs.
> others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order.
Loom[1] is somewhat of that. It's a testing system (not a runtime for a full app) which tests multiple permutations of program execution (all possible permutations I think, limited by test case complexity or an optional "maximum thread switch count"), as well as modeling atomic/weak memory effects to some degree.
If you know how complicated the transformation pipeline is on a typical compiler, you'll realize that's pretty much impossible.
And that pipeline is specific not only to your code, compiler settings, but also your target machine, and is constantly in flux, update to update.
Even if it could be documented, no one would read the documentation.
x.fetch_add(1, std::memory_order_relaxed);
y.fetch_add(1, std::memory_order_relaxed);
x.fetch_add(1, std::memory_order_relaxed);
y.fetch_add(1, std::memory_order_relaxed);
But what did they want?
They tell me they're not happy with 0% chance of some interleaving they need. Are they happy with 0.000000000001%? I'm not sure I understand the practical difference between that and 0%? Can I tell them it is possible, but rely on the death of the universe happening before they have a right to complain it didn't turn up yet? If they have some hard minimum they require, then what do they expect me to do? Completely abstract from the system scheduler to make it happen?
Doesn't seem a reasonable expectation from programmers on compiler writers, and likely wouldn't really be what they wanted even if I made it happen.
This is basically a statistical/probabilistic version of another problem: should a compiler be allowed to change the time complexity of an algorithm? If I write linear search, and the compiler proves the list is sorted, should it be allowed to switch to binary search—or vice-versa? Traditionally the answer might be 'yes', but it's not exactly hard to argue an answer of 'no' might also be desirable in a number of situations. Now in this case, it's not the time complexity that's changing, but the statistical properties of the program... and while in some cases it might be negligible (1E-10 or what have you), that's not necessarily the case, at which point a difference in degree really can become a difference in kind.
Here's an exaggerated example to get the point across. Imagine your Tesla autopilot's accuracy suddenly dropped from >99.9999% to <0.00001% overnight because of some stupid optimization (maybe this one) that was technically correct. Assume there was never a guarantee provided to the user that it would stay this accurate. Now if your 99.9999% became 99.9998% overnight, OK, I think a sane user would completely anticipate that and live with it. But when it drops orders of magnitude lower, do you really think you could shift the blame to the user because you were "technically" not guaranteeing anything? Is it really the user's fault that your optimization reduced that accuracy to 0.00001% and killed them? Can you walk away with your conscience clear at that point that you did everything 'right'? At what point do you feel like some kinds of changes just blatantly unfair and uncalled for, even if they're technically "by the book"?
I'm open to ideas on how to create understanding both ways on what the user wants and the compiler is able to provide?
Same reason people walk outside without bodyguards and "bet" on coming back home alive despite the fact that nobody ever gave them such a guarantee. It's not insane to expect the future to bear some kind of resemblance to the past without some contract to guarantee it, is it?
Well you used the example of a car and I think it would be insane to use a component in a car when the manufacturer tells you it's not designed to do that and I can't possibly guarantee that's going to work just because you think you tested it and it seemed fine.
Your example about going outside isn't covered by a technical specification with a long list of guarantees formally agreed between two parties so I don't really see how it's comparable.
I don't believe so - as long as there is a version change and it's documented in the change log, which I aim to do with optimisations I write.
If you're using undocumented apparent behaviour, please check the change log when upgrading, or ask us to document the behaviour. But as already described, we may not be able to guarantee what you want while keeping other things you depend on like performance!
If your program breaks because the compiler no longer interleaves atomics, then your program was always broken, and you have just been getting lucky until now. Normally when this type of situation comes up, the programmers perspective is at least understandable, since what they were doing was somewhat reasonable, even if not allowed by the standard. In this case, the point is that I (and, I presume chrisseaton) cannot come up with any reasonable program that would rely on an interleaving happening 50% of the time.
If the interleaving were originally observed 99.999999% of the time, I could imagine a program relying on it happening. However, if the writes are close enough that the compiler could optimize them together, chances are the pre-optmiztion chance of it happening was already much closer to 0% than to 100%; which, again, begs the question 'what was your program possibly doing that relied on the original behaviour?'
Which (if true) is completely beside my the point. Just pick something that doesn't have a guarantee. The comment wasn't about Tesla. It was about empirical performance vs. written guarantees.
> Normally when this type of situation comes up, the programmers perspective is at least understandable, since what they were doing was somewhat reasonable, even if not allowed by the standard.
Okay great, we agree on that.
> In this case, the point is that I cannot come up with any reasonable program that would rely on an interleaving happening 50% of the time.
That's easily explained by our lack of imagination. No need to assume the person relying on it is being unreasonable.
Hypothetical example: suppose two threads are trying to alternate running some specific instructions with minimal latency. Maybe there are hardware requirements (e.g. they want to avoid overheating come specific components of a CPU core for too long?), so they try to alternate work via an atomically increasing counter? That's a starting point at least, feel free to improve the scenario.
Then why did they asked for an atomic that doesn't provide that instead of one that does? The docs on memory_order_relaxed are pretty clear it provides no thread synchronization of any kind: https://en.cppreference.com/w/cpp/atomic/memory_order#Relaxe...
This isn't some undefined behavior quirk being used to optimize, this is well-defined behavior being optimized in a well-defined fashion.
No, that's not what it's saying. "Synchronization" is an imprecise term, and you're misunderstanding what it means here. Atomics (as is literally in their name) perform each operation atomically; by definition they provide at least that thread synchronization guarantee, even if you believe they provide nothing else.
The documentation explains what "are not synchronization operations" refers to in the subsequent sentences; it's most certainly not saying it doesn't provide thread synchronization "of any kind" (again, I already listed one above). In fact, it lists 2 specific kinds of thread synchronization it does provide: "atomicity" (i.e. operations are all-or-nothing, as above) and "modification order consistency" (i.e. alterations of that same variable occur in a consistent order across different threads, even under std::memory_order_relaxed). What it does not provide is a consistent ordering across different variables ("an order among concurrent memory accesses"), which is fine as it's not not something we need in this example.
Collapsing multiple atomic operations into one has nothing to do with ordering, nor with multiple locations in memory. In fact, I don't think even std::memory_order_seq_cst can prevent this. The only way I can imagine preventing it is to mark atomics as volatile, and even then I'm not sure if it's guaranteed under the as-if rule.
In fact the fact that volatile atomic has additional guarantees is a strong reason for plain atomic not to have them, otherwise there wouldn't be a way to express the more relaxed requirement.
I think atomic not being volatile by default is a good default: the majority of code doesn't need to care about atomic in the first place, for the majority of the remaining code, these sort of optimizations are benign and desirable. For the remaining code that cares, volatile is the safety hatch.
Moreover, I'm not sure 'volatile' memory access without some sort of external linkage is even meaningful. The idea of volatile is that access to a volatile variable could have observable side effects outside the program, but that discussion seems rather moot for a variable that doesn't have connections to the outside world to begin with. Heck, by the same reasoning, even for a variable with external linkage, the rules might still permit it to be optimized out under link-time optimization, unless it has been declared to be externally reachable somehow (e.g. at a fixed/exported/otherwise 'known' address)... otherwise it's by definition externally unreachable and thus again unobservable under the as-if rule.
At least, I could see the reasoning going that way, and that's how it makes sense to me as far as the abstract machine goes. I can also see people disputing it though, and claiming (say) a debugger inspecting a program is sufficient accessibility for considering side effects, or something like that. I'm not sure I agree with every objection, but I see room for debate. It's just not clear what the implications are under the as-if rule.
There is little value on explicitly optimizing volatiles but of course that can happen as a side effect (ah!) of unrelated optimizations.
I rarely use volatile at all, but when I do, I do make sure not to apply it to local objects.
edit: I think the most reliable and portable way to make sure that the address of a variable escapes is something like this:
volatile std::atomic<void*> sink; // global
void escape(void*x) {
std::atomic_signal_fence(std::memory_oreder_release);
sink.store(x, std::memory_order_relaxed);
}
What if they say the hard minimum is "occasionally"?
They're not holding you responsible for the scheduler, they just want you to leave it as possible. (and not be deliberately malicious, just in case that needs to be said)
If you need it - write it down! I can't guess your intentions as a compiler author!
And sure, there should be a way to signal intentions. By my point is that there is a reasonable way to describe what certain people would expect by default.
Thinking that atomics will not be optimized by compiler is "good enough" in my opinion for almost, and I really mean almost, everybody.
Heck, I interview people and atomics optimization is one of my staple questions (Tell me, what does volatile do in Java, exactly?). I have never heard a thorough answer to that question and yet people do work as developers and do produce working applications.
The only real users of these optimizations are atomics primitives developers, and the use it to improve them a tiny bit in some special cases.
You can technically contrive a test where you run an update that changes something to 1, then immediately to 2 on each iteration. Then you try to look at it from another core and you would expect that at least once in a blue moon you will see 1. But I just don't see any sanely written application to rely on that kind of behavior.