Optimizations in Code related to string functions!

Question

Hi All,

Are there any guidelines available that can be followed before calling standard string operation related functions in C?

For example, how much optimization will comparing the first character of two strings (and checking if they are equal) before calling strcmp provide?

What types of overhead related to string related functions in C can be expected, and what mechanisms will help avoid them?

Thanks!

Answer 1

It won't provide any optimization, because that is exactly what strcmp() does.

In general, because the str...() functions are so heavily used, you can depend on the library writers implementing them as efficiently as possible. Only after you have written your own code that uses those functions, found you have a problem, and tracked it down BY USING A PROFILER, should you consider writing replacements.

Answer 2

The string functions are there for you to use them. If you need to compare two strings, call strcmp. Don't worry about tiny performance difference, which are mostly imagined anyway. Get your code working first.

First, to answer any question about performance, if you ask "How much optimization will..." the answer is "Profile!" Nobody can predict how fast something is going to run. The implementation of the C stdlib has been continuously improved for years, any optimization tricks you try to come up with might hurt it.

For example, I think GCC will use vectorization when comparing strings, so you're actually comparing some 4-8 elements at a time. Were you expecting that? Doing your single character compare might actually slow it down.

That said, a typical implementation just checks character for character, so you'd simply be moving one comparison out of the loop, for no net gain. (But as stated, maybe for a net loss!)

So the guideline is:

Program now, optimize later.

And optimize the rational way: with evidence and testing, not with guessing.

Answer 3

Worrying about strcmp() is a micro-optimization most of the time - not worth the effort put in. There are other things to be warier of, such as:

for (i = 0; i < strlen(s); i++)
{
     ...do stuff with s[i]...
}

The optimizer may not realize that it can and should avoid the function call on each loop iteration - if you increment s in the loop, it may not be able to avoid it. That is expensive.

Once upon a very long time ago, I was using a function such as strstr() on buffers of 20 KB or so, and the program worked fine on the HP box where I developed it. I ported it back to a Sun machine (remember, this was 20 years ago - the problems been fixed long since), and the program didn't even crawl - it was practically stationary. The problem turned out to be a loop in strstr() which used strlen() more or less as shown above. When used on short buffers, there wasn't a major problem; when used on 20 KB buffers, searching for a pattern that appeared every couple of kilobytes, the poor machine ground to a halt. The problem was shown by profiling the application. I plugged in a surrogate strstr() that avoided the mistake and things went back to normal.

Another common source of slowness when carried to excess is the use of strcat(). For example:

strcpy(dst, name);
strcat(dst, "/subdir/");
strcat(dst, file);
strcat(dst, ".sfx");

Usually, these are not actually a source of performance trouble - but in the absence of evidence to the contrary, it could be a source of a buffer overflow. You need to know that the lengths are small enough to fit into dst. But, if you know the lengths of each bit (as you should to be sure that they will fit), you could write instead:

strcpy(dst, name);
dst += len_name;
strcpy(dst, "/subdir/");
dst += sizeof("/subdir/") - 1;
strcpy(dst, file);
dst += len_file;
strcpy(dst, ".sfx");

This saves repeatedly scanning a string of known length to find the end before adding the new material. With short strings, this won't matter much; with long strings and many concatenation operations, it might matter. As before, the key point is to measure the cost.

Kernighan and Pike have an interesting tale of how to improve the performance of a spam filter in the book 'The Practice of Programming'. It started using strstr() in a loop; it ended up with a very different design because the circumstances for which strstr() was designed did not match the requirements of their spam filtering system. But, again, they only did the work because it was demonstrated that there was a performance problem, and they did sufficient work to prevent the program from being the bottleneck on the system, but not more.

Answer 4

