Impact of Undefined Behavior on Performance | Hacker News Reader

Impact of Undefined Behavior on Performance

softwarebits.substack.com

47 pointsSerCe52 comments

The compiler could still sub in the equation for unsigned integers, the equation is (mostly) the same.

Not discussed (that I can see), the real problem is the loop variable -- because the loop ends with ' <= n', which means if n is the largest unsigned integer, this is an infinite loop. One easy thing UB is useful for is proving these types of loop terminate (as overflowing would be UB).

And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b

gcc doesn't seem to implement this optimization at all.

Technically it should be possible for the <=n case, too: An infinite loop is undefined behavior, so the compiler is allowed to assume it doesn't happen. But I guess (for good reasons) compiler writers are reluctant to exploit that too heavily (or it's just about ordering of optimization passes).

Didn't know clang can do it for unsigned, so it seems there really isn't anything here you can only do with UB.

EDIT: I had a quick look to see why the obvious equation ( n (n+1))/2 ) didn't just work. The only problem for large n is you need to do the 'n (n+1)' in a bigger type (it doesn't technically matter if the n*(n+1) overflows, you just need a bigger type), so when you divide by 2 you get the right value in the top-most byte of 'unsigned int'.

You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some much more general optimization.

That's a neat trick! -- I was trying to figure out how to handle the fact I didn't know which of n and n+1 was even.

One nice thing about undefined behavior is that it allows any behavior to be implemented, including diagnostics. So if your compiler has an option to do that (-fsanitize=undefined) then you can make use of that to catch bugs.

If you have defined wrapping/saturating semantics then you don't get this option, even if overflow is a bug in your program.

AFAIK rust also panics on overflow in debug builds, so it's already decided that overflow is semantically a bug by default. So in release mode as it is already a bug then you potentially can't reason about the further behavior of the program. The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much.

fwiw, rust behaves differently between debug and release but in both cases the behaviour is defined. In release mode signed overflow is two-complement wraparound.

You can use this fact to insert assertions that check if that happened and you won't be surprised that the compiler removes the check code you just wrote to check whether something happened!

> The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much.

quite the contrary, the situation is much much worse! The C compiler silently removes code you may have written with the explicit intention of checking the effects of something.

Yes sure you have bug; now with underfined behaviour you have an even harder time figuring out you have a bug in the first place!

I'd be slightly less mad at C (copmilers) if it provided me a way of annotation a statement with "please don't optimize this out".

But seriously, just don't exploit undefined behaviour. Programs have bugs; yes when a program hits a bug and continues you can say that the behaviour of the program is no longer defined according the the original intentions of the author. But wouldn't it be much much better if at least you can reason about what the program does according to how the (buggy) program is actually written?

How mad would you be at a debugger that when asked to inspect the state of a variable that has been subjected to a signed overflow, would just lie to you and tell you it has a value it had some time in the past (or worse)?

Exploit UB to do optims can degenerate to the invocation of nasal deamons. I'm not sure to what extent it would theoritically be possible to avoid daemons while still providing some optimization, nor if any people even studied that question, but pragmatically: - complete violation and exploitation of the VM is a situation that Rust is trying to address as a main goal; - the main implementation using LLVM would make it hard to avoid unbounded consequences given the internal handling of UBs by llvm are rarely exploited with such constraints in mind.

> If you have defined wrapping/saturating semantics then you don't get this option, even if overflow is a bug in your program.

Well, unsigned overflow is also a potential bug, and it's defined behavior. So if you want useful integer overflow diagnostics, you already need to break the C/C++ spec.

Of course, the correct way to model this in a programming language is to distinguish between bitvectors with defined twos-complement operations and fixed-range integers.

Interesting point, but a better post about compilers exploiting this type of ub is ryg’s:

https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...

Safe rust can eliminate the loop just fine if you use fold() or an exclusive range instead of an inclusive one. This is because in release mode it has wrapping semantics for unsigned integers. In debug mode you would get a panic instead for too large inputs. So the behavior is defined, albeit still a bit of a pitfall. But you can enable overflow checks in release mode too if desired.

