Which is faster?

[chomper]

Hi,

which code executes faster:

Example 1:

counter = (counter + len) % BUFSIZE;

Example 2:

if ( (counter = (counter + len)) >= BUFSIZE )
{
counter -= BUFSIZE;
}

[firedraco]

They don't do the same thing.

[chomper]

They do. Test it. :-)

[S6k9GNh0]

Example 1 is (counter + len) % BUFSIZE.
Example 2 is (counter + len) - BUFSIZE.

How is this the same?

[Duthomhas]

For any (counter + len) >= BUFSIZE example 1 is faster.
Otherwise they are the same speed.

Of course, there might be some small variations based upon your CPU's division opcode's clock count... but unless you are doing something really time critical, you can discount that...

Example two should read

counter += len;
while (counter >= BUFSIZE)
{
  counter -= BUFSIZE;
}

[kempofighter]

I would think that the question could have been answered by looking at the assembly code generated. In the second case isn't there going to be a boolean comparison and a jump instruction?

[Duthomhas]

Choice of assembly or C doesn't matter. But you are exactly correct: the loop works with an additional if. Remember, when counting execution time, you must decompose complex constructs into the simplest statements possible.

Most simply ('loop' version):

counter = counter + len;              // same in both
if (counter < BUFSIZE) goto line 5;   // only in 'loop' version
  counter = counter - BUFSIZE;        // comparable to counter % BUFSIZE
  goto line 2                         // only in 'loop' version

Compared with ('modulus' version):

counter = counter + len;       // same in both
counter = counter % BUFSIZE;   // comparable to counter - BUFSIZE 

So the 'loop' version executes at least one statement not in the 'modulus' version (line 20). In the best case (counter + len < BUFSIZE) then that is all and we are done. The number of statements executed is the same as that of the 'modulus' version.

In the next best case (2*BUFSIZE > counter + len > BUFSIZE) then the number of statements executed for the 'loop' version more than doubles: lines 1, 2, 3, 4, 2.

The execution time gets worse for k in (counter + len > k*BUFSIZE). k is a scalar value, meaning that the execution time for the 'loop' version is linear, or O(n).

The execution time for the 'modulus' version is always exactly two statements, which is constant time, or O(1).

Now, if you are dealing with exceedingly time sensitive code, and the vast majority of invocations are known to be (counter + len < BUFSIZE), then it is possible that the 'loop' version could perform better (for the 'next best case' scenario). But again, this is a processor- and application- specific optimization, which would more likely be coded as:

counter += len;
if (counter < BUFSIZE) goto line 4;
  counter = counter % BUFSIZE;

Hope this helps.