Alex Rivera | Logout

How to optimize a C for loop?

Asked 2009-07-30T07:46:32.120
15

I have a performance issue in a bottleneck section in my code. Basically it's a simple nested loop.

Profiling the issue reveals that the program spends a lot of time just incrementing both of the loop counters (++) and testing for termination (i/j < 8).

Watching the assembly output I see that both counters don't get registers and accessing them costs a lot of cycles. Using the "register" keyword doesn't convince the compiler to actually put them in registers. is there something which can be done to to optimize the counters access time?

Here's the assembly output. The C source is just a simple nested loop with i/j counters.

  2738  0.2479  2459  0.1707   :    1e6c:   jne    1dd1 <process_hooks+0x121>
  1041  0.0942  1120  0.0778   :    1e72:   addl   $0x1,0xffffffd4(%ebp)
  2130  0.1928  2102  0.1459   :    1e76:   cmpl   $0x8,0xffffffd4(%ebp)
  2654  0.2403  2337  0.1622   :    1e7a:   jne    1da0 <process_hooks+0xf0>
  809   0.0732   814  0.0565   :    1e80:   jmp    1ce2 <process_hooks+0x32>

As requested, here's the C code as well. Compiler is gcc btw:

for (byte_index=0; byte_index < MASK_SIZE / NBBY; byte_index++)
{
    if (check_byte(mask,byte_index))
    {
        for (bit_index=0; bit_index < NBBY; bit_index++)
        {
            condition_index = byte_index*NBBY + bit_index;
            if (check_bit(condition_mask,condition_index))
            {
                .
                .
                .
            }
        }
    }
}

Thanks

c optimization
Edit
Report

3 Answers

3

This may seem like a minor point, but instead of using the form: index++ , use ++index;

The rationale is that index++ requires cacheing the current rvalue before incrementing, whereas ++index returns the newly calculated rvalue, which should already be cached, thus saving a reference.

Of course, a good compiler will optimize this out, so that it's probably not an issue.

answered 2009-10-18T17:30:00.467
1

I hope these 2 functions are inlined (check_bit and check_byte) since they are much slower than any register variable might make your loop.

if the compiler doesn't inline them, inline them yourself into the loop.

answered 2009-07-30T09:02:48.223
0

Without seeing what is in the inner loop, there's no point in trying to optimize the loops. It looks like that the code is generated for x86 32bit. If the calculation in the loop needs several register, there is no point for the compiler to hold the loop counter in registers, as it will have to spill them anyway to the stack. Then depending on the instructions used in the inner loop there can be quite some problems with the register allocation. Shifts use the ECX register only as count, multiplication and division have restrictions concerning the registers used, string commands use ESI and EDI as registers, reducing the opportunity for the compiler to hold values in them. And as other have already stated, the call in the middle of the loop does not help either, as the registers have to be saved anyway.

answered 2009-07-30T14:00:56.740

Your Answer