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 .

• Dialecticus: If there are only two items in Migrated array they yes, it is optimized, but if there are thousands of items then there are better ways to code it.
• Dialecticus: Actually, if there are only two items in the array it would be better to check for the first character in codeB and based on it compare the string with only one viable item in the array.
• GManNickG: Get a profiler and find out.
• Hot Licks: @Kip9000 - For two elements?? Any decent compiler will unroll the loop and have it done before you've figured your first hash value.
• Marko: The key to optimising is usually to not optimise unless you have empirical evidence that it is necessary. In saying that, understanding the complexity and memory consumption of various types of containers is very worthwhile. For instance, the using a hash-table here with 2 items is a massive overhead.

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.

• ughoavgfhw: Right now Migrated is an array of pointers, so this won't work. You need to redefine it as an array of 4 character arrays. Also, you should probably make sure codeB is 4 bytes long before converting it to an integer.
• ams: Don't do this. The compiler will do this for for itself. You just need to write the code such that the compiler can see that that's a valid thing to do.

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.

• Marko: THe more assumptions you make, the better it gets. If we assume all of the strings are 3 characters long - so 4 with terminating NULL, they be compared as ints - and possibly stored in this way too. Probably not practical solution though.
• Frerich Raabe: @Marko: Sure, and if you assume that no given string matches, you could return -1 right away. ;-) You have to draw a line somewhere. I just picked a more or less random assumption to illustrate that the best potential for optimization is by considering the domain of values fed to the function.

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.

• sfstewman: Does perfect hashing do better than, say, a trie table or an Aho-Corsack automaton for matching a string against other strings? The constant factor of a hash function can be quite high (sometimes linear in the length of the string).
• ams: @sfstewman: Given this input, gperf produces this output. There's not too much computational complexity there.
• ams: @sfstewman: perfect hashing is for finding one word in a moderate sized dictionary. It's not for finding dictionary words in a corpus of text, like Aho-Corsack seems to be. Trie tables can outperform imperfect hashing, but only in the worst case, and can never outperform a perfect hash table.