310

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 ([email protected]),
   with help from Dan Sahlin ([email protected]);
   commentary by Jim Blandy ([email protected]).

   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?

10
  • 3
    Comments are not for extended discussion; this conversation has been moved to chat. Commented Aug 27, 2019 at 14:08
  • 24
    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).
    – zwol
    Commented Aug 27, 2019 at 15:22
  • 11
    Voting to close this as primarily opinion-based; "Are xxx really needed in xxx?" is subjective to people's opinions.
    – S.S. Anne
    Commented Aug 28, 2019 at 0:25
  • 2
    @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. Commented Aug 28, 2019 at 5:03
  • 13
    @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 :)
    – user719662
    Commented Aug 28, 2019 at 12:50

8 Answers 8

245

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.

21
  • 138
    Re: "very questionable speed hacks and assumptions" -- that is, very questionable in portable code. The standard library is written for a particular compiler/hardware combination, with knowledge of the actual behavior of things that the language definition leaves as undefined. Yes, most people should not be writing code like that, but in the context of implementing the standard library non-portable is not inherently bad. Commented Aug 27, 2019 at 12:30
  • 5
    Agree, never write things like this yourself. Or almost never. Premature optimization is the source of all evil. (In this case it could actually be motivated though). If you end up doing a lot of strlen() calls on the same very long string, your application could perhaps be written differently. You migt as example save the stringlength in a variable already when the string is created, and not need to call strlen() at all.
    – ghellquist
    Commented Aug 27, 2019 at 12:51
  • 80
    @ghellquist: Optimizing a frequently-used library call is hardly "premature optimization".
    – jamesqf
    Commented Aug 27, 2019 at 17:01
  • 14
    @Antti Haapala: Exactly why do you think strlen should be O(1)? And what we have here are several implementations, all of which are O(n), but with different constant multipliers. You may not think that matters, but for some of us an implementation of an O(n) algorithm that does its work in microseconds is much better than one that takes seconds, or even milliseconds, because it might be called several billion times in the course of a job.
    – jamesqf
    Commented Aug 28, 2019 at 4:11
  • 14
    @PeteBecker: not only that, in context of standard libraries (not so much in this instance though) writing nonportable code can be the norm as the purpose of a standard library is to provide a standard interface to implementation specific stuff.
    – PlasmaHH
    Commented Aug 28, 2019 at 11:02
