coptimization

Accessing items of an array by index


Suppose I use a item of an array inside a loop, like

INS *in;
for (int i = 0; i < LEN; i++) {
    in = g_ins[i];
    if (strcmp(in->mne, str) == 0)
        return in;
}

If i refer each reference using the index, this is optimized by the compiler to something like above, or it really access each index again and again?

for (int i = 0; i < LEN; i++) {
    if (strcmp(g_ins[i]->mne, str) == 0)
        return g_ins[i];
}

Solution

  • You can try it, if in doubt. For example, put your two pieces of code into functions:

    INS * f1 (INS *g_ins, const char * str)
    {
        for (int i = 0; i < LEN; i++) {
            INS *in = &g_ins[i];
            if (strcmp(in->mne, str) == 0)
                return in;
        }
        return NULL;
    }
    
    INS * f2 (INS *g_ins, const char * str)
    {
        for (int i = 0; i < LEN; i++) {
            if (strcmp(g_ins[i].mne, str) == 0)
                return &g_ins[i];
        }
        return NULL;
    }
    

    and then compile them with -O2 and -S (eg. gcc -std=c99 -O2 -S -Wall code.c -o code.s). -O2 sets the optimisation level and -S tells the compiler to produce the assembler code and stop.

    Then look at the assembler code.

    Even if you dont understand assembler very well, you should be able to get an idea of the relative sizes of the two functions. In the case of your functions, they compile to the same code.