https://rust.godbolt.org/z/1sK7GEr9E

> or _when_ undefined behavior is our friend. (emphasis mine)

I think this is the key point a lot of responses are missing. It's not that undefined behavior is innately good or bad. It's that it leaves wiggle room that can potentially be exploited for good while being too rigid may not always be the best long-term strategy.

I used to think of code as something that should live forever and compile/run for all time without change. Over time, I've come to realize that just as spoken languages evolve, so do our programming languages. To run/understand code written 2 decades ago, we often have to use compilers/interpreters from that era. I doubt that will change even with extremely rigid language specifications.

Doesn't UB also mean whatever it does might change?

This summation thing seems clever but in a large code base you probably don't want to have a bunch of clever UBs.

Quality/performance of optimizations may change, but that's separate from UB.

Behavior of the code is not supposed to ever change, unless you let the program to cause UB (e.g. give it numbers that do overflow). But you're not allowed to let the program cause UB under any circumstances, ever. So as far as "correct" programs go, it's guaranteed not to change.

UB is about giving freedom to the compiler to assume that certain cases never ever happen, so it doesn't need to worry about them. In C, C++, and unsafe Rust the programmer has responsibility to ensure that UB situations can't happen, so the effect of the assumption can't be observed.

That's not a good take. Compilers love UB because it signals unreachable code, and unreachable code can be removed and/or its surroundings can be simplified. If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part.

Specifically with this example, if the rust community cared, it could implement pattern detection for this operation and reduce it to a constant-time operation too; the reality is just that nobody cares and this optimization was probably only added to make Clang look better on a specific benchmark.

The other problem with UB is how capricious the specification is. There is no contemporary reason for why signed integer arithmetic is UB and unsigned integer arithmetic isn't. It's just a wrinkle from the past that somehow, some people prefer to praise than to fix.

> If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part.

... on hardware where the native instruction happens to trap.

Otherwise it needs to generate a conditional branch and explicit trap instruction, which is as unoptimal as any other imposed behavior.

No, you’ve missed the point. It’s still much better to have a trap than “any other imposed behaviour” because the compiler can reason that this condition is impossible on the happy path and remove code accordingly.

Removing code is both among the most sensitive and the most effective optimizations that compilers do, and they use UB as another signal for “unreachable”. The current model of “assume things never happen and don’t plan anything in particular if it does happen” does no one a service.

If you impose that the unhappy path must trap, the compiler has to guarantee that.

Conversely, if the compiler can reason that the condition is impossible, it can remove code regardless of what behavior is imposed for the condition that it knows can't happen.

> If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part.

That's not true. Suddenly, almost every single signed integer operation on a machine with different hardware integer widths than the language implementation requires branching to check for overflow.

You could also take a measured approach and, like rust, just define signed overflow to wrap. UB and its current interpretation is not worth whatever small sliver of performance the current implementation of LLVM appears to give you.

I don't agree that this is measured. It has a few big problems.

1. Basically no developer actually wants it to wrap. This is almost certainly a logical bug that just pushes the problem a few statements further into the program.

2. Defining it to wrap means that you need software checks for architectures that don't support hardware wrapping on the same width as the integer type. This means that all programs get slower when targeting these architectures. This isn't a "sliver of performance". It is a software branch at almost every integer operation. This approach is not especially well loved in the C/C++ communities.

Cool, one version of a compiler will do the cool optimization that makes it go fast. But since this is undefined behavior, it's also unspecified behavior, and one can't expect it to be reliable. Maybe in practice this doesn't matter, but theoretically there's nothing (besides perf regression testing) stopping the next version of the same compiler from not doing this. Furthermore, you'll be bound to a specific compiler if you care about performance enough to rely on specific behavior for UB, one can't reasonably expect all compilers to do the same thing when they are allowed to do UB.

The problem with undefined behavior is that there are about 200 of them in the C language spec, and I can remember only 3 or 4 at any given time (signed integer overflow, dereferencing NULL, out-of-bounds array access). And I can't remember which ones are "undefined behavior", and which ones are "implementation defined". Sometimes I remember more when I use it a lot, then I forget most of them when I shift to projects using other languages. This means my ability to write correct, non-trivial C code is basically zero.

