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)?

6
  • 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, 2011 at 22:52
  • 1
    What is the type of i? Are you targeting 64-bit? Nov 12, 2011 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, 2011 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, 2011 at 22:56
  • 2
    @MOleYArd I'd rather guess he waited 10 minutes and killed it (which is also hinted at by the >). Nov 12, 2011 at 23:01

4 Answers 4

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)?

3
  • 1
    Switching i to a long long and switching 10000000000 to 10000000000L worked. Thanks.
    – user99874
    Nov 12, 2011 at 23:12
  • Yes, it executed in 29 seconds. Thanks again.
    – user99874
    Nov 12, 2011 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 because it assumes that the value never overflows, which is allowed
    – phuclv
    Jan 26, 2015 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.

2
  • 2
    does it end ? Or you waited for 10 minutes and just shut down the program?
    – littleadv
    Nov 12, 2011 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, 2011 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?

0
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.