4 ms·

I was disappointed that Russ didn't mention the strongest argument for making arithmetic overflow UB. It's a subtle thing that has to do with sign extension and

I was disappointed that Russ didn't mention the strongest argument for making arithmetic overflow UB. It's a subtle thing that has to do with sign extension and loops. The best explanation is given by ryg here [1]. As a summary: The most common way given in C textbooks to iterate over an array is "for (int i = 0; i < n; i++) { ... array[i] ... }". The problem comes from these three facts: (1) i is a signed integer; (2) i is 32-bit; (3) pointers nowadays are usually 64-bit. That means that a compiler that can't prove that the increment on "i" won't overflow (perhaps because "n" was passed in as a function parameter) has to do a sign extend on every loop iteration, which adds extra instructions in what could be a hot loop, especially since you can't fold a sign extending index into an addressing mode on x86. Since this pattern is so common, compiler developers are loath to change the semantics here--even a 0.1% fleet-wide slowdown has a cost to FAANG measured in the millions. Note that the problem goes away if you use pointer-width indices for arrays, which many other languages do. It also goes away if you use C++ iterators. Sadly, the C-like pattern persists. [1]: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...

AlotOfReading 2y ago
There's half a dozen better ways that could have been addressed anytime in the past decade. Anything from making it implementation defined to unspecified behavior to just throwing a diagnostic warning or having a clang-tidy performance rule. I'm also incredibly suspicious of the idea that FAANG in particular won't accept minor compiler slowdowns for useful safety. Google and Apple for example have both talked publicly about how they're pushing bounds checking by default internally and you can see that in the Apple Buffer hardening RFC and the Abseil hardening modes.
- pcwalton 2y ago
  > Anything from making it implementation defined to unspecified behavior to just throwing a diagnostic warning or having a clang-tidy performance rule. To be clear, you're proposing putting a warning on "for (int i = 0; i < n; i++)"? The most common textbook way to write a loop in C? > I'm also incredibly suspicious of the idea that FAANG in particular won't accept minor compiler slowdowns for useful safety. I worked on compilers at FAANG for quite a while and know quite well how these teams justify their existence. Telling executives "we cost the company $1M a quarter, but good news, we made the semantics of the language easier for programming language nerds to understand" instead of "we saved the company $10M last quarter" is an excellent strategy for getting the team axed next time downsizing comes around.
  - frumplestlatz 2y ago
    Even if it is the most common method in text books (I’m not sure that’s true), it’s also almost always wrong. The index must always be sized to fit what you’re indexing over. As for your compiler statement — yes. At least at Apple, there is ongoing clang compiler work, focused on security, that actively makes things slower, and there has been for years.
    - pcwalton 2y ago
      > Even if it is the most common method in text books (I’m not sure that’s true), it’s also almost always wrong. The index must always be sized to fit what you’re indexing over. "The code was wrong, so it was OK that I made it slower" is a message board argument, not a business argument. > As for your compiler statement — yes. At least at Apple, there is ongoing clang compiler work, focused on security, that actively makes things slower, and there has been for years. The performance of code that runs on consumer devices has less of a measurable economic impact than that of code that runs on the server.
      - frumplestlatz 2y ago
        > “The code was wrong, so it was OK that I made it slower" is a message board argument, not a business argument. And yet, here I am, in a business, watching that argument play out in realtime. > The performance of code that runs on consumer devices has less of a measurable economic impact than that of code that runs on the server. The performance of the device literally in the entire world’s hands every day is arguably quite a bit more impactful that Facebook having to buy more servers.
  - AlotOfReading 2y ago
    No, I'm saying that there could be anything from a one word change to the standard that doesn't affect compilers at all to safety by default with a clang tidy performance warning. Clang tidy and the core guidelines have already broken the textbook Hello, World! with performance-avoid-endl warning, so I don't see why the common textbook way to write things should be our guiding principle here. Of course, the common textbook way to write things would continue working regardless, it'd just have a negligible performance cost.
