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

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

Answer 2

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)