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?

Answer 3

If you're reading TPOP, you will next see how they make this search many times faster with different data structures and algorithms.

But you can make things a bit faster by replacing things like

for (i = 0; i < n; ++i)
    foo(a[i]);

with

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

If there is a known value at the end of the array (e.g. NULL) you can eliminate the loop counter:

for (p = a; *p != NULL; ++p)
    foo(*p)

Good luck, that's a great book!

Answer 4

There is well-known technique as sentinal method. To use sentinal method, you must know about the length of "array[]". You can remove "array[i] != NULL" comparing by using sentinal.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

Answer 5

To optimize that code the best bet would be to rewrite the strcmp routine since you are only checking for equality and don't need to evaluate the entire word.

Other than that you can't do much else. You can't sort as it appears you are looking for text within a larger text. Binary search won't work either since the text is unlikely to be sorted.

My 2p (C-psuedocode):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

Answer 6

Realistically, setting i to be a register variable won't do anything that the compiler wouldn't do already.

If you are willing to spend some time upfront preprocessing the reference array, you should google "The World's Fastest Scrabble Program" and implement that. Spoiler: it's a DAG optimized for character lookups.

MSN

Answer 7

Mark Harrison: Your for loop will never terminate! (++p is indented, but is not actually within the for :-)

Also, switching between pointers and indexing will generally have no effect on performance, nor will adding register keywords (as mat already mentions) -- the compiler is smart enough to apply these transformations where appropriate, and if you tell it enough about your cpu arch, it will do a better job of these than manual psuedo-micro-optimizations.

Answer 8

A faster way to match strings would be to store them Pascal style. If you don't need more than 255 characters per string, store them roughly like this, with the count in the first byte:

char s[] = "\x05Hello";

Then you can do:

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

And to get really fast, add memory prefetch hints for string start + 64, + 128 and the start of the next string. But that's just crazy. :-)

Answer 9

Another fast way to do it is to get your compiler to use a SSE2 optimized memcmp. Use fixed-length char arrays and align so the string starts on a 64-byte alignment. Then I believe you can get the good memcmp functions if you pass const char match[64] instead of const char *match into the function, or strncpy match into a 64,128,256,whatever byte array.

Thinking a bit more about this, these SSE2 match functions might be part of packages like Intel's and AMD's accelerator libraries. Check them out.