The Performance Cost of Integer Overflow Checking
danluu.com
danluu.com
For example, ARM has a sticky overflow flag "Q". The idea is that you don't have to explicitly check the flag after every flag-setting instruction - instead you execute a bundle, and check if any set the "Q" flag at a point where you must branch or otherwise accept the output. Sadly, this is only implemented for a limited number of instructions (e.g QADD QSUB), and pretty much obsolete. Still - the idea is sound in that it doesn't cost a stall, if properly scheduled, and greatly reduces the number of branching points.
You can somewhat do the same purely in software with the compiler, but the lack of a "sticky" flag means it'll need to access - and potentially stall - at each point where flags would be overwritten by another ALU instruction.
I hear Rust did go down this path for a while but abandoned it. Pretty much all (non-Rust) code I write these days would SERIOUSLY benefit from global overflow detection. I would turn it off for only a few critical paths, audit the hell out of those code snippets, and I bet I would get very close to the original performance.
This is surprisingly expensive to implement fast and correctly in a modern OoO core. The most likely implementation would end up taking Q as a dependency for every qadd/sub, which would be terrible.
> You can somewhat do the same purely in software with the compiler, but the lack of a "sticky" flag means it'll need to access - and potentially stall - at each point where flags would be overwritten by another ALU instruction.
The jump depends on flags, but by definition has no further dependencies. So long as it's untaken and predicted as untaken the cpu can never stall on it.
The trap in Alpha ISA was done for MIPS compatibility reasons (Alpha was more or less MIPS assembly compatible).
Not-a-thing is basically a tagging scheme where the contents of registers are extended with a bit indicating whether the value is valid or not. Arithmetic operations on a NaT produce a NaT: branches or stores which consume a NaT raise an error. Given arithmetic instructions that generate NaT on overflow, the wrong result will be prevented from affecting the state of the program without explicit tests or jumps.
I'm not sure what the implementation costs would be on the hardware side, though.
Given that it's generating the same bits as x86, but with the flag stored with the output rather than in a separate register, the hardware cost shouldn't be more than one more level to select the actual result.
This is also how they handle illegal reads, which (along with vector smear and pick instructions) makes vectorizing loops possible when they might otherwise cross protection boundaries.
That is the rub right there. Think about what this means. Every ALU operation needs to read whatever register contains this state and write a new value. So every ALU operation becomes serially dependent all all previous operations. You have just totally killed performance on out-of-order processors.
Processor designers work really hard to avoid these kinds of operations. In fact between the Pentium and the Pentium Pro (aka p6) the behavior of condition codes on several x86 instructions were changed from "keep old value" to "always cleared". We couldn't find any code that cared and it was never previously documented.
This code doesn't have to use branches, it could also OR the condition codes to some register after every operation. This would also hurt performance, but only for code that cares instead of all code.
The addition is usually done using carry-look-ahead scheme [1]. This scheme has depth of O(log(N)) (N being number of bits). For 64 bits it is k * 6, and k is about 1.5. So you are looking at ~9 logical operation depth.
The computation of overflow uses bits from both operands and result. You also have to store that overflow bit somewhere. This means that 1) you have to add logical operations (usually two) to compute it and 2) you have to lay wires to store results of computations. Either way you waste timing resources (logical ops for wider processes, wires for thinner ones).
For superscalar execution you end with another result dependence to resolve and mostly ignore.
In the end you add about 5-10% of overhead of clock cycle time due to constant checking for overflow.
E.g., your request will make all computers more expensive to operate.
I have relatively extensive experience in designing hardware for a software engineer (accelerated video controller for STB, no less, from algorithmic prototype to tests). My modus operandi in that area is that you should do in hardware only what you cannot do in software.
Let's compare SPARC and MIPS. SPARC has status register (hardware support for overflow you asked for) and MIPS doesn't. SPARC lso has complicated register file, but it is out of control path, which is register-register addition, you wouldn't believe. SPARC and MIPS are equavalent otherwise. We estimated operating frequency estimations for ALUs of SPARC and MIPS for 0.13um process and for SPARC it was 400-450MHz for SPARC and was about 500MHz for MIPS, without any tweaking in low level. We have here 10% in speed difference. MIPS would be even faster if we ditch ADD/ADDI/SUB/SUBI instructions (add/subtract with overflow checking).
The same is true for OpenRISC and RISC-V. OpenRISC generates exceptions for any sneeze that may happen, RISC-V continues. Guess what is easier to develop, test and will be faster in the end.
Please, do not add to hardware any functionality you really do not need. You can check for integer overflow statically and generate special code that will generate exceptions if you cannot prove their absence conclusively. This is already done for division by zero for MIPS target (check it out, it is amazing to see difference between -O0 and -03), it can be done for integer additions.
http://www.electronics.dit.ie/staff/tscarff/8086_instruction...
You can do without carry and overflow flags in long arithmetic just fine.
And you don't need a flag resister to check for overflows. Trap on overflow (like Alpha) will work just as well. The difference is that traps are infrequent so you don't have to make them fast, just correct. You don't have to raise the trap in the same cycle that you calculate the integer operation. You just have to to do it before the commit stage. (And the last time I checked, the Alphas were quite a bit faster than MIPS.)
Of course hardware support implies some overhead and more complexity. I can see why people would oppose it. But there really is software that would greatly benefit from hardware support.
The Alphas were faster than MIPS due to manual design. Instead of using standard components they laid everything out by hand and they often used domino logic, AFAIK. Classic five stage pipeline MIPS implemented with domino logic can easily get 1GHz (twice as fast as direct synthesis).
Domino logic: http://en.wikipedia.org/wiki/Domino_logic
And software would benefit from static error checking much more than from hardware support for integer overflow.
It does not need evaluating between every operation. In fact in the example I gave (ARM SIMD) the entire point of its design is exactly so that you don't need to incur the latency of the flag generation logic for every operation.
I wouldn't dream of implementing anything quite as deliberately inefficient as what you're describing. We're decades beyond the point of two instructions serially depending on each other.
IF you add overflow checking into hardware, you doing disservice to all your users. Pure and simple.
Hardware always evaluate everything. It is hard to get for software engineer, but it is true. The little overflow flag and scheme for its computation will sit there draining energy all the time.
There is an additional latency to get flag results. The latency is not paid unless you depend on them. Overwriting is not a dependency.
Other architectures get around the cost altogether by having a separate "set" bit in their ISA, e.g ARM. If you don't want flags modified, then don't specify it, e.g ADD instead of ADDS.
I think you are quite mistaken by multiple orders of magnitude how much power cost it would have, especially when taking into account the rest of the system.
The reckless removal of safety checks in the pursuit of performance would be considered alarming were it not commonplace.
(Disclaimer: I really, really care about integer overflow for some odd reason, going so far as to be going through the entire PHP codebase to add big integer support...)
We have put a lot of thought into the matter, and the conclusion was that (a) the performance overhead, as measured by benchmarks, could be significant; (b) the relative benefits of doing the checking in Rust would be much less than in C and C++, since overflow in (safe) Rust cannot result in memory safety problems. However, we're looking into ways that we could allow folks to opt into the feature globally in the future should the performance story change or if they want to panic rather than overflow. You can already use the special checked types for arithmetic on a case-by-case basis if you'd like overflow checking.
I also think overflow errors should be conveniently handleable without putting a try! or match expression on every operation, and so should other errors, but I'll spare you that rant :-)
Rust is "memory safe" per the commonly used Saraswat definition [1] (not proven yet, but the proof is in progress). This is not something we just made up.
[1]: http://www.cis.upenn.edu/~bcpierce/courses/629/papers/Sarasw...
> This is not something we just made up.
I deliberately did not say 'made up' or 'created', but rather 'picked' meaning 'selected'. The fact that the map is pre-existing and commonly-used (and rightly so) does not alter the fact that it is not the terrain.
> What would have been unreasonable is to imply that the
> safety implications of integer overflow can't matter much
> or are somehow out of scope because of Rust memory-safety.
(For completeness, I'd like to point out here that checked arithmetic is not a panacea. For any range that you wish to express in an integral type, it is vanishingly unlikely that INT_MAX is actually the logical upper bound. If I have an RPG where characters can quiver 100 arrows but I forget to enforce the upper bound, checked arithmetic won't save me from the fact that my program can now exist in somewhere between 28 invalid states (signed eight-bit variable) and nine sextillion invalid states (for a signed pointer-sized variable on a 64-bit platform, as is so common for "default" integral types). The real solution is reifying integral bounds in the type system, as I expect the language that someday replaces Rust to do.)
Seems reasonable to me, and I certainly didn't demand overflow-checking by default in Rust. (OTOH, twelve hours ago you were so disappointed with that decision that it undermined your confidence in the Rust team...) But I don't see what that has to with picking the definitions for desirable adjectives like 'safety' when it comes to promoting or describing a system.
Well it's relatively small damage levels but it's the wrong decision, and it's the inoffensive choice made of status quo bias.
Unsafe code needs to validate its inputs. That's part of the contract of unsafe code. If your unsafe code causes memory safety errors when given MAX_INT as an input, then your unsafe code is dangerously broken regardless of how easy it is for safe code to accidentally create a MAX_INT value.
[0] http://doc.rust-lang.org/std/num/trait.Int.html#tymethod.sat...
[1] http://doc.rust-lang.org/std/num/trait.Int.html#tymethod.che...
Already this is a HUGE improvement over C. Is it allowed to silently mix checked and unchecked integers?
1. machine bit-string of size 8(2^n) bits (e.g. b/w/d/q fields) with no concept of being a signed/unsigned integer, but where you can apply both signed and unsigned integer operations to it in an optimized manner. Such code will be shimmed with sets of clever shifting ops if the target architecture doesn't actually have a storage type of that width, but you have to be explicit about what you'll allow (e.g. if an integer is of type "d|2w", then it will compile fine on a 16-bit architecture (and operate using shimmed ops), but fail to compile on an 8-bit architecture.
2. unsigned integer of fixed exactly-specified bitsize, which exactly matches the semantics of a having a value on a modular-arithmetic ring. You go up, it wraps around at 2^bitsize; you go down, it wraps back. This stays true even if the code is compiled on an architecture where the exactly-specified bitsize isn't a clean processor storage-width: a 27-bit ring on a 32-bit processor is A-OK, and shims will be inserted to enforce the semantics. Shims will also be inserted if you're targeting an ISA that doesn't have an integer type with wrapping semantics (e.g. the JVM.)
3. signed arbitrary-precision integer (i.e. optimal-machine-word-size-minus-a-tag-bit with bignum promotion checks). The optimizer might convert one of these to something of type #1 if it can be very, very sure of the value range you're operating within.
#1 is for doing pointer math in unsafe regions; #2 is for implementing cryptographic primitives; #3 is for everyone else.
(There's also a variant on #1—let's call it #1A—which is a fixed-size array of #1s you can repeat signed/unsigned integer transformations over, where this will generate optimized SIMD code. This would be the "buffer" type for wire protocol packing/unpacking, and also the backing store for non-sparse matrix ADTs, bloom filters, etc.)
The only place integer overflow raising an exception would make sense, to me, are if you want some sort of hybrid type between #1 and #3: a value that pretends to be arbitrary-precision, but in fact only has a constant-size bitstring to operate within. I could see the use of this in something like Cap'n Proto, where you're keeping wire-encoded integer bitstrings (#1s from a #1A) around and pretending they're fully-functional integers (#3) for the sake of zero-copy—but do you really gain that much by not letting a data structure be recreated resized on the stack, if you're not also throwing down optimizations like intrusive lists in fixed arenas?
• crash the request thread?
• output a floating-point value with some of the precision thrown away?
• output a machine integer with the overflow flag set?
• output an arbitrary-precision integer?
Basically, arbitrary-precision integers are a necessary part of any platform that needs to be able to hold onto, and do math to, externally-generated numbers that didn't arrive packed in #1A type structs.
To insist, in the modern day, on attempting to do arbitrary math with arbitrary numbers using strictly machine words, is like insisting on defining a Postgres column as a VARCHAR, when TEXT is just as optimal for the average case, while automatically coping with edge-cases.
Most numbers computers touch don't have bit patterns that fit in 8(2^n) bits, but not 8(2^n) - 1 bits. Tag bits are cheap, especially if you have the other two integer types to fall back on.
- output a floating-point value with some lost precision
- output an arbitrary-precision integer, or some general "number" type that can be an arbitrary-precision integer or double-precision float
- output an "integer too precise to decode" placeholder in that location in the data structure
- fail to decode the document entirely
In no case should it crash.
I don't know what you mean by "a machine integer with the overflow flag set", since it doesn't exactly work that way, so the "integer too precise to decode" value is my alternative.
For example, suppose you're making a "JSON document"-based database engine and its query language only supports double-precision numbers. In that case, I would output a correctly-rounded floating point value, if I were decoding JSON.
Usually in other cases of decoding an integer, unless you're hosting an arbitrary precision integer calculator web application, there should be maximum acceptable values on any integer you'd read off the wire. For example, there's a maximum data size, maximum timeout duration, and such.
Note that I was using the Erlang sense of "crash"—a crash from a pattern-matching failure is the default clause of most case statements, and you want those to be bubbled up by crashing linked and supervising processes until they hit something that has generic "something went wrong; I'm going to report this to the user" code in it (like e.g. Rack does in Ruby.) You don't want to specifically be throwing, immediately catching, and then converting exceptions into 500 errors in every part of your code.
Also, I was assuming in this example that you're using a modern web framework, where the JSON decoding is handled by the framework—not by you—so the framework likely doesn't expose any configuration for something like its JSON deserialization library, which it wants you to just consider an implementation detail. So you won't get to specify anything like "maximum data size". Instead, the JSON library needs to "just work" in all cases, returning its best-effort interpretation of the wire message to you. (The parallel for HTML parsing would be libraries like Beautiful Soup.)
Nit - actually the JSON standard doesn't specify a precision for the number type, but most JSON implementations don't support arbitrary precision numbers.
Though the more recent RFC does have some implementation notes for interoperability.
http://rfc7159.net/rfc7159#rfc.section.6
> "This specification allows implementations to set limits on the range and precision of numbers accepted. Since software that implements IEEE 754-2008 binary64 (double precision) numbers [IEEE754] is generally available and widely used, good interoperability can be achieved by implementations that expect no more precision or range than these provide, in the sense that implementations will approximate JSON numbers within the expected precision. A JSON number such as 1E400 or 3.141592653589793238462643383279 may indicate potential interoperability problems, since it suggests that the software that created it expects receiving software to have greater capabilities for numeric magnitude and precision than is widely available."
> "Note that when such software is used, numbers that are integers and are in the range [-(253)+1, (253)-1] are interoperable in the sense that implementations will agree exactly on their numeric values."
This is the reason that overflow checking can be so inexpensive --- no additional checking is necessary, just a conditional branch on an existing flag. Correctly predicted branches not taken are very inexpensive, and this branch will almost always be correctly predicted. The issue is that standard C doesn't allow any direct defined way to make use of the overflow flag. Instead you have to write something awkward and hope the compiler optimizes it down for you.
It's like trying to talk to Haskell about explicit thunks, or Lisp about stack-vs-heap allocation. The language encapsulates the concept away from you, so if you wrench it back, you're no longer quite writing the language; you're writing a union of it and something else.
long mega_byte = 1024 * 1024 * 8; // bits per MB long mega_bit = 1000 * 1000; // bits per megabit
If you follow the C90 standard, this code has all sorts of issues. First, // comments are not allowed. Second, identifiers are only guaranteed to have six significant characters, so the above two variables might actually be the same variable. Finally, ints are only guaranteed to be 2 bytes, so the multiplication may overflow and the program is undefined. (Assigning to longs doesn't help: the multiplication already happened.)
> A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants
And people will want complex numbers, quarternions, non-Abelian groups, etc.
So, #2 is just a few extra guarantees about the intrinsics of regular machine-words, with minimal overhead for the fast path (even on the slower path of e.g. a 30-bit ring on 32-bit storage, there's still an O(1) set of barrel-shifts and masks that can be used to implement that.)
A fully-general ringed arithmetic value, on the other hand, is more of an ADT. It could certainly be implemented in the same language and act like a number, but it wouldn't be useful as backing storage for other types in the way #1, #2, and #3 are. (Note that #2 is a better backing store than #1 for many use-cases, e.g. encoding IP addresses and subnet masks.)
Also, if you include bigints in your list of things people want, I do not find it unreasonable to add timestamps (maybe not the best example because of leap seconds) or 'day of the week', 'month of the year' to that list. Most language libraries get those (often including those perfect 86400 second days) before they get bigints.
This is incorrect: the JVM has fully well-defined modulo arithmetic:
http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.htm...
"The result is the 32 low-order bits of the true mathematical result in a sufficiently wide two's-complement format, represented as a value of type int. If overflow occurs, then the sign of the result may not be the same as the sign of the mathematical sum of the two values. Despite the fact that overflow may occur, execution of an iadd instruction never throws a run-time exception."
With this definition the JVM doesn't need distinct instructions for unsigned arithmetic since they're identical to signed arithmetic in two's complement (with some exceptions like shifting for which there are both ishr / iushr instructions).
- Without need checking after every operation
- Without impeding easy use of overflow (and/or allowing for saturation) when it's needed (in a lot of places)
So, I see a narrow use for it, IF you validated your inputs AND overflow is unexpected (or, it is expected and you do something different, but it's still on narrow cases)
I did a smaller file than Dan because I didn't have the patience to test with the 1GB file. Testing was Linux on Haswell, cycle and instruction counts are coming from 'perf stat' and are in billions except for the last column, (instructions/cycle). Not shown here is the number of mispredicted branches, which as expected does not increase for adding the checks since they are all well predicted.
cycles instructions branches ipc
clang-O3: 24.4 43.8 6.3 1.79
clang-O3-sanitize: 26.5 54.8 9.3 2.06
gcc-O3: 23.0 42.5 6.2 1.85
gcc-O3-sanitize: 24.6 47.3 7.6 1.93
icc-O3: 23.8 41.6 6.5 1.75
I'm somewhat confused as to why the increase in instructions executed is so much greater than the increase in the count of branch instructions. This would seem to confirm Dan's experience with poor generated code quality, but looking the tight loops with 'perf record' both GCC and CLang appear to be generating reasonable code. Both sanitized and normal spill to the stack much more than seems necessary, but this doesn't seem to because of the overflow checking. I'd guess the extra instructions are just by chance because of how the 'jo' checks were laid out.
f(int, int):
mov eax, edi
add eax, esi
jo .L8
ret
.L8:
...http://s24.postimg.org/xakc6eglx/idrivefail2.png
iDrive backed up a 3GB file. This overflowed a 32-bit value, and so iDrive shows the size as -149406.91 KB. This seems to have confused something in the iDrive system, and now backups won't run. Their tech support people have been working on this for two days now.
C officially considers unsigned integer overflow to be modular arithmetic. I consider that a mistake. If you want modular arithmetic, you should write
x += n % (2^32)
x += n % (1 << (SIZEOF_LONG * CHAR_BIT));Edit: https://developer.apple.com/library/ios/documentation/Swift/...
sizeof(long) * CHAR_BIT
More importantly, I think that expression produces an int value, so if sizeof(long) > sizeof(int), that shift will produce undefined behaviour (or zero? I don't have a C standard to check that on at hand. Actually, shifting any integral type by its size in bits could well be undefined behavior)
Even if that weren't the case, that doesn't do modular arithmetic. You would want
x = (x + n) % (1 << (SIZEOF_LONG * CHAR_BIT));
I think one would need custom syntax for making modular arithmetic easy in C. I would suggest something like
x += n (mod 37);
modular(43) int x;
modular(23) int y;
int n = x + y; // error?
Edit: yes, it is harder. According to http://blog.regehr.org/archives/738, left-shifting a signed integer by one bit already can trigger undefined behaviour.
void memzero_range(char* array, int start, int end) {
for(int i = start; i < end; i++)
array[i] = 0;
}
void memzero_range(char* array, int start, int end) {
int i = start;
while (i < end) {
array[i] = 0;
if (i == INT_MAX) {
assert("overflow!");
}
i++;
}
}
(and if we talk about optimizing compilation things are getting more complicated as there int31, int32 and float64 can all coexist and you can have 31-bit integer stored in a float64 value - if operation was specialized for floating point values)
FTL has already precipitated other interesting changes in LLVM (to support deoptimisation and GC).
I feel like noobs hitting an overflow for the first time think the world would be better if the machine could "just take care of it".
That said, one solution to overflow in some cases is saturating arithmetic. Supported on some processors, but by no languages that I know of. That may be worth considering.
uint32_t leToWord(uint8_t bytes)
{
return bytes[0] |
bytes[1] << 8 |
bytes[2] << 16 |
bytes[3] << 24;
}I would think that the best approach is to set up a global overflow handler, driven by an interrupt, and then maybe for cases where you actually want to be able to overflow, a special C primitive (that would use instructions that avoid overflow in some way) could be useful.
I am just wondering why the article doesn't mention this possibility at all.
Besides, if we're talking about language design and compiler optimizations, there are plenty of ways to check overflow without resorting to a branch on every arithmetic operation.