3
\$\begingroup\$

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?

\$\endgroup\$
5
  • 3
    \$\begingroup\$ why do you care? \$\endgroup\$
    – Raildex
    Feb 22 at 12:00
  • 2
    \$\begingroup\$ This sounds like something you could answer definitively by profiling. \$\endgroup\$
    – DMGregory
    Feb 22 at 12:37
  • 4
    \$\begingroup\$ @Raildex, because I don't want to just randomly do one thing or another. I want to understand the implications. \$\endgroup\$ Feb 22 at 13:38
  • 8
    \$\begingroup\$ While this isn't an automatic "not on-topic for GDSE" vote from me, I recommend asking the mods to migrate it to Stack Overflow where it would benefit from a significantly larger C++ audience. Regardless of whether it stays here or gets moved, I also recommend specifying which version(s) of C++ you are interested in. \$\endgroup\$
    – Pikalek
    Feb 22 at 15:14
  • \$\begingroup\$ The existing answers are accurate, but there are definitely cases where you should not prefer using unsigned math if it's not necessary: youtu.be/yG1OZ69H_-o?t=2357. There's a lot going on under the scenes with the optimizer you're interacting with so until you're ready to start heavily profiling, just prefer to write code simply \$\endgroup\$
    – Steve Cox
    Feb 23 at 14:29

5 Answers 5

11
\$\begingroup\$

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.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ The alternative that I came up with to avoid test and branch would be to write uint32_t c = ((a + 1) + (mask - b)) & mask; // same result but no underflow and no branching But just using uint32_t c = (a - b) & mask; is even better if there's no overhead to underflow. Thanks for confirming that. I think I will just write a comment saying that underflow is OK and intentional for this usecase. \$\endgroup\$ Feb 23 at 12:17
  • 2
    \$\begingroup\$ @QwertYuiop Definitely add that comment. Underflow/overflow is almost always undesirable, so you should always be clearly indicating that it is intended in cases where you want it to happen (and possibly also comment next to the variable definition indicating that it needs to be unsigned because you intend for specific underflow/overflow semantics). \$\endgroup\$ Feb 23 at 14:55
  • 2
    \$\begingroup\$ Yes, this is true for all CPUs. Binary subtraction is a single instruction in normal ISAs whose performance isn't data-dependent. It can produce a carry (borrow) output which might be 0 or 1, but that doesn't take extra time. On some RISCs like PowerPC or ARM / AArch64, updating the status register is optional on a per-instruction basis, like ARM sub vs. subs, but those have the same performance. (Except maybe on in-order CPUs if that creates a hazard with multiple instructions trying to write flags in the same cycle? Mostly it's useful to preserve a condition-code result for later.) \$\endgroup\$ Feb 23 at 20:18
  • \$\begingroup\$ @PeterCordes That's one case I didn't consider - the writing of a flag may mess with an optimization elsewhere. That is an unlikely case so I'm not going to edit into my answer, and putting in an 'if' statement certainly isn't going to help. \$\endgroup\$
    – MadMan
    Feb 23 at 22:56
  • 1
    \$\begingroup\$ @MadMan That was well in the past. Now, compilers aggressively assume undefined behaviour is unreachable because it helps them make code faster. \$\endgroup\$ Feb 24 at 20:13
7
\$\begingroup\$

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;

\$\endgroup\$
3
  • \$\begingroup\$ I would in fact claim that the addition version also makes for clearer code. (a + b) % m is a very common pattern and it's obvious that it means "wrap around when the addition result exceeds m". By contrast, (a - b) % m would give me a bit of a pause regarding what the modulo (or mask) actually accomplishes. \$\endgroup\$ Feb 23 at 8:57
  • 1
    \$\begingroup\$ One problem with your first example: == takes precedence over &. When in doubt, always place brackets around bitwise operations. \$\endgroup\$ Feb 23 at 12:06
  • \$\begingroup\$ @QwertYuiop Yes thanks for pointing that out, the == (of the two statements) was an after thought as leaving a = just looked wrong (ill formed expressions). The two lines should be read as pseudo code \$\endgroup\$
    – Blindman67
    Feb 24 at 20:53
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The implication of signed integer overflow being undefined behavior, is that the compiler can assume it doesn't happen and optimize accordingly (can make certain loops faster by eliminating branches that never happen). With unsigned, it does have to take into account the possibility. But what I'm wondering is whether the overflow/underflow itself has any kind of overhead. For example does overflow/underflow do branching under the hood? A trivial implementation of uint32_t c = a - b; with underflow is uint32_t c = (b > a) ? (a + 1) + (uint32_max - b) : a - b; \$\endgroup\$ Feb 22 at 14:06
  • \$\begingroup\$ @QwertYuiop It shouldn't have a noticeable impact on performance. If your project is having performance issues, try profiling it and focus on the parts that eat the most performance. I've never seen integer math cause any noticeable dent, especially compared to loading and displaying 3D meshes and Textures. \$\endgroup\$ Feb 22 at 14:17
1
\$\begingroup\$

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.

\$\endgroup\$
1
0
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Note that this question is about unsigned integers. While the behaviour of compilers on signed integers is indeed interesting, it's not an answer to this specific question. \$\endgroup\$
    – DMGregory
    Feb 24 at 13:17
  • \$\begingroup\$ @DMGregory: If unsigned overflow weren't defined as precise wrapping, the same kinds of optimizations would have been usable with unsigned values. The specified wraparound behavior of unsigned types makes a conditional expression like it (uint1+uint2> uint1) slower to evaluate than it would be if compilers could arbitrarily extend integer ranges, since that would allow the code to be simplified to if (uint2). \$\endgroup\$
    – supercat
    Feb 24 at 18:18
  • \$\begingroup\$ That is also not the case being described in the question. If you can demonstrate an optimization relevant to the case that was asked about, please edit your answer to describe that specific case. \$\endgroup\$
    – DMGregory
    Feb 24 at 19:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .