74

I have the following code:

#include <iostream>
#include <complex>
using namespace std;

int main() {
    complex<int> delta;
    complex<int> mc[4] = {0};

    for(int di = 0; di < 4; di++, delta = mc[di]) {
        cout << di << endl;
    }

    return 0;
}

I expect it to output "0, 1, 2, 3" and stop, but it outputs an endless series of "0, 1, 2, 3, 4, 5, ....."

It looks like the comparison di<4 doesn't work well and always returns true.

If I just comment out ,delta=mc[di], I get "0, 1, 2, 3" as normal. What's the problem with the innocent assignment?

I am using Ideone.com g++ C++14 with -O2 option.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
eivour
  • 1,678
  • 12
  • 20
  • 5
    I've tried it with g++, and with no optimizations it works fine. With -O3 it gives the behaviour mentioned by the OP. With -O1 it's ok. – Chris Card Sep 10 '15 at 16:05
  • 11
    Sounds like aggressive loop optimization due to undefined behavior like [this case](http://stackoverflow.com/q/24296571/1708801) – Shafik Yaghmour Sep 10 '15 at 16:07
  • Although the code does invoke undefined behavior, the optimization is rather aggressive and as I observe it does not help that gcc can not consistently provide a warning for this optimization. – Shafik Yaghmour Sep 10 '15 at 20:11
  • 2
    @Shafik Yaghmour The reason that GCC does not provide a warning with the `cout << di` is probably that the stream insertion operator for complex passes the address of `di` to some "opaque" code (or that the stream insertion operator for complex is opaque itself - which would surprise me though). And depending on what that "opaque" code does, the behavior of the program could still be well defined. I'm not saying that it would be impossible to provide a warning in this case without too many false positives (or even any false positives). Only that it would be quite hard. – Paul Groke Sep 11 '15 at 01:05
  • @ShafikYaghmour I am using Ideone.com g++ C++14 with -O2 option. (Thanks, I added it in my question.) – eivour Sep 11 '15 at 11:42
  • @ShafikYaghmour I wouldn't get a warning anyway because I was using Ideone and the compilation succeeded. Next time I will find a better editor:) – eivour Sep 11 '15 at 11:50
  • Thanks for the update on the compiler, I was waiting for that information before I updated the tags. – Shafik Yaghmour Sep 11 '15 at 11:53
  • @eivour is there really no way to get warnings from ideone? That is pretty bad. – Shafik Yaghmour Sep 11 '15 at 12:24
  • @eivour refer to my answer below. It has to do with an out of bounds situation when working with arrays. It has nothing to do with the assignment operator nor the stream operator. It has to do with the order that you are performing operations with your current for loop. – Francis Cugler Sep 12 '15 at 06:41
  • @PaulGroke just realizing that gcc with `-fsanitize=undefined` catches this case, so although the warning is not consistent we do have alternate tools to catch this with. – Shafik Yaghmour Sep 13 '15 at 02:37

4 Answers4

109

This is due to undefined behavior, you are accessing the array mc out of bounds on the last iteration of your loop. Some compilers may perform aggressive loop optimization around the assumptions of no undefined behavior. The logic would be similar to the following:

  • Accessing mc out of bounds is undefined behavior
  • Assume no undefined behavior
  • Therefore di < 4 is always true since otherwise mc[di] would invoke undefined behavior

gcc with optimization turned on and using the -fno-aggressive-loop-optimizations flag causes the infinite loop behavior to disappear(see it live). While a live example with optimization but without -fno-aggressive-loop-optimizations exhibits the infinite loop behavior you observe.

A godbolt live example of the code shows the di < 4 check is removed and replaced with and unconditional jmp:

jmp .L6

This is almost identical to the case outlined in GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks. The comments to this article are excellent and well worth the read. It notes that clang caught the case in the article using -fsanitize=undefined which I can not reproduce for this case but gcc using -fsanitize=undefined does (see it live). Probably the most infamous bug around an optimizer making an inference around undefined behavior is the Linux kernel null pointer check removal.

Although this is an aggressive optimizations, it is important to note that as the C++ standard says undefined behavior is:

behavior for which this International Standard imposes no requirements

Which essentially means anything is possible and it notes (emphasis mine):

[...]Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).[...]

In order to get a warning from gcc we need to move the cout outside the loop and then we see the following warning (see it live):

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
     for(di=0; di<4;di++,delta=mc[di]){ }
     ^

which would have likely been sufficient to provide the OP with enough information to figure out what was going on. Inconsistency like this are typical of the types of behavior we can see with undefined behavior. To get a better understanding of why such waring can be inconsitent in the face of undefined behavior Why can't you warn when optimizing based on undefined behavior? is a good read.

Note, -fno-aggressive-loop-optimizations is documented in the gcc 4.8 release notes.

