6

Why does this loop (to 1 billion) only take a few sounds to execute ...

for (i = 0; i < 1000000000; i++)
{

}

... but this loop (to 10 billion) takes >10 minutes?

for (i = 0; i < 10000000000; i++)
{

}

Shouldn't it just take 30 seconds or so (3 seconds x 10)?

  • 2
    Consider potential overflows, maybe your `i` is a 32-bit integer? So you may not be doing the same number of iterations than you expect. – Artefact2 Nov 12 '11 at 22:52
  • 1
    What is the type of i? Are you targeting 64-bit? – Richard Berg Nov 12 '11 at 22:53
  • It's probably just stuck in an infinite loop. Assuming `i` is a 32-bit integer, it's never going to exceed 10 billion. – Mysticial Nov 12 '11 at 22:54
  • 2
    If type of i is not large enough (i < 10000000000) should never evaluate to TRUE, so it would be an infinitive loop. But he stated that loop had finished. EDIT: Actually he did not state it explicity whether loop has or has not ended. If it truly has not than the answer is clear and he/she should use long int. – MOleYArd Nov 12 '11 at 22:56
  • 2
    @MOleYArd I'd rather guess he waited 10 minutes and killed it (which is also hinted at by the `>`). – Christian Rau Nov 12 '11 at 23:01
  • Although the solution is quite obvious, the details are indeed a bit confusing to me. I asked a [follow-up question](http://stackoverflow.com/q/8108642/743214) about the specific reasons for this behaviour. – Christian Rau Nov 13 '11 at 00:27

4 Answers4

13

I guess i is a 32-bit integer variable and is therefore always smaller than 10 billion (which is more than 2^32), whereas 1 billion still fits into the 32-bit range (which ends at about 2 or 4 billion, depending on signedness). Though I don't know how the compiler promotes this 10 billion constant, but he seems to realize the overflow issue and makes it an infite loop.

What happens when you make i a long long int (and maybe the 10000000000 a 10000000000L, but that seems to be no problem)?

Christian Rau
  • 45,360
  • 10
  • 108
  • 185
  • 1
    Switching `i` to a `long long` and switching `10000000000` to `10000000000L` worked. Thanks. –  Nov 12 '11 at 23:12
  • Yes, it executed in 29 seconds. Thanks again. –  Nov 12 '11 at 23:15
  • 1
    That's because signed overflow in C is undefined behavior, so the compiler is allowed to do anything. In this case it chooses to [loop infinitely](http://stackoverflow.com/questions/7682477/why-does-integer-overflow-on-x86-with-gcc-cause-an-infinite-loop) because it assumes that the value never overflows, which is allowed – phuclv Jan 26 '15 at 16:16
3

I would guess that you're not putting the code you've benchmarked here. The code as is might get optimized by the compiler to not run at all. It also may be that i overflows and then your loop will never end.

However, if you use i as index to a data structure (especially if its an array), then you have the memory paging and data caching which affects the performance greatly.

littleadv
  • 20,100
  • 2
  • 36
  • 50
  • 2
    does it **end** ? Or you waited for 10 minutes and just shut down the program? – littleadv Nov 12 '11 at 22:58
  • 1
    @nbsp then its most likely an infinite loop because of the overflow. I'm surprised you didn't get a compilation warning on this. – littleadv Nov 12 '11 at 23:13
2

The difference is that 1,000,000,000 fits into a 32 bit integer while 10,000,000,000 is 64 bit. If it's a 32 bit, which I'm going to assume that it is, it is just overflowing and will result in your loop becoming infinite.

Is your i a 64 bit variable?

Nick Savage
  • 856
  • 1
  • 7
  • 18
0

If this helps to anybody:

When a 32 bit signed number exceds its range 2^31 - 1 the number is interpreted as a negative number (due to the 2C format). I.E:

For a 16 bit number:

  0111 1111 1111 1111 (32767)
+ 0000 0000 0000 0001 (1)
---------------------
  1000 0000 0000 0000  (Shoulbe 32769 but instead is -32768)
+ 0000 0000 0000 0001
--------------------
  1000 0000 0000 0001 (-32767)....

So the infinite loop is because you are just going through all the possible values for an 32 bit signed int.

Julio Vga
  • 143
  • 1
  • 7