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

Remove those 'L' suffixes and see... You are promoting all calculations to "long"! On my 32-bits tests, that alone doubles the cost.

I also do two micro-optimizations:

• Since most strings we use scan consist of ASCII chars in the range 0~127, the high bit is (almost) never set, so only check for it in a second test.

• Increment an index rather than a pointer, which is cheaper on some architectures (notably x86) and give you the length for 'free'...

---

uint32_t gatopeich_strlen32(const char* str)
{
    uint32_t *u32 = (uint32_t*)str, u, abcd, i=0;
    while(1)
    {
        u = u32[i++];
        abcd = (u-0x01010101) & 0x80808080;
        if (abcd && // If abcd is not 0, we have NUL or a non-ASCII char > 127...
             (abcd &= ~u)) // ... Discard non-ASCII chars
        {
        #if BYTE_ORDER == BIG_ENDIAN
            return 4*i - (abcd&0xffff0000 ? (abcd&0xff000000?4:3) : abcd&0xff00?2:1);
        #else
            return 4*i - (abcd&0xffff ? (abcd&0xff?4:3) : abcd&0xff0000?2:1);
        #endif
        }
    }
}

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)

Answer 3

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

Answer 4

Obviously, crafting a tight loop like this in assembler would be fastest, however if you want/need to keep it more human-readable and/or portable in C(++), you can still increase the speed of the standard function by using the register keyword.

The register keyword prompts the compiler to store the counter in a register on the CPU instead of in memory which will significantly speed up the loop.

Note however, that the register keyword is only a suggestion and the compiler is free to ignore it if it thinks it can do better, especially if certain optimization options are used. That said, while it is almost certainly going to be ignored for a local, class variable in a triple for-loop, it is likely to be honored for the code below, thus improving performance quite a bit (nearly on par with the assembler version):

size_t strlen ( const char* s ) {
  for (register const char* i=s; *i; ++i);
  return (i-s);
}

Answer 5

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 6

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