5 ms·

Undefined behavior is critical for performance. Without undefined behavior, C compilers would not be able to optimize at all. You'd be running everything at -O0

by jules 3y ago

Undefined behavior is critical for performance. Without undefined behavior, C compilers would not be able to optimize at all. You'd be running everything at -O0 or worse.

jiggawatts 3y ago
Undefined behaviour enables only a fairly small set of optimisations. There's a large set of optimisations that can be implemented completely safely without having to make such dangerous assumptions. Other programming languages do this all the time, it's not just C/C++ that have optimisers!
- jules 3y ago
  This is simply not true. Almost all optimisations rely on undefined behavior, see https://news.ycombinator.com/item?id=38760475 https://news.ycombinator.com/item?id=38760475 Note that I am not talking about UB like signed integer overflow. Removing that would slow down programs by a couple of percent. The important type of UB is pointer provenance. This ensures that e.g., writing to a random memory address is UB.
  - jiggawatts 3y ago
    Almost all optimisations in C/C++ compilers depend on undefined behaviour, because practically no behaviour is defined! The trick is to define behaviour, which is what other programming languages do. E.g.: in both C# and Rust, integers have fixed sizes. A C# Int32 is equivalent to a Rust i32. Only God knows what a C/C++ "int" is. It could have 17 bits and use ternary.
    - jules 3y ago
      As I said, this isn't about ints, it's about pointers. What behavior will you define in C for writing to a random memory address?
renox 3y ago
Where's your proof? Rust has far fewer UB than C yet its performance is comparable to C.
- nindalf 3y ago
  Just to add, Safe Rust should have zero UB, modulo bugs in the compiler. And they're very serious about fixing such bugs. They won't dismiss it with "just be careful while programming".
- jules 3y ago
  Sure, safe Rust has no UB. The main reason why that doesn't apply to C is that if you wanted to make every C program have a defined behavior, then you also need to define behavior for out of bounds memory writes, including writes from other threads. This means that the compiler basically cannot apply any optimisations, because another thread could be overwriting your data structures at any moment.
