What is the best or fastest way to compare two strings?

Question

I am not sure how fast the below code is. If anyone knows the faster/optimized code than this, please let me know.

int xstrcmp(char *s1, char *s2)
{
  while (*s1 == *s2++)
            if (*s1++ == 0)
                    return (0);
  return (*(const unsigned char *)s1 - *(const unsigned char *)(s2-1));
}

Solution 1

Use ::strcmp instead of your own hand-rolled version. Your compiler vendor has most likely an assembly-only version which uses CPU-specific features for comparison (SSE4.2 for instance has special instructions for fast string comparison.) The MSVC version is written in assembly for instance and uses larger compares (whole words instead of individual characters) as much as possible, special casing unaligned starts/ends of the string (if you have VS2010 installed, it's in VC/crt/src/intel/strcmp.asm.)

Solution 2

Have you measured how much faster this is than strcmp? C strcmp should already be well optimized.

Some other methods you could take:

• Use memcmp if you already know the length of the strings.
• Compare 4 or 8 chars at a time by reinterpreting strings as int32 or int64 arrays, and handling the remainder chars as chars.
  • You may have issues if your pointers point to non 4-byte or 8-byte aligned memory, so compare as chars until you reach alignment

Solution 3

If I'm testing for equality, sometimes I write this:

if (a[0]==b[0] && strcmp(a, b)==0){.....

so it will only call strcmp if the first characters match, which most of the time they don't.

Comments

[Jatin]

Actually, I've been told not to use any built in function. I have to write my own string compare version :(

[Jatin]

I am just developing my concepts...so i opt not to choose any built in function.

[Anteru]

You won't beat the built-in functions in performance, but it surely doesn't matter at all. If you are just playing around, your strcmp implementation is good enough, all further speedups are rather complicated.

[Mr Lister]

I can understand you wanting to write something like this all by yourself... reinventing the wheel can be a very satisfactory experience. But if that's the case, isn't asking other people to provide their code a form of cheating? On the other hand, if it's performance you're after, nothing beats the built in routines. So what is it you want to do?

[Jatin]

I dont know how to measure how fast my code is. I am sure this code can't be fastest.

[Kevin Hsu]

You can write a test program that does strcmp and your xstrcmp millions of times on random strings. Then, run a profiler on the code (e.g. google's gperf).

[Jatin]

The code given in this path: VC/crt/src/intel/strcmp.asm and the code written by me. Which one is better???

[Anteru]

Well, the hand-written assembly is better, but yours is probably not too far off. What are you trying to achive? A reasonably fast strcmp? You're done, yours is as good as any. The fastest possible strcmp? Then you would have to start with the assembly version and tweak it for modern CPUs, etc. But on small strings, it's highly unlikely you'll end up with something faster than the years of optimization that went into the built-in strcmp.

[Jatin]

Thanks Anteru. So, now i am stopping to further optimize my code. :)

[Stefan Rein]

This is useless, this would be already in the implementation of strcmp: stackoverflow.com/a/12136398/4641479

[Mike Dunlavey]

@StefanRein: But there is overhead in calling the function. That's what this is trying to save. In most cases it doesn't matter, but in a case where this consumes a significant percent of time, it does matter.