22 ms·
We Need Hardware Traps for Integer Overflow
- shasta 12y agoIn case anyone has the same difficulty reading this as I did, "integer types that wrap" is supposed to refer to arithmetic modulo 2^n. I thought at first he was talking about wrapped integer types.
- maggit 12y ago> wrapped integer types A google search for "wrapped integer types" gives me the Wikipedia article on Integer Overflow as its first result. The other hits seem to be related. What else do you mean by "wrapped integer types" if not arithmetic modulo 2^n?
- simcop2387 12y agoI think he probably means boxed integer types: http://msdn.microsoft.com/en-us/library/yz2be5wk.aspx http://msdn.microsoft.com/en-us/library/yz2be5wk.aspx
- deleted 12y ago[deleted]
- shasta 12y agoA google search for "striped horse" gives me the Wikipedia article for Zebra as its first result. Similarly a google search for "wrapped integer types" takes you to a Wikipedia page for "integer overflow" that never uses the phrase "wrapped integer." simcop2387 is correct that I assumed he was talking about boxing at first.
- Someone 12y agoI found it weird that nobody mentioned it, but was this posted because Apple's new language Swift has integer overflow detection (with operators &+, &-, etc. operators for doing conventional C-style modulo integer math)?
- noblethrasher 12y agoIt was posted to reddit six days ago[1], four days before Swift. [1] http://www.reddit.com/r/programming/comments/26s8iu/we_need_hardware_traps_for_integer_overflow/ http://www.reddit.com/r/programming/comments/26s8iu/we_need_...
- JoshTriplett 12y agoPersonally, I'd like to see more programming done in languages that simply don't allow integer overflow in the first place. Most current languages have arbitrary-precision integers; well-implemented arbitrary-precision integers are quite efficient when they fit in a machine word, and as efficient as possible when larger. Sure, you'll lose a bit of performance due to checks for overflow, but those checks need to exist anyway, in which case it seems preferable to Just Work rather than failing.
- rlpb 12y ago> Sure, you'll lose a bit of performance due to checks for overflow... Which is why the author wants support for integer overflow traps. He even mentions Python, which does what you describe, and suggests that other languages don't do this precisely because of the performance hit for which he's proposing a solution.
- jjoonathan 12y agoChecks are the smallest cost of bignums. Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. It's one thing for a scripting language (where people expect poor, inconsistent performance) to have automatic bignums but it's quite another for a language in which people will be writing performant code to have automatic bignums. They introduce a thousand difficult-to-debug edge cases that slow your code to 1/3 or 1/5 (or 1/100th or 1/1000th) speed. I don't know about you, but I don't consider that "Just Working." Don't get me wrong, they could be a useful feature, perhaps even one which should be enabled by default in Swift (I'd argue against them, but I wouldn't be entirely unsympathetic to their proponents). However, they aren't for everyone and they don't come cheap.
- metaphorm 12y agocontext matters. most arithmetic operations are not performed in hot loops or are not performed on large vectors. I think its better to have a default where correctness and error prevention are gained at the cost of speed. When the speed is needed an explicit choice to use an unsafe but faster performing number type would be the prerogative of the programmer. Its important to have both options available, because context matters.
- sounds 12y agoModern CPUs don't like traps ("exceptions"). The exception causes a pipeline flush which kills performance for math-intensive code. For example, detecting integer overflow on x86 and x86_64 CPUs is easy: check the overflow flag after every arithmetic operation. It would only be slightly more difficult to detect overflow for SSE (vector) operations, which would require doing some bit masking and shifting. For a language such as Swift, building it in is simple.
- maggit 12y agoThe 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 :)
- mmastrac 12y agoExactly -- the premise would be that non-overflowing arithmetic would be the "fast path" and overflow would be truly exceptional. This is similar to null-reference protection in various languages and runtimes, where null dereferences are caught by mapping guard pages at the beginning of memory. Dereferencing a pointer is optimistic and assumes that it will succeed, the same as arithmetic operations would in this proposal.
- deleted 12y ago[deleted]
- vonmoltke 12y agoThe problem with a hardware implementation is that you break algorithms and coding systems for which integer overflow, or rather integer wrapping, is a necessary piece rather than an exception case. You could, in theory, add an instruction that disables integer exceptions, but that would make the hardware more complicated. You could also redesign the aforementioned algorithms and systems to not rely on the implicit wrapping, but then you make them more expensive.
- angersock 12y agoOne of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic"--explicitly and carefully catching overflows due to multiplication and addition, for example. This code proved invaluable when writing binary parsers designed to support "unsafe" mesh data coming off of the network--the file might be garbage, but we could at least safely parse it. I'd go so far to say that if you are dealing with a binary format--especially a sane one which has length headers and chunks for rapid seeking--and you aren't using something similar, you are doing it wrong. EDIT: For the curious, you may find some of these bit-twiddling hacks to be of some use. http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious http://graphics.stanford.edu/~seander/bithacks.html#IntegerL...
- TorKlingberg 12y agoRegehr, where this post is from, recently had an article about how to do safe arithmetic in C. http://blog.regehr.org/archives/1139 http://blog.regehr.org/archives/1139 As you say, it is surprisingly different to it get right, especially if you want good performance. A common mistake is checking for signed integer overflow after the fact. It is too late when undefined behavior has already happened.
- userbinator 12y ago> It is too late when undefined behavior has already happened. This seems more like a theoretical concern, as just about all the hardware out there is 2's complement and signed overflow wraps around in the usual way - because that's the simplest, most straightforward way to implement it. (This also means I think compilers that exploit this "loophole" in the language are seriously violating the principle of least surprise.) If you're working on the few exceptions to this, then integer overflow is probably going to be the least of your worries...
- zvrba 12y ago> One of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic" I'm surprised that something that necessary and tricky to implement still hasn't been considered for the C standard library.
- Gracana 12y agoARMv5 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
- stephencanon 12y agoDeprecated (and moved to NEON) in aarch64, FWIW.
- Gracana 12y agoHuh, okay, I guess that's sensible. Thanks for pointing that out, I haven't been paying much attention to the latest in ARM, so I hadn't heard that.
- zvrba 12y agoOr 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.)
- pbsd 12y agox86-64 could repurpose the Adjust flag (bit 4 of EFLAGS) for this. It is not longer used, since BCD instructions were deprecated in the x86->x86-64 transition. There is also precedent in the last few years for new instructions that change flag semantics: ADCX and ADOX.
- stormbrew 12y agoI 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.
- xxs 12y agoThe branch is to be predicted (close to perfectly) by the hardware so the branch cost would be like an extra cycle.
- stormbrew 12y agoAn interesting tangent to this, in terms of trapping math operations, is that Swift added an operator for a non-trapping div-by-zero operation: &/ I'm not sure I've seen that in any other languages before.
- jlarocco 12y agox86 processors already have overflow and carry bits in their flags register to tell when overflow has occurred. It makes more sense to me to have compiler writers check the flags if they care about overflow, and avoid the slow down if they don't.
- danbruc 12y agoNo, doing it in hardware makes more sense. If you expect overflows you disable overflow checks in the hardware and everything is as before. If you don't expect overflows you enable overflow checks in the hardware and if you have a bug you get the exception. If you do it in software you have to execute additional instruction every time but they will do nothing useful if your program is correct.
- willvarfar 12y ago(Mill team) With apologies to those tired of hearing about the new Mill CPU let me explain how the Mill traps on integer overflow: For overflow-able arithmetic operations, we support four modes: * truncate * except * saturate * double-width With excepting overflow, the result is marked as invalid (we term it "Not-a-Result (NaR)"). As these invalid results are used in further computation, the NaR propagates. When you finally use the result in non-speculatively e.g. store it or branch on it then the hardware faults. NaRs have lots of other uses. This is described in the Metadata talk http://millcomputing.com/topic/metadata/ http://millcomputing.com/topic/metadata/ And http://millcomputing.com/topic/introduction-to-the-mill-cpu-programming-model-2/ http://millcomputing.com/topic/introduction-to-the-mill-cpu-... for a broader overview.
- userbinator 12y agoIt'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 often-used) instruction, that single-byte opcode becomes wasted in 64-bit mode. With it, adding overflow-trapping arithemtic support to a compiler would be trivial and only add 1 extra byte to each arithmetic operation that needs it. Ditto for BOUND, which is useful for automatic array bounds-checking - it performs both lower and upper bounds checks. Also, I don't really get why integers wrapping around should be "unexpected". It is only to those who don't understand how integers work. The saying "know your limit, play within it" comes to mind.
- JoshTriplett 12y agoThose 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.
- ahomescu1 12y agoIf you put the INTO immediately after the overflowing instruction, the OS could just go back one instruction (harder than it seems, but not impossible). Wouldn't that work?
- JoshTriplett 12y agoThat'd require the OS to define that as part of the ABI. Also, you almost certainly don't want to just go back an instruction; you want to catch and handle the overflow.
- userbinator 12y agoThere'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.
- perlgeek 12y agoMy 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?
- danbruc 12y agoOf 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.
- throwawayaway 12y agohere'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.html http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...
- danbruc 12y agoYou can see the implementation in GCC here [1], for example addition starting on line 74. What machine code gets emitted for that obviously depends on the target architecture but it is reasonable to assume that the optimizer recognizes these patterns and uses hardware flags where available. [1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c
- throwawayaway 12y agolooking over it again, it seems like quite a leap for the optimiser to do that, i have my doubts.
- throwawayaway 12y agohttp://www.emulators.com/docs/LazyOverflowDetect_Final.pdf http://www.emulators.com/docs/LazyOverflowDetect_Final.pdf This paper seems to imply that that high level languages can't access the carry bit, yet C#'s checked mechanism uses it. I've been using -ftrapv with gcc for a long time, from here: https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options. From the code you posted, and the assembly[1] emitted in the pdf above I can't see the optimiser taking advantage of the carry bit. No mention of CF, OF: [1] lea ebx, DWORD PTR [edi+eax] cmp ebx, edi jae SHORT $LN4@unsigned_c cmp ebx, eax jae SHORT $LN4@unsigned_c mov ecx, 1 jmp SHORT $LN5@unsigned_c xor ecx, ecx The gcc flag ftapv only works for signed integers, not clear what the carry bit behaviour is for unsigned integers.
- robryk 12y agoI wonder how often it'd be possible to deduce that an overflow is not possible from the context. (For example, if we've just checked that INT_MAX/a > b before doing a*b.)
- stormbrew 12y agoThat's probably more expensive than a jno instruction after the possibly overflowing operation.
- DasIch 12y agoDivision is a lot more expensive than the multiplication itself, checking the overflow flag after the multiplication - which OP critizes for being too slow - is going to be much faster than your check.
- forrestthewoods 12y agoI'm gonna shill for a moment and link a post I wrote on integer overflows very recently. http://forrestthewoods.com/perfect-prevention-of-int-overflows/ http://forrestthewoods.com/perfect-prevention-of-int-overflo... TLDR: Not accidentally performing an undefined operation is really really hard.
- pascal_cuoq 12y agoHello, the comment system on your blog eats comments, that become lost forever when submitted. You might want to know that. Apart from that: 1) “2147483650f” is Java syntax. Also this number, written in C++ as 2147483650.0f, actually represents the number 2147483648 (assuming float is the single-precision IEEE 754 format). You might want to denote that number 2147483648.0f, which would be less confusing. 2) the line “const int min = 0x80000000;” does NOT contain undefined behavior. The overflows occurs during a conversion from an integer type to a signed integer type. Overflow during such a conversion is implementation-defined (or an implementation-defined signal is raised). Even an implementation-defined signal is not undefined behavior, but in practice, the compiler you use produces wrap-around behavior, and it will continue to do so, because it has been forced to document it.
- forrestthewoods 12y agoWhat login did you use for making the comments? It just uses Disqus which is pretty common these days. I was able to successfully make a comment with a Twitter login. Recent posts have had surprisingly few comments but not zero. Strange... The 2147483648 vs 2147483650 is actually kind of interesting. Visual Studio watch window prints floats with one less digit of precision they they need as it actually displays (from memory) 2.14748365e9 when it should display as 2.147483648e9. Thanks for the catch. I'll have to check spec docs to if the unsigned to signed overflow is undefined or implementation defined. I think you're correct but I need to verify.
- rwallace 12y agoI 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 agoHere'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.
- paulannesley 12y ago> In a unicode language we might use ⊞, ⊟, etc. Nope.
- enupten 12y agoDidn't lisp machines have Hardware traps of some kind ?
- ScottBurson 12y agoLots 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.
- acqq 12y ago"Those who do not understand the hardware are doomed to blog about it, poorly. Intel chips already detect overflow, that is what the OF (bit 11) flag in the flags/eflags register indicates. That the most recent operation overflowed. Testing, and generating a trap, for an overflow is a single instruction (JO – jump if overflow and JNO – jump if no overflow). This is true of almost all CPU’s. At the hardware/assembly programming level, overflow detection is handled by hardware, and detected by a single instruction. The reason all of your languages listed don’t have any sort of trap/etc. is simple. The language designers did not bother to check the result of their operations. Why, most likely because almost all of them are ultimately implemented in C, and C does not reflect the overflow status back into the C language level. So the problem isn’t the hardware. It is the software architectural design(s) implemented above the hardware. They are not bothering to communicate to you the results of what the hardware already has available and tells them about." (Qouting comment from Anon)
- acqq 12y agoAnd it is true, there is already the hardware "overflow" flag, just not visible in "higher" level languages.
- jacquesm 12y agoSetting a flag is not the same as raising an exception. When you get a segfault that's not because a flag was checked, that's because a chunk of hardware interrupted the next operation. So yes, you can check for overflow by inspecting a flag, but that's not all that much better from coding around the potential overflow to see if your operands + operation combo will cause an overflow. Imagine setting a flag on a divide by 0 instead of raising an exception. So the author is most likely aware of the overflow flag (just like any other old timer that has programmed in assembly and that had a cursory look at the flags register, or in some cases more than a cursory look :) ), he's writing about hardware exceptions, not about how to write in javascript. But inspecting a flag simply isn't on the same level as raising a hardware exception, right along with segfault, division by 0, FPEs and so on. That instantly propagates through to any programming language executed on the machine. Checking a flag in a register is a decision by a compiler writer and many compiler writers (consciously!) ignore that (usually because the language specs are vague enough that wrapping is considered acceptable when it is in fact almost always simply wrong).
- Sirius17 12y agoI've worked with many CPUs (i86, Z80, 6502, ...) and all had some kind of overflow / underflow indicator, normally in the status register.