Optimization for C isMigrated function

Question

char* Migrated[]={"026","109"};

int isMigrated(char* codeB)
{   
    int i;
    int n=sizeof(Migrated)/sizeof(*Migrated);

    for(i=0;i<n;i++)
    {   
        if(strcmp(Migrated[i],codeB)==0)
            return 0;
    }
    return -1;
}

is this function optimised from execution time perspective ?

Migrated should contain at maximum 200 value all of them are 4 byte .

Answer 1

I am not sure how far you intend to expand Migrated, but something like this could be an optimisation:

char* Migrated[]={"026","109"};

int isMigrated(char* codeB)
{   
    int i;
    // since we know that all strings in Migrated are 4 bytes long
    int32_t _codeB_as_int32 = *(int32_t *)codeB; 
    int32_t * Migrated_as_int32 = Migrated;

    for(i=0;
        i<sizeof(Migrated)/sizeof(*Migrated); // sizeof is a compile time constant, better to put it here
        i++)
    {   
        if(codeB == Migrated_as_int32[i])
            return 0;
    }
    return -1;
}

it all really depends on what you intend to have in Migrated.

Answer 2

You could assert that any code has to come from the Migrated array and thus only compare the addresses, i.e. omit the strcmp call and just test for Migrated[i] == codeB.

Answer 3

If Migrated is a unchanging list that really is as short as you show then you should just hard-code the strings into the code (or use a macro, or declare them const (make sure they're const pointers as well as pointers to const)). That way the compiler can optimise the strcmp calls away to almost nothing; short strings like you show might even be done via a numeric comparison (a four byte string is the same length as a number), but don't do it manually - let the compiler sort that out. The key point is that the compiler cannot optimize this to the maximum if it can't prove that Migrated is constant.

If Migrated is unchanging, but much larger than shown, then you should use "perfect hashing". There is a tool called gperf that, given a list of names, will generate C code to do the lookup in an optimal way.

If Migrated can change at run-time and is small then you're probably just about optimal already.

If Migrated can change at run-time, but can be very large then a hash table is the best option. Failing that a sorted, balanced tree would be better than a list.