11 ms·

I think the article overstates the cost of doing this in software and understates the cost of doing it in hardware. The cost of doing it in software is just a

I think the article overstates the cost of doing this in software and understates the cost of doing it in hardware. The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. I have none to hand either, but I'm going to predict that on a modern CPU with typical workloads it will be small enough that it would be very hard to measure. The article speaks as though doing it in hardware would be free, but that's very far from true. The hardware solution might have a nominal cost of 'zero clock cycles' where overflow doesn't occur, but extra transistors in critical, heavily used parts of the CPU core would be burning a small but nonzero amount of energy all the time even on code that doesn't use the overflow check - i.e. the vast majority. If you think overflow check is a great feature (of which personally I'm not at all convinced), go ahead and add it to a new language or provide it as a library function in an existing language. But imposing it as an inescapable tax on all hardware makes no sense whatsoever.

azakai 12y ago
> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. The article does mention a 5-10% cost on JavaScript VMs, as one datapoint. And as another, that languages like Rust choose to allow overflow to avoid the overhead, despite preferring the security of not having silent overflows (implying they measured a slowdown they find unacceptable).
- osmala 12y ago
  Here's another point, how much clockspeed suffers from adding this feature? What about instruction latencies? Does it increase the pipeline length for bigger branch missprediction penalty? Does it interfere with microarchitecture optimizations we are using or could be using? All these are performance questions that may result from adding this instruction. There is reason why RISC eliminated most of mixing control flow with arithmetic. As for his numbers on the performance penalty of doing it in software it surely depends on micro-architecture. All intel x86 processors before HASWELL did only ONE branch per cycle, then in haswell they increased that to two. So the cost of doing it in software should of went down recently. And Intel is adding new instructions to speed up arbitrary precision arithmetics in broadwell so they probably have already thought about this and decided its not worth the cost in hardware.
Dylan16807 12y ago
The processor is already calculating overflow with every operation. All it has to do is allow that bit to trigger a trap.
- crest 12y ago
  Which isn't as trivial as you are implying because it requires a feedback back trap handling parts of the core.
deathanatos 12y ago
> I have none to hand either, but I'm going to predict that on a modern CPU with typical workloads it will be small enough that it would be very hard to measure. I write in a language that does (sort of) this (Python!), and I'd argue that I'd agree. Python gives, by default, integers that aren't bounded, so overflow doesn't happen. Of course, under the hood, it must be keeping track of all the bits of the number somehow, and determining when it can't store a section of the integer in the underlying uintxx_t; it must use some sort of overflow here, even if perhaps it's not truly overflowing. Integer objects (for those interested) are 28 bytes by default and more if they get larger; a rough test with multiplication just now seems to take ~25-50ns (compared to ~2-3ns for a int32t in C) and in my experience, most of the time, this doesn't matter. With this flurry of new languages, I had hoped to see more of "integer" just being an integer, and fixed-sized integers being a special case. Often, I feel I really don't know what the bounds on the input will be. (Sometimes, there aren't, aside from available memory constraints.) Obviously, there will need to be code that needs to run fast and can use a more restrictive type. Something like, `ranged_integer<0, 200>`, which I can use when I know my inputs should never exceed [0, 200], and has some well-defined behavior if I over/underflow. (Or even, configurable!) In the `ranged_integer<0, 200>` case, I'd expect the compiler/library to be able to easily optimize that into a `uint8_t`. (You could have `native::uint8_t`, which is just whatever the processor has, and you're on you're own, but it's more obvious that you're on your own.)
stephengoodwin 12y ago
I agree and would add: What do you do when an integer overflow occurs? This would add additional complexity to transferring and handling this knowledge all way up to the application level.
brigade 12y ago
Eh, new instructions are added all the time. Just look at BMI - I'd be willing to bet the static power cost of adding that dwarfs what trapping arithmetic would cost. And most of those instructions are more esoteric and/or give less benefit over existing instructions than trapping arithmetic would. Also the current branches for overflow checks might be well-predicted, but only if it uses branch prediction resources that could go to other branches. Not to mention the extra codesize and issue resources taken.
jcalvinowens 12y ago
> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. While I agree with you that hardware overflow traps are a bad idea, I think the article's author is referring more to the general overhead of a software BIGNUM implementation. Specifically with his JavaScript example, I think it's very plausible that using integers instead of IEEE754 would incur a 10% overhead if you were throwing lots of big enough numbers around. What the author really wants is a hardware BIGNUM implementation, not overflow trapping. I just don't think he really thought it through. His contention that simply checking for overflow in C or C++ incurs a 5% overhead is unquestionably false though. Typically one would check for integer overflow in C like this: unsigned int do_addition(unsigned int a, unsigned int b) { unsigned int tmp; tmp = a; a += b; if (a < tmp) asm volatile ("nop;" ::); /* Handle it here */ return a; } Any decent compiler will do the right thing (GCC with -Os): 0000000000000000 <do_addition>: 0: 89 f0 mov %esi,%eax 2: 01 f8 add %edi,%eax 4: 73 01 jae 7 <do_addition+0x7> 6: 90 nop 7: c3 retq I think rwallace is absolutely right in saying the overhead of such a check would be very close to zero in the non-overflow case.
- stormbrew 12y ago
  Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.
  - sounds 12y ago
    In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.