dcrazy 2y ago
The C language does not specify that `int` is 32-bits. That is a choice made by compiler developers to make compiling non-portable code written for 32-bit platforms easier, because most codebases wind up baking in assumptions about variable sizes. In Swift, for example, `Int` is 64 bits wide on 64-bit targets. If we ever move to 128-bit CPUs, the Swift project will be forced to decide to stick to their guns or make `Int` 64-bits on 128-bit targets.
- pcwalton 2y ago
  > The C language does not specify that `int` is 32-bits. That is a choice made by compiler developers to make compiling non-portable code written for 32-bit platforms easier, because most codebases wind up baking in assumptions about variable sizes. Making int 32-bit also results in not-insignificant memory savings.
  - bobmcnamara 2y ago
    And even wastes cycles on 16bit size_t MCUs.
    - moefh 2y ago
      Is there any MCU where `size_t` is 16 bits but `int` is 32 bits? I'm genuinely curious, I have never seen one.
      - bobmcnamara 2y ago
        The original 32-bit machine, the Manchester Baby, would've likely had a 32-bit int, but with only 32 words of RAM, C would be rather limited, though static-stack implementations would work.
      - dcrazy 2y ago
        Me either, but it wouldn’t be unreasonable if the target has 32-bit ALUs but only 16 address lines and no MMU.
    - 2y ago
tmoravec 2y ago
size_t has been in the C standard since C89. "for (int i = 0..." might have it's uses so it doesn't make sense to disallow it. But I'd argue that it's not really a common textbook way to iterate over an array.
- pcwalton 2y ago
  The first example program that demonstrates arrays in The C Programming Language 2nd edition (page 22) uses signed integers for both the induction variable and the array length (the literal 10 becomes int).
  - Maxatar 2y ago
    From what I see, that book was published in 1988.
  - frumplestlatz 2y ago
    The language has evolved significantly, and we’ve learned a lot about how to write safer C, since that was published in 1988.
Someone 2y ago
> Sadly, the C-like pattern persists. I think that’s the main problem: C-style “arrays are almost identical to pointers” and C-style for loops may be good ideas for the first version of your compiler, but once you’ve bootstrapped your compiler, you should ditch them.
sapiogram 2y ago
Thank you so much for this comment. I think Russ Cox (along with many others) is way too quick to declare that removing one source of UB is worth a (purportedly) minuscule performance reduction. While I'm sure that's sometimes true, he hasn't measured it, and even a 1% slowdown of all C/C++ would have huge costs globally.
dooglius 2y ago
As mentioned in the linked post, the compiler could in fact prove the increment on i wont overflow, and in my testing, -fwrapv does produce identical assembly (YMMV). The post talks about hypothetical more complex cases where the compiler would not prove the loop bound. But if -fwrapv semantics were mandated by spec, then presumably compilers would at least hardcode a check for such a common optimization (if they are not doing so already).
- pcwalton 2y ago
  > But if -fwrapv semantics were mandated by spec, then presumably compilers would at least hardcode a check for such a common optimization (if they are not doing so already). I don't know what this means. The optimization becomes invalid if fwrapv is mandated, so compilers can't do it anymore.
  - dooglius 2y ago
    The optimization is still valid under -fwrapv semantics. To see this, observe the invariant (0 <= i && i < count) when entering the loop body, and (i==0 || (0 < i && i <= count)) when doing the loop test -- in particular, 0<=i<INT_MAX when entering the loop body (since count <= INT_MAX), so wraparound cannot occur.

AlotOfReading 2y ago

There's half a dozen better ways that could have been addressed anytime in the past decade. Anything from making it implementation defined to unspecified behavior to just throwing a diagnostic warning or having a clang-tidy performance rule. I'm also incredibly suspicious of the idea that FAANG in particular won't accept minor compiler slowdowns for useful safety. Google and Apple for example have both talked publicly about how they're pushing bounds checking by default internally and you can see that in the Apple Buffer hardening RFC and the Abseil hardening modes.

pcwalton 2y ago
> Anything from making it implementation defined to unspecified behavior to just throwing a diagnostic warning or having a clang-tidy performance rule. To be clear, you're proposing putting a warning on "for (int i = 0; i < n; i++)"? The most common textbook way to write a loop in C? > I'm also incredibly suspicious of the idea that FAANG in particular won't accept minor compiler slowdowns for useful safety. I worked on compilers at FAANG for quite a while and know quite well how these teams justify their existence. Telling executives "we cost the company $1M a quarter, but good news, we made the semantics of the language easier for programming language nerds to understand" instead of "we saved the company $10M last quarter" is an excellent strategy for getting the team axed next time downsizing comes around.
- frumplestlatz 2y ago
  Even if it is the most common method in text books (I’m not sure that’s true), it’s also almost always wrong. The index must always be sized to fit what you’re indexing over. As for your compiler statement — yes. At least at Apple, there is ongoing clang compiler work, focused on security, that actively makes things slower, and there has been for years.
  - pcwalton 2y ago
    > Even if it is the most common method in text books (I’m not sure that’s true), it’s also almost always wrong. The index must always be sized to fit what you’re indexing over. "The code was wrong, so it was OK that I made it slower" is a message board argument, not a business argument. > As for your compiler statement — yes. At least at Apple, there is ongoing clang compiler work, focused on security, that actively makes things slower, and there has been for years. The performance of code that runs on consumer devices has less of a measurable economic impact than that of code that runs on the server.
    - frumplestlatz 2y ago
      > “The code was wrong, so it was OK that I made it slower" is a message board argument, not a business argument. And yet, here I am, in a business, watching that argument play out in realtime. > The performance of code that runs on consumer devices has less of a measurable economic impact than that of code that runs on the server. The performance of the device literally in the entire world’s hands every day is arguably quite a bit more impactful that Facebook having to buy more servers.
