"Possible" v "Permissible" is not the problem. What seems to be needed (based on reading the post but no other knowledge) is the phrase "including but not limited to".
I don't think that is what the article is arguing for. There it would be more akin to "absolutely limited to" as they don't want anything outside of the examples. Unfortunately for them the examples are still open enough to allow for what compilers do (things like remove code that the author intended be left in).
Personally I'm OK with the more aggressive optimisations, but they are still very controversial -- I think more so in the C than the C++ community (I'm in the C++ one).
> Unfortunately for them the examples are still open enough to allow for what compilers do (things like remove code that the author intended be left in).
Though one could argue that, I don't really think this is the case.
Certainly "ignoring" it isn't the case when you record the fact that there is UB and then optimize based on it.
They also aren't issuing a diagnostic and terminating, either at compile or runtime.
So the remaining option is "behave in a manner characteristic of the environment". Which is fairly loose/rubbery, and I'd be happy to tighten it further. I still don't think it allows the current behavior even as written though, because I don't see how that is "characteristic of the environment". But the stinger is that the behavior has to be documented, which very little of the UB exploitation currently is.
The author concedes that he isn't a compiler engineer, but doesn't seem to think that perhaps compiler engineers have good reason for having their compilers generate code that behaves bizarrely if there's undefined behavior.
There is, of course: performance.
If you want a compiler that generates code which behaves intuitively even under UB, that requirement is at odds with compiler optimisation. Compiler optimisation generally means doing strange and unexpected things to your code, and the reason C has undefined behaviour in the first place (unlike, say, Java) is to maximally enable compiler optimisation.
In other words, C values performance over safety, and that's part of the point.
If you want to catch undefined behaviour at runtime and treat it as an error, the tooling for doing that is better than ever: Clang's 'UBSan', for instance.
Edit
Aside: I have a personal favourite 'incident' pertaining to exactly this tension (between performance and intuitive behavior). Torvalds vents his frustrations on the GCC mailing list, regarding legal-but-counterintuitive behaviour of code generated for the Alpha architecture: https://gcc.gnu.org/ml/gcc/2012-02/msg00038.html
> C has undefined behaviour in the first place (unlike, say, Java) is to maximally enable compiler optimisation.
My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
> Compiler optimisation generally means doing strange and unexpected things
In the first place it should make code faster. I'm no one to judge, but the general reception seems to be that exploiting undefined behaviour (by assuming it will never happen) rarely brings obvious speed advantages. "Strange and unexpected things" can be a bad tradeoff for a tiny speed advantage.
For example, I'll boldly state that optimizing out a "if (p == NULL)" only because p was dereferenced earlier never makes sense. Code containing such a check is never performance sensitive enough to justify the tradeoff (or it's really bad code).
And without being a compiler engineer I assume that it should be easy to change compilers to NOT do this optimization (I assume the not-NULL inference is a special case in the code that can simply be removed).
> In other words, C values performance over safety, and that's part of the point.
Many people value C because of control and allowing one to not paint oneself in a corner. Performance is only a side effect.
> > C has undefined behaviour in the first place (unlike, say, Java) is to maximally enable compiler optimisation.
> My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
These are two ways of looking at the same thing. A naive translation of C statements to what seems like the most straightforward way to do them on some target architecture is an optimization over emulating some other architecture’s behavior. Consider the problem of translating one arch’s assembly to another’s. Essentially, C needs to be defined at a certain level of abstraction for all of this to work, but it also happens that detecting holes in this abstraction is undecideable.
Without changing the output. That's the crucial part of the contract current compilers are breaking. And then try to lawyer it away by claiming that the original was undefined anyway so they can do whatever the hell they want.
I'm no one to judge, but my impression is that the general reception is that exploiting undefined behaviour (by assuming it will never happen) rarely brings speed advantages.
I’ll play devil’s advocate here, even though I strongly dislike the current direction of the major C compilers.
This aggressive interpretation of undefined behavior apparently can enable some important optimizations. Here are a couple of examples:
First, say you have an index variable where you increment it (i += n) and check it’s within bounds (i >= start && I < end). It could be useful to assume that i won’t overflow and wrap, so some of the bounds checks can be optimized out. (The downside is that if you want to explicitly check for overflow, it’s tricky to do so correctly.)
Second, say you have a function that takes several pointers and copies data between them. It can be useful to assume those pointers aren’t aliased, so we can assume that memory isn’t changing in unexpected ways, and therefore it’s safe to optimize out some repeated reads.
I do feel like those cases could be handled in different ways, though. In the second case, perhaps the compiler could insert a runtime check for aliasing, and branch to either a fast path or a slow path as appropriate.
I’m also not sure that C really needs to try to be the fastest and most highly optimized language, even though it’s widely regarded as being very fast. As far as I know C isn’t the most popular language for scientific supercomputing, for example, where the users really do care about performance.
It could be useful to assume that i won’t overflow and wrap, so some of the bounds checks can be optimized out.
This is a very common example, but how hard is it for the compiler to prove that it won't overflow? I know in the general case it's the halting problem, but for specific cases (especially where a human inspecting the code would easily see) it should be easy --- especially those cases which warrant optimisation.
You could go over your source code and see how many operations are done using non-constant data from non-local-scope sources. I would be pretty amazed by a compiler that could find all or most of my operations that don't overflow. Almost all never do, or shouldn't, but that's probably hard to prove and requires global analysis.
Yep, the overflow optimizations are totally needed. Also, aliasing is a big issue of course. I was overgeneralizing. It would be interesting to think what kinds of UB optimizations fall into the "strange and unexpected" camp in the first place. (I don't think overflow or aliasing optimizations do).
Something I'd consider strange and unexpected is that passing NULL pointers as destination to `memset` or `memcpy` is undefined behavior, even if the `size` argument is zero. So compilers are allowed to remove null checks after calls to such functions and AFAIK already implement such optimizations:
memset(dest, value, size);
if (dest == NULL) {
// will be optimized away, although size could be 0.
}
I think most people would agree that `memset(NULL, v, 0)` should simply be a (well-defined) no-op and not result in undefined behavior.
The problem is that array bounds are not available in general. If you use global static arrays compilers can indeed insert checks. In other cases the size might for example be bounded by a terminator sentinel, or have an implicit size based on other runtime variables, etc.
Indeed. To rework the whole ecosystem to enable bounds-checking would be quite a task. External native code that allocates, alloca... not easily done. Not as 'tidy' as Java/.Net where arrays are just somewhat special objects.
> not sure that C really needs to try to be the fastest and most highly optimized language
Sure it does. That's the whole point: performance and low-level access over safety and convenient features. These are the defining attributes of the C language (along with its minimalism).
If you want a safe and convenient language, why are you using C?
If you don't think C should be as fast as possible, which language should? How would that language differ from C?
It's not C's fault that people use it when they shouldn't.
> In the second case, perhaps the compiler could insert a runtime check for aliasing, and branch to either a fast path or a slow path as appropriate.
I don't get you. Are you referring to the dangers of the 'restrict' keyword? Otherwise, it's quite legal to pass aliasing pointers, and the compiler is free to introduce a check for aliasing.
If you're thinking of the strict aliasing rule, I think you're misunderstand it. It has to do with misusing types. To quote Wikipedia:
> pointer arguments in a function are assumed not to alias if they point to fundamentally different types, except for char* and void*, which may alias to any other type
If you want a safe and convenient language, why are you using C?
Plenty of reasons, besides raw speed! If I just want speed and don’t care about safety at all, I’d be using assembly, right?
C has (somewhat) strong typing which catches some errors at compile time. It has higher-level constructs than assembly, like function calls and loops. It’s exceptionally portable (although you have to be wary of undefined behavior and platform-specific weirdness).
Speed is definitely an important part of the story but it’s by no means the only part.
If you don't think C should be as fast as possible, which language should? How would that language differ from C?
Something like FORTRAN maybe? No pointers, as I understand it, hence no aliasing problems.
Unrestricted pointers aren’t necessarily great for speed, but they’re great for flexibility, which makes C a great systems language. FORTRAN might do matrix operations faster, but C is better for wrangling a fiddly file system data structure. Again, it’s not all about speed.
it’s quite legal to pass aliasing pointers, and the compiler is free to introduce a check for aliasing
Right, what I’m getting at is, the compiler is also free not to add a check, and most compilers do not in fact add a check, because they care more about speed.
In fact most C compilers seem to go further; aliased pointers of different types can lead to undefined behavior, so the compiler assumes that this behavior cannot happen, and therefore that the pointers cannot be aliased. That seems to me a logical leap too far.
> If I just want speed and don’t care about safety at all, I’d be using assembly, right?
Not really. C is a reasonable choice of language for high-performance code. There may be instances where your hand-written assembly can outperform compiled C, but it's far from guaranteed, and of course even if you did have such a guarantee, it might not be worth the productivity impact.
Even performance-critical codebases like the Unreal Engine don't use much assembly, as far as I know.
> Speed is definitely an important part of the story but it’s by no means the only part.
Agree.
> Something like FORTRAN maybe? No pointers, as I understand it, hence no aliasing problems.
Indeed, but my understanding is that the performance wins there aren't exactly night-and-day. C is pretty close to as fast as it gets.
> Right, what I’m getting at is, the compiler is also free not to add a check, and most compilers do not in fact add a check, because they care more about speed.
I was unclear - I meant the compiler is permitted to add a check and then use a special optimised path in the case that the pointers do not alias.
It’s quite legal to pass aliasing pointers. When compiling a function which has two pointer-to-int parameters, the compiler is not permitted to assume that they do not alias, unless you use the 'restrict' keyword (which is rarely seen as it's so risky).
> aliased pointers of different types can lead to undefined behavior
Correct (with the special exceptions of void* and char*). Because you shouldn't be doing that.
> I assume the not-NULL inference is a special case in the code that can simply be removed
No I would think it happens naturally as a result of more generally giving abstract values stamps, narrowing the stamps based on expressions, and then simplifying expressions using those stamps. I would guess you wouldn't want stamps and optimisations based on them removed entirely.
> C has undefined behaviour where there is no universally sensible implementation across all architectures.
But that's really the same thing.
Java takes the opposite approach: it lays down the law, and if your CPU does things differently, the JIT compiler will have to generate however many extra instructions are necessary to bend things to Java's approach.
For instance, Java mandates 2's complement, where C does not. Java mandates the size of an 'int', where C does not. Java specifies exactly what happens if you attempt to dereference null, where C does not.
(Too late I see that oddity just made the same points.)
> In the first place it should make code faster
Well of course, or it's not optimisation, it's obfuscation.
> the general reception seems to be that exploiting undefined behaviour (by assuming it will never happen) rarely brings obvious speed advantages
Depends what you mean by 'obvious' I suppose. For instance, Java pays a non-zero performance penalty for insisting on range-checks for array-element accesses.
> I'll boldly state that optimizing out a "if (p == NULL)" only because p was dereferenced earlier never makes sense.
> Code containing such a check is never performance sensitive enough to justify the tradeoff
C programmers tend to hold some disdain for the attitude that they should be made to trade off performance for safety, and not without reason. Claiming they should 'never' care about the overhead of some check, isn't the C way.
If you want a safe language, don't use C. (Well, there's MISRA C, I suppose.)
> it should be easy to change compilers to NOT do this optimization
I don't know exactly what change you're proposing. If you manually check for null, the compiler can't just eliminate your check. Or do you mean C should always check for null at every dereference? The overhead there would be considerable.
Yes, you've got undefined behaviour (i.e. a serious bug in your code), and as far as the compiler is concerned, anything goes.
As the old joke goes, the philosophy of the C language is that the programmer is always right, even when they are wrong. i.e. that it's your job to ensure there's no UB in your source code.
The 'C way' is not to have the language shield you from your mistakes. You can't have that without losing C's advantages. Fortunately, tools exist to help detect undefined behaviour.
It's a pity that runtime detection of easily-detected UB hasn't been an option in C compilers since the beginning. For dev/debug builds, that's almost certainly what you want.
> i.e. that it's your job to ensure there's no UB in your source code.
Have you seen the UB list though? It seems to me that almost all programs fall under some kind of UB. It would be nice to have the compiler produce warnings where it would otherwise optimize based on that UB.
Unfortunately it's a theoretical impossibility to detect all instances of UB in a static-analysis. Rice's theorem strikes again.
These days we have pretty good static analysis tools, and tools like UBSan which can insert certain checks at runtime. Not perfect though.
I believe it's possible to approach it from the other side though: use MISRA C, a terribly strict C programming ruleset, which I believe can be mechanically verified, and which avoids any possible UB. (This is an 'overly strict' approach, as it forbids doing certain perfectly legal things.)
2. The easiest ones to hit by accident are integer overflow ones followed by trapping floating point math.
3. Pointer aliasing is hard to hit if you're not baiting it.
4. Threading requires Data Race Free code. No language known validates this enough.
5. Unchecked pointer dereference and lifetime problems can be avoided especially in C++. It is a subset of missing input validation which again is not enforced in most programming languages.
6. Object slicing rarely comes into play on its own.
7. Format string mess also easy to avoid, s are weirdness caused by longjmp, signals and other ways of messing with the stack.
There are 193 UB cases in C99 and most of them are redundant and group able. Bunch of them can be called "programmer brain is out to lunch".
The list is bigger slightly in C20.
You're right I was too dismissive of the non-technical reasons that a language like C can do well: existence of legacy code, and the fact that all serious programmers already know C.
At the time though, all compiler-generated code would have been at least as bad, no? With the possible exception of FORTRAN.
Performance is relative. Assembly is rarely used today even for high-performance code, as modern optimising compilers are so good.
Today, we know it's not impossible for a new language to gain traction, but all new languages that are used in anger are much more high-level than C. With the single exception of the Zig language, no other language emphasises raw performance and low-level access the way C does. Rust isn't too far off I suppose (from what little I know about it).
Incidentally, Zig has UB too, but it's designed to be nowhere near as troublesome as it is in C.
> My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
There are two less drastic options used by the Standard for those cases.
- Unspecified behavior: behavior that must be "sane" in some sense but may differ between implementations. Vendors need not document the exact behavior.
- Implementation-defined behavior: behavior that must be sane and may differ between implementations. Vendors are required to document the behavior.
> My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
That's somewhat true for things like signed integer overflow, but it's more than that. For instance, if there wasn't UB around pointers being "in bounds", then either there would have to be expensive checking of every pointer dereference ever (both read and write), or other performance drains like values never ending up in registers (both literally and conceptually) for extended periods, they'd have to be loaded from memory every time they're used, effectively treated as `volatile`. (And, this inhibits other optimizations like breaking up structs via SROA.)
For instance,
int f(int *p) {
int x = 0;
*p = 10;
if (x != 0) { ... }
}
The compiler can't optimize out the branch unless it can assume (or dynamically ensure) that the dereference of the pointer p won't point to an unrelated object (x). Arbitrary transformations on pointers (including constructing them directly from integers, and one might guess the stack address of x) are "only" undefined behaviour in C, not prohibited statically.
> Arbitrary transformations on pointers (including constructing them directly from integers, and one might guess the stack address of x) are "only" undefined behaviour in C, not prohibited statically.
Sure, that's what it means to have full pointer arithmetic. It's very much an aim away from face feature of the language.
Yes, that is exactly my point. It's a dangerous feature of the language, or, said another way, has a lot of potential for undefined behaviour. If one is trying to reword the standard to control undefined behaviour, this is one feature that needs to be considered.
For example, I'll boldly state that optimizing out a "if (p == NULL)" only because p was dereferenced earlier never makes sense. Code containing such a check is never performance sensitive enough to justify the tradeoff (or it's really bad code).
This kind of thing really comes to the fore when the compiler is doing a lot of inlining. Say you have some kind of utility function:
int frob(struct foo *f)
{
int r;
if (f != NULL)
{
/* things */
}
else
{
/* other things */
}
/* more things */
return r;
}
..and you call this function all over the place. If some of those callsites end up with `frob()` being inlined, and the compiler can see that the pointer passed is never NULL at that particular site, it can usefully eliminate the dead code. This despite the fact that the code isn't dead in general - just at some of the callers.
Then maybe it should, cause you're using only happy hot path and not the NULL one.
Removing even one branch and debloating cache in a hot path can be significant. And then DCE will enable further optimizations.
If you want to ensure something is not inlined, you're free to do so.
If it were really that performance critical the programmer would not call a swiss army knife utility function that contains a lot of unneeded code (replace "would" by "should" if you like).
If compiler optimization gets to be more and more about making poorly structured code barely faster, no wonder we have all these discussions about uncalled-for optimizations.
If the alternative is the coder having to write a separate "frob_notnull()" function, to be used specifically in certain fastpaths, then yes - that is exactly what many people want from compiler optimisation.
I'd also point out that this is a strange optimisation to choose to pick on, because the only time it's potentially problematic is when a NULL pointer dereference doesn't necessarily trap, which certainly not the usual case on the platforms where common compilers enable it by default (and for the unusual cases, like kernels, the compiler option to disable it is there).
That's true - see my other comment below the original one. I'd remembered that one from faint memory as one of the canonical examples of optimizations gone wrong. And think it might have been a case where that access comes AFTER a test. I don't really remember, though - and I've never had serious problems with optimizations myself.
> If you want to ensure something is not inlined, you're free to do so.
Not really. The compiler is permitted to inline or 'outline' as it sees fit, courtesy of the 'as if' rule. C doesn't let you tell the compiler what code to generate.
The example I should have given was "is dereferenced LATER". Because only in this setting the optimization actually has an effect on most platforms (where dereferencing NULL segfaults).
The optimisation isn't valid unless the dereference always happens.
The criticism arose because this optimisation had been applied in a kernel environment, where the dereference happened before the test, but in some circumstances might not trap. It isn't something that concerns normal applications, though.
I should have researched a better example. But anyways, what about a case like this one?
int *p = get_the_pointer();
if (p == NULL) {
remove_me();
}
printf("Hello %d\n", *p);
At least for some things that remove_me() could do, wouldn't it be possible for a compiler to remove the branch entirely?
I mean I'm pretty sure that compilers can move the conditional below the printf under certain circumstances (as long as there isn't an observable difference for C's definition of "observable"). Add to that the UB and the compiler might as well remove the conditional branch. (And this would be a case that can really take programmers by surprise when debugging).
> Yes, it depends on whether remove_me() (provably) always returns or not.
Oops, I hadn't thought of that. So the compiler isn't permitted to assume that a function-call will return? Surely that's a huge obstacle to optimisation.
You and caf are right, the compiler can indeed remove the remove_me() call. It is permitted to assume the absence of undefined behavior, so it can 'reason' as you describe.
Of course, the compiler can have the code do anything at all, as it's undefined behaviour. In practice, the resulting behaviour can be deeply counterintuitive ('impossible looking' results).
> C's definition of "observable"
Indeed, which essentially changes meaning when we introduce multithreading. The perceived order of our writes isn't assured to match up to our source-code. The horror-show continues!
> And this would be a case that can really take programmers by surprise when debugging
Or worse: only in release builds. Not impossible, if you do all your debugging on unoptimised builds, but release optimised builds.
C has undefined, unspecified and implementation-defined behavior in those places where there was no implementation consensus 35 years ago; it's just maintaining the status quo.
The thing that were and were not codified as requirements in 1989 ANSI C were a historic accident of the time; now that historic accident is just being preserved, more or less.
E.g. we must have unspecified evaluation order of function arguments because we've always had unspecified evaluation order of function arguments.
I'll ramble about the evaluation order thing: I presume the reason the C standards folks refuse to mandate left-to-right evaluation order is that it might cause trouble for some arcane embedded compiler somewhere, or something.
The original intention was to enable optimisations, after all. If you do
make_coffee( get_barista(), get_beans() );
then if your target platform uses a stack-based calling convention, you'll want to do those two 'inner' calls in a certain order (depending on whether it's a 'reversed' stack-based calling convention or not).
If you're passing by registers, it will presumably make no difference.
It's a pretty wacky micro-optimisation by anyone's standards, and allows strange platform-specific bugs to arise, but I presume the refusal to specify evaluation order is just the standards body exhibiting a healthy resistance to changing the very stable C language. They don't want to cause a downside for anyone, even the strangest half-baked compilers.
They could specify that there are exactly two possible evaluation orders (left-right or right-left) the choice of which is implementation-defined (must be documented) and that there is a sequence point between the evaluations of the argument expressions. (As well as between evaluating the function designating expression and the arguments.)
The fact that there are N! possible evaluation orders for N argument expressions: which implementation does that serve?
Or that there is no sequence points: which calling convention does that serve?
If the compiler has deduced statically that a p == NULL expression might be executed after a dereference of p, the number one priority is to issue a diagnostic for this situation, because it is quite likely a coding mistake.
The programmer almost certainly didn't put in the dereference on purpose, as a way of encouraging p == NULL to be optimized away!
It's very irresponsible to treat situations that are coding mistakes as "let's assume there is no mistake and just optimize".
> It's very irresponsible to treat situations that are coding mistakes as "let's assume there is no mistake and just optimize".
Well, that's the C philosophy, and it's part of the reason it's so fast. As I've said repeatedly throughout this thread, if you want a safe language, why are you using C?
If the compiler detects undefined behavior, it should of course issue a loud warning to the programmer, but that's not the issue. The issue is that the compiler assumes absence of UB and optimises accordingly, spending relatively little effort investigating whether UB is actually present.
If that's what you want, use a proper static-analysis tool. (They really deserve more use!)
The compiler has deduced that a comparison of a pointer to null makes no sense, because it was dereferenced; if that code is reached, the comparison will always be true. That should be diagnosed, just like, say, an unsigned-type > 0 comparison that is always true.
> why are you using C?
For detailed control of the machine with minimal run-time support, without resorting to assembly language. Basically, the original reasons for C, before all this historic revisionism.
I want reasonable speed: good use of registers and basic optimizations like jump threading and peephole code improvements. Optimization in C is otherwise the job of the programmer. The machine code should more or less follow from the calculations that are written in the source, and every memory access through pointers should be there, in the order it appears.
The "trust the programmer" mantra never meant "trust that there is no undefined behavior" but simply "trust that the programmer put every every expression in place for a reason and just translate it to machine code".
> For detailed control of the machine with minimal run-time support, without resorting to assembly language.
Exactly. C is about low-level control. That's why operating systems are written in C and numeric codes in FORTRAN, and not the other way around. Speed is something C enables for the programmer to obtain via the low-level control, not something it provides by trying to read your mind.
> Basically, the original reasons for C, before all this historic revisionism.
Yes, the revisionism is really, really frustrating.
P̶a̶u̶l̶ Fran Allen is a well known compiler engineer, Turing awardee and she pretty clear has another point of view regarding C optimization practices.
"Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue....
Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels?
Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities."
-- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
High-level languages are doing extremely well these days. In certain domains, no-one writes C. No-one writes a website in C. Desktop GUI applications are a mixed bag - some use C/C++ (inappropriately, in my opinion), and some use 'managed' languages.
Incidentally I studied compilers at university. I agree that any supposedly serious computer science course that doesn't study them, is cheating their students.
> By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine.
Java and C# weren´t even a thing.
I suggest you read the IBM RISC research papers done with PL/8 with an LLVM like architecture in the mid-70's before they pivoted into UNIX when going into the market.
The way system programming was done in Burroughs in mid-60's, nowadays still sold as Unisys ClearPath platform.
OS/400 firmware being written in PL/S in the early 80's.
Or even some analysis of Ada deployments in High Integrity Systems, like "Building High Integrity Applications with SPARK" (2015).
What she meant was that the adoption of C kind of destroyed their work doing optimizing compilers since the mid-60's, as C lacked any kind of optimization putting that on the shoulders of developers.
It was the years of optimization work in C compilers, specially regarding UB abuse that has kind of matched what they were already doing on mainframes.
As mentioned PL/8 was a safe systems programming language used to for IBM's RISC compilers and respective OS. The paper describing the toolchain was implemented and
the pluggable optimization passes could be describing LLVM today.
So with UNIX's adoption the computing world has spent a couple of decades making C compilers up to date with mainframe
optimizers, rebuilding the world instead of carrying on where they already were, hence the "destroyed our ability to advance the state of art".
> C lacked any kind of optimization putting that on the shoulders of developers
I don't get you. C is a low-level language. Its compilers perform ever more extensive optimisations. These aren't in tension.
I don't know much about PL/8, but it sounds like the only reason it was fast was because it specifically targeted a particular RISC machine, and ran fast on that one platform? I don't think I'm being dismissive in saying that's essentially cheating, if we're talking about optimising compilers. Assembly code is fast too, but that's not what we're talking about.
A fast high-level language means it can compile down to fast code for any target platform. Back then, all compilers were garbage. That's not C's fault.
Could PL/8 compile to high-performance code for other platforms? If not, it's not doing the same thing as C. If yes, I'd like to know what it does differently to C. Other than the considerable issues that arise from pointer aliasing, C is a very optimisable language.
It's a good thing that we've evolved beyond building languages specifically for machines, and building machines specifically for languages.
> the pluggable optimization passes could be describing LLVM today
Except nowhere near as sophisticated, and accomplishing nowhere near as much.
I really don't buy this idea that C is somehow a slow high-level language, or that its existence has held-back the field of compiler optimisation.
> So with UNIX's adoption the computing world has spent a couple of decades making C compilers up to date with mainframe optimizers, rebuilding the world instead of carrying on where they already were
The idea that the optimising compilers of yesteryear were just as impressive as today's optimising compilers, strikes me as simply untrue.
Compiler optimisation has been improving steadily for decades. I don't see anything to complain about.
> C is a low-level language. Its compilers perform ever more extensive optimisations. These aren't in tension.
Yes they absolutely are. A low-level language has fairly little to get between you and the processor. Extensive optimizations get between you and the processor.
> perhaps compiler engineers have good reason for having their compilers generate code that behaves bizarrely if there's undefined behavior.
> There is, of course: performance.
It is a reason. But it is not a good one.
Especially when you're not ignoring the possible outcomes and just ""optimizing"" code away (and even disregarding the behaviour of their own platform)
> If C took that approach, it would lose many of its unique advantages.
Such as?
> Whether performance matters, depends wholly on what you're doing. There can be no one-size-fits-all programming language.
Correct. But I think the performance side is overrated because C does not have the needed expressiveness to use most modern performance enhancements (like SIMD, auto vectorizing requires a lot of work and checking of conditions, and is not very efficient) and what were important optimizations 40 yrs ago today are reckless (like no boundary checks)
(This discussion doesn't apply to embedded systems for the most part, those today a lot of them are faster than 15y.o. PCs)
Extremely high performance, compact binaries, and its ability to be used both for cross-platform functionality, and for low-level and platform-specific functionality. All the reasons C took over the world (every major operating-system and game-engine, for starters), rather than its competitors.
Kernel developers and game-engine developers care about performance. Embedded developers care about binary size. It doesn't do to pretend that C's advantages there don't really matter.
C isn't a 'big government' language like Java. It isn't meant to be. It's meant to be more of a very-high-level assembly language.
Programming languages are a matter of tradeoffs, not of the 'one true path'. If you want a language with good safety assurances, look elsewhere.
> C does not have the needed expressiveness to use most modern performance enhancements (like SIMD, auto vectorizing requires a lot of work and checking of conditions, and is not very efficient)
Auto-vectorisation is a tough nut to crack, sure. That's not specific to C though. Even frameworks like OpenCL are based on C.
> what were important optimizations 40 yrs ago today are reckless (like no boundary checks)
C has a pretty terrible track-record on security, yes. Precisely because it's not a safe language.
I believe Clang now has a flag to add runtime boundary-checks. For many applications, I agree with you that it would be worth the performance penalty to enable that runtime check in all builds.
> Extremely high performance, compact binaries, and its ability to be used both for cross-platform functionality, and for low-level and platform-specific functionality. All the reasons C took over the world (every major operating-system
and game-engine, for starters), rather than its competitors.
Nah, it's had those advantages since year 1. Like the the other guy said, it's pretty much high level, portable assembly. It wasn't until later that modern languages introduced bounds checking, virtual machines, garbage collectors, and other things that improve safety but have performance and bloat tradeoffs.
Me and others that had our 16 bit codebases full with inline Assembly beg to differ.
C benefited from the domino effect of UNIX's adoption, that is all.
Had AT&T been allowed to sell UNIX at the same price points as VMS, OS/360, Star among many others, and C would have been a footnote on the history of system programming languages, like many others.
C became faster thanks to 30 years of compiler research improving optimization algorithms while taking advantage of UB.
Something else naturally, with stronger memory guarantees and memory unsafe constructs clearly expressed on the type system, like Ada/SPARK, PL/8, PL/S, BLISS or whatever else might have wiped UNIX if it had been closed source sold at the same price level as OS/360, VMS among others.
I agree it's a shame there's so little Ada/SPARK. Does Ada hold its own at low-level work though? C interfaces well with assembly code, has pointers, etc. Can Ada compete there?
Ah yes, I forget C# has those low-level features. Have never had need to use them.
Microsoft copied many of the mistakes of Java when they made C# (all objects are locks, covariant array types, plenty else besides), but they were right to leave out the 'purity' silliness.
C was nothing special get that in your head, it wasn't even used outside AT&T, before they started giving away UNIX source code to universities with the symbolic price of around 100 dollars instead of the closed source systems costing several thousand dollars that those universities were paying for.
C was just yet another systems programming language looking for developer eyes, among PL/I, PL/S, PL/8, NEWP, Mesa, Modula-2, Concurrent Pascal, Object Pascal, UCSD Pascal, PL/M, Ada, CLU, ...
C is the JavaScript of systems programming languages, designed without care for what being done outside AT&T walls since the mid 60's in language research and compiler technology, helped by UNIX and POSIX adoption across the industry thanks to source code availability and symbolic prices until AT&T got split and tried to close down BSD, and naturally the years of investment in optimization research.
Otherwise, interesting points, thanks. I wonder if we'll see the rise of another minimal low-level language anything like C. To put that another way: I wonder if Zig will take off .(I know of no other such projects. I don't know much about Rust but I believe it's a more 'feature-rich' language.)
Zig seems like a neat idea for a language - there's plenty to improve on in C without introducing a full 'managed' framework, like its insane implicit type conversions.
I still don't know what you mean by "years of investment in optimization research". We have high-performance cross-platform code now. Yes, that took decades.
Sorry if I offend you that wasn't really my intention.
For someone that watched C riding the UNIX wave while killing other safer alternatives, that weren't lucky enough to be bundled with an winning OS, it kind of throws me out when I see C being argued as the ultimate systems programming language.
It is an historically accident that things turned out this way, and at very least JTC1/SC22/WG14 should provide a safe C subset.
Even ISO C++ working group has ongoing proposals to reduce C's unsafety influence on C++.
Otherwise POSIX derived OS will continue to be a collection of security patches and band aids trying to make up for those issues.
If you want a 'safe' C subset, that's what MISRA C is for, no?
C++ is a bit of a different beast, as they occasionally concede performance for convenience/correctness. std::shared_ptr is always thread-safe, like it or not.
> Otherwise POSIX derived OS will continue to be a collection of security patches and band aids trying to make up for those issues.
Agree. The constant stream of buffer-overflow attacks shows just that.
It's regrettable that C/C++ are the 'default' languages for writing things like web servers, DBMSs, shells. I imagine it wouldn't be impractical to have a lot of kernel code written in a safer language, for that matter.
C is sometimes appropriate, but it's used everywhere.
Sure they have reasons. And for them, these reasons are "good". The problem is that what is good for the compiler engineers has ceased to align with what is good for most compiler users.
The reasons for this are complex, but one huge one is that we all generally don't pay for compilers any longer, at least not directly. If you have paying customers, you don't pull stunts like that.
Michael Stonebraker talked about a very similar phenomenon in database systems and research:
The observation I found particularly interesting is that the few commercial companies that still interact with research, and I think the same goes for compiler/optimizer engineering, are the "whales", companies like Microsoft, Amazon, Google and Facebook. Their needs are very different from most everyone else who doesn't run datacenter where a 0.1% performance increase can mean millions of dollars of cost savings and therefore be worth quite a bit of pain. Particularly when it is pain for others.
> C values performance over safety
No. Well, yes, because it doesn't value safety much at all. Certainly not when I started, which was with K&R C, so no type-checking at all for function calls, for example. What C values is DWITYTD, "Do What I Tell You To Do". C makes it possible for programmers to write code that performs well, it doesn't try to make code perform well. That's a crucial difference.
I propose that, instead of it being a wording change that sparked the current “craziness” of optimizing C compilers it was the combination of two things:
1) Faster CPUs and more memory allowing compilers to step beyond mostly just peephole-optimization to do optimizations that were once prohibitively expensive.
2) The general convergence of mainstream processors on more or less identical characteristics (16/32/64 bit registers, MMUs giving the appearance of a flat memory space, code exists in memory, 2s complement, etc...) causing programmers to forget how truly diverse computers can be.
In effect, as a collective, we’ve forgotten why these parts of C were never defined and now that compilers are smart enough to optimize code in magical ways but not smart enough to perfectly verify that the programmer didn’t make a mistake, we have this situation of terrible UX and programming pitfalls.
I’m conflicted, and it feels wrong to say this, but maybe it is time to accept that all the world’s more or less an x86 and spin off a more well defined C that’s perf-optimal under some compilation settings for x86-likes. Everyone else not in the sanctioned-land would write code in their own dialect of C with well defined characteristics or limitations for their now-obscure architecture. There are a couple other issues that would need to be resolved, but in some sense, this is already the world we live in.
Except, what about this new web architecture? Do we consider the problem of compiling C to it impossible until we’ve extended it to the point that the semantics are similar to x86?
This could prevent some useful optimizations. The following can be a single rotate instruction but only when relying on undefined behavior of shifts (otherwise the code has to produce zero for i outside the sensible range)
Of course that code is broken (relies on undefined behavior) when i is zero, which is a totally reasonable input for a rotate function. A nice illustration of the pitfalls of undefined behavior.
You can find a correct implementation in a blog post by John Regehr [1].
I don't really buy the idea that invoking undefined behaviour is ok so long as you know it happens to work on your platform.
If that disaster really does boil down to one instruction, I'd hope the compiler would expose an intrinsic.
Doing that kind of thing isn't so evil if you're careful to include a compile-time assert that will break the build (or perhaps 'failover' to safe code) if you try to compile on anything but your exact compiler and for anything but your exact target platform, but even so, I've never seen an appropriate time to deliberately invoke UB like that.
The biggest problem is, the most classic C bug is writing an array out of bounds. It would be almost impossible to efficiently add bounds checking to all C arrays, so let's assume we are going to leave that as undefined behaviour.
That out of bounds write could go anywhere. Into any other variable. Changing the code of the program (if it isn't write protected). So the most common C bug can lead to absolutely any change (hypothetically) to the running program.
That's one of the reasons writing text to "explain" what undefined behaviour can do is so hard.
What many people don't expect is that if the compiler can prove that some function invokes undefined behavior, the compiler can emit no code for it at all--before, during, and after the UB expression.
Saying that writing past the end of an array could modify any other variable is one thing. Saying that writing past the end of an array could make your entire program do nothing is quite another.
What you describe is pretty much exactly the range of "undefined" behavior one would expect, and also in the range of what used to be "permissible":
you just write to that address
What happens then is hard to predict, and therefore in a sense the behavior after that becomes "undefined". This is fine. What's not fine is the compiler taking some action other than
1. just writing to that address (ignoring), or
2. emitting a compiler error and terminating, or
3. doing something else that is "characteristic" of the environment, and documenting it
Current optimizing compilers don't do any of these things, and also not something that in any way resembles any of these options.
Undefined behavior simply means that the standard doesn't have requirements for what is being expressed in the program.
The possible range of actual behaviors doesn't define what UB is; that wording just clarifies that UB doesn't necessarily mean that there is a software defect: it is possible to behave in a documented manner characteristic of an implementation. This refers to documented extensions.
The way to fix C isn't to monkey with the definition of UB, but to target specific cases where there aren't requirements and, like, put requirements there.
> The possible range of actual behaviors doesn't define what UB
Hmm...you might want to actually read an article before declaring it an "ignorant diatribe".
The current standards do say "possible". The first ANSI/ISO standard said "permissible". It also wasn't a "NOTE" back then.
If the standard currently said what I would like it to say, why on earth would I advocate changing it?!?
And once again, the wording I want is the way it was in ANSIC-C '89. So I am advocating changing the wording back to what it was...and lo-and-behold, C compilers were more sensible back then.
A lot of things were better in the ANSI C/C90 era; but the definition of undefined behavior is essentially the same.
"Permissible" is a poor choice of word; "possible" is a legitimate clarification.
The reason "permissible" is poor because it wrongly hints at the possibility that some behaviors in response to UB may be "impermissible". Which, in turn, wrongly suggests that UB is something other than the absence of requirements.
Compilers were more sensible, but not because of squabbling over some minor wording over the definition of undefined behavior.
It was never the case that undefined behavior was intended to be constrained in any way.
114 comments
[ 3.0 ms ] story [ 148 ms ] threadPersonally I'm OK with the more aggressive optimisations, but they are still very controversial -- I think more so in the C than the C++ community (I'm in the C++ one).
Though one could argue that, I don't really think this is the case.
Certainly "ignoring" it isn't the case when you record the fact that there is UB and then optimize based on it.
They also aren't issuing a diagnostic and terminating, either at compile or runtime.
So the remaining option is "behave in a manner characteristic of the environment". Which is fairly loose/rubbery, and I'd be happy to tighten it further. I still don't think it allows the current behavior even as written though, because I don't see how that is "characteristic of the environment". But the stinger is that the behavior has to be documented, which very little of the UB exploitation currently is.
There is, of course: performance.
If you want a compiler that generates code which behaves intuitively even under UB, that requirement is at odds with compiler optimisation. Compiler optimisation generally means doing strange and unexpected things to your code, and the reason C has undefined behaviour in the first place (unlike, say, Java) is to maximally enable compiler optimisation.
In other words, C values performance over safety, and that's part of the point.
If you want to catch undefined behaviour at runtime and treat it as an error, the tooling for doing that is better than ever: Clang's 'UBSan', for instance.
Edit
Aside: I have a personal favourite 'incident' pertaining to exactly this tension (between performance and intuitive behavior). Torvalds vents his frustrations on the GCC mailing list, regarding legal-but-counterintuitive behaviour of code generated for the Alpha architecture: https://gcc.gnu.org/ml/gcc/2012-02/msg00038.html
My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
> Compiler optimisation generally means doing strange and unexpected things
In the first place it should make code faster. I'm no one to judge, but the general reception seems to be that exploiting undefined behaviour (by assuming it will never happen) rarely brings obvious speed advantages. "Strange and unexpected things" can be a bad tradeoff for a tiny speed advantage.
For example, I'll boldly state that optimizing out a "if (p == NULL)" only because p was dereferenced earlier never makes sense. Code containing such a check is never performance sensitive enough to justify the tradeoff (or it's really bad code).
And without being a compiler engineer I assume that it should be easy to change compilers to NOT do this optimization (I assume the not-NULL inference is a special case in the code that can simply be removed).
> In other words, C values performance over safety, and that's part of the point.
Many people value C because of control and allowing one to not paint oneself in a corner. Performance is only a side effect.
> My understanding is that C has undefined behaviour where there is no universally sensible implementation across all architectures.
These are two ways of looking at the same thing. A naive translation of C statements to what seems like the most straightforward way to do them on some target architecture is an optimization over emulating some other architecture’s behavior. Consider the problem of translating one arch’s assembly to another’s. Essentially, C needs to be defined at a certain level of abstraction for all of this to work, but it also happens that detecting holes in this abstraction is undecideable.
Optimisation refers to code transformations which result in output code which has better performance (whether in terms of space or time).
Changing the definition of the source language, isn't optimisation.
Whether the source language can cleanly be mapped to the target machine, may be significant to performance, but it's not optimisation.
Without changing the output. That's the crucial part of the contract current compilers are breaking. And then try to lawyer it away by claiming that the original was undefined anyway so they can do whatever the hell they want.
I’ll play devil’s advocate here, even though I strongly dislike the current direction of the major C compilers.
This aggressive interpretation of undefined behavior apparently can enable some important optimizations. Here are a couple of examples:
First, say you have an index variable where you increment it (i += n) and check it’s within bounds (i >= start && I < end). It could be useful to assume that i won’t overflow and wrap, so some of the bounds checks can be optimized out. (The downside is that if you want to explicitly check for overflow, it’s tricky to do so correctly.)
Second, say you have a function that takes several pointers and copies data between them. It can be useful to assume those pointers aren’t aliased, so we can assume that memory isn’t changing in unexpected ways, and therefore it’s safe to optimize out some repeated reads.
I do feel like those cases could be handled in different ways, though. In the second case, perhaps the compiler could insert a runtime check for aliasing, and branch to either a fast path or a slow path as appropriate.
I’m also not sure that C really needs to try to be the fastest and most highly optimized language, even though it’s widely regarded as being very fast. As far as I know C isn’t the most popular language for scientific supercomputing, for example, where the users really do care about performance.
This is a very common example, but how hard is it for the compiler to prove that it won't overflow? I know in the general case it's the halting problem, but for specific cases (especially where a human inspecting the code would easily see) it should be easy --- especially those cases which warrant optimisation.
Sure it does. That's the whole point: performance and low-level access over safety and convenient features. These are the defining attributes of the C language (along with its minimalism).
If you want a safe and convenient language, why are you using C?
If you don't think C should be as fast as possible, which language should? How would that language differ from C?
It's not C's fault that people use it when they shouldn't.
> In the second case, perhaps the compiler could insert a runtime check for aliasing, and branch to either a fast path or a slow path as appropriate.
I don't get you. Are you referring to the dangers of the 'restrict' keyword? Otherwise, it's quite legal to pass aliasing pointers, and the compiler is free to introduce a check for aliasing.
If you're thinking of the strict aliasing rule, I think you're misunderstand it. It has to do with misusing types. To quote Wikipedia:
> pointer arguments in a function are assumed not to alias if they point to fundamentally different types, except for char* and void*, which may alias to any other type
Plenty of reasons, besides raw speed! If I just want speed and don’t care about safety at all, I’d be using assembly, right?
C has (somewhat) strong typing which catches some errors at compile time. It has higher-level constructs than assembly, like function calls and loops. It’s exceptionally portable (although you have to be wary of undefined behavior and platform-specific weirdness).
Speed is definitely an important part of the story but it’s by no means the only part.
If you don't think C should be as fast as possible, which language should? How would that language differ from C?
Something like FORTRAN maybe? No pointers, as I understand it, hence no aliasing problems.
Unrestricted pointers aren’t necessarily great for speed, but they’re great for flexibility, which makes C a great systems language. FORTRAN might do matrix operations faster, but C is better for wrangling a fiddly file system data structure. Again, it’s not all about speed.
it’s quite legal to pass aliasing pointers, and the compiler is free to introduce a check for aliasing
Right, what I’m getting at is, the compiler is also free not to add a check, and most compilers do not in fact add a check, because they care more about speed.
In fact most C compilers seem to go further; aliased pointers of different types can lead to undefined behavior, so the compiler assumes that this behavior cannot happen, and therefore that the pointers cannot be aliased. That seems to me a logical leap too far.
Not really. C is a reasonable choice of language for high-performance code. There may be instances where your hand-written assembly can outperform compiled C, but it's far from guaranteed, and of course even if you did have such a guarantee, it might not be worth the productivity impact.
Even performance-critical codebases like the Unreal Engine don't use much assembly, as far as I know.
> Speed is definitely an important part of the story but it’s by no means the only part.
Agree.
> Something like FORTRAN maybe? No pointers, as I understand it, hence no aliasing problems.
Indeed, but my understanding is that the performance wins there aren't exactly night-and-day. C is pretty close to as fast as it gets.
> Right, what I’m getting at is, the compiler is also free not to add a check, and most compilers do not in fact add a check, because they care more about speed.
I was unclear - I meant the compiler is permitted to add a check and then use a special optimised path in the case that the pointers do not alias.
It’s quite legal to pass aliasing pointers. When compiling a function which has two pointer-to-int parameters, the compiler is not permitted to assume that they do not alias, unless you use the 'restrict' keyword (which is rarely seen as it's so risky).
> aliased pointers of different types can lead to undefined behavior
Correct (with the special exceptions of void* and char*). Because you shouldn't be doing that.
No I would think it happens naturally as a result of more generally giving abstract values stamps, narrowing the stamps based on expressions, and then simplifying expressions using those stamps. I would guess you wouldn't want stamps and optimisations based on them removed entirely.
But that's really the same thing.
Java takes the opposite approach: it lays down the law, and if your CPU does things differently, the JIT compiler will have to generate however many extra instructions are necessary to bend things to Java's approach.
For instance, Java mandates 2's complement, where C does not. Java mandates the size of an 'int', where C does not. Java specifies exactly what happens if you attempt to dereference null, where C does not.
(Too late I see that oddity just made the same points.)
> In the first place it should make code faster
Well of course, or it's not optimisation, it's obfuscation.
> the general reception seems to be that exploiting undefined behaviour (by assuming it will never happen) rarely brings obvious speed advantages
Depends what you mean by 'obvious' I suppose. For instance, Java pays a non-zero performance penalty for insisting on range-checks for array-element accesses.
> I'll boldly state that optimizing out a "if (p == NULL)" only because p was dereferenced earlier never makes sense.
No need for boldness: Apple says that UBSan's performance penalty is around 20%. https://developer.apple.com/documentation/code_diagnostics/u...
> Code containing such a check is never performance sensitive enough to justify the tradeoff
C programmers tend to hold some disdain for the attitude that they should be made to trade off performance for safety, and not without reason. Claiming they should 'never' care about the overhead of some check, isn't the C way.
If you want a safe language, don't use C. (Well, there's MISRA C, I suppose.)
> it should be easy to change compilers to NOT do this optimization
I don't know exactly what change you're proposing. If you manually check for null, the compiler can't just eliminate your check. Or do you mean C should always check for null at every dereference? The overhead there would be considerable.
> Performance is only a side effect
No, performance is central to the appeal of C.
Their post was predicated on the assumption that the compiler can in fact do this if 'p' was dereferenced before the check. Is that not the case?
Oops, I misread!
Yes, you've got undefined behaviour (i.e. a serious bug in your code), and as far as the compiler is concerned, anything goes.
As the old joke goes, the philosophy of the C language is that the programmer is always right, even when they are wrong. i.e. that it's your job to ensure there's no UB in your source code.
The 'C way' is not to have the language shield you from your mistakes. You can't have that without losing C's advantages. Fortunately, tools exist to help detect undefined behaviour.
It's a pity that runtime detection of easily-detected UB hasn't been an option in C compilers since the beginning. For dev/debug builds, that's almost certainly what you want.
Have you seen the UB list though? It seems to me that almost all programs fall under some kind of UB. It would be nice to have the compiler produce warnings where it would otherwise optimize based on that UB.
These days we have pretty good static analysis tools, and tools like UBSan which can insert certain checks at runtime. Not perfect though.
I believe it's possible to approach it from the other side though: use MISRA C, a terribly strict C programming ruleset, which I believe can be mechanically verified, and which avoids any possible UB. (This is an 'overly strict' approach, as it forbids doing certain perfectly legal things.)
2. The easiest ones to hit by accident are integer overflow ones followed by trapping floating point math.
3. Pointer aliasing is hard to hit if you're not baiting it.
4. Threading requires Data Race Free code. No language known validates this enough.
5. Unchecked pointer dereference and lifetime problems can be avoided especially in C++. It is a subset of missing input validation which again is not enforced in most programming languages.
6. Object slicing rarely comes into play on its own.
7. Format string mess also easy to avoid, s are weirdness caused by longjmp, signals and other ways of messing with the stack.
There are 193 UB cases in C99 and most of them are redundant and group able. Bunch of them can be called "programmer brain is out to lunch". The list is bigger slightly in C20.
It surely didn't felt like that using 8 and 16 bit compilers up to early 90's.
We were using it because we were porting code from and to UNIX systems, nothing else.
At the time though, all compiler-generated code would have been at least as bad, no? With the possible exception of FORTRAN.
Performance is relative. Assembly is rarely used today even for high-performance code, as modern optimising compilers are so good.
Today, we know it's not impossible for a new language to gain traction, but all new languages that are used in anger are much more high-level than C. With the single exception of the Zig language, no other language emphasises raw performance and low-level access the way C does. Rust isn't too far off I suppose (from what little I know about it).
Incidentally, Zig has UB too, but it's designed to be nowhere near as troublesome as it is in C.
Abrash and Norton MS-DOS books expose this reality quite well.
On 70's mainframes outside AT&T walls not so much.
NEWP uses CPU instrisics. Burroughs architecture doesn't expose Assembly.
Xerox PARC moved away from BCPL into Mesa for their Star and Pilot workstations. With the last generation using Mesa/Cedar.
Speaking of which, BCPL was originally only meant for bootstrapping CPL, before getting a life of its own.
There are two less drastic options used by the Standard for those cases.
- Unspecified behavior: behavior that must be "sane" in some sense but may differ between implementations. Vendors need not document the exact behavior.
- Implementation-defined behavior: behavior that must be sane and may differ between implementations. Vendors are required to document the behavior.
That's somewhat true for things like signed integer overflow, but it's more than that. For instance, if there wasn't UB around pointers being "in bounds", then either there would have to be expensive checking of every pointer dereference ever (both read and write), or other performance drains like values never ending up in registers (both literally and conceptually) for extended periods, they'd have to be loaded from memory every time they're used, effectively treated as `volatile`. (And, this inhibits other optimizations like breaking up structs via SROA.)
For instance,
The compiler can't optimize out the branch unless it can assume (or dynamically ensure) that the dereference of the pointer p won't point to an unrelated object (x). Arbitrary transformations on pointers (including constructing them directly from integers, and one might guess the stack address of x) are "only" undefined behaviour in C, not prohibited statically.Sure, that's what it means to have full pointer arithmetic. It's very much an aim away from face feature of the language.
This kind of thing really comes to the fore when the compiler is doing a lot of inlining. Say you have some kind of utility function:
..and you call this function all over the place. If some of those callsites end up with `frob()` being inlined, and the compiler can see that the pointer passed is never NULL at that particular site, it can usefully eliminate the dead code. This despite the fact that the code isn't dead in general - just at some of the callers.If you want to ensure something is not inlined, you're free to do so.
If compiler optimization gets to be more and more about making poorly structured code barely faster, no wonder we have all these discussions about uncalled-for optimizations.
Not really. The compiler is permitted to inline or 'outline' as it sees fit, courtesy of the 'as if' rule. C doesn't let you tell the compiler what code to generate.
The example I should have given was "is dereferenced LATER". Because only in this setting the optimization actually has an effect on most platforms (where dereferencing NULL segfaults).
The criticism arose because this optimisation had been applied in a kernel environment, where the dereference happened before the test, but in some circumstances might not trap. It isn't something that concerns normal applications, though.
I mean I'm pretty sure that compilers can move the conditional below the printf under certain circumstances (as long as there isn't an observable difference for C's definition of "observable"). Add to that the UB and the compiler might as well remove the conditional branch. (And this would be a case that can really take programmers by surprise when debugging).
Optimisations frequently do things that take people by surprise when debugging, but that's par for the course.
Oops, I hadn't thought of that. So the compiler isn't permitted to assume that a function-call will return? Surely that's a huge obstacle to optimisation.
Opinions are divided in the case where it doesn't return because it enters an infinite loop.
Of course, the compiler can have the code do anything at all, as it's undefined behaviour. In practice, the resulting behaviour can be deeply counterintuitive ('impossible looking' results).
> C's definition of "observable"
Indeed, which essentially changes meaning when we introduce multithreading. The perceived order of our writes isn't assured to match up to our source-code. The horror-show continues!
> And this would be a case that can really take programmers by surprise when debugging
Or worse: only in release builds. Not impossible, if you do all your debugging on unoptimised builds, but release optimised builds.
The thing that were and were not codified as requirements in 1989 ANSI C were a historic accident of the time; now that historic accident is just being preserved, more or less.
E.g. we must have unspecified evaluation order of function arguments because we've always had unspecified evaluation order of function arguments.
The original intention was to enable optimisations, after all. If you do
then if your target platform uses a stack-based calling convention, you'll want to do those two 'inner' calls in a certain order (depending on whether it's a 'reversed' stack-based calling convention or not).If you're passing by registers, it will presumably make no difference.
It's a pretty wacky micro-optimisation by anyone's standards, and allows strange platform-specific bugs to arise, but I presume the refusal to specify evaluation order is just the standards body exhibiting a healthy resistance to changing the very stable C language. They don't want to cause a downside for anyone, even the strangest half-baked compilers.
The fact that there are N! possible evaluation orders for N argument expressions: which implementation does that serve?
Or that there is no sequence points: which calling convention does that serve?
The programmer almost certainly didn't put in the dereference on purpose, as a way of encouraging p == NULL to be optimized away!
It's very irresponsible to treat situations that are coding mistakes as "let's assume there is no mistake and just optimize".
Well, that's the C philosophy, and it's part of the reason it's so fast. As I've said repeatedly throughout this thread, if you want a safe language, why are you using C?
If the compiler detects undefined behavior, it should of course issue a loud warning to the programmer, but that's not the issue. The issue is that the compiler assumes absence of UB and optimises accordingly, spending relatively little effort investigating whether UB is actually present.
If that's what you want, use a proper static-analysis tool. (They really deserve more use!)
> why are you using C?
For detailed control of the machine with minimal run-time support, without resorting to assembly language. Basically, the original reasons for C, before all this historic revisionism.
I want reasonable speed: good use of registers and basic optimizations like jump threading and peephole code improvements. Optimization in C is otherwise the job of the programmer. The machine code should more or less follow from the calculations that are written in the source, and every memory access through pointers should be there, in the order it appears.
The "trust the programmer" mantra never meant "trust that there is no undefined behavior" but simply "trust that the programmer put every every expression in place for a reason and just translate it to machine code".
> For detailed control of the machine with minimal run-time support, without resorting to assembly language.
Exactly. C is about low-level control. That's why operating systems are written in C and numeric codes in FORTRAN, and not the other way around. Speed is something C enables for the programmer to obtain via the low-level control, not something it provides by trying to read your mind.
> Basically, the original reasons for C, before all this historic revisionism.
Yes, the revisionism is really, really frustrating.
Too bad I can only upvote you once.
Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels?
Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities."
-- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
High-level languages are doing extremely well these days. In certain domains, no-one writes C. No-one writes a website in C. Desktop GUI applications are a mixed bag - some use C/C++ (inappropriately, in my opinion), and some use 'managed' languages.
Incidentally I studied compilers at university. I agree that any supposedly serious computer science course that doesn't study them, is cheating their students.
One year and a half missing to one decade, in case we are counting them.
Java and C# weren´t even a thing.
I suggest you read the IBM RISC research papers done with PL/8 with an LLVM like architecture in the mid-70's before they pivoted into UNIX when going into the market.
The way system programming was done in Burroughs in mid-60's, nowadays still sold as Unisys ClearPath platform.
OS/400 firmware being written in PL/S in the early 80's.
Or even some analysis of Ada deployments in High Integrity Systems, like "Building High Integrity Applications with SPARK" (2015).
Was the interview in 2009, or not? That was the Java 6 era.
I'm still trying to make sense of "destroyed our ability to advance the state of the art" given that we now have modern Java and C#.
What she meant was that the adoption of C kind of destroyed their work doing optimizing compilers since the mid-60's, as C lacked any kind of optimization putting that on the shoulders of developers.
It was the years of optimization work in C compilers, specially regarding UB abuse that has kind of matched what they were already doing on mainframes.
As mentioned PL/8 was a safe systems programming language used to for IBM's RISC compilers and respective OS. The paper describing the toolchain was implemented and the pluggable optimization passes could be describing LLVM today.
So with UNIX's adoption the computing world has spent a couple of decades making C compilers up to date with mainframe optimizers, rebuilding the world instead of carrying on where they already were, hence the "destroyed our ability to advance the state of art".
I don't get you. C is a low-level language. Its compilers perform ever more extensive optimisations. These aren't in tension.
I don't know much about PL/8, but it sounds like the only reason it was fast was because it specifically targeted a particular RISC machine, and ran fast on that one platform? I don't think I'm being dismissive in saying that's essentially cheating, if we're talking about optimising compilers. Assembly code is fast too, but that's not what we're talking about.
A fast high-level language means it can compile down to fast code for any target platform. Back then, all compilers were garbage. That's not C's fault.
Could PL/8 compile to high-performance code for other platforms? If not, it's not doing the same thing as C. If yes, I'd like to know what it does differently to C. Other than the considerable issues that arise from pointer aliasing, C is a very optimisable language.
It's a good thing that we've evolved beyond building languages specifically for machines, and building machines specifically for languages.
> the pluggable optimization passes could be describing LLVM today
Except nowhere near as sophisticated, and accomplishing nowhere near as much.
I really don't buy this idea that C is somehow a slow high-level language, or that its existence has held-back the field of compiler optimisation.
> So with UNIX's adoption the computing world has spent a couple of decades making C compilers up to date with mainframe optimizers, rebuilding the world instead of carrying on where they already were
The idea that the optimising compilers of yesteryear were just as impressive as today's optimising compilers, strikes me as simply untrue.
Compiler optimisation has been improving steadily for decades. I don't see anything to complain about.
I leave it at that, there are plenty of places to find about history of computing.
Good talking to you.
Yes they absolutely are. A low-level language has fairly little to get between you and the processor. Extensive optimizations get between you and the processor.
https://en.wikipedia.org/wiki/Low-level_programming_language
> Compiler optimisation has been improving steadily for decades.
Not all that much. See Proebsting's Law. Also see "The Death of Optimizing Compilers", by D.J. Bernstein
https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf
> There is, of course: performance.
It is a reason. But it is not a good one.
Especially when you're not ignoring the possible outcomes and just ""optimizing"" code away (and even disregarding the behaviour of their own platform)
If C took that approach, it would lose many of its unique advantages.
Whether performance matters, depends wholly on what you're doing. There can be no one-size-fits-all programming language.
Such as?
> Whether performance matters, depends wholly on what you're doing. There can be no one-size-fits-all programming language.
Correct. But I think the performance side is overrated because C does not have the needed expressiveness to use most modern performance enhancements (like SIMD, auto vectorizing requires a lot of work and checking of conditions, and is not very efficient) and what were important optimizations 40 yrs ago today are reckless (like no boundary checks)
(This discussion doesn't apply to embedded systems for the most part, those today a lot of them are faster than 15y.o. PCs)
Extremely high performance, compact binaries, and its ability to be used both for cross-platform functionality, and for low-level and platform-specific functionality. All the reasons C took over the world (every major operating-system and game-engine, for starters), rather than its competitors.
Kernel developers and game-engine developers care about performance. Embedded developers care about binary size. It doesn't do to pretend that C's advantages there don't really matter.
C isn't a 'big government' language like Java. It isn't meant to be. It's meant to be more of a very-high-level assembly language.
Programming languages are a matter of tradeoffs, not of the 'one true path'. If you want a language with good safety assurances, look elsewhere.
> C does not have the needed expressiveness to use most modern performance enhancements (like SIMD, auto vectorizing requires a lot of work and checking of conditions, and is not very efficient)
Auto-vectorisation is a tough nut to crack, sure. That's not specific to C though. Even frameworks like OpenCL are based on C.
> what were important optimizations 40 yrs ago today are reckless (like no boundary checks)
C has a pretty terrible track-record on security, yes. Precisely because it's not a safe language.
I believe Clang now has a flag to add runtime boundary-checks. For many applications, I agree with you that it would be worth the performance penalty to enable that runtime check in all builds.
After 30 years of throwing money at it.
C benefited from the domino effect of UNIX's adoption, that is all.
Had AT&T been allowed to sell UNIX at the same price points as VMS, OS/360, Star among many others, and C would have been a footnote on the history of system programming languages, like many others.
> C would have been a footnote on the history of system programming languages, like many others
Which programming language would Vulkan be using if we didn't have C?
Presumably a language much like C, no?
Something else naturally, with stronger memory guarantees and memory unsafe constructs clearly expressed on the type system, like Ada/SPARK, PL/8, PL/S, BLISS or whatever else might have wiped UNIX if it had been closed source sold at the same price level as OS/360, VMS among others.
I am leaving out an endless list of other examples.
Microsoft copied many of the mistakes of Java when they made C# (all objects are locks, covariant array types, plenty else besides), but they were right to leave out the 'purity' silliness.
Which high-level language used to roundly outperform C, then?
C used to be far slower than assembly, sure. That's not the point.
C was just yet another systems programming language looking for developer eyes, among PL/I, PL/S, PL/8, NEWP, Mesa, Modula-2, Concurrent Pascal, Object Pascal, UCSD Pascal, PL/M, Ada, CLU, ...
C is the JavaScript of systems programming languages, designed without care for what being done outside AT&T walls since the mid 60's in language research and compiler technology, helped by UNIX and POSIX adoption across the industry thanks to source code availability and symbolic prices until AT&T got split and tried to close down BSD, and naturally the years of investment in optimization research.
Manners.
Otherwise, interesting points, thanks. I wonder if we'll see the rise of another minimal low-level language anything like C. To put that another way: I wonder if Zig will take off .(I know of no other such projects. I don't know much about Rust but I believe it's a more 'feature-rich' language.)
Zig seems like a neat idea for a language - there's plenty to improve on in C without introducing a full 'managed' framework, like its insane implicit type conversions.
I still don't know what you mean by "years of investment in optimization research". We have high-performance cross-platform code now. Yes, that took decades.
For someone that watched C riding the UNIX wave while killing other safer alternatives, that weren't lucky enough to be bundled with an winning OS, it kind of throws me out when I see C being argued as the ultimate systems programming language.
It is an historically accident that things turned out this way, and at very least JTC1/SC22/WG14 should provide a safe C subset.
Even ISO C++ working group has ongoing proposals to reduce C's unsafety influence on C++.
Otherwise POSIX derived OS will continue to be a collection of security patches and band aids trying to make up for those issues.
C++ is a bit of a different beast, as they occasionally concede performance for convenience/correctness. std::shared_ptr is always thread-safe, like it or not.
> Otherwise POSIX derived OS will continue to be a collection of security patches and band aids trying to make up for those issues.
Agree. The constant stream of buffer-overflow attacks shows just that.
It's regrettable that C/C++ are the 'default' languages for writing things like web servers, DBMSs, shells. I imagine it wouldn't be impractical to have a lot of kernel code written in a safer language, for that matter.
C is sometimes appropriate, but it's used everywhere.
Sure they have reasons. And for them, these reasons are "good". The problem is that what is good for the compiler engineers has ceased to align with what is good for most compiler users.
The reasons for this are complex, but one huge one is that we all generally don't pay for compilers any longer, at least not directly. If you have paying customers, you don't pull stunts like that.
Michael Stonebraker talked about a very similar phenomenon in database systems and research:
https://www.youtube.com/watch?v=DJFKl_5JTnA
The observation I found particularly interesting is that the few commercial companies that still interact with research, and I think the same goes for compiler/optimizer engineering, are the "whales", companies like Microsoft, Amazon, Google and Facebook. Their needs are very different from most everyone else who doesn't run datacenter where a 0.1% performance increase can mean millions of dollars of cost savings and therefore be worth quite a bit of pain. Particularly when it is pain for others.
> C values performance over safety
No. Well, yes, because it doesn't value safety much at all. Certainly not when I started, which was with K&R C, so no type-checking at all for function calls, for example. What C values is DWITYTD, "Do What I Tell You To Do". C makes it possible for programmers to write code that performs well, it doesn't try to make code perform well. That's a crucial difference.
1) Faster CPUs and more memory allowing compilers to step beyond mostly just peephole-optimization to do optimizations that were once prohibitively expensive.
2) The general convergence of mainstream processors on more or less identical characteristics (16/32/64 bit registers, MMUs giving the appearance of a flat memory space, code exists in memory, 2s complement, etc...) causing programmers to forget how truly diverse computers can be.
In effect, as a collective, we’ve forgotten why these parts of C were never defined and now that compilers are smart enough to optimize code in magical ways but not smart enough to perfectly verify that the programmer didn’t make a mistake, we have this situation of terrible UX and programming pitfalls.
I’m conflicted, and it feels wrong to say this, but maybe it is time to accept that all the world’s more or less an x86 and spin off a more well defined C that’s perf-optimal under some compilation settings for x86-likes. Everyone else not in the sanctioned-land would write code in their own dialect of C with well defined characteristics or limitations for their now-obscure architecture. There are a couple other issues that would need to be resolved, but in some sense, this is already the world we live in.
Except, what about this new web architecture? Do we consider the problem of compiling C to it impossible until we’ve extended it to the point that the semantics are similar to x86?
You can find a correct implementation in a blog post by John Regehr [1].
[1] https://blog.regehr.org/archives/1063
If that disaster really does boil down to one instruction, I'd hope the compiler would expose an intrinsic.
Doing that kind of thing isn't so evil if you're careful to include a compile-time assert that will break the build (or perhaps 'failover' to safe code) if you try to compile on anything but your exact compiler and for anything but your exact target platform, but even so, I've never seen an appropriate time to deliberately invoke UB like that.
That out of bounds write could go anywhere. Into any other variable. Changing the code of the program (if it isn't write protected). So the most common C bug can lead to absolutely any change (hypothetically) to the running program.
That's one of the reasons writing text to "explain" what undefined behaviour can do is so hard.
Saying that writing past the end of an array could modify any other variable is one thing. Saying that writing past the end of an array could make your entire program do nothing is quite another.
you just write to that address
What happens then is hard to predict, and therefore in a sense the behavior after that becomes "undefined". This is fine. What's not fine is the compiler taking some action other than
1. just writing to that address (ignoring), or
2. emitting a compiler error and terminating, or
3. doing something else that is "characteristic" of the environment, and documenting it
Current optimizing compilers don't do any of these things, and also not something that in any way resembles any of these options.
If he kept that word intact his argument would collapse.
However, it can be perfectly predictable what code will be emitted: a store.
Undefined behavior simply means that the standard doesn't have requirements for what is being expressed in the program.
The possible range of actual behaviors doesn't define what UB is; that wording just clarifies that UB doesn't necessarily mean that there is a software defect: it is possible to behave in a documented manner characteristic of an implementation. This refers to documented extensions.
The way to fix C isn't to monkey with the definition of UB, but to target specific cases where there aren't requirements and, like, put requirements there.
Hmm...you might want to actually read an article before declaring it an "ignorant diatribe".
The current standards do say "possible". The first ANSI/ISO standard said "permissible". It also wasn't a "NOTE" back then.
If the standard currently said what I would like it to say, why on earth would I advocate changing it?!?
And once again, the wording I want is the way it was in ANSIC-C '89. So I am advocating changing the wording back to what it was...and lo-and-behold, C compilers were more sensible back then.
So please inform yourself.
"Permissible" is a poor choice of word; "possible" is a legitimate clarification.
The reason "permissible" is poor because it wrongly hints at the possibility that some behaviors in response to UB may be "impermissible". Which, in turn, wrongly suggests that UB is something other than the absence of requirements.
Compilers were more sensible, but not because of squabbling over some minor wording over the definition of undefined behavior.
It was never the case that undefined behavior was intended to be constrained in any way.