Why does glibc's strlen need to be so complica

Question

I was looking through the strlen code here and I was wondering if the optimizations used in the code are really needed? For example, why wouldn't something like the following work equally good or better?

unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

Isn't simpler code better and/or easier for the compiler to optimize?

The code of strlen on the page behind the link looks like this:

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund ([e-mail]),
   with help from Dan Sahlin ([e-mail]);
   commentary by Jim Blandy ([e-mail]).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
strlen (str)
     const char *str;
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      /* We tentatively exit the loop if adding MAGIC_BITS to
     LONGWORD fails to change any of the hole bits of LONGWORD.

     1) Is this safe?  Will it catch all the zero bytes?
     Suppose there is a byte with all zeros.  Any carry bits
     propagating from its left will fall into the hole at its
     least significant bit and stop.  Since there will be no
     carry from its most significant bit, the LSB of the
     byte to the left will be unchanged, and the zero will be
     detected.

     2) Is this worthwhile?  Will it ignore everything except
     zero bytes?  Suppose every byte of LONGWORD has a bit set
     somewhere.  There will be a carry into bit 8.  If bit 8
     is set, this will carry into bit 16.  If bit 8 is clear,
     one of bits 9-15 must be set, so there will be a carry
     into bit 16.  Similarly, there will be a carry into bit
     24.  If one of bits 24-30 is set, there will be a carry
     into bit 31, so all of the hole bits will be changed.

     The one misfire occurs when bits 24-30 are clear and bit
     31 is set; in this case, the hole at bit 31 is not
     changed.  If we had access to the processor carry flag,
     we could close this loophole by putting the fourth hole
     at bit 32!

     So it ignores everything except 128's, when they're aligned
     properly.  */

      longword = *longword_ptr++;

      if (
#if 0
      /* Add MAGIC_BITS to LONGWORD.  */
      (((longword + magic_bits)

        /* Set those bits that were unchanged by the addition.  */
        ^ ~longword)

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */
       & ~magic_bits)
#else
      ((longword - lomagic) & himagic)
#endif
      != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

Why does this version run quickly?

Isn't it doing a lot of unnecessary work?

Answer 1

In addition to the great answers here, I want to point out that the code linked in the question is for GNU's implementation of strlen.

The OpenBSD implementation of strlen is very similar to the code proposed in the question. The complexity of an implementation is determined by the author.

...
#include <string.h>

size_t
strlen(const char *str)
{
    const char *s;

    for (s = str; *s; ++s)
        ;
    return (s - str);
}

DEF_STRONG(strlen);

---

EDIT: The OpenBSD code I linked above looks to be a fallback implementation for ISAs that don't have there own asm implementation. There are different implementations of strlen depending on architecture. The code for amd64 strlen, for example, is asm. Similar to PeterCordes' comments/answer pointing out that the non-fallback GNU implementations are asm as well.

Answer 2

It is explained in the comments in the file you linked:

 27 /* Return the length of the null-terminated string STR.  Scan for
 28    the null terminator quickly by testing four bytes at a time.  */

and:

 73   /* Instead of the traditional loop which tests each character,
 74      we will test a longword at a time.  The tricky part is testing
 75      if *any of the four* bytes in the longword in question are zero.  */

In C, it is possible to reason in detail about the efficiency.

It is less efficient to iterate through individual characters looking for a null than it is to test more than one byte at a time, as this code does.

The additional complexity comes from needing to ensure that the string under test is aligned in the right place to start testing more than one byte at a time (along a longword boundary, as described in the comments), and from needing to ensure that the assumptions about the sizes of the datatypes are not violated when the code is used.

In most (but not all) modern software development, this attention to efficiency detail is not necessary, or not worth the cost of extra code complexity.

One place where it does make sense to pay attention to efficiency like this is in standard libraries, like the example you linked.

---

If you want to read more about word boundaries, see this question, and this excellent wikipedia page

Answer 3

You want code to be correct, maintainable, and fast. These factors have different importance:

"correct" is absolutely essential.

"maintainable" depends on how much you are going to maintain the code: strlen has been a Standard C library function for over 40 years. It's not going to change. Maintainability is therefore quite unimportant - for this function.

"Fast": In many applications, strcpy, strlen etc. use a significant amount of the execution time. To achieve the same overall speed gain as this complicated, but not very complicated implementation of strlen by improving the compiler would take heroic efforts.

Being fast has another advantage: When programmers find out that calling "strlen" is the fastest method they can measure the number of bytes in a string, they are not tempted anymore to write their own code to make things faster.

So for strlen, speed is much more important, and maintainability much less important, than for most code that you will ever write.

Why must it be so complicated? Say you have a 1,000 byte string. The simple implementation will examine 1,000 bytes. A current implementation would likely examine 64 bit words at a time, which means 125 64-bit or eight-byte words. It might even use vector instructions examining say 32 bytes at a time, which would be even more complicated and even faster. Using vector instructions leads to code that is a bit more complicated but quite straightforward, checking whether one of eight bytes in a 64 bit word is zero requires some clever tricks. So for medium to long strings this code can be expected to be about four times faster. For a function as important as strlen, that's worth writing a more complex function.

PS. The code is not very portable. But it's part of the Standard C library, which is part of the implementation - it need not be portable.

PPS. Someone posted an example where a debugging tool complained about accessing bytes past the end of a string. An implementation can be designed that guarantees the following: If p is a valid pointer to a byte, then any access to a byte in the same aligned block that would be undefined behaviour according to the C standard, will return an unspecified value.

PPPS. Intel has added instructions to their later processors that form a building block for the strstr() function (finding a substring in a string). Their description is mind boggling, but they can make that particular function probably 100 times faster. (Basically, given an array a containing "Hello, world!" and an array b starting with 16 bytes "HelloHelloHelloH" and containing more bytes, it figures out that the string a doesn't occur in b earlier than starting at index 15).

Answer 4

There's been a lot of (slightly or entirely) wrong guesses in comments about some details / background for this.

You're looking at glibc's optimized C fallback optimized implementation. (For ISAs that don't have a hand-written asm implementation). Or an old version of that code, which is still in the glibc source tree. https://code.woboq.org/userspace/glibc/string/strlen.c.html is a code-browser based on the current glibc git tree. Apparently it is still used by a few mainstream glibc targets, including MIPS. (Thanks @zwol).

On popular ISAs like x86 and ARM, glibc uses hand-written asm

So the incentive to change anything about this code is lower than you might think.

This bithack code (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord) isn't what actually runs on your server/desktop/laptop/smartphone. It's better than a naive byte-at-a-time loop, but even this bithack is pretty bad compared to efficient asm for modern CPUs (especially x86 where AVX2 SIMD allows checking 32 bytes with a couple instructions, allowing 32 to 64 bytes per clock cycle in the main loop if data is hot in L1d cache on modern CPUs with 2/clock vector load and ALU throughput. i.e. for medium-sized strings where startup overhead doesn't dominate.)

glibc uses dynamic linking tricks to resolve strlen to an optimal version for your CPU, so even within x86 there's an SSE2 version (16-byte vectors, baseline for x86-64) and an AVX2 version (32-byte vectors).

x86 has efficient data transfer between vector and general-purpose registers, which makes it uniquely(?) good for using SIMD to speed up functions on implicit-length strings where the loop control is data dependent. pcmpeqb / pmovmskb makes it possible to testing 16 separate bytes at a time.

glibc has an AArch64 version like that using AdvSIMD, and a version for AArch64 CPUs where vector->GP registers stalls the pipeline, so it does actually use this bithack. But uses count-leading-zeros to find the byte-within-register once it gets a hit, and takes advantage of AArch64's efficient unaligned accesses after checking for page-crossing.

Also related: Why is this code 6.5x slower with optimizations enabled? has some more details about what's fast vs. slow in x86 asm for strlen with a large buffer and a simple asm implementation that might be good for gcc to know how to inline. (Some gcc versions unwisely inline rep scasb which is very slow, or a 4-byte-at-a-time bithack like this. So GCC's inline-strlen recipe needs updating or disabling.)

Asm doesn't have C-style "undefined behaviour"; it's safe to access bytes in memory however you like, and an aligned load that includes any valid bytes can't fault. Memory protection happens with aligned-page granularity; aligned accesses narrower than that can't cross a page boundary. Is it safe to read past the end of a buffer within the same page on x86 and x64? The same reasoning applies to the machine-code that this C hack gets compilers to create for a stand-alone non-inline implementation of this function.

When a compiler emits code to call an unknown non-inline function, it has to assume that function modifies any/all global variables and any memory it might possibly have a pointer to. i.e. everything except locals that haven't had their address escape have to be in sync in memory across the call. This applies to functions written in asm, obviously, but also to library functions. If you don't enable link-time optimization, it even applies to separate translation units (source files).

---

Why this is safe as part of glibc but not otherwise.

The most important factor is that this strlen can't inline into anything else. It's not safe for that; it contains strict-aliasing UB (reading char data through an unsigned long*). char* is allowed to alias anything else but the reverse is not true.

This is a library function for an ahead-of-time compiled library (glibc). It won't get inlined with link-time-optimization into callers. This means it just has to compile to safe machine code for a stand-alone version of strlen. It doesn't have to be portable / safe C.

The GNU C library only has to compile with GCC. Apparently it's not supported to compile it with clang or ICC, even though they support GNU extensions. GCC is an ahead-of-time compilers that turn a C source file into an object file of machine code. Not an interpreter, so unless it inlines at compile time, bytes in memory are just bytes in memory. i.e. strict-aliasing UB isn't dangerous when the accesses with different types happen in different functions that don't inline into each other.

Remember that strlen's behaviour is defined by the ISO C standard. That function name specifically is part of the implementation. Compilers like GCC even treat the name as a built-in function unless you use -fno-builtin-strlen, so strlen("foo") can be a compile-time constant 3. The definition in the library is only used when gcc decides to actually emit a call to it instead of inlining its own recipe or something.

When UB isn't visible to the compiler at compile time, you get sane machine code. The machine code has to work for the no-UB case, and even if you wanted to, there's no way for the asm to detect what types the caller used to put data into the pointed-to memory.

Glibc is compiled to a stand-alone static or dynamic library that can't inline with link-time optimization. glibc's build scripts don't create "fat" static libraries containing machine code + gcc GIMPLE internal representation for link-time optimization when inlining into a program. (i.e. libc.a won't participate in -flto link-time optimization into the main program.) Building glibc that way would be potentially unsafe on targets that actually use this .c.

In fact as @zwol comments, LTO can't be used when building glibc itself, because of "brittle" code like this which could break if inlining between glibc source files was possible. (There are some internal uses of strlen, e.g. maybe as part of the printf implementation)

---

This strlen makes some assumptions:

• CHAR_BIT is a multiple of 8. True on all GNU systems. POSIX 2001 even guarantees CHAR_BIT == 8. (This looks safe for systems with CHAR_BIT= 16 or 32, like some DSPs; the unaligned-prologue loop will always run 0 iterations if sizeof(long) = sizeof(char) = 1 because every pointer is always aligned and p & sizeof(long)-1 is always zero.) But if you had a non-ASCII character set where chars are 9 or 12 bits wide, 0x8080... is the wrong pattern.
• (maybe) unsigned long is 4 or 8 bytes. Or maybe it would actually work for any size of unsigned long up to 8, and it uses an assert() to check for that.

Those two aren't possible UB, they're just non-portability to some C implementations. This code is (or was) part of the C implementation on platforms where it does work, so that's fine.

The next assumption is potential C UB:

• An aligned load that contains any valid bytes can't fault, and is safe as long as you ignore the bytes outside the object you actually want. (True in asm on every GNU systems, and on all normal CPUs because memory protection happens with aligned-page granularity. Is it safe to read past the end of a buffer within the same page on x86 and x64? safe in C when the UB isn't visible at compile time. Without inlining, this is the case here. The compiler can't prove that reading past the first 0 is UB; it could be a C char[] array containing {1,2,0,3} for example)

That last point is what makes it safe to read past the end of a C object here. That is pretty much safe even when inlining with current compilers because I think they don't currently treat that implying a path of execution is unreachable. But anyway, the strict aliasing is already a showstopper if you ever let this inline.

Then you'd have problems like the Linux kernel's old unsafe memcpy CPP macro that used pointer-casting to unsigned long (gcc, strict-aliasing, and horror stories).

This strlen dates back to the era when you could get away with stuff like that in general; it used to be pretty much safe without the "only when not inlining" caveat before GCC3.

---

UB that's only visible when looking across call/ret boundaries can't hurt us. (e.g. calling this on a char buf[] instead of on an array of unsigned long[] cast to a const char*). Once the machine code is set in stone, it's just dealing with bytes in memory. A non-inline function call has to assume that the callee reads any/all memory.

---

Writing this safely, without strict-aliasing UB

The GCC type attribute may_alias gives a type the same alias-anything treatment as char*. (Suggested by @KonradBorowsk). GCC headers currently use it for x86 SIMD vector types like __m128i so you can always safely do _mm_loadu_si128( (__m128i*)foo ). (See Is `reinterpret_cast`ing between hardware vector pointer and the corresponding type an undefined behavior? for more details about what this does and doesn't mean.)

strlen(const char *char_ptr)
{
  typedef unsigned long __attribute__((may_alias)) aliasing_ulong;

  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
  for (;;) {
     unsigned long ulong = *longword_ptr++;  // can safely alias anything
     ...
  }
}

You could also use aligned(1) to express a type with alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

A portable way to express an aliasing load in ISO is with memcpy, which modern compilers do know how to inline as a single load instruction. e.g.

   unsigned long longword;
   memcpy(&longword, char_ptr, sizeof(longword));
   char_ptr += sizeof(longword);

This also works for unaligned loads because memcpy works as-if by char-at-a-time access. But in practice modern compilers understand memcpy very well.

The danger here is that if GCC doesn't know for sure that char_ptr is word-aligned, it won't inline it on some platforms that might not support unaligned loads in asm. e.g. MIPS before MIPS64r6, or older ARM. If you got an actual function call to memcpy just to load a word (and leave it in other memory), that would be a disaster. GCC can sometimes see when code aligns a pointer. Or after the char-at-a-time loop that reaches a ulong boundary you could use
p = __builtin_assume_aligned(p, sizeof(unsigned long));

This doesn't avoid the read-past-the-object possible UB, but with current GCC that's not dangerous in practice.

---

Why hand-optimized C source is necessary: current compilers aren't good enough

Hand-optimized asm can be even better when you want every last drop of performance for a widely-used standard library function. Especially for something like memcpy, but also strlen. In this case it wouldn't be much easier to use C with x86 intrinsics to take advantage of SSE2.

But here we're just talking about a naive vs. bithack C version without any ISA-specific features.

(I think we can take it as a given that strlen is widely enough used that making it run as fast as possible is important. So the question becomes whether we can get efficient machine code from simpler source. No, we can't.)

Current GCC and clang are not capable of auto-vectorizing loops where the iteration count isn't known ahead of the first iteration. (e.g. it has to be possible to check if the loop will run at least 16 iterations before running the first iteration.) e.g. autovectorizing memcpy is possible (explicit-length buffer) but not strcpy or strlen (implicit-length string), given current compilers.

That includes search loops, or any other loop with a data-dependent if()break as well as a counter.

ICC (Intel's compiler for x86) can auto-vectorize some search loops, but still only makes naive byte-at-a-time asm for a simple / naive C strlen like OpenBSD's libc uses. (Godbolt). (From @Peske's answer).

A hand-optimized libc strlen is necessary for performance with current compilers. Going 1 byte at a time (with unrolling maybe 2 bytes per cycle on wide superscalar CPUs) is pathetic when main memory can keep up with about 8 bytes per cycle, and L1d cache can deliver 16 to 64 per cycle. (2x 32-byte loads per cycle on modern mainstream x86 CPUs since Haswell and Ryzen. Not counting AVX512 which can reduce clock speeds just for using 512-bit vectors; which is why glibc probably isn't in a hurry to add an AVX512 version. Although with 256-bit vectors, AVX512VL + BW masked compare into a mask and ktest or kortest could make strlen more hyperthreading friendly by reducing its uops / iteration.)

I'm including non-x86 here, that's the "16 bytes". e.g. most AArch64 CPUs can do at least that, I think, and some certainly more. And some have enough execution throughput for strlen to keep up with that load bandwidth.

Of course programs that work with large strings should usually keep track of lengths to avoid having to redo finding the length of implicit-length C strings very often. But short to medium length performance still benefits from hand-written implementations, and I'm sure some programs do end up using strlen on medium-length strings.

Answer 5

Briefly: checking a string byte by byte will potentially be slow on architectures that can fetch larger amounts of data at a time.

If the check for null termination could be done on 32 or 64 bit basis, it reduces the amount of checks the compiler has to perform. That's what the linked code attempts to do, with a specific system in mind. They make assumptions about addressing, alignment, cache use, non-standard compiler setups etc etc.

Reading byte by byte as in your example would be a sensible approach on a 8 bit CPU, or when writing a portable lib written in standard C.

Looking at C standard libs for advise how to write fast/good code isn't a good idea, because it will be non-portable and rely on non-standard assumptions or poorly-defined behavior. If you are a beginner, reading such code will likely be more harmful than educational.

Answer 6

In short, this is a performance optimization the standard library can do by knowing what compiler it is compiled with - you shouldn't write code like this, unless you are writing a standard library and can depend on a specific compiler. Specifically, it's processing alignment number of bytes at the same time - 4 on 32-bit platforms, 8 on 64-bit platforms. This means it can be 4 or 8 times faster than naïve byte iteration.

To explain how does this work, consider the following image. Assume the 32-bit platform here (4 bytes alignment).

Let's say that the letter "H" of "Hello, world!" string was provided as an argument for strlen. Because the CPU likes having things aligned in memory (ideally, address % sizeof(size_t) == 0), the bytes before the alignment are processed byte-by-byte, using slow method.

Then, for each alignment-sized chunk, by calculating (longbits - 0x01010101) & 0x80808080 != 0 it checks whether any of the bytes within an integer is zero. This calculation has a false positive when at least one of bytes is higher than 0x80, but more often than not it should work. If that's not the case (as it is in yellow area), the length is increased by alignment size.

If any of bytes within an integer turns out to be zero (or 0x81), then the string is checked byte-by-byte to determine the position of zero.

This can make an out-of-bounds access, however because it's within an alignment, it's more likely than not to be fine, memory mapping units usually don't have byte level precision.