The Performance Cost of Integer Overflow Checking

by nicholasjbs • 12 years ago

166 106 12 years 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/), 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...)

SamReidHughes8• 12 years 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• 12 years 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...

TazeTSchnitzel8• 12 years ago

Huh, Swift actually does overflow checking and traps by default. That's quite refreshing.

pcwalton3• 12 years 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.

derefr5• 12 years 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?

lifthrasiir3• 12 years 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.

raverbashing• 12 years 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• 12 years ago

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

TazeTSchnitzel8• 12 years ago

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

pbsd• 12 years 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• 12 years 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.

sanxiyn3• 12 years 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.

TazeTSchnitzel8• 12 years ago

You're referring to the optimisation of storing JS Numbers as integers until they get too large, presumably?

sanxiyn3• 12 years ago

Yes.

gsg2• 12 years ago

Not to mention Swift.

FTL has already precipitated other interesting changes in LLVM (to support deoptimisation and GC).

nkurz2• 12 years ago

I just did my own comparison using bzip2 (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.

Animats2• 12 years ago

Ah yes, integer overflow checking. Here's iDrive, the commercial backup service, failing at it:

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.

TazeTSchnitzel8• 12 years ago

More portable:

  x += n % (1 << (SIZEOF_LONG * CHAR_BIT));

jevinskie2• 12 years ago

Perhaps the C++ standard could add 'operator{+,-,etc}%'.

Animats2• 12 years 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.

Someone3• 12 years ago

I don't think SIZEOF_LONG is portable C. You would want

     sizeof(long) * CHAR_BIT

instead (while at it, use sizeof(x) instead, ?and abort if sizeof(n) > sizeof(x)?)).

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));

and of course, that computes x+n before doing the modulus, so even that doesn't do modular arithmetic.

I think one would need custom syntax for making modular arithmetic easy in C. I would suggest something like

  x += n (mod 37);

That may make parsing difficult, though, if one allows expressions after the 'mod'. Alternatively, put the 'do modular arithmetic' thing in the type:

  modular(43) int x;
  modular(23) int y;
  int n = x + y; // error?

Summary: this is way harder than it seems. I bet people will find errors in the above that show that conclusively.

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.

dezgeg2• 12 years 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?

gsnedders4• 12 years 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!

pslam3• 12 years 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-Fish2• 12 years 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• 12 years 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.

solarexplorer5• 12 years ago

If you assume that reading (and clearing) the Q bit is infrequent, you can do something much cheaper. Because the bit is sticky, the order in which you set it does not matter. And when you need to read (or to clear) the Q bit, you just block the instruction that wants to read/clear until the OoO core is empty.

lifthrasiir3• 12 years ago

Yes! John Regehr seriously advocates that [1] and I fully agree to him.

[1] http://blog.regehr.org/archives/1154

solarexplorer5• 12 years ago

Yes, AMD should have added it to x64. It isn't exactly new either. The Alpha's integer instructions had a bit in the instruction word that indicated if an overflow should cause a trap or not. IMHO that is the ideal solution.

solarexplorer5• 12 years ago

The sticky overflow bit is useful when you do signal processing with integers. To detect bugs it would be better to have a real exception that indicates which instruction caused the overflow. But to do that you would have to change/extend the instruction set which is rather likely. ARM and AMD missed the change to add this when they migrated to 64bit ISAs.

gsg2• 12 years ago

Itanium style not-a-thing constructs might be interesting for that.

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.

Rusky2• 12 years ago

The Mill CPU also works like that- they have instructions for wrapping, overflow, and saturated add, and the overflow ones generate viral bad values that only trap on store/branch/etc.

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.

WayneS• 12 years ago

A sticky overflow flag would be great... "if properly scheduled"

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.

stephencanon• 12 years ago

Floating-point flags behave in exactly this "sticky" fashion on every mainstream architecture, and processor designers don't have trouble breaking the apparent serial dependency. It's annoying, but it's well-understood, and there are widely-used techniques that address it.

thesz5• 12 years ago

You wouldn't believe the cost of hardware support.

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.

[1] http://en.wikipedia.org/wiki/Carry-lookahead_adder

scott_s2• 12 years ago

How do you feel about John Regehr's suggestion (http://blog.regehr.org/archives/1154) mentioned below? His suggestion sounds reasonable to me because the instructions would optionally trap on overflow. That should avoid the cost (which I have an intuition for) for the common case.

solarexplorer5• 12 years ago

A flag register is indeed an additional dependency and may end up in the critical path. But x86 and ARM already have a flag register. They already pay the cost.

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.

pslam3• 12 years ago

I am not describing constant checking of overflow. The sticky flag is the OR of any overflow flag between the last flag-clear operation and a speculation pivot.

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.

asgard10242• 12 years 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.

gsnedders4• 12 years ago

x86 doesn't support it.

asgard10242• 12 years 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• 12 years ago

fefe?

lelf• 12 years ago

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

sp332• 12 years ago

Yes! You can make code that runs as fast as you want if it doesn't have to actually work.

Rusky2• 12 years 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• 12 years 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• 12 years 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• 12 years 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• 12 years ago

This is more about C's integer promotion rules than it is about overflow.

The Performance Cost of Integer Overflow Checking

Related Stories