10 ms·

The Performance Cost of Integer Overflow Checking

166 points by nicholasjbs 12y ago

TazeTSchnitzel 12y ago
The fact many languages don't overflow check by default really saddens me. Integer overflow is the cause of so many bugs (many user-facing: http://www.reddit.com/r/softwaregore/ http://www.reddit.com/r/softwaregore/), and yet people keep making new languages which don't check overflow. They check buffer overruns, they check bounds, and yet not integer overflow. Why? The supposed performance penalty. 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...)
- SamReidHughes 12y ago
  This is the main reason I don't trust the mob of people working on Rust to get their act together and make it a good language. You can see some awareness of the value of integer overflow detection among some individuals that work on Rust but despite that, here we are without that feature. Swift, on the other hand, is one language that has put some thought to the matter.
  - doublec 12y ago
    There was a discussion in the Rust mailing list about it a while back. I used that as a basis for looking at overflow detection at compile time in ATS: http://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and-bounds-checking.html http://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and...
    - codygman 12y ago
      Thanks for the great read. As someone who's been eyeing ATS for a while and checking it out more lately, this was very inspirational.
  - TazeTSchnitzel 12y ago
    Huh, Swift actually does overflow checking and traps by default. That's quite refreshing.
  - pcwalton 12y ago
    > You can see some awareness of the value of integer overflow detection among some individuals that work on Rust but despite that, here we are without that feature. Swift, on the other hand, is one language that has put some thought to the matter. 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.
    - SamReidHughes 12y ago
      Not to re-relitigate old discussion, but (as I'm sure you know) it's now more probable that you might overflow your integers and then pass them to unsafe code or external APIs, and there are many other bugs or undesirable behavior that could be killed dead instead of allowing them to behave badly. For a not contrived example, I don't want weird stuff to happen when my semaphore counter overflows, or underflows, I want it to just crash, right there. (My perspective and desires come from a project where I didn't care about "raw" performance that much -- the project being a storage engine where C++ was chosen with the performance concerns in mind being lack of GC and resultant traffic shockwaves, so my preferences lie a bit away from CPU integer operation performance and more towards crashing obviously at the spot of the foul. It's the worst kind of bug when you hang mysteriously in production or to write garbage to disk when the error could be caught, and I had many C++ integer underflow worries at that job.) 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 :-)
      - leoc 12y ago
        It's that old song. "Our language is safe!—for some very specific, rather convenient definition of 'safe' which we just picked ourselves."
  - derefr 12y ago
    It seems to me that, despite all the flexibility people demand, they only really want (and use) exactly three integer data-types in a language: 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?
    - SamReidHughes 12y ago
      I don't want 3, because I don't want tag bits or space wastage, but also because I don't want to have to link a bigint library.
  - lifthrasiir 12y ago
    Asides from pcwalton's argument, I think any successful (or to-be-successful) language is trying to solve some problems very well and other problems reasonably well. For Rust, the former includes the memory safety and the latter includes the integer overflow detection (but you can always name a lot more). It would be very hard to solve all problems at once (especially when known solutions to some problems worsen other problems, as seen in Rust). That can be said to Swift as well, it just picked different problems to solve very well.
    - SamReidHughes 12y ago
      I don't think it's hard to solve the problem of memory safety and integer overflow detection at the same time.
      - lifthrasiir 12y ago
        Both problems are undergoing active research. They are indeed orthogonal (albeit one can somehow reduce the severity of another and vice versa), but with a finite resource and time you sometimes have to choose.
  - raverbashing 12y ago
    What is missing is a good and easy way of doing the check: - 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)
olliej 12y ago
I'd be curious about the effect of manually substituting the clang overflow arithmetic intrinsics on the codegen.
- TazeTSchnitzel 12y ago
  I suspect that'd make it worse, as you've added a new inline call.
pbsd 12y ago
GCC 4.9 does have `-fsanitize=signed-integer-overflow`, and it generates pretty good code for that toy function: f(int, int): mov eax, edi add eax, esi jo .L8 ret .L8: ...
- Marat_Dukhan 12y ago
  Older gcc versions have `-ftrapv` option, which checks overflow for signed addition, subtraction, and multiplication. However, the implementation calls libgcc functions to do the checks, resulting in non-negligible overhead.
