7 ms·
Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior
- mpweiher 13y agoSeems to be a problem of language-lawyers coding compiler optimizations. Stop doing that. See also "Doctor, it hurst when I move my arm this way".
- CurtHagenlocher 13y agoGiven the reasons that people use C, what do you think makes for a better sales pitch -- "our compiler produces the fastest code" or "our compiler produces the safest code"? This is simply the compiler market optimizing for what it's customers want.
- anon1385 13y agoWell the existence of CompCert seems to indicate that there is at least some demand for a compiler with a greater emphasis on correctness than speed. It doesn't fix the issue of undefined behaviour of course since that is part of the language standard itself. http://compcert.inria.fr/compcert-C.html http://compcert.inria.fr/compcert-C.html
- pascal_cuoq 13y agoCompCert is a research project. Its unqualified existence does not prove that any demand exist for anything. You might as well say that there is some demand for aspect-oriented programming because so much research is being done on the topic (substitute the topic of your choice if my having picked this one offends you). It so happens that this particular research project found a few industrial users eager to try it out and study the feasibility of deploying it, but it wasn't necessary for the research project to exist.
- mikeash 13y agoNot at all. The problem is that there are useful, effective optimizations allowed by the language spec which also have unexpected consequences on subtly incorrect code. Take an oversized shift, for example. The result is undefined, and for good reason. This allows an expression like x << y to be translated directly to a single machine instruction on just about every architecture. If there was a defined result for oversized shifts, then many architectures' instructions would not match it, forcing the compiler to generate inefficient code on those architectures. For every example of a weird optimization causing problems, you can find an example of that same optimization making code go much faster. You could say that compilers should value correctness over speed, and I would agree with you, but: all of these optimizations are correct. These are C compilers, and they compile C programs just fine. Where they have trouble is on programs that aren't actually valid C, but are just close. You can argue that they are being technically correct in a bad way, but then if you abandon the standard and decide that you should "correctly" compile a certain class of invalid programs, how do you decide what "correct" means?
- cliffbean 13y agoOrdinarily, unsigned left shift silently shifts bits off the end. 0xffffffff << 0 is 0xffffffff 0xffffffff << 1 is 0xfffffffe .. 0xffffffff << 30 is 0xc0000000 0xffffffff << 31 is 0x80000000 It is defined to ignore overflow. Therefore, I claim that there's enough consistency here that we can extend the pattern to this: 0xffffffff << 32 is 0x00000000 I claim this really is the mathematically correct answer. It's consistent with the most obvious pattern, and there are no other relevant patterns. C has chosen to call this undefined behavior instead of returning the correct answer here, and I call that choosing optimization over correctness.
- tel 13y agoThat may be a useful left shift operator, but it's just not C's left shift operator. You can argue the spec is poor, but you cannot argue that the compiler writers are incorrect.
- joosters 13y agoAre you so sure that all architectures that implement a left shift operator work the same way? For example, if you shift left by 'x' they might shift left by 'x modulo 32' With C, you could still use the shift instruction on that architecture. With your 'correct answer', the compiler would have to output instructions to check the value of x prior to the shift. Besides which, shifting is just one specific case. C has an easily understandable and documented behavior: overflow is undefined, no matter how you achieve it. We don't have to go into horrific detail about what happens when you overflow with adds, multiplys, shifts and so on.
- rayiner 13y agoPeople writing compiler optimizations are necessarily language lawyers. Their job is to make the code run as fast as possible given the semantics of the language.
- jerf 13y agoIn a way, the problem is that C dates too much from a time before language lawyers. I can't think of a modern language that is as underspecified as C, because we know better now. If were to be written again today, it would be much better specified (see: Go). I don't even mean this as a criticism of anybody in particular, it was a different time. "Fixing" C would be creating a new dialect, unfortunately. (Personally, I just consider C a last resort, and I've found that works pretty well.)
- Dylan16807 13y agoThe problem is deciding what kind of optimizations are 'resonable'. In one context, assuming x+1 is greater than x will avoid some wasteful code in your loops. In another context, it could destroy your program's logic. If you restrict yourself to guaranteed-safe optimizations, you miss out on most of the potential gains.
- osivertsson 13y agoMore info: https://css.csail.mit.edu/stack https://css.csail.mit.edu/stack Code: https://github.com/xiw/stack https://github.com/xiw/stack
- octo_t 13y agoSimple solution: remove the undefined behaviour from your codebase.
- DanWaterworth 13y agoBetter solution, don't use languages that allow undefined behaviour.
- wslh 13y agoDo you mean Haskell? because its compiler is very advanced and does complex optimizations.
- DanWaterworth 13y agoI didn't have a particular language in mind. Though Haskell is certainly a fine choice.
- tel 13y agoIt's semantically well-defined, though. The compiler will never change the value of your result, it will only discover more efficient ways to compute it.
- chongli 13y agoHaskell allows plenty of undefined behaviour! unsafePerformIO, unsafeCoerce, the FFI, even something as simple as unchecked arithmetic can cause it.
- octo_t 13y agowhy? languages like ruby etc dont even have universally defined behaviour - there is no spec etc, just a reference implementation.
- DanWaterworth 13y agoAre you arguing that that is a good thing?
- Too 13y agoC is deceivingly simple, I wonder how many people know about strict aliasing rules for example. To verify a C-program you should really 1. Do static analysis, preferable using many different tools, 2. Test on different optimization levels, 3. Test on different compilers.
- bowyakka 13y agoI posted this a while ago https://news.ycombinator.com/item?id=6230503 https://news.ycombinator.com/item?id=6230503 It still intrigues me that this happens, I do wonder if it is limited to languages like C or if it could conceivably happen in anything with an advanced runtime (think the porter stemmer bug that broke java7 on release) Maybe we can introduce this to jit-spraying ? (http://dsecrg.com/files/pub/pdf/HITB%20-%20JIT-Spray%20Attacks%20and%20Advanced%20Shellcode.pdf http://dsecrg.com/files/pub/pdf/HITB%20-%20JIT-Spray%20Attac...)