On my recent question on twitter I asked how this piece of code would behave in case of built-in arithmetic types (which I inaccurately referred to as basic numeric types):

template<typename T> T f() {
    T t{};
    while (t < t+1) {
        t++;
    }
    return t;
}

The question is more complex than it seems.

For the sake of this discussion, I’ll also consider a slightly modified version of the same code:

template<typename T> int f() {
    T t{};
    while (t < t+1) {
        t++;
    }
    return 1;
}

I’ll call the first version v1, and the second v2.

First of all, the “obvious” case: for unsigned integral types, the standard mandates “Unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer”. Under these laws, for unsigned int(*) the increment of a variable t whose value is 2n – 1 will give 0. The loop will terminate, and the result is std::numeric_limits<unsigned int>::max(). So, we can exclude the cases “Loop never terminates” and “Nobody knows” because there’s at least one case when somebody knows that the loop terminates.

What happens with unsigned short and unsigned char? Well, it’s complicated. They can be promoted to either int or unsigned int, they’re converted to the firsto one capable of containing the whole range. In practice, the conversion to unsigned int only happens if the size of unsigned char and/or unsigned short is exactly the same of unsigned int: in this case we go back to the previous case of unsigned int. In the other cases (which are all normal platform), our loop ends up being always infinite because our value is always smaller than its int-promoted-and-incremented version.

For signed integral types, I wasn’t able to pinpoint the exact wording in the standard, but it’s well known that overflow is Undefined. The options for int(*) are two:

  1. The compiler makes no assumption, generates the code, and get caught by surprise if at a certain point t < t+1 evaluates to false, terminating the loop. Our result will be again std::numeric_limits<T>::max().
  2. The compiler wants to be smart and assume that the condition t < t+1 always evaluates to true, and thus generates an infinite loop. But infinite loops are also Undefined Behaviour as well, and in theory the compiler is allowed to assume that the loop will terminate. In this case, in v1 it won’t be able to decide at compile time a value for t, while in v2 it could assume a return 1. In practice, I found no compiler optimizing v2 to a simple return 1;, but if you can try yourself hereUPDATE (2018/02/19 14:56): Furkas noted that ICC does optimize that (see comments). Oddly, I found out that version 16, 17 and 18 optimize it correctly, but version 13 completely ignores the +5 that he added after the return.

So, for int() the termination is really Undefined. For small ints, we fall in the same case in the degenerate case when they are equivalent (as happened in the unsigned case), or we end up with an infinite loop for proper smaller ints, those where sizeof(T) < sizeof(int).()

But there’s more!

What about floating point? Well, in such case the result isn’t defined (termination), and isn’t undefined: it’s Implementation Defined.

First let’s consider an IEEE-754 compliant implementation (those where std::numeric_limits<T>::is_iec559 == true), even here we have two different possible behaviors:

If std::numeric_limits<T>::round_style is round_toward_zero or round_toward_neg_infinity the result is well defined: it will terminate at 224 for binary32 (on most implementation float) and 254 for binary64 (on most implementation double), and istd::numeric_limits<T>::round_style is round_to_nearest the result is probably going to be the same (it is, on the processor I was able to test). Those numbers are the first values where rounding error becomes ±1 (so, a simple increment can’t be represented and must be rounded).

If std::numeric_limits<T>::round_style is round_toward_infinity, the result is going to be std::numeric_limits<T>::infinity(): I wasn’t able to test it anywhere, but my assumption is that when t reaches infinity, the expression t < t+1 becomes infinity < infinity + 1, which in turn becomes infinity < infinity, which is false by definition in IEEE-754.

For non-IEEE-754 floating point numbers, with round_toward_infinity and a different infinity rules (one where infinity < infinity equals true, maybe),  the loop will be infinite.

And now for something completely different, non-arithmetic types!

First, there’s the strange case of dr. bool: this is only valid until C++14, and the result is even more counterintuitive than before, because t+1 and t++ are actually very different beasts:

  • the expression t++ is (was, until C++14) by definition equivalent to the statement t = true
  • the expression t+1 is of type int, and is obtained by casting the bool t to int, and then adding 1.

Possible values of this expression t+1 == 1 when t is false, and t+1 == 2 when t = true, thus t < t+1 becomes a bool-to-int comparison, and is equivalent to (int)t < t+1, so it’s 0 < 1 when t is false and 1 < 2 when t is true, thus the condition is always true, and the loop is infinite.

Finally, pointers! In this last case, we’re in the open sea of UB, first of all because we start with a null pointer and try to increment it: this itself is NOT UB, because we’re not dereferencing (turns out that’s also UB, see this reddit post), butand we’re not pointing to an array (by definition the comparison between two pointers make sense only if they point inside the same array, or struct), so the comparison result is UB. Even if we change the code to find a sensible initialization (e.g. at the beginning of an array), it’s just a matter of time: array are finite, and at a certain point in time the variable t will point after the last element of the array, and from the next iteration it will start sailing toward infinity (eventually wrapping around the end of the world, and proving that the earth is round and not flat).

  • UDPATE (2018/02/22 00:54 CET): The discussion of smaller ints has been updated after vrt3’s comment.

  • UDPATE (2022/02/20 14:14 CET): Updated reflecting a comment about incrementing a null pointer.

4 Comments

  1. Furkan

    You are saying that no compiler optimized V2, but it looks to me that ICC is optimizing away the function call: https://godbolt.org/g/CUF6Dq

    Reply
    • Marco Foco

      Oh, nice catch, thank you! Fixing…

      Reply
  2. vrt3

    You don’t always get a result even for small unsigned integral types: t < t + 1 will always be true because of integer promotion. Example: if T is unsigned char and t is 255, t + 1 is the int 256 and not the unsigned char 0, resulting in an infinite loop.

    You can fix it by rewriting the condition as t < T(t + 1).

    Reply
    • Marco Foco

      Ahahah, good catch too! I’ll add that and some considerations on what’s happening to the original code and some other variations to mitigate the problem.
      I’m not sure I’ll be able to do it tonight, but I’ll try… It might actually deserve a new post :)
      Thank you!

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.