18 ms·
No sane compiler would optimize atomics (2015)
- rurban 5y agoLikewise no sane compiler would optimize memset. Unluckily we don't have sane compilers
- rowanG077 5y agoWhy not? This makes little sense to me. Why shouldn't a compiler optimize it?
- 1ris 5y agoBecause, when a programmer write a call to memset, she does, if you, as a compiler, take her seriously at all, expects the memory to be set, and not it just being a mere suggestion 1). should added a separate function called it memsetOrDontIfYouThinkINeverReadThisAgain. Does this make sense? 1) Yes, I know there are rules and all that are precise and allow that.
- rowanG077 5y agoIf you take this stance most optimizations are of the table. Optimization are rewriting code in some way to ensure it runs faster. In that sense yes the entirety of a program "is a mere suggesting on how to compute the output". If you actually want to tell the CPU what to do you have to use ASM and an ISA that specs what exactly every instruction does and how it does it.
- 1ris 5y agoLet me paraphrase this differently, on a more pragmatic level. From the perspecitve of a compiler user, rather than a compiler author: How likely do you think is it that a program that contains memset and has this optimisation applied how diverts from the indented behaviour and now has a serious flaw in it? The answer to this question is the answer to your question "Why not?". When people write C, they often do so for specific domains. Crypto, embedded, device drivers. They choose C for these domains because they think, and they are taught that C is some kind of macro assembler, because in these domains they care deeply about the "how". If they wouldn't, they would write java or any current top 20 programming languages. So almost all optimization off looks ok. Reasonable compared to this, anyhow.
- rowanG077 5y agoI would assume it doesn't divert because the user cannot tell from the output of the program if a memset is optimized away. If you want the memset itself to be observable you need to use volatile or memset_s. Else you are not describing your intent properly If people truly still think C is a macro assembler then that's the problem. Besides if you care deeply about how modern high performance architectures won't cut it anyway.
- Gibbon1 5y agoI think the thing is users of C compilers generally care about raw performance much much less than compiler maintainers who are universally using C++. Compiler writers are stuck in a trap. C++ compilation model is broken. Which makes compiling C++ programs very slow. Which means compiler writers care a lot about how fast compilers are. So they desperately add more optimizations to speed up the compiler program. But which adds more work to the process of compiling a program. Most of the other users, especially C programmers don't care about speed nearly as much. Notably because while the compilation model for C is also broken, it's not nearly so. So their programs compile in a few seconds, not minutes to hours.
- MauranKilom 5y agoI submit that this viewpoint is very mistaken. If it were true, "users of C compilers" would just compile with optimizations off and there would not be any problem. Evidently, "most of the other users" do care about performance. Unsurprisingly, I might add.
- Gibbon1 5y agoIf I am mistaken why do most programmers prefer slower to vastly slower languages such as JavaScript, Java, C#, Go, Python, PHP, or Lua? If they really thought that speed was the most important thing wouldn't that abandon those languages for C++. Explain yourself.
- 5y ago
- overgard 5y ago> the entirety of a program "is a mere suggesting on how to compute the output". Maybe people using Java or various interpretted languages are fine with that, but most C programmers want their code to be a very close mapping to what they specified.
- umanwizard 5y agoThen they can compile with -O0 and get basically that. What’s the problem?
- overgard 5y agoThe problem is, I want optimizations.. that don't break things. There's -O1 or -O3 but not -Ononewbugs. I don't expect perfection but changing the meaning of memset or collapsing atomic operations is like "settle down".
- innocenat 5y agoBut -O3 is suppose to do that. The problem is that there will almost always be bug. The flag that may allow things to break is -Ofast.
- gpderetta 5y agoThe set of all the optimizations that do not break any program is very likely empty. So you are happy to break other people programs as long as yours keep working?
- overgard 5y agoI'm pretty happy to leave the optimizations off. Writing the correct data structures matters a lot more than a clever compiler collapsing two commands into one.
- umanwizard 5y agoEvery optimization changes the observable behavior of a program in some way. How is the compiler supposed to know which changes you deem acceptable? Eliminating dead stores (including calls to memcpy whose result is never read) seems like one of the most basic and least objectionable optimizations I can imagine. So, if you’re against eliminating dead stores, what optimizations _are_ you okay with?
- aaronmdjones 5y ago> If you actually want to tell the CPU what to do you have to use ASM and an ISA that specs what exactly every instruction does and how it does it. Even that isn't enough, unless you go with a CPU that doesn't have any branch prediction, speculative execution, or out-of-order execution. I'm not aware of any such processors.
- rowanG077 5y agoThat's exactly what I meant with "how". If an ISA has branch prediction, speculative executions or out-of-order execution this definitely is included on how an ISA handles it's instructions.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- aqrit 5y agohttps://media.ccc.de/v/35c3-9788-memsad https://media.ccc.de/v/35c3-9788-memsad
- halayli 5y agoCompilers are sane and written by very smart people. They do have bugs just like any other software. In my 20+ yrs of coding, I can count the number of bugs I've encountered on one hand. memset tend to be optimized out in the dead code elimination pass and highly relies on SSA. Compilers adhere to the abstract machine specs. If you want memset not to be optimized out then use memset_s because the spec explicitly doesn't allow that. if an optimization relies on a UB and surprised the programmer then the programmer was also relying on a UB in the first place.
- secondcoming 5y agoIsn't memset different in that it's an external function that compiler writers have chosen to intercept and perform themselves? Why is saying 'use memset_s' acceptable when they could have stopped treating memset as a special case?
- chrisseaton 5y ago> Isn't memset different in that it's an external function that compiler writers have chosen to intercept and perform themselves? The semantics of memset and memset_s are defined by a standard. They're not unknown functions that could do anything, and they're breaking a rule by treating them differently, like you're suggesting they are.
- Someone 5y agoIf you include a standard header (using <> brackets) and call a function that the standard says get declared when doing that, the compiler is allowed to assume you want the standard behavior, and inline that/replace it by a specialized version/etc. Optimizing memset, in particular, can reap huge benefits, for example for sizes of 4 or 8 bytes in tight loops or for zeroing cache line sized blocks.
- halayli 5y agomemset is not a special case. Compiler designers are very much against special casing, and rightfully so. Compilers do have an intrinsic equivalent but that has nothing to do with whether it gets optimized out or kept. Following SSA rules, if you are writing to a non-volatile memory and not reading from it for the remaining duration of its lifetime then it's dead code. use memset_s was a suggestion if your goal is to scrub memory because it guarantees the write will happen. The guarantee comes from the C standard: > Unlike memset, any call to the memset_s function shall be evaluated strictly according to the rules of the abstract machine as described in (5.1.2.3). That is, any call to the memset_s function shall assume that the memory indicated by s and n may be accessible in the future and thus must contain the values indicated by c Which essentially means treat the memory as-if it's volatile.
- chrisseaton 5y agoA similar thing is that I often come across people who are well-informed but still surprised that compilers will combine two observable operations into one, and complain that some other thread somehow 'should' be able to observe the intermediate state. But I don't understand how they think they would be able to tell the difference between an interleaving that never happens to happen, and one that will never happen.
- historyloop 5y agoIt can be tricky in that fuzzing your program to discover race conditions seems to behave perfectly on one compilation target where these atomics are detected and reified, while you later discover on another platform surprisingly your app crashes 20% of the time. 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.
- gizmo686 5y agoIt is not about translating intent accurately. What you need is for compilation to be fully specified. Anywhere where there is multiple correct ways to compile something introduces a risk for bugs that only show up with some compilers. 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.
- tester756 5y ago>For Compiler Writers >Get back to work, there’s so much more to optimize… and so much code to break! Help users write good code: the compiler should provide diagnostics when it detects anti-patterns or misuses of atomics. Is it worth to put effort into compiler optimizations instead of putting more effort into providing "diagnostics" and informations for programmer? in context of this: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.434&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29....
- andi999 5y agoWhy is it surprising that atomic can be optimized?
- Sharlin 5y agoWriting correct, even if non-optimal, code that uses atomics is already highly non-trivial. Transforming code that uses atomics into more efficient forms while guaranteeing the same behavior is even more non-trivial.
- andi999 5y agoBut is difficult for the programmer not more difficult for the compiler, isn't it?
- dang 5y agoOne past thread: No Sane Compiler Would Optimize Atomics - https://news.ycombinator.com/item?id=11694325 https://news.ycombinator.com/item?id=11694325 - May 2016 (56 comments)
- elliotpage 5y ago2105? I love posts from the future
- georgeoliver 5y agoI had a very weird moment of cognitive dissonance reading the headline, having just finished rereading the novel Dune yesterday.
- bpodgursky 5y agoI too was briefly worried that Ix was up to no good with their thinking machines. Honor the Butlerian Jihad! This kind of optimization should be left to the Mentats.
- MauranKilom 5y agoCould you fix the title to not be almost a century in the future please? :)
- dang 5y agoWhoops! twas a typo (2105). An editor has fixed it now.
- overgard 5y agoI'd love to have a compiler that just tells me what optimizations could be made, but let me either do it myself (if syntactically available in the language), or explicitly mark the optimization as ok through a #pragma or something like that. I just think having to read the disassembly to figure out what happened isn't a great user experience.
- tjalfi 5y agoSGI compilers had diagnostic information called love notes that explains what optimizations had been applied to loops. Here is an example taken from [0]. #<loop> Loop body line 1, nesting depth: 1, estimated iterations: 17 #<loop> Unrolled 2 times #<swps> Pipelined loop line 1 steady state #<swps> 50 estimated iterations before pipelining 2 unrollings before pipelining #<swps> 6 cycles per 2 iterations #<swps> 4 flops #<swps> ( 33% of peak) (madds count as 2) #<swps> ( 16% of peak) (madds count as 1) ( 33% of peak) #<swps> 2 flops #<swps> 2 madds #<swps> 6 mem refs #<swps> 3 integer ops ( 25% of peak) #<swps> 11 instructions ( 45% of peak) 1 short trip threshold #<swps> 5 integer registers used. #<swps> 9 float registers used. [0] https://cug.org/5-publications/proceedings_attendee_lists/2002CD/S02_Proceedings/Pages/Authors/Cellis.pdf https://cug.org/5-publications/proceedings_attendee_lists/20...
- ndesaulniers 5y agoThese are called remarks in GCC and clang and are controlled by -R family of flags.
- ndesaulniers 5y agoI don't think you would. The list would get unwieldy quick and the order of passes might give you surprising results. It's also possible to get into situations where your code is incorrect (relies on UB), and just so happens to work with these flags, but not those!
- overgard 5y agoMaybe not, but I feel like as a C programmer I'm already kind of a control freak, and I really want to be able to tell the compiler what I want and where, I don't want magic. I'm using C explicitly because I want to know and control what's going on. If I'm dealing with atomics and concurrent code I really want to tell the compiler, hey, inline constants maybe, but don't reorder or combine operations. Even if the compiler is "right" or my code is subtly wrong, I don't want the compiler making things worse.
- deleted 5y ago[deleted]
- DangitBobby 5y agoFeels like a really weird context for click-bait. I guess I shouldn't be surprised.
- a1369209993 5y ago> int rlo() { > // Dead store eliminated. > y.store(0, std::memory_order_release); > // Redundant load eliminated. > x = 1; > return 0; // Stored value propagated here. > } This is actually wrong, for subtler reasons than one might initially think[0]. Consider the case where rlo is called with x!=0,1 and y!=0. Another thread that observes y=0 is guaranteed not to see the originial value of x - it might see 0, it might see 1, but something has to have been written to x by the time it observes y=0. The above optimization allows even a single-processor execution to context-switch at "// Redundant load eliminated" and observe y=0, x=??? from another thread. Oddly, the correct code seems to be: x = 1; y.store(0, std::memory_order_release); return 0; On the face of it, the load acquire seems like it would prohibit that, but in that's only a problem if it (the acquire) observes some release with which x = 1 can't be reordered. But it's hard coded to always observe the y = 0 release, so that can't happen. (I'm less sure that this is correct than that the previous version is wrong, admittedly.) 0: In particular, it's not just a matter of "x = 0 has to happen because store-release".
- agalunar 5y ago> This is actually wrong [...]. I fairly sure it's correct! precisely because of the initial store `int x = 0;`, for the reason given by the article. If that were `int x = 2;` instead, then I agree that the transformation would be invalid. (Perhaps this is what you meant? but I wanted to clarify.) In case anyone is curious, here are the relevant parts of the C++ reference: > Absent any constraints on a multi-core system, when multiple threads simultaneously read and write to several variables, one thread can observe the values change in an order different from the order another thread wrote them. Indeed, the apparent order of changes can even differ among multiple reader threads. Some similar effects can occur even on uniprocessor systems due to compiler transformations allowed by the memory model. > If an atomic store in thread A is tagged memory_order_release and an atomic load in thread B from the same variable is tagged memory_order_acquire, all memory writes (non-atomic and relaxed atomic) that happened-before the atomic store from the point of view of thread A, become visible side-effects in thread B. That is, once the atomic load is completed, thread B is guaranteed to see everything thread A wrote to memory. > The synchronization is established only between the threads releasing and acquiring the same atomic variable. Other threads can see different order of memory accesses than either or both of the synchronized threads. https://en.cppreference.com/w/cpp/atomic/memory_order https://en.cppreference.com/w/cpp/atomic/memory_order
- benny89 5y agoThanks for sharing the information.. https://www.indigocard.run/ https://www.indigocard.run/