sanxiyn 12y ago
I hope optimiztion of integer overflow checking improves in LLVM, since now there is a highly visible project(JavaScriptCore FTL JIT) using the feature. JavaScript semantics pretty much forces you to do integer overflow checking fast.
- TazeTSchnitzel 12y ago
  You're referring to the optimisation of storing JS Numbers as integers until they get too large, presumably?
  - sanxiyn 12y ago
    Yes.
    - TazeTSchnitzel 12y ago
      Native integer overflow checks can only go so far, there, since there's no 52-bit integer type.
      - sanxiyn 12y ago
        What? JavaScript engines check for 32-bit integer overflow and promote to double.
        kevingadd 12y ago
        IIRC v8 promotes to double at 31 bits. But yeah.
        gsnedders 12y ago
        Yeah, V8 is a bit of an odd one out here. Everyone else just promotes once a signed 32-bit int overflows.
        mraleph 12y ago
nkurz 12y ago
I just did my own comparison using bzip2 (http://www.bzip.org/ http://www.bzip.org/), comparing both CLang 3.4 and GCC 4.9 with -O3 -fsanitize=signed-integer-overflow. I omitted the 'unsigned-integer-overflow' because my version of GCC didn't support it. ICC is shown for the non-sanitized version, as it doesn't support it the automatic overflow checking. 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 For Clang, adding signed integer overflow checking adds about 20% to the count of instructions executed, but only about 7% to the runtime. For GCC, 10% more instructions but also about 7% increase in execution time. Agreeing with this, the instructions per cycle ratio goes up more for CLang than for GCC, but in both cases there is a significant increase showing that each check costs less than a cycle. 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.
Animats 12y ago
Ah yes, integer overflow checking. Here's iDrive, the commercial backup service, failing at it: http://s24.postimg.org/xakc6eglx/idrivefail2.png 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) which can be easily optimized to eliminate the divide. Otherwise, it should be an error.
- TazeTSchnitzel 12y ago
  More portable: x += n % (1 << (SIZEOF_LONG * CHAR_BIT));
  - jevinskie 12y ago
    Perhaps the C++ standard could add 'operator{+,-,etc}%'.
    - TazeTSchnitzel 12y ago
      Along the lines of Swift's & operators?
      - jevinskie 12y ago
        Yes, those seem quite nice! Edit: https://developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/AdvancedOperators.html https://developer.apple.com/library/ios/documentation/Swift/...
  - Animats 12y ago
    If the program wants 32-bit unsigned modular arithmetic, that's what you should get, regardless of the underlying machine architecture. If you code that, you're probably doing a checksum, and you want the answer to be consistent across platforms.
dezgeg 12y ago
I wonder if these estimations of integer overflow cost have taken into account all the possible optimizations where the compiler could safely remove overflow checks. For example, consider: void memzero_range(char* array, int start, int end) { for(int i = start; i < end; i++) array[i] = 0; } In that example, a sufficiently smart compiler could just check for the `start > end` case once at the start of the loop, and remove the overflow check from the body. Perhaps this is something that today's Clang/GCC can already do?
- gsnedders 12y ago
  Rewriting it as follows, with an overflow check: 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++; } } Clang does indeed manage to see that the check is equivalent to a start > end case (with -O1) and hoists it out of the loop. It also then rewrites the body of the loop to use the LLVM memset intrinsic!