184

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 using strlen heavily 6.5x slower with GCC 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 compiler that turns 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 system, 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_casting 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(&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.

18
  • 13
    A few notes: (1) It is not currently possible to compile glibc itself with any compiler other than GCC. (2) It is not currently possible to compile glibc itself with link-time optimizations enabled, because of precisely these sorts of cases, where the compiler will see UB if inlining is allowed to happen. (3) CHAR_BIT == 8 is a POSIX requirement (as of the -2001 rev; see here). (4) The C fallback implementation of strlen is used for some supported CPUs, I believe the most common one is MIPS.
    – zwol
    Commented Aug 27, 2019 at 15:30
  • 1
    Interestingly, the strict-aliasing UB could be fixed by making use of __attribute__((__may_alias__)) attribute (this is non-portable, but it should be fine for glibc).
    – null
    Commented Aug 27, 2019 at 21:59
  • 1
    @SebastianRedl: You can read/write any object through a char*, but it's still UB to read/write a char object (e.g. part of a char[]) through a long*. Strict aliasing rule and 'char *' pointers Commented Aug 28, 2019 at 7:11
  • 1
    The C and C++ standards do say that CHAR_BIT must be at least 8 (q.v. Annex E of C11), so at least 7-bit char is not something a language lawyer needs to worry about. This was motivated by the requirement, “For UTF−8 string literals, the array elements have type char, and are initialized with the characters of the multibyte character sequence, as encoded in UTF−8.”
    – Davislor
    Commented Aug 28, 2019 at 14:36
  • 2
    Seems this analysis is a good basis for proposing a patch making the code more robust in the face of currently disabled optimisations, aside from making an awesome answer. Commented Aug 28, 2019 at 21:08
66

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


I also think that this answer above is a much clearer and more detailed discussion.

40

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.

10
  • 6
    That makes a very nice illustration of the different values being optimized in OpenBSD vs GNU tools.
    – Jason
    Commented Aug 26, 2019 at 23:42
  • 14
    It's glibc's portable fallback implementation. All the major ISAs have hand-written asm implementations in glibc, using SIMD when it helps (e.g. on x86). See code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/… and code.woboq.org/userspace/glibc/sysdeps/aarch64/multiarch/… Commented Aug 27, 2019 at 3:55
  • 4
    Even the OpenBSD version has a flaw that the original avoids! The behaviour of s - str is undefined if the result is not representable in ptrdiff_t. Commented Aug 27, 2019 at 4:24
  • 2
    @AnttiHaapala: In GNU C, the max object size is PTRDIFF_MAX. But it's still possible to mmap more memory than that on Linux at least (e.g. in a 32-bit process under an x86-64 kernel I could mmap about 2.7GB contiguous before I started getting failures). IDK about OpenBSD; the kernel could make it impossible to reach that return without segfaulting or stopping within the size. But yes, you'd think defensive coding that avoids the theoretical C UB would be something OpenBSD would want to do. Even though strlen can't inline and real compilers will just compile it to a subtract. Commented Aug 27, 2019 at 4:33
  • 2
    @PeterCordes exactly. Same thing in OpenBSD, e.g. i386 assembly: cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/i386/string/…
    – dchest
    Commented Aug 27, 2019 at 15:32
35

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

3
  • Or... If I'm finding that I'm doing a lot of string based processing and there is a bottleneck, I'm probably going to implement my own version of Pascal Strings instead of improving strlen...
    – Baldrickk
    Commented Aug 27, 2019 at 14:41
  • 1
    Nobody asks you to improve strlen. But making it good enough avoids nonsense like people implementing their own strings.
    – gnasher729
    Commented Aug 27, 2019 at 21:12
  • 1
    strlen() is sometimes overused. Commented Aug 29, 2019 at 0:28
26

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.

3
  • 1
    Of course the optimizer is highly likely to unroll or auto-vectorize this loop, and the pre-fetcher can trivially detect this access pattern. Whether these tricks actually matter on modern processors would need to be tested. If there is a win to be had it is probably using vector instructions.
    – russbishop
    Commented Aug 26, 2019 at 22:03
  • 7
    @russbishop: You'd hope so, but no. GCC and clang are completely incapable of auto-vectorizing loops where the iteration count isn't known ahead of the first iteration. That includes search loops, or any other loop with a data-dependent if()break. ICC can auto-vectorize such loops, but IDK how well it does with a naive strlen. And yes, SSE2 pcmpeqb / pmovmskb is very good for strlen, testing 16 bytes at a time. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html is glibc's SSE2 version. See also this Q&A. Commented Aug 27, 2019 at 3:51
  • Oof, that is unfortunate. I'm usually very anti-UB but as you point out C strings require the technically UB end-of-buffer read to even allow vectorization. I think the same applies to ARM64 since it requires alignment.
    – russbishop
    Commented Aug 28, 2019 at 23:42
1

why wouldn't something like the following work equally good or better?

// OP's code - what is needed to portably function correctly?
unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

OP's code has functional errors.

Easy enough to amend though.


In writing portable code, care is needed to first get the function correct and then look to performance improvements.

Even the very simple, seemingly correct code can be functionally flawed.

Type

A string length is in the range of size_t which may differ from unsigned long. Problem with function signature as does not match size_t (*f)() = strlen. Problem with uncommon platforms where ULONG_MAX < SIZE_MAX and the string length is enormous.

const

s should be const char *.

Non-2's complement

(This concern affects a vanishingly small number of processors today so is really only of pedantic concern. Non-2's complement will likely get spec'd out in the next C (C23?)).

The s[i] != '\0' may trigger on -0 when char is signed and not 2's complement. It should not. str...() function as if the characters are accessed as unsigned char.

For all functions in this subclause, each character shall be interpreted as if it had the type unsigned char (and therefore every possible object representation is valid and has a different value).


To repair these aspects of OP's simple code

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

Now armed with a better, portable strlen() candidate, look to comparing it to the "complicated" alternatives.

2
  • @JimBalter C library has "For all functions in this subclause, each character shall be interpreted as if it had the type unsigned char (and therefore every possible object representation is valid and has a different value)." for string functions. String processing should not interpret a -0 as a null character and instead access that byte via unsigned char *.
    – chux
    Commented May 24, 2022 at 10:50
  • @JimBalter "A string is a sequence of char (signed or unsigned, depending on the implementation)" is a spec mis-quote. C lib has "A string is a contiguous sequence of characters terminated by and including the first null character." C library treats characters as some unsigned type, even when char is signed. Example: <ctype.h> “value of which shall be representable as an unsigned char”, and <stdio.h>: “int argument is converted to an unsigned char, and the resulting character is written.”
    – chux
    Commented May 24, 2022 at 10:51
-7

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

2
  • 5
    How does this answer the question?
    – S.S. Anne
    Commented Aug 28, 2019 at 0:28
  • 1
    The question in OP was "wouldn't this simpler code work better?", and that is a question that isn't always decided on technical merit. For a project like GNU, avoiding legal pitfalls is an important part of code "working better", and "obvious" implementations of strlen() are likely to come out similar or identical to existing code. Something as "crazy" as glibc's implementation can't be traced back like that. Considering how much legal wrangling there was over the rangeCheck — 11 lines of code! — in the Google/Oracle fight, I'd say the FSF's concern was well-placed.
    – Jack Kelly
    Commented Aug 28, 2019 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.