Jonathan is absolutely right, especially the strlen(s) example, which I have found (in other people's code :-) by means of a single stackshot.

You are talking about micro-optimization, which is the the right thing to worry about AFTER you have otherwise tuned the blazes out of the code. Comparing the first character before calling strcmp does save some time due to the overhead of function entry/exit, but my rule-of-thumb is it is only worth doing if those calls to strcmp are costing more than 10%.

Answer 5

It may be educational to study the glibc implementation of strlen:

• There are no checks for NULL arguments (not even asserts)
• Strings are compares byte-by-byte until reaching a longword-aligned address. After that, all comparisons are done in 4- or 8-byte chunks.
• There is no vectorization or architecture-specific stuff (i.e. no #ifdefs).
• The tricky part when comparing 4 or 8 bytes at a time is to figure out which byte was zero when a comparison fails.

Answer 6

You might be interested in this article (by Joel Spolsky). It's about low level (particularly C string) functions and how they are optimized.

Answer 7

The standard c-runtime string stuff is pretty highly optimized. It's unlikely that you will be able to improve on it except by exploiting knowledge about your problem domain that the c-runtime can't have.

Your idea about pre-testing the first character has some merit - IFF most of your comparisons are between unlike strings. (i.e. most will fail). In that case you avoid the overhead of a function call.

But you make comparing strings that match even more expensive!

strcmp is most costly when given strings that match. so if your algorithm will ever pass the same pointer as both parameters of strcmp, you could optimize by comparing the pointers first. Only you can know if your code will actually do this frequently enough to be worth it.

The only other general piece of advice I have is: don't use strcat. Sure it's quick and easy, but it gets more expensive the more you use it. Better to keep track of the end of the string and strcpy to the end.

Answer 8

The C standard library is sweet because it's very optimized. And some compilers inline the CRT functions so you save the overhead of a call instruction. However, if you still want more speed, there a few options available. If you visit this link I give you, you will be able to download a program that countains a few strcmp routines written by expert assembly language programmers.

http://www.masm32.com/board/index.php?topic=2508.0

I would especially take a look at the function that the forum member lingo wrote. This guy writes the fastest assembly code I've ever seen.

If you don't know how to use an assembly language function with your C program, just ask another StackOverflow question and many people, including me, will be able to help you.

Here are the results they get when comparing the string abcdefg to abcz

lstrcmp - original (from Microsoft) : 19314 clocks; Return value: 1
lstrcmp - kunt0r  : 957 clocks; Return value: 24832
lstrcmp - Lingo   : 501 clocks; Return value: 1

As seen by the number of clocks (less is better), the other functions are much faster.

Answer 9

Are there any guidelines available that can be followed before calling standard string functions in C?

Yes: Don't worry about which library functions are faster or slower than which others or how can tweak them to be microscopically faster (or slower!). Instead find the functions which enable you to express your intent most clearly.

Eventually, if you have evidence that your application is too slow, you can profile and see if string functions have anything to do with your problem. And if improvement is more likely to come from a sublinear algorithm like Boyer-Moore than by tweaking strcmp.

---

Michael A. Jackson's two rules of optimization:

1. Don't do it.

2. (For experts only) Don't do it yet.

Answer 10

<sarcasm>

Contrary to the other answers, about your statement:

For example, how much optimization will comparing the first character of two strings (and checking if they are equal) before calling strcmp provide?

I think it's an excellent idea. So, we should do this:

int compstr(const char *a, const char *b)
{
   if (*a == *b) return strcmp(a+1, b+1);
   else return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

But, why stop there? We should check one more character, giving us better optimization:

int compstr(const char *a, const char *b)
{
    size_t i;
    for (i=0; *a == *b && i < 2; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == 2) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

Of course, we can do much better than that. Let's make the number of characters to be compared a parameter:

/* Really fast implementation to compare strings,
   takes the optimization parameter n_comp */
int compstr(const char *a, const char *b, size_t n_comp)
{
    int i;
    for (i=0; *a == *b && i < n_comp; ++a, ++b, ++i)
        if (*a == 0)
            return 0;
    if (i == n_comp) return strcmp(a, b);
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

But if we are going to all this trouble of comparing the first few characters, why not just do it all by ourselves? So, here's the final, completely optimized version:

/* Final, highly optimized function to compare strings */
int strcmp (const char *a, const char *b)
{
    for (; *a == *b; ++a, ++b)
        if (*a == 0)
            return 0;
    return *(unsigned char *)a < *(unsigned char *)b ? -1 : 1;
}

After writing our version, we are happy to find that it is identical to the version in P.J. Plauger's The Standard C Library (and it of course avoids any architecture-specific optimizations that a good library would have used)!

</sarcasm>

In other words, as others have said, there is no point in premature optimization.

Note: I haven't really checked to see if my code snippets above are correct. Another reason to avoid reinventing the wheel: you have to do all the hard work yourself!

Answer 11

I believe that an important thing is that every string related repository/database might have its own characteristics, that could be manipulated or used for creating your optimal string operation functions. However, in this post there are some easy tricks for some occasions - you can choose what fits your needs and use it: http://www.codemaestro.com/articles/21