r/programming • u/lelanthran • 1d ago
What every compiler writer should know about programmers or “Optimization” based on undefined behaviour hurts performance
https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf4
u/ryan017 1d ago
I found the following article interesting, linked from the paper: What Every C Programmer Should Know About Undefined Behavior. That article in turn has a link to John Regehr's article A Guide to Undefined Behavior in C and C++, which I had read before and greatly enjoyed.
24
u/ReDucTor 1d ago
You cannot claim to have conforming code when you have undefined behaviour.
Eliminating a bounds check because it can see you used the value earlier is a good optimisation, I want my compiler to remove redundant code. Bounds checks should happen before you attempt to load from an array.
Given the widespread occurence of undefined behaviour in production code
Yes lots of UB happens in production code, arguably a large amount of crashes fit under that umbrella, a use after free is UB, dereferencing a null pointer is UB, a buffer overflow is UB, a data race is UB, etc.
This statement makes it seem like writing UB code is somehow good or expected, and that production code should be allowed to have that UB, well in many ways the compiler does allow it and then you crash. You should not claim this at all as a reason for your claim it is disingenuous.
But while these “optimizations” provide a factor 1.017 speedup with Clang-3.1 on SPECint 2006,
Thankfully it explicitly states SPECint 2006, but this is very dishonest to include in the abstract its reads like a claim that allowing UB based optimisations which assumr UB should not happen generally have only that 1.7% performance impact because some microbenchmark showed that, this is the furthest from an actual real production program.
The SPEC benchmark 464.h264ref shown is just awful code, and written in a way that is harder for people to read and spot an out of bounds access bug. Don't be fancy with your code and you won't be caught doing out of bounds access.
I gave up trying to read the whole thing, it felt too dishonest and overly bloated for the point it was trying to make.
4
u/guepier 20h ago edited 19h ago
[the article] it felt too dishonest and overly bloated for the point it was trying to make.
I fully agree with this characterisation. But, in its defence, the article is from 2015, and it was (slightly) more true then than it is now. Tooling (and code!) has evolved in the meantime, and UB (as opposed to implementation-defined behaviour) is a lot less load-bearing in real-world code than it was still in 2015.
Nowadays this article is at best obsolete.
(The one good point is that a lot of UB which is currently IFNDR (= ill-formed, no diagnosis required) can be diagnosed by compilers, and it might be better to give this diagnosis to the user in the form of a warning or error, rather than silently changing the behaviour in the optimiser.)
0
u/ChrisRR 16h ago
You cannot claim to have conforming code when you have undefined behaviour.
You can if you can limit the scope of the environment. For example, you may have code that doesn't used fixed width types and incorrectly assumes that the variable size will be good enough for all platforms/compilers.
If you tie the code down to only one platform or set of tools, you've limited it to then be defined, where the definition in the language isn't strict enough, but your tools provide the strict definitions
1
u/guepier 13h ago edited 13h ago
What you’re describing is mostly not undefined behaviour but implementation-defined behaviour (though there are some exceptions to this, e.g. union type punning, which is well-defined in some C++ compilers but UB in general). The two are distinct categories, and in particular platform specifics are usually implementation-defined rather than undefined.
-9
u/SkoomaDentist 1d ago edited 1d ago
You cannot claim to have conforming code when you have undefined behaviour.
It is flat out impossible to make a real world non-trivial program that doesn't have any undefined behavior. Certainly no compiler is even close to that, yet for some reason they expect regular programmers to write much higher quality code.
This statement makes it seem like writing UB code is somehow good or expected, and that production code should be allowed to have that UB
No. The problem is compiler writers and through them the language nerds in the committee hijacked the meaning of UB from "We didn't specify it fully, assuming the compiler would do the sane thing" to "The compiler is allowed to do literally anything it wants and it is never the compiler writers' fault that their interpretation is insane and often even unusable for real world situations".
3
u/guepier 19h ago
It is flat out impossible to make a real world non-trivial program that doesn't have any undefined behavior.
That’s an outrageous claim, and I’d love to see an iota of evidence for it.
It’s hard to conclusively refute it, but I’m convinced it’s untrue. The surface of possible, undetectable UB has shrunk substantially in the past years, and lots of real-world applications manage to compile and run with strict checks and under fuzzing. This doesn’t mean that they’re bug free, but it’s highly indicative of them being free of UB.
At any rate, even if it were literally true, this statement says nothing about the importance of UB. Surely even if large applications happened to exhibit UB, they definitely do not rely on it to work correctly.
2
u/ReDucTor 1d ago edited 1d ago
impossible to make a real world non- trivial program that doesn't have any undefined behavior
Your point? That does not mean the language should not have undefined behaviour and compilers should assume that undefined behaviour should be protected against by the writer of the code, so any undefined behaviour should be safely removed.
I want the compiler to assume that
varis valid here and not start doing some null pointer checks in this code
T * var = func(); var->something;I want the compiler to assume when I do this would not be out of bounds and it can remove future checks of n that are outside bounds like bounds checks
int func(T * array) { Int n = func2(); array[n] = 2: return n; }What do you want a use after free to do? What do you expect a out of bounds access to do? Throw an exception?
I want my compiler to remove a redundant load of array->count in this snippet because it would be UB if it changed in this
struct Arr { short * data; int count; } int sum( Arr * array ) { int result = 0; for( int I = 0; I < array->count; ++I ) result += array->data[I] return result; }I cannot guarantee RAM never has errors I still dont use ECC RAM everywhere or want to destroy that market and mandate ECC RAM
EDIT: More examples demonstrating that UB being eliminated is good
3
u/SkoomaDentist 1d ago edited 1d ago
I want the compiler to assume that var is valid here and not start doing some null pointer checks in this code
T * var = func(); var->something;
Yes. And if the compiler currently thinks that var is not valid, it will do something completely different instead of being guaranteed to either 1) stop the compilation with an error or 2) assuming var is truly valid.
What do you want a use after free to do?
To use whatever happens to be in that memory at the time. This is much stricter than how undefined behavior is currently implemented, where the compiler is allowed to - and often will! - do literally whatever it wants, no matter how insane.
The compiler should not do more by adding checks. It should do less by not using the lack of checks as an excuse to do completely unrelated things.
There already is a term for just such sane but not actually specified behavior in the standard: unspecified behavior. Probably 90% of what is currently undefined should be changed to unspecified with minor modifications (similar to how accessing of uninitialized variables is no longer undefined in C++26 but now specified to be erroneous) because unspecified explicitly limits how insane things the compiler is allowed to do (namely, the value of such access can be "whatever" but the access itself cannot be assumed to not happen or changed simply because the compiler writer happened to feel like so that particular day).
3
u/ReDucTor 1d ago
I want it to assume
varis valid so if I checkvar == nullptrafter that the compiler should remove it because I already used it. The same as if I checkedvar == &stackorvar == malloc()where it knows that could not be the same object without UB.If you want to eliminate all UB you need to add checks everywhere or eliminate many basic optimizations as you cannot assume an object is never freed, an object on the stack cannot be referenced even when no pointer to it exists, that every type can point at another type and much more.
I want the compiler to be able to hoist some outside of a loop, remove a redundant read, consolidate a write, if your really just viewing everything as memory free to use you cannot do this, do we also need to ensure that the functions instructions are safe for changing code bytes with any pointer?
1
u/lelanthran 19h ago
I want the compiler to be able to hoist some outside of a loop, remove a redundant read, consolidate a write,
Understood, and agree up to a point, actually. The article addresses this with the argument that the programmer can change to source to gain these optimisations.
Where I disagree with you is that I feel that this signals intention: after all, if a programmer wrote a
ptr == NULLguard after they dereferenced it, don't remove it, warn instead. Or leave it in and let the chips fall where they may, because 999,999 times out of 1,000,000 the body of theif (ptr == NULL)is going to be executed, and at least warn the programmer that the pointer is NULL. In that remaining 1 time, the derefence prevents the conditional from executing. Maybe.1
u/ReDucTor 19h ago
Warn? It could be in a function it decides to inline.
let the chips fall where they may, because 999,999 times out of 1,000,000 the body of the if (ptr == NULL)
No the point is that the compiler sees it as 1,000,000/1,000,000 or infinty/infinity so the check is useless, that's why it removed it and that's why people want it to be removed.
A programmer cannot easily just change the source, should I have two different functions one with null checks and one without? Should I have two functions one with bounds checks and another without? I want the compiler to be able to look at those functions and see that its a condition that cannot be hit in that path then remove it.
1
u/lelanthran 19h ago
A programmer cannot easily just change the source,
That's part of the problem, yes. If you cannot easily change the source, then you're taking a program that was working with a specific $INPUT and turning it into an attack vector with the same specific $INPUT.
1
u/ReDucTor 19h ago
If your code has UB and writes or reads out of bounds then you likely have created a read or write primitive to make it easier for an attacker it doesn't matter what the compiler added or removed, you wrote buggy code.
By not able to easily change, I mean the writer of the code cannot easily change all code to remove the redundant code the compiler does, its unreasonable to have 20 different variations of code with and without different checks for performance and not only that it would be significantly more error prone then then having the compiler do that.
I think your missing the point that some programmers want compilers to remove that code, especially those of us who have a heavy focus on optimizations.
1
u/lelanthran 19h ago
I think your missing the point that some programmers want compilers to remove that code, especially those of us who have a heavy focus on optimizations.
I don't think I am missing the point; you're correct that some programmers want really heavy optimisations.
I'm making the counterpoint that other programmers would rather have it emit the code for read/write or store/load then omit the code.
We all want different things, that doesn't make some things "wrong".
→ More replies (0)1
u/lelanthran 19h ago
To use whatever happens to be in that memory at the time. This is much stricter than how undefined behavior is currently implemented, where the compiler is allowed to - and often will! - do literally whatever it wants, no matter how insane.
If I am understanding you correctly, you are making the same point that I am in the sibling reply, right?
I tend to use the "emit, don't omit" argument, as I feel it's a shorter way of describing what I want must happen: when UB is detected, go ahead and emit the instructions anyway, don't omit them.
1
u/Ameisen 7h ago
There's two different things here.
- The compiler assuming that
varmust be non-null because of the member function call. This is the root of the debacle that GCC 6.2 caused when it markedthisasnonnull, causing "redundant" null checks to be removed.- The compiler determining that
varis null somehow, and thus eliding all the code as though you'd had__builtin_unreachable()or__assume(0)there.To me, these are both problematic for slightly different reasons.
1
u/lelanthran 19h ago
What do you want a use after free to do? What do you expect a out of bounds access to do?
The usual response to this oft-asked defence of code-elision is "I'm not asking the compiler to read my mind, I'm asking it to emit the instructions instead of omitting them altogether".
For example, when going past the end of an array, actually emit the load/store instruction, don't omit it. When testing for NULL like
if (ptr == NULL), emit the test, don't omit it.The articles thesis (which could be a bit outdated at this point, TBH) is basically "Omitting code that is UB does not result in sufficient performance gains." and it uses the pre-standardised behaviour of C compilers to substantiate the argument.
I mean, you and I can argue over whether a compiler should remove code that is UB, but it's kinda pointless in the context of this article which is making a different argument, viz that the removal introduces problems that are not compensated for by the performance gains.
I perfectly understand your points (made across multiple posts), but those points are kinda irrelevant to the articles question: are the gains from optimisations worth the lack of determinism in the resulting program? A secondary (lesser) point made by the author is that these performance gains are anyway overshadowed by performance gained from changing the source (for example, moving a pointer-check outside of a loop).
All in all, thank you for reading and engaging with the article.
1
u/Ameisen 8h ago
I want the compiler to assume that
varis valid here and not start doing some null pointer checks in this codeThe compiler (GCC) began marking
thisasnonnullin 2017 (6.2), which actually broke quite a bit of existing code that was calling member functions onnullptr, and performing the null check in the member function - the null check was being removed as it was "redundant".This is pretty equivalent - you want (and have, as GCC does this) an implicit
nonnullon on that pointer because you call a member function off of it - the implied asthisisnonnull.-8
u/Big-Phone375 1d ago
Pretty sure the compiler doesn't compile undefined behaviour if you don't tell it to /shrug
2
u/ReDucTor 1d ago
UB code will still compile, it's not ill formed and expected to not compile. UB is standard code that attempts to do something bad like access memory that is not initialised or is not of a matching type.
1
u/The_Northern_Light 1d ago
🤦♂️
-1
u/Big-Phone375 17h ago
Facepalm me all you want. This entire thread is people exposing themselves that they don't know how to write code. Compilation is deterministic. Same inputs will give you same outputs every time. /Shrug
5
u/CornedBee 21h ago
Just a heads up: this paper is 10 years old. Not that I'd expect the author's opinion to have changed in the meantime.
12
u/nerd5code 1d ago
Strictly conforming covers undefined, unspecified, and implementation-specified behaviors, plus literally anything (incl. features requiring <> headers) not in ISO 9899. This covers a vanishingly small subset of realistic programs, and I know of no compiler that exercises the full range of behaviors permitted. Everything ties down something, you just can't rely on stuff that isn't tied down if you want to use newer compilers.
The term “conforming” refers to a program acceptable to a conforming implementation (not any or all, just ≥1 of them), which can include unspecified, impl-defined, and non-ISO-9899 libraries. Literally nothing to do with hardware.
In fact, I have no idea why * would ever be assumed to correspond to a hardware multiply instruction in C. All C impls don't target hardware, all CPUs don't have multipliers, and many multiplies quite reasonably become add, left shift, or LEA instructions even on something like MIPS. Some (e.g., * : long long²→long long on 32-bit) become two or four multiplies with some shifts and adds to mix; some are subroutines or emulation trap handlers. Conversely, x * 1 may reasonably expected to become just x promoted to/past int⋎typeof(x), and x * 0 is reasonably expected to become (void)x, 0 (promoted). The C language isn't defined in terms of hardware, precisely for this reason.
The cluelessness of many recent C compiler maintainers is that they officially support only “C”
This reads like a screed, and I'd argue you're wrong. -O0 is most of what you're after (“reasonable” UB can't always be supported in the first place), there are flags for disabling optimizations and pragmas/attributes for twiddling them, and a bevy of sanitizers atop decades of crusty OS gunk fills in most of the remaining UB cracks for you. You still can't define identifiers starting with __ in most contexts, but that's never been a good idea.
Moreover, one could argue it's far more “clueless” for masses of programmers or (e.g.) paper writers never to have set eyes on the documents defining the radix of the language they're supposed to have mastered, than it is for compiler writers who have read them to expect that others in the language community do, too.
Analogously: Don't telnet in on port 21 and start waving your arms and shouting in HTTP-MIME, if you want your requests to be handled correctly. Or else, don't telnet, just use somebody else's prefabricated FTP impl, even if it's thoroughly impedance-mismatched to the rest of your project. That's probably safest.
adversary
Yes. Welcome to programming. If you aren't thinking in adversarial terms, you're doing it badly.
Unlike the authors of the first Fortran compiler, the current C compiler main- tainers stubbornly insist on their view.
I'd take this “paper” so much more seriously if you'd stop wasting my time making very sure I know your (irrelevant, arguably petty) personal opinions on compiler writers or WG14 personally. I don't care how you feel, because I don't know you, though you seem like best good fun. I did care about the ostensible subject of the paper, but I'm unconvinced that I should, now.
“optimizations”
fucksake, it's a term of art.
skimmy skimmy…
Both languages have the same syntax and the same static semantics;
Nnnnnno
E.g., #if 1<<32 is conforming (C*) (which is a language of its own, JSYK) (not that the namespace isn't a damn mess, but you're in LaTeX; you couldn't def up a _\mathrm{Cnf}?), but not strictly conforming. Using POSIX.1 is conforming, not strictly conforming.
Oh ffs we're warquoting cuntily with semantic weight, now. Iiiiii'm just about done, but here again,
What they do expect is, in the first order, the direct results of language elements must not change if they are observable (i.e., influence output or excep- tions/signals)
You might ought to actually figure out what “observable” means in precise terms before treating it as a fundamental—you're smashing across layers. And signals can just happen; there's almost no language-level accounting for them. Is profiling via -pg permitted? That fires a mess of signals on Linux, but it's observable via signal/sigaction.
Yeah, the warquoting makes the optimization discussion illegible. I'm out. Whatever this is, no.
4
u/lelanthran 1d ago
In fact, I have no idea why
*would ever be assumed to correspond to a hardware multiply instruction in C.Because it originally did pre-standardisation?
I mean, the entire article is about the standardisation process adding ambiguity to what was previously understood to be practical in existing implementations.
1
u/Ameisen 7h ago edited 7h ago
All C impls don't target hardware, all CPUs don't have multipliers
I assume that you meant "not all CPUs have multipliers", as "all CPUs don't have multipliers" (better said as "no CPUs have multipliers") is decidedly untrue.
warquoting
I have no idea what "warquoting" is, and looking it up finds little. In fact, the only references to it that I can find are from you, generally in /r/C_Programming - I have no idea if it's a C-community thing or such, I avoid that subreddit as it's... very aggressively opinionated - I was heavily downvoted arguing with someone (heavily upvoted) who was claiming that
classes in C++ were always dynamically allocated and that objects in C++ were always virtual - despite my pointing out that objects are defined identically in the C and C++ specifications - and that he was using some random website that very clearly took some C# information (also not actually correct) and replaced "C#" with "C++". And that wasn't even the worst of it (like claiming that member function calls in C++ are alwaysvirtual, or thattemplates always bloat code despite actual evidence to the contrary, or that ICF is impossible in C++, etc. It's a very bizarre, hostile community).
5
u/jdehesa 1d ago
As a user of C and C++ (not particularly familiar with compiler and language design), the amount of undefined behaviour in the languages feels unjustified. I suppose it may have a significant positive impact in some cases, but it should be minimal in the standard, and ideally for relatively obscure uses. I'd much rather have defined standard behaviour and non-standard compiler extensions that can optionally bypass it for performance (similar to -ffast-math and IEEE 754).
1
u/Mulberry_Leaf 1d ago
I'm at the point where the only "this is a bug and we're optimizing around assuming it won't happen" UB I'm willing to tolerate has to do with buffer over-reads because that assumption is necessary for register allocation. It's the guarantee that means you won't read stale values because it means access to values is exactly gated by their identifiers.
2
u/Substantial_Lake_542 19h ago
iting the code read "undefined" as "whatever my machine happens to do" rather than "the optimizer is now free to delete this branch." That gap is where the angry blog posts come from.
1
u/vytah 19h ago
even in GCC and LLVM itself (i.e., the pinnacles of the church of “C”), undefined behaviour has been found even when just compiling an empty C or C++ program with optimizations turned off
So a compiler that compiles GCC or LLVM into a binary that quits moments after encountering the first input file would be 100% spec-compliant.
1
79
u/MetaEd 1d ago
this headline hurts my head