While loop execution time

Question

We were having a performance issue in a C# while loop. The loop was super slow doing only one simple math calc. Turns out that parmIn can be a huge number anywhere from 999999999 to MaxInt. We hadn't anticipated the giant value of parmIn. We have fixed our code using a different methodology.

The loop, coded for simplicity below, did one math calc. I am just curious as to what the actual execution time for a single iteration of a while loop containing one simple math calc is?

int v1=0;

while(v1 < parmIn) {
    v1+=parmIn2;
}

Answer 1

Assuming an optimal compiler, it should be one operation to check the while condition, and one operation to do the addition.

Answer 2

It depends on the processor you are using and the calculation it is performing. (For example, even on some modern architectures, an add may take only one clock cycle, but a divide may take many clock cycles. There is a comparison to determine if the loop should continue, which is likely to be around one clock cycle, and then a branch back to the start of the loop, which may take any number of cycles depending on pipeline size and branch prediction)

IMHO the best way to find out more is to put the code you are interested into a very large loop (millions of iterations), time the loop, and divide by the number of iterations - this will give you an idea of how long it takes per iteration of the loop. (on your PC). You can try different operations and learn a bit about how your PC works. I prefer this "hands on" approach (at least to start with) because you can learn so much more from physically trying it than just asking someone else to tell you the answer.

Answer 3

The time, small as it is, to execute just one iteration of the loop shown in your question is ... surprise ... small.

However, it depends on the actual CPU speed and whatnot exactly how small it is.

It should be just a few machine instructions, so not many cycles to pass once through the iteration, but there could be a few cycles to loop back up, especially if branch prediction fails.

In any case, the code as shown either suffers from:

1. Premature optimization (in that you're asking about timing for it)
2. Incorrect assumptions. You can probably get a much faster code if parmIn is big by just calculating how many loop iterations you would have to perform, and do a multiplication. (note again that this might be an incorrect assumption, which is why there is only one sure way to find performance issues, measure measure measure)

What is your real question?

Answer 4

The while loop is couple of instructions and one instruction for the math operation. You're really looking at a minimal execution time for one iteration. it's the sheer number of iterations you're doing that is killing you.

Note that a tight loop like this has implications on other things as well, as it bogs down one CPU and it blocks the UI thread (if it's running on it). Thus, not only it is slow due to the number of operations, it also adds a perceived perf impact due to making the whole machine look unresponsive.

Answer 5

There is something else going on here. The following will complete in ~100ms for me. You say that the parmIn can approach MaxInt. If this is true, and the ParmIn2 is > 1, you're not checking to see if your int + the new int will overflow. If ParmIn >= MaxInt - parmIn2, your loop might never complete as it will roll back over to MinInt and continue.

static void Main(string[] args)
{
    int i = 0;

    int x = int.MaxValue - 50;

    int z = 42;

    System.Diagnostics.Stopwatch st = new System.Diagnostics.Stopwatch();
    st.Start();

    while (i < x)
    {
        i += z;
    }

    st.Stop();

    Console.WriteLine(st.Elapsed.Milliseconds.ToString());
    Console.ReadLine();

}

Answer 6

If you're interested in the actual execution time, why not time it for yourself and find out?

int parmIn = 10 * 1000 * 1000;  // 10 million
int v1=0;

Stopwatch sw = Stopwatch.StartNew();
while(v1 < parmIn) {
    v1+=parmIn2;
}
sw.Stop();

double opsPerSec = (double)parmIn / sw.Elapsed.TotalSeconds;

And, of course, the time for one iteration is 1/opsPerSec.

Answer 7

Whenever someone asks about how fast control structures in any language you know they are trying to optimize the wrong thing. If you find yourself changing all your i++ to ++i or changing all your switch to if...else for speed you are micro-optimizing. And micro optimizations almost never give you the speed you want. Instead, think a bit more about what you are really trying to do and devise a better way to do it.

I'm not sure if the code you posted is really what you intend to do or if it is simply the loop stripped down to what you think is causing the problem. If it is the former then what you are trying to do is find the largest value of a number that is smaller than another number. If this is really what you want then you don't really need a loop:

// assuming v1, parmIn and parmIn2 are integers,
// and you want the largest number (v1) that is
// smaller than parmIn but is a multiple of parmIn2.
// AGAIN, assuming INTEGER MATH:

v1 = (parmIn/parmIn2)*parmIn2;

EDIT: I just realized that the code as originally written gives the smallest number that is a multiple of parmIn2 that is larger than parmIn. So the correct code is:

v1 = ((parmIn/parmIn2)*parmIn2)+parmIn2;

If this is not what you really want then my advise remains the same: think a bit on what you are really trying to do (or ask on Stackoverflow) instead of trying to find out weather while or for is faster. Of course, you won't always find a mathematical solution to the problem. In which case there are other strategies to lower the number of loops taken. Here's one based on your current problem: keep doubling the incrementer until it is too large and then back off until it is just right:

int v1=0;
int incrementer=parmIn2;

// keep doubling the incrementer to
// speed up the loop:
while(v1 < parmIn) {
    v1+=incrementer;
    incrementer=incrementer*2;
}
// now v1 is too big, back off
// and resume normal loop:
v1-=incrementer;
while(v1 < parmIn) {
    v1+=parmIn2;
}

Here's yet another alternative that speeds up the loop:

// First count at 100x speed
while(v1 < parmIn) {
    v1+=parmIn2*100;
}
// back off and count at 50x speed
v1-=parmIn2*100;
while(v1 < parmIn) {
    v1+=parmIn2*50;
}
// back off and count at 10x speed
v1-=parmIn2*50;
while(v1 < parmIn) {
    v1+=parmIn2*10;
}
// back off and count at normal speed
v1-=parmIn2*10;
while(v1 < parmIn) {
    v1+=parmIn2;
}

In my experience, especially with graphics programming where you have millions of pixels or polygons to process, speeding up code usually involve adding even more code which translates to more processor instructions instead of trying to find the fewest instructions possible for the task at hand. The trick is to avoid processing what you don't have to.