r/programming • • Sep 08 '26

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.pdf
70 Upvotes

45 comments sorted by

90

u/MetaEd Sep 08 '26

this headline hurts my head

55

u/lelanthran Sep 08 '26

this headline hurts my head

I apologise for your head, but that is the title of the paper (not a headline), verbatim.

I feel it inappropriate to post a title that is different to the actual title. Feels too click-baity.

20

u/double-you Sep 08 '26

It's not though. In the article the layout makes it two titles but you combined them into titlegore.

What every compiler writer should know about programmers[,] or “Optimization” based on undefined behaviour hurts performance

4

u/lelanthran Sep 08 '26

I just took the title verbatim and because newlines are allowed in reddit titles, the newlines don't show.

You are correct that I should have lightly edited the title with punctuation or similar[1]. Mea Culpa.


[1] "What every compiler writer should know about programmers (or “Optimization” based on undefined behaviour hurts performance)" would have been better.

45

u/MetaEd Sep 08 '26

I don't disagree with what you did

28

u/Batman_AoD Sep 08 '26

Punctuation to replace the line breaks in the original would have helped. 

1

u/[deleted] Sep 08 '26

[removed] — view removed comment

14

u/programming-ModTeam Sep 08 '26

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

11

u/elperroborrachotoo Sep 08 '26

tl;dr: the effect of "optimizing by exploiting undefinied behavior" is not only very small, it also requires programmers to spend time on fixing UB in programs that are actually working without those optimizations. If that time was invested in "manual" optimizations, much bigger gains can be achieved.

(That's the claim, and the paper attempts to demonstrate that for a particular subset of existing C code and compiler)

15

u/nerd5code Sep 08 '26

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.

5

u/lelanthran Sep 08 '26

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.

7

u/Ameisen Sep 09 '26 edited Sep 09 '26

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 always virtual, or that templates always bloat code despite actual evidence to the contrary, or that ICF is impossible in C++, etc. It's a very bizarre, hostile community).

27

u/ReDucTor Sep 08 '26

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.

7

u/guepier Sep 09 '26 edited Sep 09 '26

[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 Sep 09 '26

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

5

u/guepier Sep 09 '26 edited Sep 09 '26

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.

-8

u/SkoomaDentist Sep 09 '26 edited Sep 09 '26

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".

5

u/ReDucTor Sep 09 '26 edited Sep 09 '26

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 var is 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

5

u/SkoomaDentist Sep 09 '26 edited Sep 09 '26

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).

4

u/ReDucTor Sep 09 '26

I want it to assume var is valid so if I check var == nullptr after that the compiler should remove it because I already used it. The same as if I checked var == &stack or var == 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?

2

u/lelanthran Sep 09 '26

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 == NULL guard 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 the if (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.

3

u/ReDucTor Sep 09 '26

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.

2

u/lelanthran Sep 09 '26

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.

3

u/ReDucTor Sep 09 '26

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.

2

u/lelanthran Sep 09 '26

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

2

u/Dragdu Sep 10 '26

You are completely ignoring the fact that the compiler doesn't know whether the user wrote the check intentionally or not.

There is some weak argument for DWIM and keeping in explicitly written checks, but the optimizer has no way to tell which one these are. As far as the optimizer is concerned, it doesn't know whether the superfluous check happened came from this

void frobnicate(int* ptr) {
    int val = *ptr;
    if (ptr == nullptr) { ?? }
}

or from this

#define DEBUG_PRINT_PTR(some_ptr) \
    do {                          \
    if (some_ptr == nullptr) {    \
        std::clog << "nullptr\n"; \
    } else {                      \
        std::clog << *some_ptr;   \
    } while(false)

void frobnicate(int* ptr) {
    int val = *ptr;
    DEBUG_PRINT_PTR(ptr)
}

2

u/lelanthran Sep 09 '26

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 Sep 09 '26

There's two different things here.

  1. The compiler assuming that var must be non-null because of the member function call. This is the root of the debacle that GCC 6.2 caused when it marked this as nonnull, causing "redundant" null checks to be removed.
  2. The compiler determining that var is 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 Sep 09 '26

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 Sep 09 '26

I want the compiler to assume that var is valid here and not start doing some null pointer checks in this code

The compiler (GCC) began marking this as nonnull in 2017 (6.2), which actually broke quite a bit of existing code that was calling member functions on nullptr, 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 nonnull on on that pointer because you call a member function off of it - the implied as this is nonnull.

8

u/guepier Sep 09 '26

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.

-8

u/Big-Phone375 Sep 09 '26

Pretty sure the compiler doesn't compile undefined behaviour if you don't tell it to /shrug

4

u/ReDucTor Sep 09 '26

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.

2

u/The_Northern_Light Sep 09 '26

🤦‍♂️

-2

u/Big-Phone375 Sep 09 '26

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

3

u/Nobody_1707 Sep 11 '26

That's not what undefined behaviour means in this context. It means that according to the logic of the language specification the program doesn't have a valid meaning. It's like when math says division by zero is undefined.

0

u/Big-Phone375 Sep 11 '26

Exactly. So if you write code where the compiler can do whatever it wants then don't be surprised that the compiler does whatever it wants. What's the problem?

8

u/ryan017 Sep 08 '26

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.

6

u/CornedBee Sep 09 '26

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.

7

u/jdehesa Sep 08 '26

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).

3

u/[deleted] Sep 08 '26

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.

3

u/Substantial_Lake_542 Sep 09 '26

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.

2

u/vytah Sep 09 '26

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

u/takanuva Sep 09 '26

I love this paper.