5 ms·
What every compiler writer should know about programmers (2015) [pdf]
- chrisseaton 8y agoIf you're interested in the weight that the author puts on 'confirming' and don't know what it exactly means - a 'conforming' program is one that runs correctly on some 'conforming' implementation. So it's a program that at some point ran correctly on some compiler somewhere. If your C program is only 'conforming' then it isn't necessarily portable between compilers or even versions of compilers.
- userbinator 8y agoGood to see a detailed study on this --- it's been my experience that Intel's compiler (icc) is far less eager to exploit undefined behaviour, yet generates just as competitive if not sometimes significantly better code than GCC. It's also worth mentioning the note that the standard has about UB (emphasis mine): "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)." That emphasised part is what the majority of programmers using C expect.
- colejohnson66 8y agoCould that be because of ICC’s dispatch code? It compiles code for different feature sets and then uses the CPUID feature list to know which to run.
- userbinator 8y agoThat's for autovectorisation, but my experience has been that icc's regular scalar code generation is what makes it perform so well. Instruction selection, register allocation, etc.
- conistonwater 8y agoAren't those common to all compilers? So it just does everything that clang/gcc do also, but does it better?
- naikrovek 8y agoDepending on what you are doing a bit, stuff compiled with `icc` runs about 20% faster than the same code compiled with `gcc` or MSVC's compiler on Intel CPUs.
- colejohnson66 8y agoInteresting. Any links to benchmarks?
- earenndil 8y agoHmmm. The one time I tried it (for a crypto miner), it ran about 60% the speed of gcc and clang (which were comparable; one was slightly ahead, I forget which but I think it was gcc). Granted, I may have gotten the flags wrong (there were a lot of them), but I turned all the ones that looked relevant.
- keldaris 8y agoWould you happen to know if recent versions of icc still generate horrible code for AMD CPUs (particularly Ryzen/EPYC)?
- zzo38computer 8y agoGCC has some options that you can specify in order to change how some of the undefined behaviour stuff is implemented.
- jasonhansel 8y agoI really think that we need a standard variant of C in which all undefined behavior is (somehow, even if arbitrarily) defined. (Also: a variant with some restricted level of polymorphism would make C much less painful.)
- deleted 8y ago[deleted]
- mpweiher 8y agoThe standard actually has a definition of the range of permissible behavior for UB: Permissible 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). However, an update to the standard made this definition non-binding. It is still in the standard, verbatim, but compiler writers have interpreted that to mean they can completely ignore it and build compilers whose behavior goes way outside the "permissible" range. See https://blog.metaobject.com/2018/07/a-one-word-change-to-c-standard-to-make.html https://blog.metaobject.com/2018/07/a-one-word-change-to-c-s...
- mannykannot 8y agoYou seem to be saying that the meaning of this clause in the standards is undefined (or is it implementation-defined?) I have no idea what the authors of the standard would have in mind in putting a non-binding constraint in a standard, unless there's a faction that hopes to make it binding in the future, and hopes this will pave the way.
- mpweiher 8y agoIt used to be binding, was later changed to be non-binding.
- ychen306 8y agoThis is unlikely to happen because of the performance penalty it would incur (e.g. defining outcome of all out-of-bound memory accesses).
- whatshisface 8y agoThis entire issue comes from "poor" (by modern standards, it was great for its time) language design. The compiler writers have to fight with the compiler users because the language that was meant for communication between them does not include all of the information that the compiler needs to know. Instead, it depends on implicit things that "everybody knew" in 1980 but which are not all true today. In order to know what your C program is going to do, you have to have some idea of how it is compiled. That's bad, because if they go and change how it is compiled your expectations will be wrong. Instead languages should be designed so that you write down what you want to have happen, without having to think about how the compiler will implement it.
- cle 8y agoVery rarely have I gotten deep enough into a project and not had to pop open the hood. How the lower level abstraction implements things is often important and often leaves you with no practical choice but to depend on implementation details. These are just unavoidable realities. “Hiding implementation details” is one of the great lies of abstraction.
- afarrell 8y agoI am a bit surprised to hear that this is true in your common case. What problems are you usually solving and what tools are you usually using?
- whatshisface 8y agoThat's an example of what I'm talking about: for example C has no facility for expressing instruction timing, so if you are on a microcontroller and need to generate a signal you have to keep an eye on the assembly. Ideally there would be some facility for telling the compiler that a certain variable needed to have its value computed after N cycles, then you could use it for those specific cases and not abandon the optimizer for the rest.
- dooglius 8y agoThat feature wouldn't make any sense outside of very basic microcontrollers, you don't have any sort of determinism due to things like branch misprediction, cache misses, and pre-emptive multitasking.
- mannykannot 8y agoIn section 2.2, the author claims that the intent of a programmer is knowable when the programmer writes something that could result in undefined behavior, but this claim does not hold up for the example given. When a program attempts to read from beyond the end of an array, it is rarely something that a programmer intended to happen, and it is rarely the case that any action the program takes as a response to that event (even if it is a segmentation or general protection fault) is in conformance with what the programmer intended to happen after the sequence of inputs that led up to this event. It is much more likely that the programmer did not even think that this could happen, and expected that the program would continue to run and produce results conforming to the purpose they intended the program to serve. If I can divine what the author of this article actually intended to say, I think it is that, in at least some cases of undefined behavior, programmers commonly have intuitions about what would happen if that behavior occurred during the execution of their programs. I don't know if the rest of the thesis can be salvaged by substituting that reading.
- abcdef123xyz 8y agoI think it is clear they mean what the programmer would expect /even if they knew the code was wrong/: "And that’s what programmers expect: In the normal case a read from an array (even an out-of-bounds read) performs a load from the address computed for the array element; the programmer expects that load to produce the value at that address, or, in the out-of-bounds case, it may also lead to a segmentation violation (Unix), general protection fault (Windows), or equivalent; but most programmers do not expect it to “optimize” a bounded loop into an endless loop."
- mannykannot 8y agoWell, that's what I wrote in my second paragraph, and the article would have been more straightforward if the author had not drawn an unjustified conclusion from it. For example, he goes on to say that some programs capable of undefined behavior are nevertheless correct if compiled in a certain way, but how is the compiler-writer to determine that? The unstated assumption is that there is a preferred compilation under which all programs are 'more correct', but when it comes to undefined behavior, then, by (non)definition, there is no 'more correct' way to compile it. Therefore, saying there is a 'more correct' way is equivalent to saying that at least some undefined behavior should be defined in a particular way. The article would have been simpler if the author had realized that this is what he is proposing, and skipped the confused correctness arguments.
- virgilp 8y agoI'm tempted to write a "what every programmer should know about compiler writing" article. In particular, that they're not alone in the universe. The price that you have to pay for the incredible combo "performance + portability" is undefined behavior. Why do people assume that if they don't care about some sorts of portability and exotic platforms, nobody else does?
- anfilt 8y agoProbably because a lot programmers are just used to the fact pretty much at the desktop level it's x86/64. However, when you start talking microcontrollers for instance the architectures are all over the place. C covers both these use cases.
- dumael 8y agoIndeed, the likes of x86 little endian assumptions of programmers (even compiler engineers) can be hilarious (in the sad clown way) when targeting something like MIPS64 big endian.
- MaulingMonkey 8y agoI'm seeing Rust with stricter aliasing rules, targeting microcontrollers, using the same high performing LLVM backend, without undefined behavior lurking behind every corner. That price is not a given. The one advantage C has on portability is that for any given platform, you can probably be assured there's at least one buggy C compiler for it that doesn't properly comply with the standard out there. There's a niche for that, but it is a niche. Otherwise? C and C++ aren't great at portability. I've spent a lot of time porting games, and a lot of that time has been spent porting C and C++. I can't even assume two compilers will compile the same defined-behavior code targeting x86-64 the same way - someone somewhere will have typedefed something in terms of long, and put that into a bytewise serialized struct, and one compiler will be LP64 whereas the other will be LLP64. Add ARM, PPC, or even just 32-bit x86 into the mix, and suddenly previously working programs turn into multi-month fixup projects on medium sized codebases, before even touching all the system APIs I need to change because of the completely anemic standard library. The further off the beaten path we go, the more likely we are to encounter straight up compiler bugs where not even the authors correctly interpreted the standard, so now we get to debug other people's compilers and write extensive test suites which we pray will catch all the codegen bugs. They won't, but they'll catch some percentage of them, at least. There's a whole slew of porting issues that just don't show up in C#, Java, JavaScript, ActionScript, Lua, Python, Squirrel, or any number of other programming languages games and game tools use - that are uniquely terrible about C and C++. Maybe I fixup a few paths, maybe there's a few filesystem permission issues, maybe a few OS APIs don't work quite the same. This is all time not spent optimizing your actual program, nor porting things in your program that are actually supposed to be platform specific. C and C++ aren't the greatest languages from a performance standpoint either. I still can't convince MSVC to properly align stack variables consistently, so I must resort to my own stupid padding hacks or dynamic allocation. Not that this is sufficient to coax the optimizer into emitting appropriate SIMD instructions, so I resort to doing so by hand. The standard library completely lacks any means of actually doing this, and whatever middleware I choose probably lacks targeting for at least one platform or instruction set, so I get to port that too, taking extreme care to not introduce extra overhead via the supposedly "zero cost" abstractions these languages give me. Maybe it's just easier to write the same math N times instead. They're not JIT compiled, although function multi-versioning is finally spreading (quite late) to enough compilers that you might not need to choose between a baseline architecture or multiple binaries. Then a constexpr function shows up in my profiling results, I see trivial static init invoked at runtime, I chase down another optimizer induced heisenbug and figure out if it's UB or a compiler codegen bug, and I'm left wondering why people are so busy defending int overflow being UB for some loop microbenchmark instead of fixing something that would actually help me with perf.
- pcwalton 8y agoThe author seems to be saying, in section 4, that compilers should just stop doing some optimizations (such as converting int to size_t where appropriate) and should expect programmers to do those optimizations instead, in order to reduce undefined behavior. The problem with this argument is that it doesn't match economic reality. Compiler authors wouldn't disagree that it would be nice to not have to do these optimizations! (Chris Lattner has said as much to me, for example.) Unfortunately, there is a lot more application code out there than there is compiler code. So it makes economic sense to add optimizations to the compiler rather than to individual programs, so that the huge universe of C and C++ programs can benefit without having to be optimized by hand at the source level. This is why companies like Google and Apple employ compiler engineers: so that their large codebases can become faster automatically. It's trendy to complain about compiler engineers because they're an easy target, and because of nostalgia for the days of Turbo Pascal when optimizations weren't done and programs were slow. It's much less trendy to analyze the complex circumstances that has led to UB exploitation in C and C++. In my opinion, if I had to assign blame to one thing, it would go to the C language itself, for e.g. encouraging use of int for array indices. P.S. As always, Fabian Giesen's description of why compilers exploit signed overflow is a must-read: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... Note that the conclusion is not as simple as "compilers should stop doing this optimization in C". There in fact isn't a great solution precisely because int is 32 bits for popular ABIs in C; the best options are "hope the programmer used size_t right" or "use another language".
- petergeoghegan 8y ago> The problem with this argument is that it doesn't match economic reality. Compiler authors wouldn't disagree that it would be nice to not have to do these optimizations! I think that the extent to which that's actually true is pretty debatable. Note that both Linux and Postgres use -fwrapv/-fno-strict-overflow and -fno-strict-aliasing. I'm not a compiler engineer, but if I was I might think to ask why that's the policy of these projects, and address the criticism on something closer to its own terms. The author makes a clear distinction between "Optimization*" and "Optimization". That distinction might be a bit squishy, but not so much that it isn't still useful. Even the Fabian Giesen thing that you linked to says "A lot of people (myself included) are against transforms that aggressively exploit undefined behavior", right at the start. It's trendy to blame the C language itself, but surely we can expect C compilers to care about the C language.
- cryptokernel 8y agoJust leaving this here: Earn crypto by doing tasks https://coincircle.com/l/50VVxbObg3 https://coincircle.com/l/50VVxbObg3
- WalterBright 8y ago"Compiler writers are sometimes surprisingly clueless about programming." Sure, but there's another aspect, which is trying to guess at what the minimum level of knowledge the user of the language should be expected to have. For an interesting debate on if an "isOdd(int i)" as opposed to just using (i & 1) should exist as a standard library component or not, see: https://digitalmars.com/d/archives/digitalmars/D/food_for_thought_-_swift_5_released_-_bottom_types_string_325712.html#N325778 https://digitalmars.com/d/archives/digitalmars/D/food_for_th...
- earenndil 8y agofunction isEven(int i) { return !isOdd(i); }
- earenndil 8y ago> For example, if I saw "isOdd" in code, I'd wonder what the heck that was doing. I'd go look up its documentation, implementation, test cases, etc., find out "oh, it's just doing the obvious thing", and be annoyed at the waste of my time. Huh. That is not at all what I would do. I would think 'oh, that's checking if the thing is odd' and keep going. If I see i&1, then I have to unpack that, parse it, figure out why it's there and that it checks oddness. Also relevant is that i&1 checking if i is odd is a detail of i's internal representation. There's nothing intrinsically odd-related about the operation &1; that it checks for oddness is a co-incidental side effect, just like how making a truth table of (0, 0) => 0, (1, 0) => 1, (0, 1) => 1, (1, 1) => 1 happens to correctly simulate the behaviour of an or logic gate, even though there's nothing inherently or-y about it.
- DannyBee 8y agoWe have this discussion every few years :) https://news.ycombinator.com/item?id=11219874 https://news.ycombinator.com/item?id=11219874 I have the same comment now i had then.
- nkurz 8y agoAnd reading it once again, I'm still sympathetic to Anton's argument and frustrated by your response. Although reading the exchange between the two of you at the bottom, I do see why you might have difficulty looking afresh at his argument. But in the hope of moving the discussion ahead at least a little, could you perhaps respond here to forthy's comment from the last thread? https://news.ycombinator.com/item?id=11226391 https://news.ycombinator.com/item?id=11226391. In particular, why does the C standard seem to prefer undefined behavior over the easier to reason about implementation defined behavior?
- bigcheesegs 8y agoImplementation defined behavior isn't actually any easier to reason about. Compilers are free to choose "assumes this never happens" as their behavior, as there is no limit on what can happen. This is different from implementation defined value or unspecified behavior (which generally has a list of options).
- bigcheesegs 8y agoA major issue with removing UB exploitation is that you've now created C, but each compiler implements a different C. It becomes harder to port code, and you end up with bugs that can be harder to catch, especially if don't consider what you're doing an error, as now you can't even use the sanitizers. What my team has been looking at to help developers that have these issues is providing low overhead ways to give defined, but likely to crash, behavior for these cases. This helps protects against UB without creating C. An example would be variable auto-init, which intentionally doesn't support zero init, as that is likely to hide bugs: https://reviews.llvm.org/D54604 https://reviews.llvm.org/D54604 I'm fine with fully defining some things that are currently UB or IB. I'm also fine with keeping things as UB. What I'm not fine with is creating this implicit C that programmers think they know what it is, but it's not actually defined anywhere, and not everyone working on the compiler is on the same page about.
- perl4ever 8y agoTo me, whenever something is undefined at one level, there are still constraints on it at another level. We go about our daily lives without laws and regulations explicitly detailing our every interaction, and rely on custom and ingrained behavioral rules to fill in the gaps. Every level of abstraction has another layer behind it. When I read someone arguing about undefined behavior allowing a compiler writer to do anything, it makes me imagine someone who, if they could afford the finest lawyers and found the appropriate loophole, would consider it not just their right, but their duty, to kill and eat me. It's not terrifying to imagine there are monsters here and there; there always have been a certain number. What terrifies me is the idea that this mentality is infecting society and altering norms and interactions. It doesn't feel like evil as such, it feels more like a metaphorical prion disease. There's something fundamental to being a human being in being able to deal with undefined situations by breaking out of a given context into a broader one.