azakai 12y ago

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. The article does mention a 5-10% cost on JavaScript VMs, as one datapoint. And as another, that languages like Rust choose to allow overflow to avoid the overhead, despite preferring the security of not having silent overflows (implying they measured a slowdown they find unacceptable).

osmala 12y ago
Here's another point, how much clockspeed suffers from adding this feature? What about instruction latencies? Does it increase the pipeline length for bigger branch missprediction penalty? Does it interfere with microarchitecture optimizations we are using or could be using? All these are performance questions that may result from adding this instruction. There is reason why RISC eliminated most of mixing control flow with arithmetic. As for his numbers on the performance penalty of doing it in software it surely depends on micro-architecture. All intel x86 processors before HASWELL did only ONE branch per cycle, then in haswell they increased that to two. So the cost of doing it in software should of went down recently. And Intel is adding new instructions to speed up arbitrary precision arithmetics in broadwell so they probably have already thought about this and decided its not worth the cost in hardware.

Dylan16807 12y ago

The processor is already calculating overflow with every operation. All it has to do is allow that bit to trigger a trap.

crest 12y ago
Which isn't as trivial as you are implying because it requires a feedback back trap handling parts of the core.

deathanatos 12y ago

> I have none to hand either, but I'm going to predict that on a modern CPU with typical workloads it will be small enough that it would be very hard to measure. I write in a language that does (sort of) this (Python!), and I'd argue that I'd agree. Python gives, by default, integers that aren't bounded, so overflow doesn't happen. Of course, under the hood, it must be keeping track of all the bits of the number somehow, and determining when it can't store a section of the integer in the underlying uintxx_t; it must use some sort of overflow here, even if perhaps it's not truly overflowing. Integer objects (for those interested) are 28 bytes by default and more if they get larger; a rough test with multiplication just now seems to take ~25-50ns (compared to ~2-3ns for a int32t in C) and in my experience, most of the time, this doesn't matter. With this flurry of new languages, I had hoped to see more of "integer" just being an integer, and fixed-sized integers being a special case. Often, I feel I really don't know what the bounds on the input will be. (Sometimes, there aren't, aside from available memory constraints.) Obviously, there will need to be code that needs to run fast and can use a more restrictive type. Something like, `ranged_integer<0, 200>`, which I can use when I know my inputs should never exceed [0, 200], and has some well-defined behavior if I over/underflow. (Or even, configurable!) In the `ranged_integer<0, 200>` case, I'd expect the compiler/library to be able to easily optimize that into a `uint8_t`. (You could have `native::uint8_t`, which is just whatever the processor has, and you're on you're own, but it's more obvious that you're on your own.)

stephengoodwin 12y ago

I agree and would add: What do you do when an integer overflow occurs? This would add additional complexity to transferring and handling this knowledge all way up to the application level.

brigade 12y ago

Eh, new instructions are added all the time. Just look at BMI - I'd be willing to bet the static power cost of adding that dwarfs what trapping arithmetic would cost. And most of those instructions are more esoteric and/or give less benefit over existing instructions than trapping arithmetic would. Also the current branches for overflow checks might be well-predicted, but only if it uses branch prediction resources that could go to other branches. Not to mention the extra codesize and issue resources taken.

jcalvinowens 12y ago

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. While I agree with you that hardware overflow traps are a bad idea, I think the article's author is referring more to the general overhead of a software BIGNUM implementation. Specifically with his JavaScript example, I think it's very plausible that using integers instead of IEEE754 would incur a 10% overhead if you were throwing lots of big enough numbers around. What the author really wants is a hardware BIGNUM implementation, not overflow trapping. I just don't think he really thought it through. His contention that simply checking for overflow in C or C++ incurs a 5% overhead is unquestionably false though. Typically one would check for integer overflow in C like this: unsigned int do_addition(unsigned int a, unsigned int b) { unsigned int tmp; tmp = a; a += b; if (a < tmp) asm volatile ("nop;" ::); /* Handle it here */ return a; } Any decent compiler will do the right thing (GCC with -Os): 0000000000000000 <do_addition>: 0: 89 f0 mov %esi,%eax 2: 01 f8 add %edi,%eax 4: 73 01 jae 7 <do_addition+0x7> 6: 90 nop 7: c3 retq I think rwallace is absolutely right in saying the overhead of such a check would be very close to zero in the non-overflow case.

stormbrew 12y ago
Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.
- sounds 12y ago
  In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.