4 ms·

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 spe

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.

userbinator 8y ago
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.
- jstimpfle 8y ago
  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.
jstimpfle 8y ago
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).
- nwellnhof 8y ago
  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.
  - MaxBarraclough 8y ago
    Even without redefining those functions, it doesn't seem like too much to ask to have a runtime check and a noisy explosion, at least in debug builds.
    - jstimpfle 8y ago
      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.
      - MaxBarraclough 8y ago
        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.
MaxBarraclough 8y ago
> 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
- iainmerrick 8y ago
  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.

userbinator 8y ago

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.

jstimpfle 8y ago
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.

jstimpfle 8y ago

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

nwellnhof 8y ago
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.
- MaxBarraclough 8y ago
  Even without redefining those functions, it doesn't seem like too much to ask to have a runtime check and a noisy explosion, at least in debug builds.
  - jstimpfle 8y ago
    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.
    - MaxBarraclough 8y ago
      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.

MaxBarraclough 8y ago

> 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

iainmerrick 8y ago
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.