News for hackers. Stuff that matters.
Re:Relive: 50 years of C, the good, the bad and the ugly by titzer on Friday December 30, 2022 @01:40PM (#34188289)
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.

Re:Relive: 50 years of C, the good, the bad and the ugly by menaerus on Saturday December 31, 2022 @05:37AM (#34195235)
> 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 more theoretical.

Re:Relive: 50 years of C, the good, the bad and the ugly by titzer on Saturday December 31, 2022 @03:06PM (#34200209)
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.

Re:Relive: 50 years of C, the good, the bad and the ugly by menaerus on Monday January 02, 2023 @06:34AM (#34216840)
> 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's an attached cost as well because each of those branches will occupy 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're now sprinkling our check-for-overflow if's all over the place. And 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.