faster strlen ?

Question

Typical strlen() traverse from first character till it finds \0. This requires you to traverse each and every character. In algorithm sense, its O(N).

Is there any faster way to do this where input is vaguely defined. Like: length would be less than 50, or length would be around 200 characters.

I thought of lookup blocks and all but didn't get any optimization.

Answer 1

Sure. Keep track of the length while you're writing to the string.

Answer 2

The short answer: no.

The longer answer: do you really think that if there were a faster way to check string length for barebones C strings, something as commonly used as the C string library wouldn't have already incorporated it?

Without some kind of additional knowledge about a string, you have to check each character. If you're willing to maintain that additional information, you could create a struct that stores the length as a field in the struct (in addition to the actual character array/pointer for the string), in which case you could then make the length lookup constant time, but would have to update that field each time you modified the string.

Answer 3

Obviously, if your string has a known minimum length, you can begin your search at that position.

Beyond that, there's not really anything you can do; if you try to do something clever and find a \0 byte, you still need to check every byte between the start of the string and that point to make sure there was no earlier \0.

That's not to say that strlen can't be optimized. It can be pipelined, and it can be made to process word-size or vector chunks with each comparison. On most architectures, some combination of these and other approaches will yield a substantial constant-factor speedup over a naive byte-comparison loop. Of course, on most mature platforms, the system strlen is already implemented using these techniques.

Answer 4

You can try to use vectorization. Not sure if compiler will be able perform it, but I did it manually (using intrinsics). But it could help you only for long strings.

Use stl strings, it's more safe and std::string class contains its length.

Answer 5

Jack,

strlen works by looking for the ending '\0', here's an implementation taken from OpenBSD:

size_t
strlen(const char *str)
{
        const char *s;

        for (s = str; *s; ++s)
                ;
        return (s - str);
}

Now, consider that you know the length is about 200 characters, as you said. Say you start at 200 and loop up and down for a '\0'. You've found one at 204, what does it mean? That the string is 204 chars long? NO! It could end before that with another '\0' and all you did was look out of bounds.

Answer 6

Actually, glibc's implementation of strlen is an interesting example of the vectorization approach. It is peculiar in that it doesn't use vector instructions, but finds a way to use only ordinary instructions on 32 or 64 bits words from the buffer.

Answer 7

Get a Core i7 processor.

Core i7 comes with the SSE 4.2 instruction set. Intel added four additional vector instructions to speed up strlen and related search tasks.

Here are some interesting thoughts about the new instructions:

http://smallcode.weblogs.us/oldblog/2007/11/