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

81–90 of 112 posts

Re: We Need Hardware Traps for Integer Overflow

#81

Post by JoshTriplett »

xxs wrote: post #76
JoshTriplett wrote: post #39

Earlier quoted context omitted.

> Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. So don't do either of those things until your arithmetic overflows the size of a word; until then, you can keep numbers in a register.

That's not easy either as it'd require very heavy inlining by the compiler. Functions that accept just 'integer' have to check if the value is a native number or actual reference and process differently. C/C++,Java* ,C# have it easier there - when you pass 'int'/'long' the receiver knows it's a native number. * Fixnums support (headless objects) needed for non-Java lanaguages on JVM is still unimplemented to my knowl…

> That's not easy either as it'd require very heavy inlining by the compiler.

Right, bignums need to be a language feature, not a library feature. Compilers with native bignum support often have ways of handling native unboxed single-register numbers, and then branching to full bignum routines when needed. Haskell can do that, for instance.

Also, you can use the standard trick of decreasing the maximum single-register size and using the extra bits to identify indirect objects.

Re: We Need Hardware Traps for Integer Overflow

#82

Post by jcalvinowens »

xenonflash wrote: post #71
stormbrew wrote: post #59

Earlier quoted context omitted.

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.

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary dupl…

> For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it

Sure, but that calculation is CPU-dependent, since it depends on how the underlying hardware represents signed integers. By definition, it is impossible to portably check for signed integer overflow in C, as I'm sure you know.

I implemented a simplistic BIGNUM library in C once (that's where I pulled that expanding multiply code in the other comment from). The only truly portable way to do that is to make your bignums sign-magnitude and use exclusively unsigned arithmetic on them. That's what I was envisioning in my original point about performance degradation due to overflow checking.

Realistically of course, most CPU's these days are twos-complement, and you can make signed overflow defined by compiling with "-fwrapv", which I would guess is what you're doing.

Re: We Need Hardware Traps for Integer Overflow

#83

Post by xxs »

JoshTriplett wrote: post #81
xxs wrote: post #76

Earlier quoted context omitted.

That's not easy either as it'd require very heavy inlining by the compiler. Functions that accept just 'integer' have to check if the value is a native number or actual reference and process differently. C/C++,Java* ,C# have it easier there - when you pass 'int'/'long' the receiver knows it's a native number. * Fixnums support (headless objects) needed for non-Java lanaguages on JVM is still unimplemented to my knowl…

> That's not easy either as it'd require very heavy inlining by the compiler. Right, bignums need to be a language feature, not a library feature. Compilers with native bignum support often have ways of handling native unboxed single-register numbers, and then branching to full bignum routines when needed. Haskell can do that, for instance. Also, you can use the standard trick of decreasing the maximum single-registe…

>>Also, you can use the standard trick of decreasing the maximum single-register size and using the extra bits to identify indirect objects.

That's given, you still pay the price (like mask/shift), though. That was the part the "languages like C/C#/Java have it easier" about. The point is mostly that even if built-in support (interrupts) exist in the hardware, bignums still need quite a lot of extra code in-place, plus a good optimizing/inilining compiler.

Personally I am happy with constrained integer types - else the entire stack (incl. storage) must support bignums and often (like almost always) going out of range would be a bug actually.

Re: We Need Hardware Traps for Integer Overflow

#84

Post by userbinator »

JoshTriplett wrote: post #40
userbinator wrote: post #32

It's a little amusing that x86 has the INTO instruction, a single byte opcode at position CEh, that was designed specifically for this purpose and was there since the 8086, but when AMD designed their 64-bit extensions, it turned into an invalid instruction (and Intel was forced to go along, presumably for compatibility.) A rather shortsighted move, I think; instead of having a possibly useful (but not previously oft…

Those instructions generate an interrupt; you'd have to define the OS ABI to make those instructions trap back to the application in a catchable way.

There's an existing way to do this already: SIGFPE + the UNIX signal-handling mechanism. Integer overflow is even mentioned as one of the possible causes of this signal. The BSDs have a defined constant FPE_INTOVF_TRAP for it too. On Windows, SEH is an equivalent functionality.

Re: We Need Hardware Traps for Integer Overflow

#85

Post by xenonflash »

jcalvinowens wrote: post #82
xenonflash wrote: post #71

Earlier quoted context omitted.

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary dupl…

> For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it Sure, but that calculation is CPU-dependent, since it depends on how the underlying hardware represents signed integers. By definition, it is impossible to portably check for signed integer overflow…

Yes I'm assuming two's complement, but there's not a lot of hardware around these days that isn't two's complement. I'm writing a library for something that already assumes two's complement while doing other things.

If the code had to be portable to one's complement hardware, then I would create special cases for that type of hardware. Laying my hands on such hardware for testing would be the big problem, and if you haven't tested it, then how do you know that it works?

As for "-fwrapv", it's not portable either, and I need to cover both signed and unsigned math. It's also not compatible with what I need to link to (I've gone down this road already). I also need to cover the largest native word sizes, so the trick of using a larger word size won't work for me.

I'm only dealing with arrays of numbers though, so I can often amortize the checking calculations over many array elements instead of doing them each time. This is an example of knitting the checks into the overall algorithm instead of using a generic approach.

As things stand, there's currently no universal ones-size-fits-all answer to this problem in most languages.

I do like how Python has handled this - integers are infinitely expandable and simply can't overflow. This comes at the expense of performance though. What this type of solution needs is an option for unchecked native arithmetic for cases where you need maximum speed.

Re: We Need Hardware Traps for Integer Overflow

#87

Post by ScottBurson »

enupten wrote: post #86

Didn't lisp machines have Hardware traps of some kind ?

Lots of them. But the CPU wasn't even pipelined, never mind superscalar, so adding traps was easy -- just more microcode.

For example, there was tag type DTP-GC-FORWARD. When the CPU loaded a word from memory with this value in the tag field, it would automatically indirect through the pointer contained in the word.

Re: We Need Hardware Traps for Integer Overflow

#88

Post by ScottBurson »

userbinator wrote: post #32

It's a little amusing that x86 has the INTO instruction, a single byte opcode at position CEh, that was designed specifically for this purpose and was there since the 8086, but when AMD designed their 64-bit extensions, it turned into an invalid instruction (and Intel was forced to go along, presumably for compatibility.) A rather shortsighted move, I think; instead of having a possibly useful (but not previously oft…

Also, the original SPARC chips had TADDCCTV, which would add two 32-bit integers, trapping either if there was overflow or if either operand had a nonzero value in its two low-order bits. This was specifically to support tagged fixnum addition in Lisp.

They dropped this instruction for the 64-bit SPARCs.

Re: We Need Hardware Traps for Integer Overflow

#89

Post by cliffbean »

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…

There probably is close to zero overhead in a small benchmark. Hardware branch prediction is indeed good. However, it's a finite resource. In a large application, lots of needless branches everywhere translates into fewer branch prediction resources available for the branches that matter, which means more mispredictions. Also, they take up icache, itlb, etc. It's not at all obvious that the overhead would be close to zero in context.

Re: We Need Hardware Traps for Integer Overflow

#90

Post by stephencanon »

Gracana wrote: post #15

ARMv5 and beyond have saturating arithmetic instructions , which can be pretty handy. It won't cause an exception, but it is at least one way to improve the situation. and a sticky saturation flag in the status register

Deprecated (and moved to NEON) in aarch64, FWIW.
Post reply on HN