I wanted to know if there are even faster ways of comparing strings in C than using strcmp(), especially when I have to compare a string with multiple pre-defined strings in a switch statement fashion. In my application, the string to be compared can sometimes go as big as 1000 chars, so was just thinking if strcmp() is sufficient enough or if there exists better and efficient way which I am not familiar with. I am actually working on a low power embedded IoT project where more CPU cycles cost power.
1 Answer
It doesn't sound as if the problem has as much to do with strcmp itself, as how you use it.
The fastest way to compare strings against a table of pre-defined strings, is to ensure that the strings are sorted alphabetically, then use binary search. Where strcmp acts as the comparison function. C standard bsearch may or may not be feasible on an embedded system. Otherwise, it is fairly simple to implement yourself.
That is, unless the number of strings are vast. Then at some point, some manner of hash table will perform better than searching. To give an exact answer of what performs best, one needs all the details of the data.
With fixed-length strings you can improve performance ever so slightly by using memcmp instead - that way you don't have to check against null termination. But that's really a micro-optimization.
2 Comments
Lee Daniel Crocker
A hash table would probably be even faster.
Lundin
@LeeDanielCrocker Generally, yes, unless this is a limited amount of strings. A hash table has almost random access time, but calling the hash function gives a bit of overhead. Typically it contains division/modulus etc which might chew up a fair amount of CPU cycles. So it isn't obvious where exactly the hash table starts to out-perform binary search, only that it eventually will, at table size "x" and beyond.
strcmp". Before that,AandBare evaluated for non-null test, and skips invokingstrcmpand returns0if either are null. A bit misleading, considering if both are null they're certainly "equal", but still report0. Regardless, if string comparison is really the bottleneck, perhaps you'd be better off analyzing how to not do it as much rather than trying to optimize this thing.strcmpbeing well-optimized for the general case. If your case is specific, you need to specify the details of your case. Your macro example does not really help, because it is not an "optimization" at all, but a change of thestrcmpsemantics -- an empty string now always compares equal to anything else. user3386109 has pointed to potential candidates for specific case optimizations.