Cœur
  • 37,241
  • 25
  • 195
  • 267
Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
  • 26
    This. Undefined behavior is not (only) about crashes. It's about assumptions, and if you violate the compiler's assumptions (as defined by the language specification) then all bets are off... – Matthieu M. Sep 10 '15 at 19:15
  • @MatthieuM. indeed, we keep coming back to that theme, some of [quotes in my answer here](http://stackoverflow.com/a/31746063/1708801) are relevant as well. – Shafik Yaghmour Sep 10 '15 at 20:45
  • What a fool of me, I didn't notice I was accessing mc[4] ;) I was using Ideone.com, so I wouldn't get a warning anyway. Next time I will use an editor that gives me warnings even when compilation succeeds:) – eivour Sep 11 '15 at 11:32
  • @eivour it can be helpful to provide a link to your online example, in this case I think every time you run an example in ideone it provides a url to that example. I personally prefer to use [Coliru](http://coliru.stacked-crooked.com/) or [Wandbox](http://melpon.org/wandbox/) which both provide a share button. – Shafik Yaghmour Sep 11 '15 at 11:48
  • gcc 4.9.3 still does not produce any warning: `g++ -Waggressive-loop-optimizations -Wall -Wextra -O3 test.cpp` - according to this page the compiler should display a warning: https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html – Peter VARGA Sep 16 '15 at 07:42
  • @AlBundy when we are dealing with undefined behavior such warnings can be inconsistent, I made [this link](http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html) more obvious in my answer and it explains why this is the case. – Shafik Yaghmour Sep 16 '15 at 09:19
  • One of the big advantages of using a compiled language vs. a dynamic one is that the compiler can catch bugs for you, so the decision by the compiler to quietly omit code vs. warning about undefined behaviour is a poor choice. This question is a perfect example of where the compiler could have helped its user, but instead chose to confuse them. – jtchitty Feb 11 '18 at 04:10
  • The fact that the Standard imposes no *requirements* in a particular situation does not imply any judgment about whether quality compilers intended for various platforms and purposes should behave in predictable fashion *anyhow*. Indeed, the authors of the Standard note in the rationale that one of the things that makes C useful for so many purposes is that many implementations do precisely that. – supercat Aug 05 '18 at 20:51
  • That's why we should follow Sean Parent and avoid using raw loops. – Dev Null Aug 22 '18 at 12:01
38

Since you are incrementing di before you use it to index mc, the fourth time through the loop your will be referencing mc[4], which is past the end of your array, which could in turn lead to troublesome behavior.

Logicrat
  • 4,438
  • 16
  • 22
  • Ignore my last comment, that may have been a problem with ideone.com not rerunning my code properly after editing. Another test did work: http://ideone.com/vLtvcy – interjay Sep 10 '15 at 16:11
  • 2
    Using either `di++,delta=mc[di-1]` or `delta=mc[di],di++` also fixes the problem. Looks like Logicrat is correct. – KompjoeFriek Sep 10 '15 at 16:15
  • 2
    Perhaps there's an off-by-one error, and eivour meant `delta=mc[di++]` rather than `delta=mc[++di]`, to use all the `mc` values? – Toby Speight Sep 10 '15 at 16:21
5

You have this:

for(int di=0; di<4; di++, delta=mc[di]) {
  cout<<di<<endl;
}

Try this instead:

for(int di=0; di<4; delta=mc[di++]) {
   cout<<di<<endl;
}

EDIT:

To clarify what is going on Lets Break Down The Iteration Of Your For Loop:

1st iteration: Initially di is set to 0. Comparison check: Is di less than 4? Yes okay proceed. Increment di by 1. Now di = 1. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 2nd element since this indexed value is 1 and not 0. Finally perform the code block/s inside the for loop.

2nd iteration: Now di is set to 1. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 2. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 3rd element since this indexed value is 2. Finally perform the code block/s inside the for loop.

3rd iteration: Now di is set to 2. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 3. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 4th element since this indexed value is 3. Finally perform the code block/s inside the for loop.

4th iteration: Now di is set to 3. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 4. (Can you see where this is going?) Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 5th element since this indexed value is 4. Uh Oh we have a problem; our array size is only 4. Delta now has garbage and this is undefined behavior or corruption. Finally perform the code block/s inside the for loop using "garbage delta".

5th iteration. Now di is set to 4. Comparison check: Is di less than 4? No, break out of loop.

Corruption by exceeding bounds of contiguous memory (array).

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
Francis Cugler
  • 7,788
  • 2
  • 28
  • 59
5

It's because di++ is executed on the last run of the loop.

For example;

int di = 0;
for(; di < 4; di++);
// after the loop di == 4
// (inside the loop we see 0,1,2,3)
// (inside the for statement, after di++, we see 1,2,3,4)

You are accessing mc[] when di == 4, so it's an out of bounds problem, potentially destroying part of the stack and corrupting variable di.

a solution would be:

for(int di = 0; di < 4; di++) {
    cout << di << endl;
    delta = mc[di];
}
PaulHK
  • 269
  • 1
  • 9