How to implement strlen as fast as possible

Question

Assume that you're working a x86 32-bits system. Your task is to implement the strlen as fast as possible.

There're two problems you've to take care: 1. address alignment. 2. read memory with machine word length(4 bytes).

It's not hard to find the first alignment address in the given string.

Then we can read memory once with the 4 bytes, and count up it the total length. But we should stop once there's a zero byte in the 4 bytes, and count the left bytes before zero byte. In order to check the zero byte in a fast way, there's a code snippet from glibc:

unsigned long int longword, himagic, lomagic;
himagic = 0x80808080L;  
lomagic = 0x01010101L;

// There's zero byte in 4 bytes.
if (((longword - lomagic) & ~longword & himagic) != 0) {
    // do left thing...
}

I used it in Visual C++, to compare with CRT's implementation. The CRT's is much more faster than the above one.

I'm not familiar with CRT's implementation, did they use a faster way to check the zero byte?

Answer 1

First CRT's one is written directly in assembler. you can see it's source code here C:\Program Files\Microsoft Visual Studio 9.0\VC\crt\src\intel\strlen.asm (this is for VS 2008)

Answer 2

You could save the length of the string along with the string when creating it, as is done in Pascal.

Answer 3

It depends. Microsoft's library really has two different versions of strlen. One is a portable version in C that's about the most trivial version of strlen possible, pretty close (and probably equivalent) to:

size_t strlen(char const *str) { 
    for (char const *pos=str; *pos; ++pos)
        ;
    return pos-str;
}

The other is in assembly language (used only for Intel x86), and quite similar to what you have above, at least as far as load 4 bytes, check of one of them is zero, and react appropriately. The only obvious difference is that instead of subtracting, they basically add pre-negate the bytes and add. I.e. instead of word-0x0101010101, they use word + 0x7efefeff.

Answer 4

Assuming you know the maximum possible length, and you've initated the memory to \0 before use, you could do a binary split and go left/right depending on the value(\0, split on left, else split on right). That way you'd dramatically decrease the amount of checks you'll need to find the length. Not optimal(requires some setup), but should be really fast.

// Eric

Answer 5

there are also compiler intrinsic versions which use the REPNE SCAS instruction pair, though these are generally on older compilers, they can still be pretty fast. there are also SSE2 versions of strlen, such as Dr Agner Fog's performance library's implementation, or something such as this