- AlotOfReading 2y ago
  No, I'm saying that there could be anything from a one word change to the standard that doesn't affect compilers at all to safety by default with a clang tidy performance warning. Clang tidy and the core guidelines have already broken the textbook Hello, World! with performance-avoid-endl warning, so I don't see why the common textbook way to write things should be our guiding principle here. Of course, the common textbook way to write things would continue working regardless, it'd just have a negligible performance cost.

dcrazy 2y ago

The C language does not specify that `int` is 32-bits. That is a choice made by compiler developers to make compiling non-portable code written for 32-bit platforms easier, because most codebases wind up baking in assumptions about variable sizes. In Swift, for example, `Int` is 64 bits wide on 64-bit targets. If we ever move to 128-bit CPUs, the Swift project will be forced to decide to stick to their guns or make `Int` 64-bits on 128-bit targets.

pcwalton 2y ago
> The C language does not specify that `int` is 32-bits. That is a choice made by compiler developers to make compiling non-portable code written for 32-bit platforms easier, because most codebases wind up baking in assumptions about variable sizes. Making int 32-bit also results in not-insignificant memory savings.
- bobmcnamara 2y ago
  And even wastes cycles on 16bit size_t MCUs.
  - moefh 2y ago
    Is there any MCU where `size_t` is 16 bits but `int` is 32 bits? I'm genuinely curious, I have never seen one.
    - bobmcnamara 2y ago
      The original 32-bit machine, the Manchester Baby, would've likely had a 32-bit int, but with only 32 words of RAM, C would be rather limited, though static-stack implementations would work.
    - dcrazy 2y ago
      Me either, but it wouldn’t be unreasonable if the target has 32-bit ALUs but only 16 address lines and no MMU.
  - 2y ago

tmoravec 2y ago

size_t has been in the C standard since C89. "for (int i = 0..." might have it's uses so it doesn't make sense to disallow it. But I'd argue that it's not really a common textbook way to iterate over an array.

pcwalton 2y ago
The first example program that demonstrates arrays in The C Programming Language 2nd edition (page 22) uses signed integers for both the induction variable and the array length (the literal 10 becomes int).
- Maxatar 2y ago
  From what I see, that book was published in 1988.
- frumplestlatz 2y ago
  The language has evolved significantly, and we’ve learned a lot about how to write safer C, since that was published in 1988.

Someone 2y ago

> Sadly, the C-like pattern persists. I think that’s the main problem: C-style “arrays are almost identical to pointers” and C-style for loops may be good ideas for the first version of your compiler, but once you’ve bootstrapped your compiler, you should ditch them.

sapiogram 2y ago

Thank you so much for this comment. I think Russ Cox (along with many others) is way too quick to declare that removing one source of UB is worth a (purportedly) minuscule performance reduction. While I'm sure that's sometimes true, he hasn't measured it, and even a 1% slowdown of all C/C++ would have huge costs globally.

dooglius 2y ago

As mentioned in the linked post, the compiler could in fact prove the increment on i wont overflow, and in my testing, -fwrapv does produce identical assembly (YMMV). The post talks about hypothetical more complex cases where the compiler would not prove the loop bound. But if -fwrapv semantics were mandated by spec, then presumably compilers would at least hardcode a check for such a common optimization (if they are not doing so already).

pcwalton 2y ago
> But if -fwrapv semantics were mandated by spec, then presumably compilers would at least hardcode a check for such a common optimization (if they are not doing so already). I don't know what this means. The optimization becomes invalid if fwrapv is mandated, so compilers can't do it anymore.
- dooglius 2y ago
  The optimization is still valid under -fwrapv semantics. To see this, observe the invariant (0 <= i && i < count) when entering the loop body, and (i==0 || (0 < i && i <= count)) when doing the loop test -- in particular, 0<=i<INT_MAX when entering the loop body (since count <= INT_MAX), so wraparound cannot occur.