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

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.