4 ms·

C would be a better language if it really lived up to its old ideal of being a "portable assembly language". That stopped being true as compilers started optimi

by titzer 4y ago

C would be a better language if it really lived up to its old ideal of being a "portable assembly language". That stopped being true as compilers started optimizing undefined behavior (e.g. signed overflow). Instead of a "+" in the source code yielding an honest-to-goodness hardware add instruction, it could be "optimized"--i.e. constant folded, CSE'd, strength-reduced, value-range-analyzed, among others--by an optimizing compiler in ways that completely ignore what the hardware instruction actually does upon overflow. That meant the C language became more like a vague suggestion of assembly and it became pretty much impossible to code to the machine anymore.

menaerus 4y ago
In the absence of CPU instruction which does the saturated ADD, how do you solve the overflow problem in a bare-metal language without introducing the performance hit?
- zozbot234 4y ago
  The performance hit of overflow has nothing to do with lacking assembly instructions. It's all about having to preserve error states whenever overflow occurs and inhibiting optimization.
  - menaerus 4y ago
    I don't follow. If we had the saturated ADD instruction supported in hardware we wouldn't have to deal with saturation logic in software. Compiler would simply be able to emit SADD instruction whenever we asked for it to and would be given a chance to spit out more optimized code because that would essentially be a branchless code. Reality though is that we don't have such hardware and we have to deal with it in software, so, instead of a single instruction emitted there will be a bunch of them, and of which there will be certainly branches involved.
- titzer 4y ago
  It depends on how you define your language semantics. If you choose 2's complement wraparound semantics, which is what nearly all CPUs in the world have standardized on, there is nothing for the compiler to do. It's a pure operation, a single instruction, and can be constant-folded, strength-reduced, CSE'd, moved, dead-code-eliminated, etc. If you want a different semantics at the source level, e.g. overflow is an exception, then the compiler needs to emit additional code. For Virgil I chose to settle on 2's complement because it's what hardware gives and has no overhead. It comes with the full compliment of fixed-width integers of widths 1-64 and odd-width ones come with zero-extension or sign-extension as necessary to make the underlying hardware width unobservable.
  - menaerus 4y ago
    > If you want a different semantics at the source level, e.g. overflow is an exception, then the compiler needs to emit additional code. Yes, and which is exactly what I hinted at with my question to your comment. With the HW we have today, implementing such semantics without an extra hit is not possible and which is why I thought your comment wasn't completely fair but coming from more theoretical stance.
    - titzer 4y ago
      Checking for overflow is basically adding a conditional branch (usually to out-of-line code) after arithmetic. It's very cheap, almost free, if there are enough execution units, I-cache isn't a bottleneck, etc etc. But yeah, it is theoretically an overhead, which is why I avoided it for Virgil. I suppose range analysis can eliminate many overflow checks, e.g. in counted loops, but it's not completely zero cost.
      - menaerus 4y ago
        > Checking for overflow is basically adding a conditional branch (usually to out-of-line code) after arithmetic. Yes, but now as well you have to return a value to communicate the overflow to the call site. And call site has to check for that value and that's yet another and another ... and another branch. Depends how deeply you want to propagate that error and decide how (?) to deal with it, this will grow the code size, which can contribute to the higher frequency of I-cache misses and page-faults, but it can also inhibit compiler optimizations. On the CPU level, I think there also could be an attached cost as well in case some of those branches end up as entries either in branch-target (BTB) or branch-order (BOB) buffers or both. Sizes of these buffers are quite scarce so ending up with the unfavorable ratio of check-for-overflow entries vs entries occupied by other type of branches found in the code is something that will put more pressure to our branch-prediction unit. More "important" branches will now more frequently start to lack their entry in the branch history simply because of the fact that we started sprinkling check-for-overflow branches. And yet we know that branch misprediction is the costliest operation (15-20 cycles) we can encounter in the CPU pipeline. Also, I think a bigger picture must be observed in this context. E.g. what is the percentage of arithmetic operations some big real-world sized binaries contain? I'd figure that in average it would be a sizeable amount, and in ones with a lot of math even more so. And then I wonder what we could observe if we applied the check-for-overflow transformation to all such signed-arithmetic operations. I'm aware that there are some artificial benchmarks showing that there's no cost attached to branches which are essentially never taken but it makes me wonder if that cost would really be zero if we exercised that change on the actual code instead. For at least the reasons from above.
tialaramex 4y ago
> if it really lived up to its old ideal of being a "portable assembly language". What "old ideal" ? Where do you believe this "ideal" was expressed? Should I expect to find it in the First Edition K&R perhaps? Or in the documentation for the original C compiler? In the ANSI standard ? C was never this mythical "portable assembly language" that's just something people say about it, mostly to ridicule it, you are engaging in Nostalgia.
- pjmlp 4y ago
  From Dennis himself, "The language is also widely used as an intermediate representation (essentially, as a portable assembly language) for a wide variety of compilers, both for direct descendents like C++, and independent languages like Modula 3 [Nelson 91] and Eiffel [Meyer 88]. " -- https://www.bell-labs.com/usr/dmr/www/chist.html https://www.bell-labs.com/usr/dmr/www/chist.html
  - tialaramex 4y ago
    That same document claims, "C's approach to strings works well" which, I mean I admire Dennis Ritchie but he's just wrong.
    - pjmlp 4y ago
      Moving goalposts, you were asking who said it, the language authors did. If they are right or not, it is another matter.
      - timbit42 4y ago
        Regarding that matter, he was wrong. I wish he'd never written the garbage that is C. It's a stain on his reputation.
        titzer 4y ago
        I'm willing to forgive those who move on to better ideas, but we are really stuck with this 50 years later. When most of PL land knows better than to keep digging in this hole.