pslam 12y ago
It's not that unreasonable to ask for hardware support for overflow checking. There's various ways it can be supported which make it much cheaper than naive methods. 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.
- Tuna-Fish 12y ago
  > ARM has a sticky overflow flag "Q". 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.
  - anewhnaccount 12y ago
    I'm pretty rusty so excuse me if I'm spouting nonsense, but I think MRS (read register file) has a dependency on the value of Q (so q/add/sub/clear) and operations which OR a new value with Q (q/add/sub [do q |= 0 or q |= 1) have a dependency on operations which change the register file (MSR). Basically qadd and qusb commute on Q. I'm a bit fuzzy on the details, but I think this means that you just have to stall/predict when there's about to be a branch anyway. Please correct me/clarify if I'm wrong.
asgard1024 12y ago
I wonder why not use interrupts for overflow checking? (Maybe x86 still doesn't support that - my knowledge of it is very old.) That seems smarter, if the overflow is really going to be an exceptional case.. 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.
- gsnedders 12y ago
  x86 doesn't support it.
  - asgard1024 12y ago
    Ah well. I work on zSeries mainframes, and this architecture does support interrupts on integer overflows (as well as many other number formats). So I thought that x86 architecture already got that option too.
dgdsgdsg 12y ago
fefe?
co1987 12y ago
Summing up, integer overflow checks ought to cost something like 5% on typical integer-heavy workloads, but poor optimization can easily make the cost 2x to 6x what an optimal compiler would produce.
lelf 12y ago
Honestly we should talk about “The Security Cost of No Overflow Checking” first.
- sp332 12y ago
  Yes! You can make code that runs as fast as you want if it doesn't have to actually work.
- Rusky 12y ago
  It's good to talk about, but not every article on performance needs to be prefaced with a talk about security. Being aware of the performance costs of your tools is just as important in many cases. 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.
niche 12y ago
This calls for BaseN computing; an algorithm that compiles code down to the most optimal base (minimizing overflow) and then ran it on a quantum baseN computer; post compilation basing; cross basing; etc
phkahler 12y ago
It is the programmers job to check for overflow. There are a lot of comments here about having a language check for overflow, but that is not practical. Specifically, the language doesn't know what to do in the case of overflow. The best it could possibly do is throw an exception, and I suppose that's what those commenters want it to do. But it's still up to the programmer to decide what to do and implement something. Are you going to do that for every math operation in a program? If not then you're already thinking about where potential problems may occur. Sometimes you want an overflow. I like to use 16 bit values to represent angles from 0 to 360 degrees - you can add and subtract these and never need to worry about the wraparound - I don't want that to throw an exception. If your code is going to overflow when you don't expect it to, you've got a bug and the language isn't going to be able to save you. 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.
- aidenn0 12y ago
  Spot the signed integer overflow here that leads to undefined behavior on targets where "int" is 32-bits: uint32_t leToWord(uint8_t bytes) { return bytes[0] | bytes[1] << 8 | bytes[2] << 16 | bytes[3] << 24; }
  - detrino 12y ago
    This is more about C's integer promotion rules than it is about overflow.

166 points by nicholasjbs 12y ago

The fact many languages don't overflow check by default really saddens me. Integer overflow is the cause of so many bugs (many user-facing: http://www.reddit.com/r/softwaregore/ http://www.reddit.com/r/softwaregore/), and yet people keep making new languages which don't check overflow. They check buffer overruns, they check bounds, and yet not integer overflow. Why? The supposed performance penalty. 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...)

SamReidHughes 12y ago
This is the main reason I don't trust the mob of people working on Rust to get their act together and make it a good language. You can see some awareness of the value of integer overflow detection among some individuals that work on Rust but despite that, here we are without that feature. Swift, on the other hand, is one language that has put some thought to the matter.
- doublec 12y ago
  There was a discussion in the Rust mailing list about it a while back. I used that as a basis for looking at overflow detection at compile time in ATS: http://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and-bounds-checking.html http://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and...
  - codygman 12y ago
    Thanks for the great read. As someone who's been eyeing ATS for a while and checking it out more lately, this was very inspirational.
- TazeTSchnitzel 12y ago
  Huh, Swift actually does overflow checking and traps by default. That's quite refreshing.
- pcwalton 12y ago
  > You can see some awareness of the value of integer overflow detection among some individuals that work on Rust but despite that, here we are without that feature. Swift, on the other hand, is one language that has put some thought to the matter. 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.
  - SamReidHughes 12y ago
    Not to re-relitigate old discussion, but (as I'm sure you know) it's now more probable that you might overflow your integers and then pass them to unsafe code or external APIs, and there are many other bugs or undesirable behavior that could be killed dead instead of allowing them to behave badly. For a not contrived example, I don't want weird stuff to happen when my semaphore counter overflows, or underflows, I want it to just crash, right there. (My perspective and desires come from a project where I didn't care about "raw" performance that much -- the project being a storage engine where C++ was chosen with the performance concerns in mind being lack of GC and resultant traffic shockwaves, so my preferences lie a bit away from CPU integer operation performance and more towards crashing obviously at the spot of the foul. It's the worst kind of bug when you hang mysteriously in production or to write garbage to disk when the error could be caught, and I had many C++ integer underflow worries at that job.) 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 :-)
    - leoc 12y ago
      It's that old song. "Our language is safe!—for some very specific, rather convenient definition of 'safe' which we just picked ourselves."
- derefr 12y ago
  It seems to me that, despite all the flexibility people demand, they only really want (and use) exactly three integer data-types in a language: 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?
  - SamReidHughes 12y ago
    I don't want 3, because I don't want tag bits or space wastage, but also because I don't want to have to link a bigint library.
- lifthrasiir 12y ago
  Asides from pcwalton's argument, I think any successful (or to-be-successful) language is trying to solve some problems very well and other problems reasonably well. For Rust, the former includes the memory safety and the latter includes the integer overflow detection (but you can always name a lot more). It would be very hard to solve all problems at once (especially when known solutions to some problems worsen other problems, as seen in Rust). That can be said to Swift as well, it just picked different problems to solve very well.
  - SamReidHughes 12y ago
    I don't think it's hard to solve the problem of memory safety and integer overflow detection at the same time.
    - lifthrasiir 12y ago
      Both problems are undergoing active research. They are indeed orthogonal (albeit one can somehow reduce the severity of another and vice versa), but with a finite resource and time you sometimes have to choose.
- raverbashing 12y ago
  What is missing is a good and easy way of doing the check: - 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)

olliej 12y ago

I'd be curious about the effect of manually substituting the clang overflow arithmetic intrinsics on the codegen.

TazeTSchnitzel 12y ago
I suspect that'd make it worse, as you've added a new inline call.

pbsd 12y ago

GCC 4.9 does have `-fsanitize=signed-integer-overflow`, and it generates pretty good code for that toy function: f(int, int): mov eax, edi add eax, esi jo .L8 ret .L8: ...

Marat_Dukhan 12y ago
Older gcc versions have `-ftrapv` option, which checks overflow for signed addition, subtraction, and multiplication. However, the implementation calls libgcc functions to do the checks, resulting in non-negligible overhead.

sanxiyn 12y ago

I hope optimiztion of integer overflow checking improves in LLVM, since now there is a highly visible project(JavaScriptCore FTL JIT) using the feature. JavaScript semantics pretty much forces you to do integer overflow checking fast.

TazeTSchnitzel 12y ago
You're referring to the optimisation of storing JS Numbers as integers until they get too large, presumably?
- sanxiyn 12y ago
  Yes.
  - TazeTSchnitzel 12y ago
    Native integer overflow checks can only go so far, there, since there's no 52-bit integer type.
    - sanxiyn 12y ago
      What? JavaScript engines check for 32-bit integer overflow and promote to double.
      - kevingadd 12y ago
        IIRC v8 promotes to double at 31 bits. But yeah.
        gsnedders 12y ago
        Yeah, V8 is a bit of an odd one out here. Everyone else just promotes once a signed 32-bit int overflows.
        mraleph 12y ago

nkurz 12y ago

I just did my own comparison using bzip2 (http://www.bzip.org/ http://www.bzip.org/), comparing both CLang 3.4 and GCC 4.9 with -O3 -fsanitize=signed-integer-overflow. I omitted the 'unsigned-integer-overflow' because my version of GCC didn't support it. ICC is shown for the non-sanitized version, as it doesn't support it the automatic overflow checking. 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 For Clang, adding signed integer overflow checking adds about 20% to the count of instructions executed, but only about 7% to the runtime. For GCC, 10% more instructions but also about 7% increase in execution time. Agreeing with this, the instructions per cycle ratio goes up more for CLang than for GCC, but in both cases there is a significant increase showing that each check costs less than a cycle. 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.

Animats 12y ago

Ah yes, integer overflow checking. Here's iDrive, the commercial backup service, failing at it: http://s24.postimg.org/xakc6eglx/idrivefail2.png 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) which can be easily optimized to eliminate the divide. Otherwise, it should be an error.

TazeTSchnitzel 12y ago
More portable: x += n % (1 << (SIZEOF_LONG * CHAR_BIT));
- jevinskie 12y ago
  Perhaps the C++ standard could add 'operator{+,-,etc}%'.
  - TazeTSchnitzel 12y ago
    Along the lines of Swift's & operators?
    - jevinskie 12y ago
      Yes, those seem quite nice! Edit: https://developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/AdvancedOperators.html https://developer.apple.com/library/ios/documentation/Swift/...
- Animats 12y ago
  If the program wants 32-bit unsigned modular arithmetic, that's what you should get, regardless of the underlying machine architecture. If you code that, you're probably doing a checksum, and you want the answer to be consistent across platforms.

dezgeg 12y ago

I wonder if these estimations of integer overflow cost have taken into account all the possible optimizations where the compiler could safely remove overflow checks. For example, consider: void memzero_range(char* array, int start, int end) { for(int i = start; i < end; i++) array[i] = 0; } In that example, a sufficiently smart compiler could just check for the `start > end` case once at the start of the loop, and remove the overflow check from the body. Perhaps this is something that today's Clang/GCC can already do?

gsnedders 12y ago
Rewriting it as follows, with an overflow check: 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++; } } Clang does indeed manage to see that the check is equivalent to a start > end case (with -O1) and hoists it out of the loop. It also then rewrites the body of the loop to use the LLVM memset intrinsic!

