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

If you control the allocation of the string, you could make sure there is not just one terminating \0 byte, but several in a row depending on the maximum size of vector instructions for your platform. Then you could write the same O(n) algorithm using X bytes at a time comparing for 0, making strlen amortized O(n/X). Note that the amount of extra \0 bytes would not be equal to the amount of bytes on which your vector instructions operate (X), but rather 2*X - 1 since an aligned region should be filled with zeroes.

You would need to iterate over a couple of bytes normally in the beginning though, until you reach an address that is aligned to a boundary of X bytes.

The use case for this is kind of non-existent though: the amount of extra bytes you need to allocate would easily be more than simply storing a simple 4 or 8 byte integer containing the size directly. Even if it is important to you for some reason that this string can be passed solely as a pointer, without passing its size as well I think storing the size as the first Y bytes during allocation might be the fastest. But this is already far from the strlen optimization you're asking about.

Clarification:

the_size | the string ...
         ^
 the pointer to the string

The glibc implementation is way cooler.

Answer 2

Here I attached the asm code from glibc 2.29. I removed the snippet for ARM cpus. I tested it, it is really fast, beyond my expectation. It merely do alignment then 4 bytes comparison.

ENTRY(strlen)
bic     r1, r0, $3              @ addr of word containing first byte
ldr     r2, [r1], $4            @ get the first word
ands    r3, r0, $3              @ how many bytes are duff?
rsb     r0, r3, $0              @ get - that number into counter.
beq     Laligned                @ skip into main check routine if no more
orr     r2, r2, $0x000000ff     @ set this byte to non-zero
subs    r3, r3, $1              @ any more to do?
orrgt   r2, r2, $0x0000ff00     @ if so, set this byte
subs    r3, r3, $1              @ more?
orrgt   r2, r2, $0x00ff0000     @ then set.
Laligned:               @ here, we have a word in r2.  Does it
tst     r2, $0x000000ff         @ contain any zeroes?
tstne   r2, $0x0000ff00         @
tstne   r2, $0x00ff0000         @
tstne   r2, $0xff000000         @
addne   r0, r0, $4              @ if not, the string is 4 bytes longer
ldrne   r2, [r1], $4            @ and we continue to the next word
bne     Laligned                @
Llastword:              @ drop through to here once we find a
tst     r2, $0x000000ff         @ word that has a zero byte in it
addne   r0, r0, $1              @
tstne   r2, $0x0000ff00         @ and add up to 3 bytes on to it
addne   r0, r0, $1              @
tstne   r2, $0x00ff0000         @ (if first three all non-zero, 4th
addne   r0, r0, $1              @  must be zero)
DO_RET(lr)

END(strlen)

Answer 3

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/

Answer 4

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 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

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 7

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 8

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 9

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