> And how much impact does it have on runtime performance? Well even computing a sum for a relative small number 1000, according to cppbench, the signed version is 430X faster.

Although you can find these kind of examples for a few lines of code snippet, the question is what is the impact on overall program? Nowadays, I guess it has no impact for almost all programs. Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance compared to optimizations enabled by undefined behaviors.

I'm not so sure, while these certainly have a large impact on performance, I know that compiler optimizations have a huge impact as well, now what part of that is enabled by assuming the lack of undefined behavior I don't know.

You are wrong.

Optimizations directly enabled by Undefined behavior are only a very negligible part of the performance benefits of the existence of UB.

For example, consider the fact that array access out of bounds is UB. Because of this a compiler can assume (without proof) that all accesses are actually going to be in range. This enables a boatload of loop optimizations.

All non trivial optimizations done by a compiler usually assume such facts.

The problem has always been that in practice any nontrivial codebase had UB somewhere (invalidating the entire program!) and diagnosing any particular instance was generally painful until recently. Compilers didn't point most things out, sanitizers didn't exist, and prior to 2011, I don't think there was even a list of UB in C besides the entire standard. C++ is still largely in that position AFAIK.

It's a complete disaster on all sides.

Invalidating the entire program is theoretically correct, but not really a useful statement.

In practice, weird miscompilations due to UB are just slightly more difficult to debug than your usual segfault. You can generally keep reducing your problem to localize the issue in the code.

Also, such issues are not very common because the value obtained from an UB operation is usually nonsense (shifting past bitwidth, out of bounds array element, etc) so a compiler switching things around is just garbage-in-garbage-out. It is of course a serious issue if a program is actually depending on such a value for a crucial operation. That's how you get exploits, with or without the compiler doing something clever.

One of my least favorite bugs came from a loop that iterated from *p to *(p+n) (exclusive). For n=0 and values of p other than null, the loop body never executes. For n=0 and p=null, the loop body is allowed to execute, because null+0 is allowed to be any value.

Nice example! Seems solvable by printf debugging though..

The fact that it’s fixable doesn’t mean it’s fun…

Miscompilations due to UB are normally silent and can remove checks written into the code for security purposes; e.g. checks for overflowing signed integers, or for null pointers.

They're not harder to debug. Debugging them isn't the issue. The problem is knowing that the code in the editor doesn't correspond to the code under execution.

All I can do is point out that very big names in CS (including Linus) disagree with you: http://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf

This is probably because they’ve seen the effects of the foot gun first hand. They also recall what C/C++ looked like before the standards bodies made exploiting UB in compilers open season. There’s also a reason why Rust doesn’t have any UB in its safe dialect even though it sits on infrastructure capable of most/all the same possible optimizations via LLVM.

There was in fact a direct kernel security issue UB exploitation caused in the Linux kernel whereas without that optimization there is no security issue. if I recall correctly the code looked something like:

    Some_value = ptr->value
    If (!ptr) { return; }

This worked correctly in all cases before the compiler added the optimization. It worked less well after because the !ptr check was UB since it followed a dereference. It also wasn’t immediately obvious this code was broken because there was no diagnostic nor any indication that upgrading a compiler would suddenly elide the check. The value-add of such optimizations at scale vs the correctness issues exploiting it causes is questionable.

The problem wasn’t that it’s not fixable. It’s that it takes time to find and you may not even find it until after it’s being exploited.

That code is buggy if ptr can be null. There isn't an especially rigorous distinction between a bug and a vuln. So saying "this was definitely a safe bug and the compiler elevated it to a vuln" can be a thing in very specific situations, but it also isn't generalizable in any way.

Linus is an important figure, but there are plenty of world experts on the other side of this argument. And there is even a third side that states that not only should the compiler avoid optimizations based on UB assumptions, C implementations should instead function more like a virtual machine for a PDP-11 and have everything under the sun be defined (at great cost of performance).