pslam 12y ago

It's not that unreasonable to ask for hardware support for overflow checking. There's various ways it can be supported which make it much cheaper than naive methods. 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.

Tuna-Fish 12y ago
> ARM has a sticky overflow flag "Q". 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.
- anewhnaccount 12y ago
  I'm pretty rusty so excuse me if I'm spouting nonsense, but I think MRS (read register file) has a dependency on the value of Q (so q/add/sub/clear) and operations which OR a new value with Q (q/add/sub [do q |= 0 or q |= 1) have a dependency on operations which change the register file (MSR). Basically qadd and qusb commute on Q. I'm a bit fuzzy on the details, but I think this means that you just have to stall/predict when there's about to be a branch anyway. Please correct me/clarify if I'm wrong.

asgard1024 12y ago

I wonder why not use interrupts for overflow checking? (Maybe x86 still doesn't support that - my knowledge of it is very old.) That seems smarter, if the overflow is really going to be an exceptional case.. 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.

gsnedders 12y ago
x86 doesn't support it.
- asgard1024 12y ago
  Ah well. I work on zSeries mainframes, and this architecture does support interrupts on integer overflows (as well as many other number formats). So I thought that x86 architecture already got that option too.

dgdsgdsg 12y ago

fefe?

co1987 12y ago

Summing up, integer overflow checks ought to cost something like 5% on typical integer-heavy workloads, but poor optimization can easily make the cost 2x to 6x what an optimal compiler would produce.

lelf 12y ago

Honestly we should talk about “The Security Cost of No Overflow Checking” first.

sp332 12y ago
Yes! You can make code that runs as fast as you want if it doesn't have to actually work.
Rusky 12y ago
It's good to talk about, but not every article on performance needs to be prefaced with a talk about security. Being aware of the performance costs of your tools is just as important in many cases. 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.

niche 12y ago

This calls for BaseN computing; an algorithm that compiles code down to the most optimal base (minimizing overflow) and then ran it on a quantum baseN computer; post compilation basing; cross basing; etc

phkahler 12y ago

It is the programmers job to check for overflow. There are a lot of comments here about having a language check for overflow, but that is not practical. Specifically, the language doesn't know what to do in the case of overflow. The best it could possibly do is throw an exception, and I suppose that's what those commenters want it to do. But it's still up to the programmer to decide what to do and implement something. Are you going to do that for every math operation in a program? If not then you're already thinking about where potential problems may occur. Sometimes you want an overflow. I like to use 16 bit values to represent angles from 0 to 360 degrees - you can add and subtract these and never need to worry about the wraparound - I don't want that to throw an exception. If your code is going to overflow when you don't expect it to, you've got a bug and the language isn't going to be able to save you. 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.

aidenn0 12y ago
Spot the signed integer overflow here that leads to undefined behavior on targets where "int" is 32-bits: uint32_t leToWord(uint8_t bytes) { return bytes[0] | bytes[1] << 8 | bytes[2] << 16 | bytes[3] << 24; }
- detrino 12y ago
  This is more about C's integer promotion rules than it is about overflow.