Optimizing a search algorithm in C

Question

Can the performance of this sequential search algorithm (taken from The Practice of Programming) be improved using any of C's native utilities, e.g. if I set the i variable to be a register variable ?

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

Answer 1

Yes, but only very slightly. A much bigger performance improvement can be achieved by using better algorithms (for example keeping the list sorted and doing a binary search).

In general optimizing a given algorithm only gets you so far. Choosing a better algorithm (even if it's not completely optimized) can give you a considerable (order of magnitude) performance improvement.

Answer 2

I think, it will not make much of a difference. The compiler will already optimize it in that direction.

Besides, the variable i does not have much impact, word stays constant throughout the function and the rest is too large to fit in any register. It is only a matter how large the cache is and if the whole array might fit in there.

String comparisons are rather expensive computationally.

Can you perhaps use some kind of hashing for the array before searching?