c – Why does glibc’s strlen need to be so complicated to run quickly?

The Question :

287 people think this question is useful

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 (tege@sics.se),
   with help from Dan Sahlin (dan@sics.se);
   commentary by Jim Blandy (jimb@ai.mit.edu).

   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
            &amp; (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.  */
       &amp; ~magic_bits)
#else
      ((longword - lomagic) &amp; 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?

The Question Comments :
  • Comments are not for extended discussion; this conversation has been moved to chat.
  • For future reference, the official source repository for GNU libc is at <sourceware.org/git/?p=glibc.git>. <sourceware.org/git/?p=glibc.git;a=blob;f=string/…> does indeed show code similar to the above; however,a hand-written assembly language implementation from the sysdeps directory will be used instead, on most of glibc’s supported architectures (the most commonly used architecture that doesn’t have a replacement is MIPS).
  • Voting to close this as primarily opinion-based; “Are xxx really needed in xxx?” is subjective to people’s opinions.
  • @JL2210: Good point, fixed the title to capture the spirit of the question in a title that doesn’t sound like it’s wondering if performance is needed, just why we need these optimizations to get performance.
  • @JL2210 FWIW, the original title was “Why is strlen so complex in C [sic!]”, and it got closed as “too broad”, then reopened, then closed as “primarily opinion-based”. I tried to fix this (getting in the crossfire of “you broke my question!” and “you guys are abusing your editing powers!” in the meantime), but IMVHO the problem lied (and still lies) in the question’s basic premise, which was problematic (“this code is too complex for me to understand” is not well-suited for Q&A – IMO it is a request for tutoring, not for an answer). I’m not touching it again with a 60-foot pole 🙂

The Answer 1

234 people think this answer is useful

You don’t need and you should never write code like that – especially if you’re not a C compiler / standard library vendor. It is code used to implement strlen with some very questionable speed hacks and assumptions (that are not tested with assertions or mentioned in the comments):

  • unsigned long is either 4 or 8 bytes
  • bytes are 8 bits
  • a pointer can be cast to unsigned long long and not uintptr_t
  • one can align the pointer simply by checking that the 2 or 3 lowest order bits are zero
  • one can access a string as unsigned longs
  • one can read past the end of array without any ill effects.

What is more, a good compiler could even replace code written as

size_t stupid_strlen(const char s[]) {
    size_t i;
    for (i=0; s[i] != '\0'; i++)
        ;
    return i;
}

(notice that it has to be a type compatible with size_t) with an inlined version of the compiler builtin strlen, or vectorize the code; but a compiler would be unlikely to be able to optimize the complex version.


The strlen function is described by C11 7.24.6.3 as:

Description

  1. The strlen function computes the length of the string pointed to by s.

Returns

  1. The strlen function returns the number of characters that precede the terminating null character.

Now, if the string pointed to by s was in an array of characters just long enough to contain the string and the terminating NUL, the behaviour will be undefined if we access the string past the null terminator, for example in

char *str = "hello world";  // or
char array[] = "hello world";

So really the only way in fully portable / standards compliant C to implement this correctly is the way it is written in your question, except for trivial transformations – you can pretend to be faster by unrolling the loop etc, but it still needs to be done one byte at a time.

(As commenters have pointed out, when strict portability is too much of a burden, taking advantage of reasonable or known-safe assumptions is not always a bad thing. Especially in code that’s part of one specific C implementation. But you have to understand the rules before knowing how/when you can bend them.)


The linked strlen implementation first checks the bytes individually until the pointer is pointing to the natural 4 or 8 byte alignment boundary of the unsigned long. The C standard says that accessing a pointer that is not properly aligned has undefined behaviour, so this absolutely has to be done for the next dirty trick to be even dirtier. (In practice on some CPU architecture other than x86, a misaligned word or doubleword load will fault. C is not a portable assembly language, but this code is using it that way). It’s also what makes it possible to read past the end of an object without risk of faulting on implementations where memory protection works in aligned blocks (e.g. 4kiB virtual memory pages).

Now comes the dirty part: the code breaks the promise and reads 4 or 8 8-bit bytes at a time (a long int), and uses a bit trick with unsigned addition to quickly figure out if there were any zero bytes within those 4 or 8 bytes – it uses a specially crafted number to that would cause the carry bit to change bits that are caught by a bit mask. In essence this would then figure out if any of the 4 or 8 bytes in the mask are zeroes supposedly faster than looping through each of these bytes would. Finally there is a loop at the end to figure out which byte was the first zero, if any, and to return the result.

The biggest problem is that in sizeof (unsigned long) - 1 times out of sizeof (unsigned long) cases it will read past the end of the string – only if the null byte is in the last accessed byte (i.e. in little-endian the most significant, and in big-endian the least significant), does it not access the array out of bounds!


The code, even though used to implement strlen in a C standard library is bad code. It has several implementation-defined and undefined aspects in it and it should not be used anywhere instead of the system-provided strlen – I renamed the function to the_strlen here and added the following main:

int main(void) {
    char buf[12];
    printf("%zu\n", the_strlen(fgets(buf, 12, stdin)));
}

The buffer is carefully sized so that it can hold exactly the hello world string and the terminator. However on my 64-bit processor the unsigned long is 8 bytes, so the access to the latter part would exceed this buffer.

If I now compile with -fsanitize=undefined and -fsanitize=address and run the resulting program, I get:

% ./a.out
hello world
=================================================================
==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340
READ of size 8 at 0x7ffffe63a3f8 thread T0
    #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)
    #1 0x55fbec46b139 in main (.../a.out+0x2139)
    #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x55fbec46a949 in _start (.../a.out+0x1949)

Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame
    #0 0x55fbec46b07c in main (.../a.out+0x207c)

  This frame has 1 object(s):
    [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen
Shadow bytes around the buggy address:
  0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]
  0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==8355==ABORTING

i.e. bad things happened.

The Answer 2

156 people think this answer is useful

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). (Modern Linux compiles with -fno-strict-aliasing instead of being careful with may_alias attributes.)

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 before GCC3, even without an “only when not inlining” caveat.


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 SIMD 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;

  // handle unaligned startup somehow, e.g. check for page crossing then check an unaligned word
  // else check single bytes until an alignment boundary.
  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;

  for (;;) {
     // alignment still required, but can safely alias anything including a char[]
     unsigned long ulong = *longword_ptr++;

     ...
  }
}

You can use aligned(1) to express a type with alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;. This could be useful for the unaligned-startup part of strlen, if you don’t just do char-at-a-time until the first alignment boundary. (The main loop needs to be aligned so you don’t fault if the terminator is right before an unmapped page.)

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(&amp;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.

The Answer 3

61 people think this answer is useful

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

The Answer 4

39 people think this answer is useful

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.

The Answer 5

34 people think this answer is useful

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.

The Answer 6

32 people think this answer is useful

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

The Answer 7

24 people think this answer is useful

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.

The Answer 8

-6 people think this answer is useful

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

Add a Comment