by titzer 4y ago

menaerus 4y ago

In the absence of CPU instruction which does the saturated ADD, how do you solve the overflow problem in a bare-metal language without introducing the performance hit?

zozbot234 4y ago
The performance hit of overflow has nothing to do with lacking assembly instructions. It's all about having to preserve error states whenever overflow occurs and inhibiting optimization.
- menaerus 4y ago
  I don't follow. If we had the saturated ADD instruction supported in hardware we wouldn't have to deal with saturation logic in software. Compiler would simply be able to emit SADD instruction whenever we asked for it to and would be given a chance to spit out more optimized code because that would essentially be a branchless code. Reality though is that we don't have such hardware and we have to deal with it in software, so, instead of a single instruction emitted there will be a bunch of them, and of which there will be certainly branches involved.
titzer 4y ago
It depends on how you define your language semantics. If you choose 2's complement wraparound semantics, which is what nearly all CPUs in the world have standardized on, there is nothing for the compiler to do. It's a pure operation, a single instruction, and can be constant-folded, strength-reduced, CSE'd, moved, dead-code-eliminated, etc. If you want a different semantics at the source level, e.g. overflow is an exception, then the compiler needs to emit additional code. For Virgil I chose to settle on 2's complement because it's what hardware gives and has no overhead. It comes with the full compliment of fixed-width integers of widths 1-64 and odd-width ones come with zero-extension or sign-extension as necessary to make the underlying hardware width unobservable.
- menaerus 4y ago
  > If you want a different semantics at the source level, e.g. overflow is an exception, then the compiler needs to emit additional code. Yes, and which is exactly what I hinted at with my question to your comment. With the HW we have today, implementing such semantics without an extra hit is not possible and which is why I thought your comment wasn't completely fair but coming from more theoretical stance.
  - titzer 4y ago
    Checking for overflow is basically adding a conditional branch (usually to out-of-line code) after arithmetic. It's very cheap, almost free, if there are enough execution units, I-cache isn't a bottleneck, etc etc. But yeah, it is theoretically an overhead, which is why I avoided it for Virgil. I suppose range analysis can eliminate many overflow checks, e.g. in counted loops, but it's not completely zero cost.
    - menaerus 4y ago
      > Checking for overflow is basically adding a conditional branch (usually to out-of-line code) after arithmetic. Yes, but now as well you have to return a value to communicate the overflow to the call site. And call site has to check for that value and that's yet another and another ... and another branch. Depends how deeply you want to propagate that error and decide how (?) to deal with it, this will grow the code size, which can contribute to the higher frequency of I-cache misses and page-faults, but it can also inhibit compiler optimizations. On the CPU level, I think there also could be an attached cost as well in case some of those branches end up as entries either in branch-target (BTB) or branch-order (BOB) buffers or both. Sizes of these buffers are quite scarce so ending up with the unfavorable ratio of check-for-overflow entries vs entries occupied by other type of branches found in the code is something that will put more pressure to our branch-prediction unit. More "important" branches will now more frequently start to lack their entry in the branch history simply because of the fact that we started sprinkling check-for-overflow branches. And yet we know that branch misprediction is the costliest operation (15-20 cycles) we can encounter in the CPU pipeline. Also, I think a bigger picture must be observed in this context. E.g. what is the percentage of arithmetic operations some big real-world sized binaries contain? I'd figure that in average it would be a sizeable amount, and in ones with a lot of math even more so. And then I wonder what we could observe if we applied the check-for-overflow transformation to all such signed-arithmetic operations. I'm aware that there are some artificial benchmarks showing that there's no cost attached to branches which are essentially never taken but it makes me wonder if that cost would really be zero if we exercised that change on the actual code instead. For at least the reasons from above.

tialaramex 4y ago

> if it really lived up to its old ideal of being a "portable assembly language". What "old ideal" ? Where do you believe this "ideal" was expressed? Should I expect to find it in the First Edition K&R perhaps? Or in the documentation for the original C compiler? In the ANSI standard ? C was never this mythical "portable assembly language" that's just something people say about it, mostly to ridicule it, you are engaging in Nostalgia.

pjmlp 4y ago
From Dennis himself, "The language is also widely used as an intermediate representation (essentially, as a portable assembly language) for a wide variety of compilers, both for direct descendents like C++, and independent languages like Modula 3 [Nelson 91] and Eiffel [Meyer 88]. " -- https://www.bell-labs.com/usr/dmr/www/chist.html https://www.bell-labs.com/usr/dmr/www/chist.html
- tialaramex 4y ago
  That same document claims, "C's approach to strings works well" which, I mean I admire Dennis Ritchie but he's just wrong.
  - pjmlp 4y ago
    Moving goalposts, you were asking who said it, the language authors did. If they are right or not, it is another matter.
    - timbit42 4y ago
      Regarding that matter, he was wrong. I wish he'd never written the garbage that is C. It's a stain on his reputation.
      - titzer 4y ago
        I'm willing to forgive those who move on to better ideas, but we are really stuck with this 50 years later. When most of PL land knows better than to keep digging in this hole.