If you take an especially pessimistic view from the compiler, then really really basic stuff is almost impossible. A write to a dereferenced pointer is almost equivalent to a full program havoc. This invalidates almost all facts that the compiler knows and prevents virtually every optimization near that write. Heck, technically this can interfere with things like vtables and invalidate any sort of devirtualization, which is hugely valuable for performance.

No, unfortunately in kernel land this isn't buggy. It's perfectly "valid" to dereference null. You'll read garbage but it won't panic & the null check on the following line prevents any issues (assuming the compiler isn't exploiting UB optimizations).

Sure. I agree with you in principle it's cleaner to have the nullptr check before. However, it's also important to remember that UB & the compiler optimizing around it is a relatively "new" phenomenon & the compiler going out of its way to punish you for it (for a perf improvement that likely doesn't matter in many/most cases) seems punative & not helpful to most C/C++ codebases (with the exception of some heavy math or HFT applications that could probably be better suited with their own language/dialect). IIRC the standard relaxed to allow this in C99 & the consequences weren't well understood until about 10-15 years later once compiler authors realized what the standard was allowing them to do. This is also the most innocuous case - there's plenty of even more subtle issues that UB can cause.

While I agree there can be nuance in viewpoints, I'm not sure what the 3 you are talking about are. Generally there's the pro-UB & optimizing assumptions around it which is largely populated by compiler authors & "performance at all costs". I'd say Chris Lattner, Linus & DJ Bernstein hold a largely similar point of view of UB = bad decision by the C/C++ standards bodies & probably only differ on the solution (Chris = "switch to a different language", Linus = "give me back the behavior before UB was introduced", DJB = "define all current UB").

Personally, while I'm a fan of performance, I'm not convinced that UB has proven enough of a performance gain that it's not better as sitting behind a flag like `ffast-math` - most software would benefit from removing most of the UB optimizations & it's not clear to me that they performance impact would be all that significant.

> Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance

In most media apps, the actually processing intensive part definitely does not do syscalls or OS interaction. It's pure computations for as long as possible (and often non-parallelizable, e.g. x[i] *= x[i-1] sort of things). Disabling those optimisations is a killer.

So, in a narrow, simplistic case signed integer overflow undef behaviour made it possible to replace a loop with a constant. Hooooray!

Pretending that integer overflows don't happen because of undef behaviour is... Funny. Integer overflow do happen a lot, both with signed and unsigned ints. Compilers should only apply radical optimisations in this situation if they can prove an overflow will never happen. Otherwise, they should not touch the loop.

EDIT: typos, rephrasing for clarity

The problem is that “radical” is in the eye of the beholder. If a language is so poorly specified that developers and the specification don’t agree on the meaning of a program, that leaves optimizers in an unwinnable situation.

In this particular case the problem can relatively painfully defined away by Wg14.

Is this really an optimization that we want/need a compiler to do? I kind of get it for really high-level languages like Haskell, but for low-level languages like C/C++ it feels like a silly toy example. The abstract machine is so low-level that many big optimizations can’t be done. Instead the compiler can only do little O(1) optimizations. And you know what, I’m perfectly fine with that. C/C++ trades it all in order to give the programmer significant control over how the code works. If I want to use the summation formula, I can just write that myself. Honestly the thing I hate about the standards bodies is that they try to have it both ways so their compiler developer buds can implement their favorite (imho dubious) optimizations. But as a programmer, what I really want is well-defined, predictable constructs. Worrying about UB while also trying to design an algorithm, while also designing good data structures, while also designing for cache hierarchy , while also optimizing, while also thinking about cache coherency, while also thinking about paging and tlb behaviors, while also.. .. .. It’s all already too complicated before having to worry about what UB the compiler may try to exploit next week. I have a very strong suspicion that almost any non-trivial C/C++ program has UB somewhere. If so, then something is seriously wrong with this whole concept when useful and practical programs written in C are not technically defined/valid C programs!

I think that Zig has undefined behaviour for + overflow both both signed and unsigned values. It also has an 'add_modulo' operator.

Hm… so Rust compiles code as is, whereas C “overly smart” compiler mangles correct code into faster, less correct version.

If Rust is too slow (as measured by the profiler… premature optimisation etc.), you can always take another look at the algorithm and optimise it manually, and correctly.

On the other hand, if C is wrong… let’s hope you manage to isolate the fault to this function (a big if!)… start up the debugger… the assembly will likely look correct, because the compiler won’t optimise so aggressively in a debug build! Good luck debugging <3

If your code has UB then it was never correct. The issue is that instead of telling you about your UB, compiler writers use it to generate very quick but broken programs

Suppose there are 3 translation units compiled from:

a.c

    int foo(int* ptr);

    int main() { return foo(0); }

b.c

    int foo(int* ptr) { return *ptr; }

c.c

    int foo(int* ptr) { return 5; }

All three translation units do not have undefined behavior, so no compiler should report it.

At the time of compilation of a.c, foo does not have a definition. If it is linked with b.c's object file, the program would have undefined behavior. But if it is linked with c.c's object file, there is no undefined behavior. Object files can't tell who they're going to be linked with.

And when b.c is compiled, foo only exhibits undefined behavior if somebody else calls it with an invalid pointer. It's not b.c's problem.

Further, a.c and b.c might be compiled with different C compilers(very common), so you can't rely on any kind of caching of type information or state-tracking across translation units.

When the linker is run, the undefined behavior is instantiated to create an incorrect binary, but linkers aren't regulated by the C standard so it wouldn't be appropriate to include a UB checker in one.

To do what you're saying, you'd need a language designed for whole-program analysis. Rust and Haskell do this, and they both require you to have source code for all your dependencies so they can recompile them each time. It'd be quite the design change for C, and not something compiler writers can "fix" by themselves.

It sounds like we should solve the issue by never using dynamic linking

What OP said has no thing to do with dynamic linking. OP is talking about the linker; the thing that generates the binary by stitching together all the compiled code.

Yes but dynamic linking causes unexpected changes at runtime of the program. Undefined behavior often happens at runtime, so an update of a library can cause undefined behavior in your application. The only way a sufficiently skilled developer can avoid undefined behavior is by checking for undefined behavior at runtime. We are now back to the reason why undefined behavior exists: because we wanted to avoid runtime checking.

The idea that you can just stop writing code with undefined behavior is absurd.

> The idea that you can just stop writing code with undefined behavior is absurd.

If this is true, then this should also apply to Rust or other proven languages: your program will still run in a dynamic environment, and probably calling into all kind of OS and third party libraries. Unless... you write your own (unsafe) wrappers around libraries, trying to catch, as much as possible, errors that can filter into the Rust (or whatever) code. But still, someone has to write these wrappers. If it's not you, you have to trust on somebody else's work, and this is a runtime check that will slow your program down.

Undefined behavior applies internally to the language's code, not to foreign code. FFIs specify how the compiler is to invoke foreign code, how to prepare any arguments, and how to handle any return values. They are not typically part of the language standard, but rather the OS standard.

Windows has different requirements for invoking foreign code vs. Linux for example.

The foreign code may have requirements on how it should be called, but it is not C's undefined behavior to invoke an OS system call incorrectly because the OS is not regulated by the C standard.

You can formally prove that a program has no undefined behavior, and it can still have lots of errors when actually run.

If you statically link the final binary, my point still stands: No translation unit has undefined behavior until the linker statically links them into a binary. (Actually, not until the offending code is run, but if a program can be proved to always trigger undefined behavior you can be a bit loose and say the compiled program has the undefined behavior)

Dynamic linking vs. static linking is irrelevant.

When you write it like that, it sounds insane. But it's very far from how compilers work. There is nothing like "find UB, then take advantage of it", it's completely inverted.

The normal rules the optimizer works from assume there is no UB. It's just always the normal rules, and they work the same way for all programs.

MichaelBurge's comment has illustrated this better than I could.

You could use appropriate tools like valgrind and compile with ubsan to make this a non-issue.

So I'd happily take more performance for code without UB trading off slight inconveniences for debugging UB issues.

Reply on news.ycombinator.com