bigstrat2003 3y ago
Even if that's true (which is not given, as others have said), it would be a worthy trade to make. Software needs to do what it's meant to do first and foremost. Speed doesn't mean shit if you can't trust that the software actually works.
- lpapez 3y ago
  But that is simply not true, and can be proved by looking at the world we live in. C became the dominant language precisely due to hardware constraints, and the ability to extract every last drop from limited hardware was back in the day more important than software working perfectly always. If this wasn't the case, other safer alternatives would have been preferred. Unless in very specific domains, hardware advances have outpaced the software needs (eg. there is only so much compute power a spreadsheet user will need). That is why today we allow ourselves to think about "luxuries of the past" such as corectness, safety, ergonomics, composability etc.
  - kaba0 3y ago
    > [..] and the ability to extract every last drop from limited hardware was back in the day more important than software working perfectly always That seems to contradict the “very simple to implement compiler”
  - pjmlp 3y ago
    C became dominat, because UNIX was a free beer OS, with source tapes and a book to come along for the ride (Lion's commentary). Had UNIX been as expensive as VMS, or System/370, with a commercial license, no university would have cared to port UNIX, and focus on the systems language used to develop it (post-UNIX V5). As for its performance myth, regarding 1980's C compilers. "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
nindalf 3y ago
> Undefined behavior is critical for performance Not only is this not true, it's trivially easy to prove it's not true. Both rustc and clang generate LLVM IR and use LLVM to optimise and generate machine code. The code that's generated is equally performant, as you'd expect since most of the optimisation is being done by LLVM, not the front end. The difference between the two frontends is that rustc is stricter, rejecting programs where UB may arise.
- jules 3y ago
  I do agree that if you remove `unsafe` blocks from Rust, then you have a performant language without UB. However: (1) We are talking about C here, not Rust (2) Rust has UB due to `unsafe` (3) LLVM IR has UB.
- wavemode 3y ago
  To play devil's advocate, that doesn't negate the claim that undefined behavior is critical for performance. Rust (as well as LLVM IR itself) also have a concept of undefined behavior.
yxhuvud 3y ago
Then fence it in and have it be as little of it as possible and as obvious as possible when it can happen.
nikic 3y ago
The main performance-critical undefined behavior in C is provenance. The rest can be removed without major performance impact. (Which is not to say they can't give you 10% on specific workloads, just they aren't what is taking you from -O0 to -O3.) A related student poster from EuroLLVM 2023: https://llvm.org/devmtg/2023-05/slides/Posters/05-Popescu-PerformanceImpactOfExploitingUndefinedBehavior.pdf https://llvm.org/devmtg/2023-05/slides/Posters/05-Popescu-Pe... It tests the performance impact of some of the secondary undefined behaviors, and the result is basically what you'd expect. They do have impact, but if you average over all benchmarks the improvement is, at best, in the low single digits.
- jules 3y ago
  Yes, I do agree that you basically only need provenance, and that C has more UB than necessary. You can indeed reduce UB without any major performance impact (e.g., shifts by a large n, signed overflow). I think that would be a good idea.

by jules 3y ago

Undefined behavior is critical for performance. Without undefined behavior, C compilers would not be able to optimize at all. You'd be running everything at -O0 or worse.

jiggawatts 3y ago

Undefined behaviour enables only a fairly small set of optimisations. There's a large set of optimisations that can be implemented completely safely without having to make such dangerous assumptions. Other programming languages do this all the time, it's not just C/C++ that have optimisers!

jules 3y ago
This is simply not true. Almost all optimisations rely on undefined behavior, see https://news.ycombinator.com/item?id=38760475 https://news.ycombinator.com/item?id=38760475 Note that I am not talking about UB like signed integer overflow. Removing that would slow down programs by a couple of percent. The important type of UB is pointer provenance. This ensures that e.g., writing to a random memory address is UB.
- jiggawatts 3y ago
  Almost all optimisations in C/C++ compilers depend on undefined behaviour, because practically no behaviour is defined! The trick is to define behaviour, which is what other programming languages do. E.g.: in both C# and Rust, integers have fixed sizes. A C# Int32 is equivalent to a Rust i32. Only God knows what a C/C++ "int" is. It could have 17 bits and use ternary.
  - jules 3y ago
    As I said, this isn't about ints, it's about pointers. What behavior will you define in C for writing to a random memory address?

renox 3y ago

Where's your proof? Rust has far fewer UB than C yet its performance is comparable to C.

nindalf 3y ago
Just to add, Safe Rust should have zero UB, modulo bugs in the compiler. And they're very serious about fixing such bugs. They won't dismiss it with "just be careful while programming".
jules 3y ago
Sure, safe Rust has no UB. The main reason why that doesn't apply to C is that if you wanted to make every C program have a defined behavior, then you also need to define behavior for out of bounds memory writes, including writes from other threads. This means that the compiler basically cannot apply any optimisations, because another thread could be overwriting your data structures at any moment.

bigstrat2003 3y ago

Even if that's true (which is not given, as others have said), it would be a worthy trade to make. Software needs to do what it's meant to do first and foremost. Speed doesn't mean shit if you can't trust that the software actually works.

lpapez 3y ago
But that is simply not true, and can be proved by looking at the world we live in. C became the dominant language precisely due to hardware constraints, and the ability to extract every last drop from limited hardware was back in the day more important than software working perfectly always. If this wasn't the case, other safer alternatives would have been preferred. Unless in very specific domains, hardware advances have outpaced the software needs (eg. there is only so much compute power a spreadsheet user will need). That is why today we allow ourselves to think about "luxuries of the past" such as corectness, safety, ergonomics, composability etc.
- kaba0 3y ago
  > [..] and the ability to extract every last drop from limited hardware was back in the day more important than software working perfectly always That seems to contradict the “very simple to implement compiler”
- pjmlp 3y ago
  C became dominat, because UNIX was a free beer OS, with source tapes and a book to come along for the ride (Lion's commentary). Had UNIX been as expensive as VMS, or System/370, with a commercial license, no university would have cared to port UNIX, and focus on the systems language used to develop it (post-UNIX V5). As for its performance myth, regarding 1980's C compilers. "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

nindalf 3y ago

> Undefined behavior is critical for performance Not only is this not true, it's trivially easy to prove it's not true. Both rustc and clang generate LLVM IR and use LLVM to optimise and generate machine code. The code that's generated is equally performant, as you'd expect since most of the optimisation is being done by LLVM, not the front end. The difference between the two frontends is that rustc is stricter, rejecting programs where UB may arise.

jules 3y ago
I do agree that if you remove `unsafe` blocks from Rust, then you have a performant language without UB. However: (1) We are talking about C here, not Rust (2) Rust has UB due to `unsafe` (3) LLVM IR has UB.
wavemode 3y ago
To play devil's advocate, that doesn't negate the claim that undefined behavior is critical for performance. Rust (as well as LLVM IR itself) also have a concept of undefined behavior.

yxhuvud 3y ago

Then fence it in and have it be as little of it as possible and as obvious as possible when it can happen.

nikic 3y ago

The main performance-critical undefined behavior in C is provenance. The rest can be removed without major performance impact. (Which is not to say they can't give you 10% on specific workloads, just they aren't what is taking you from -O0 to -O3.) A related student poster from EuroLLVM 2023: https://llvm.org/devmtg/2023-05/slides/Posters/05-Popescu-PerformanceImpactOfExploitingUndefinedBehavior.pdf https://llvm.org/devmtg/2023-05/slides/Posters/05-Popescu-Pe... It tests the performance impact of some of the secondary undefined behaviors, and the result is basically what you'd expect. They do have impact, but if you average over all benchmarks the improvement is, at best, in the low single digits.

jules 3y ago
Yes, I do agree that you basically only need provenance, and that C has more UB than necessary. You can indeed reduce UB without any major performance impact (e.g., shifts by a large n, signed overflow). I think that would be a good idea.