Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

We Need Hardware Traps for Integer Overflow

blog.regehr.org

Post reply on HN
Print view View original

51–60 of 112 posts

Re: We Need Hardware Traps for Integer Overflow

#51

Post by xxs »

stormbrew wrote: post #37
zvrba wrote: post #26

Or you could have a "sticky" overflow flag, so that you could check for overflow after each complete expression instead of after every single math operation. This needs one new flag and one new conditional instruction. (Plus compiler modifications.)

I don't know if this solves all the associated problems. If part of the chain of operations isn't side-effect-free, eg. function call, you'll still have to check more than once for the whole chain. And if you want to do more than throw an error/exception you may need to re-run the operations on a slow path to get the correct result. But I like it a lot even so. For a general case it seems like it would help.

The branch is to be predicted (close to perfectly) by the hardware so the branch cost would be like an extra cycle.

Re: We Need Hardware Traps for Integer Overflow

#52

Post by solarexplorer »

al2o3cr wrote: post #36
maggit wrote: post #11

Earlier quoted context omitted.

The entire premise of the linked article is that doing it the way you suggest is too expensive for the common case, where no overflow happens. Further, it implicitly asserts that the cost of a hardware trap/exception, while great, will be offset by the savings from the common case. Now, it doesn't back these assertions with much data, but neither do you :)

The problem is that potentially-overflowing integer instructions make a real mess out of things like out-of-order execution and speculative execution. For data to back this, see your favorite computer architecture reference, particularly anything that discusses the consequences of highly-complex instructions in things like the VAX.

To the contrary, out-of-order execution and speculative execution make precise exceptions trivial to support. As long as exceptions are not frequent, there is no performance pentalty either. It's the older in-order pipelines who struggle with precise exceptions. But there are well-known tricks to work around that too...

Re: We Need Hardware Traps for Integer Overflow

#53

Post by deathanatos »

rwallace wrote: post #42

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 w…

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

Re: We Need Hardware Traps for Integer Overflow

#54

Post by stephengoodwin »

rwallace wrote: post #42

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 w…

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.

Re: We Need Hardware Traps for Integer Overflow

#55

Post by crest »

Dylan16807 wrote: post #49
rwallace wrote: post #42

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 w…

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

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

Re: We Need Hardware Traps for Integer Overflow

#57

Post by brigade »

rwallace wrote: post #42

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 w…

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.

Re: We Need Hardware Traps for Integer Overflow

#58

Post by jcalvinowens »

rwallace wrote: post #42

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 w…

> 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
Any decent compiler will do the right thing (GCC with -Os):

  0000000000000000 :
     0:	89 f0                	mov    %esi,%eax
     2:	01 f8                	add    %edi,%eax
     4:	73 01                	jae    7 
     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.

Re: We Need Hardware Traps for Integer Overflow

#59

Post by stormbrew »

jcalvinowens wrote: post #58
rwallace wrote: post #42

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 w…

> 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…

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.

Re: We Need Hardware Traps for Integer Overflow

#60

Post by throwawayaway »

danbruc wrote: post #35
perlgeek wrote: post #33

My assembler is very rusty, couldn't compilers check the carry flag on i386 after a math operation that could potentially overflow, and handle the trapping in software?

Of course and this is what actually happens if you enable overflow checking but it comes at a price - if your code is correct you will never need the checks but you will execute them every time.

here's the best guide i could find on enabling those checks in gcc. it is unclear whether they take advantage of the carry bits, do you have a source for that information?

http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...

Post reply on HN