Do we really need undefined behavior?
ralfj.de
ralfj.de
> Here I refer to the typical modern interpretation of UB: assumptions the compiler may trust, without bounds on what happens if they are violated.
Makes that abundantly clear.
This basic realization opens up many avenues for interdisciplinary research. For example, maybe all the ink spill on "paraconsistent logics" will finally be useful for designing an unsafe language like C. (https://plato.stanford.edu/entries/logic-paraconsistent/ https://ncatlab.org/nlab/show/paraconsistent+logic .) Maybe "unsafe" in Rust is best understood as a logical "mode" of some sort. Lattice of allowed behaviors lead to a nice fine-grained semantics for semi-defined behavior.
I honestly don't know whether no one talks about this because it is very obvious to researchers in the field, or because no one actually dove deep into this interpretation.
Just to be clear, Ralf Jung might be writing for a popular audience with this blog post, but is certainly a preeminent research of this stuff.
I guess I hope some writes a "back to the basics" blog post of this stuff at some point!
1. fully binary: "[all] UB is nonsense" vs. "[all] UB is necessary for performance"
2. qualitative / anecdotic: "look at this compiler doing something unexpected" vs. "look at this optimizing compiler's transformation that would be impossible without UB".
Instead I would love to see a more fine-grained and quantitative study. There are many different types of UB. I'm sure every one of them is exploited by optimizing compilers. However, what would be the quantitative impact of disabling each of them on, say, SPECINT benchmarks? Of course some types of UB-related assumptions are deeply embedded in compilers, so it's clearly a question easier asked than answered. But I think simple things like signed-integer overflow handling can be changed (in clang at least?). Has anyone done benchmarking with this? Are you aware of any papers on the topic?
If, like C, you think you do, you accept (on currently popular CPUs) that code may read from and write to arbitrary memory, and that means you have to define that as “anything can happen”.
If you don’t, I think you can get rid of the most common causes of UB.
So, with modern compiler technology, are languages that check array bounds necessarily slower than those that aren’t? If so, is the difference large enough?
For performance sensitive tasks - definitely! I certainly don't want array bound checking in my (soft)realtime audio processing code.
As a side note: when I write an audio plugin, it's the responsibility of the host application to tell me the correct buffer sizes, so I basically deal with trusted input. It's still possible to mess up, of course, but personally I found writing DSP code to be pretty safe.
In Rust, if you use iterators or make loops simple enough for LLVM to understand, then redundant bounds checks are optimized out, so the safety is essentially free.
However, there are certain types of hot loops, like matrix operations, that are too cumbersome to write as 1d iterators, and are too complex for LLVM to prove safe. In that case bounds checks hurt performance a lot. Not because of checks themselves, but because added control flow prevents autovectorization and other optimizations that depend on reordering code.
We need smarter optimizers that understand they can collapse and move bounds checks. Currently `a[1], a[2]` has 2 bounds checks, but `a[2], a[1]` has 1, because the optimizer thinks you care exactly which one of them will fire, rather than merely ensuring the safety.
I think introducing UB while planning tight integration in the language's tooling beforehand has lots of upside. Even GCC's ubsan does quite a good job, although created retrospectively.
But once compilers start adding these special cases then new code has to be written to understand "if I add a bounds check on some wrapping operation this compiler thinks I am insane and removes it as it assumes I am an idiot using the wrong type". And once compilers start doing that, particularly with incompatible heuristics, the concepts of what the language is even guaranteeing begin to erode and the standards adjust to define "undefined" behavior.
But the correct solution wasn't to fix the compiler... it was to use the correct data type! Whether that feels like it should be size_t or uintptr_t I will refrain from providing an opinion on in this comment (to avoid bike-shedding), but the premise that the compiler is a billion little attempts to figure out how to make my code faster--rules that change constantly and see under-specified--when it is the code that is wrong is extremely frustrating.
If you want to avoid some aliasing use case, or make math operations faster, or avoid issues with the calling convention on "this" pointers, or whatever it is... we should agree on what the code should look like to make those semantics clear and then forcibly deprecate as non-compliant any implementation that uses strange quirks to auto-detect and "improve" old code.
Alternatively, we should have a special mode the compiler should support to "just do what the code says even if it is slow" and we should then guide developers in the direction that it is a "code smell" to stay in quirks mode: that if there is a way to make the "strict" compiler mode understand your code correctly and still be as fast as the one with tons of undefined behavior, it is your code that is at fault.
But like, the market incentives will never support this: people evaluating between two compilers are going to run benchmarks against projects that they have been using for decades and choose the compiler that "works better"; and meanwhile, convincing developers to stop using "int" or explicitly call out aliasing or whatever will never happen because people will benchmark the code against a compiler with all these bells and whistles and decide "the risk of making these modifications to every single place in our code where it might matter is you great as we might break something in the process and the compiler seems to compile our code just as fast without it being explicit (due to UB)" with a side of "the explicit syntax for that is caught up in committee and isn't supported on one of our key targets yet".
So, I personally consider this all a "lost cause". But I also really want to point out that the root cause of all of this undefined behavior is due to an underlying incentive structure that your pet language isn't immune to: you just got to start off clean without a ton of legacy baggage code. You don't have a ridiculously large amount of code written with silly assumptions for 16-bit systems that has been carefully dragged through the ages into 64-bit, and you have a ton of explicit syntax already to prevent a lot of the other brutal cases in all new code... and there is also (probably) a single implementation of the compiler.
But, one day, 20 years from now, after a billion lines of code have been written in your language, there are four big implementations of the compiler (only one of which still supporting legacy ARM CPUs, as everyone has since moved on to KR7 or whatever is hip in 2040), and you've made a ton of sad choices in an attempt to hold your community together, someone is going to weigh a cost/benefit analysis and decide "keeping existing code working but making it faster is more important--and wins us more marketshare--than telling people how to port their code to the new era".
Now, I don't know what these cases are going to be--maybe something super complex involving how massively parallel execution environments handle order of execution for old code designed to run on a classic computer core, or how to map explicit integer representations into prime-order field elements for zero-knowledge execution, or what to do with information leakage during homomorphic encryption--but it is going to happen, and we are going to repeat all of these "quirks mode vs. strict mode" discussions each generation for every actually-important piece of technology, just as we have for standards even so far afield to "programming" as HTML and TCP.
Is it? I always internalized int as “the most natural sized number for the platform”. For a lot of uses, that’s a pretty reasonable choice, despite there more specific/constrained types available now.
Basically, to get decent perf out of C loops, arithmetic overflow has to be left as UB for int. If the standard index variable type had historically been unsigned and defined to terminate on overflow or something, you could make wrap-on-overflow standard for int without killing the performance of hot inner loops.
GCC says:
> -faggressive-loop-optimizations This option tells the loop optimizer to use language constraints to derive bounds for the number of iterations of a loop. This assumes that loop code does not invoke undefined behavior by for example causing signed integer overflows or out-of-bound array accesses. The bounds for the number of iterations of a loop are used to guide loop unrolling and peeling and loop exit test optimizations.
int *x = j + 32/4;
*x = 40;
int x; // &x would have size 1
int *y = malloc(5 * sizeof(int)); // Size 5
int *z = y + 2; // Size 3
int w[4]; // Size 4
As for pointers to already-freed objects, it is undefined behavior to read, calculate, or compare them in any way; the only legal operation is to overwrite or dispose of the pointer.
Though one of the confusing issue with UBs is that the purpose of the UB varies.
Some UBs are really close cousins of IBs like UBs on signed overflow: it could be IB but was probably found not worth the status, so was left undefined.
Others are about the intersection of efficiency and lack of expressivity, like dereferencing null pointers: implicitly checking each and every access was (likely) considered too costly, but the language has no way of expressing nullability statically.
So given a language with C-type semantics, you don't need the first UB (though it can certainly be leveraged by compilers), while the second one is much harder to get rid off.
(And to be clear--I think the article is being incredibly diplomatic in saying "there isn't enough research" into compilers that don't optimize based on UB. It would be absolutely shocking if a non-UB-based compiler were able to come anywhere close to modern C compilers on either real-world programs or toy benchmarks, because almost every avenue of optimization would be closed to them. When any out of bounds write from anywhere in your code, including another thread, can modify a variable on the stack, it's not even usually possible to coalesce or rearrange writes, or remove redundant reads! These sorts of things are the bread and butter of compiler optimizations. Hell, are we even allowed to inline function calls? It might break out of bounds writes to the saved stack pointer!).
Anyway, if this is basically just "C is bad", whatever, I'm not using C for anything. I'd use Zig or Rust.
That's literally what UB is.
If the compiler makes any optimizations based on those axioms, and the axioms are violated, you'll end up with unexpected behaviors ("lighting your program on fire") that are crazy hard to debug. So saying "the compiler can have UB, but it just shouldn't make weird optimizations based on that" is a little hard to justify, or else you get absurd results like what I outlined in the post above. A lot of beginning C programmers do find it strange that they can't index past the end of a variable and expect to always hit the next variable on the stack, for example, but experienced C programmers aren't. Being able to rearrange, reuse, and register allocate variable slots is one of the most fundamental optimizations out there.
Now, imagine if compilers were never allowed to reorder writes and loads because another thread might potentially update them... pretty crazy, right? Well, a lot of the "benign data races" people yell at compilers for screwing with, are caused by exactly that kind of reasoning, assuming that writes in one thread will always be seen in the same order by other threads without any explicit synchronization or ordering primitives. And that's not even necessarily a "messing with what the hardware does" thing, because there's hardware out there that will reorder ordinary loads and stores for you!
Modern C# has next to no undefined behavior, you can disregard the managed features and write low level code with it, and it JIT-compiles nearly as efficiently as C.
Unity has an LLVM-based compiler for a subset of C# that emits extremely clean native assembly.
These days there's no real reason for languages to be as ugly as C.
The calculus for memory-safe languages is completely different. They are not allowed to perform arbitrary, unchecked, out-of-bounds writes, so optimizations assuming those writes don't exist are sound without UB. If you mix them with an unsafe language or component that can use raw pointers, that part of the language has a lot of the same UB that C does, or else it would invalidate optimizations in the managed part of the language. If you've ever seen C++ code that needs to interact with a managed runtime, you're well aware of how careful the unmanaged part has to be to avoid treading on runtime invariants.
Anyway I'm not defending C here. I'm defending UB. It exists in the language for a reason, which is that it's not meaningfully possible to optimize programs without it. If people don't want to deal with it, they should use another language that isn't C. That doesn't mean that the amount of UB in C couldn't be greatly reduced, but the article is responding to people who claim that a modern optimizing C compiler could reasonably avoid non-"platform specific" UB altogether.