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 7 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.

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

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.

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).

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.

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.

One important thing not mentioned by the other answers is that the FSF is very cautious about ensuring that proprietary code does not make it into GNU projects. In the GNU Coding Standards under Referring to Proprietary Programs, there is a warning about organising your implementation in a way that it cannot be confused with existing proprietary code:

Don’t in any circumstances refer to Unix source code for or during your work on GNU! (Or to any other proprietary programs.)

If you have a vague recollection of the internals of a Unix program, this does not absolutely mean you can’t write an imitation of it, but do try to organize the imitation internally along different lines, because this is likely to make the details of the Unix version irrelevant and dissimilar to your results.

For example, Unix utilities were generally optimized to minimize memory use; if you go for speed instead, your program will be very different.

(Emphasis mine.)

Yes, strlen requires optimization. It's a function that is called a lot, and if it is slow (as your implementation is), your program could run a full 2-3 seconds slower.

The optimized C code (bitwise AND-ing with some magic values) is just part of the portable fallback implementation, and is often replaced with machine-specific assembly code from the sysdeps directory. These examples are often a lot faster (running in a few milliseconds or less).

Your (naive) code iterates on every single character of the string, and jumps around every time the character is not null. This can be very slow for large inputs (upwards of ten seconds) and as such is not very good for program speed. However, the optimized code divides the amount of computations by the size of long on your platform (usually 8 or 4); as such, it is much faster than the naive C implementation.