Is there any performance penalty to unsigned integer underflow?

Question

Is there any performance penalty to unsigned integer underflow?

Suppose I have a computation subtracting two unsigned integers (so underflow can happen if b > a), but still gives the correct result for my application logic because I want it to wrap anyway:

// Note: a and b are uint32_t
uint32_t c = (a - b) & mask; // mask is doing the equivalent of modulo

Performance-wise, is it better to intentionally let the underflow happen, or am I better off taking measures to avoid underflow, such having an if statement to handle the case b > a differently?

Answer 1

You didn't specify the processor or the compiler you are using.

On any of the x86 family and any compiler I'm aware of, the answer would be that overflow has no impact on performance whatsoever. This is probably true for other processors as well.

If you want to be sure, look at the assembly code that is produced (-S in clang or gcc, make sure there is a -g or -ggdb3 so it includes the source code line numbers), and you will probably find it translates to something like (produced with gcc on x86-64):

    subl    %esi, %edi
    andl    %edx, %edi

If you do the same thing with signed,

    subl    %esi, %edi
    andl    %edx, %edi

So there is no difference, and if you want to be complete about it, look up the instruction timing for your processor (https://www.agner.org/optimize/instruction_tables.pdf is great for this for x86) to check that there is no timing penalty for setting the overflow carry flag (I've never seen a processor for which this is the case). Under the hood, the difference between signed and unsigned usually only matters when doing something like inequality, multiplication, division or converting to and from strings.

Adding in a specific test will either make it slower, or the compiler will optimize the test out if it sees that both sides do the same thing.

Having said that, you risk running into undefined behavior when you try this sort of thing (even if this particular case is not undefined) and should at the very least add a comment about what you are doing so this doesn't trip you up later.

Answer 2

No performance penalty

Generally the overflow / underflow (carry flag) is automatically set and does not have a performance penalty.

Avoid branching code

You suggest "having an if statement to handle the case b > a differently?"

That would introduce a performance penalty. CPUs look ahead and load instructions ahead of the current program counter (address) so that instructions can be processed optimally. Branches have two paths, and thus the CPU must guess which path will be taken. If the guess is incorrect then the CPU must wind back the cached instructions. This is a significant performance penalty.

Fast code avoids branching when it can.

Use addition?

Using a modulo you don't need to subtract, you can add. Example the same calculation using subtraction and addition.

10 - 2 & 0xFF == 8

10 + 254 & 0xFF == 8; // no overflow

Using unsigned 32bit int and mask has all bits from top most to bottom set, eg 0x1ff == 511. The following lines are equivalent .

c = (a - b) & mask;

c = a - b & mask; // - has precedence over bitwise And &

c = a + mask + 1 - b & mask;

This may be a better option if calculating mask + 1 - b is trivial or if b is a constant value (meaning mask + 1 - b is constant as well).

Trust the compiler and just use c = a - b & mask;

Answer 3

Unsigned integer overflow (and underflow) shouldn't have any noticeable impact on performance.

On top of that, based on Wikipedia - Integer Overflow, unsigned integer overflow is defined to wrap around, but signed integer overflow is undefined behaviour. It mentions C but the same should be true for C++:

In C, unsigned integer overflow is defined to wrap around, while signed integer overflow causes undefined behavior.

When you're asking about performance, it starts to sound like Premature Optimisation. My advice would be, don't focus on micro-optimising every line of code, but when your project starts using more performance than you want it to, profile it and focus on the areas that use the most performance.

Should you depend on unsigned integer overflow behaviour?

Part of me feels like it might be a better idea not to. The code might be harder to read if a new person is looking at it. There's also the human error element, if your code depends too much into unsigned integer overflow, someone might accidentally decide to switch to signed integer, which will cause undefined behaviour in your project.

Answer 4

Is there any performance penalty to unsigned integer underflow?

No.

There is no cost to the wrapping (modulo) behavior of arithmetic with unsigned integral types. Processors use same instructions for integer subtraction regardless of whether the values are considered signed or unsigned. So there's no performance difference of that subtraction based on the signedness of the operands.

(For some bitshift operations, different instructions are used for signed and unsigned types, but I'd be surprised if they ran at different speeds.)

Both C and C++ agree that unsigned integer arithmetic is well-defined for overflow and underflow. When the programmer chooses to use unsigned integral types for the operands, they are choosing the wraparound behavior. Neither the processor nor the compiler has to do any extra work to produce the correct result.

With signed integers, however, the C and C++ standards say the behavior of subtraction is undefined if an underflow occurs (even though we know what the processor will do!). Declaring it undefined frees the compiler to apply certain optimizations and/or to help catch bugs.

At first glance, the expression x - 42 < x (where x and 42 are signed integral types) seems like it should always be true. But it's not because x - 42 will underflow for certain values of x. Maybe the programmer knows it'll never happen because x will always be larger than 42. Or maybe they forgot to consider the possibility of underflow.

If the standard defined what the program's behavior must be in that case, the compiler would have to generate the instructions to do the subtraction and the comparison and possibly more to get the behavior aligned with what the standard required. And since the programmer's intent is unclear, what behavior should the standard require here?

Instead, the standard leaves it undefined. Any program where that subtraction can underflow is invalid. The compiler doesn't have any obligation to invalid programs, so it can assume that the underflow will never ever happen. And thus it can optimize away the entire expression.

Being able to detect whether an operation would over- or underflow could be useful. (Ironically, it's tricky to do correctly without over- or underflowing.) And a correct test could be costly in terms of performance.

It might be relatively inexpensive to have the compiler, when targeting certain processors, insert instructions to test for overflow and underflow immediately after it occurs. (Remember, the behavior is well-defined for the processor, just not the language.) Thus the compiler could make your code trap when the problem occurs. Like dereferencing an invalid pointer, a crash is likely better than the program proceeding in a bad state. I believe clang's undefined behavior sanitizer (UBSan) does that.

Answer 5

While the CPU can deal with undeflow without any performance hit, there are some cases where the undefined behaviour of signed integer underflow/overflow can actually help the compiler optimize code.

This probably isn't the case for the code mentioned above, but it can have an influence in some cases. This is discussed in some detail at: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion.