last day (16 days later) » 

12:10
108
A: Why is strlen so complex in C?

Antti HaapalaTL;DR 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: unsigned long is either 4 or 8 bytes bytes are 8 bits a pointer can be c...

user11954200
wow, this is super helpful. Thank you so much for taking the time to write this up. I hope it will be very helpful to others as well. Cheers.
The internals of a compiler lib lives in its own word though, where they can make assumptions about size, alignment, aliasing etc that application programmers cannot. The lib will be compiled with its own non-standard setup and they need not necessarily have portability in mind. All of this assuming that the lib programmers know what they are doing - we have to assume as much, but that's not always the case, particularly not with open source.
@Lundin Hence "you should never write code like that - especially if you're not a C compiler / standard library vendor"... :D
jpa
jpa
Eh, efficiency is sometimes important even if you are not writing a standard library. And furthermore, most projects do not need to be portable, they can take advantage of specific platform in optimization. The real lesson is to only write such code when it really has a measurable benefit.
This answer makes a number of false statements, starting with the first sentence. (a) People do at times need code like this, when performance is critical, and it is false they should never write it. It should be written when needed and can be written with the necessary definitions and requirements provided by a C implementation.
12:10
The standard library makes the assumption that a word-sized access at a word-aligned address is either completely valid (although possibly with undefined contents in some bits) or completely invalid. That assumption holds on any machine where memory protection granularity is larger than the word size. This is machine knowledge you do not have in portable code though.
(b) It is false that the behavior of accessing the string past the terminator is undefined in a general sense. It is true that the behavior of accessing the string past the terminator is not defined by the C standard. But it is defined by other things, such as the combination of the virtual memory architecture, the fact that the address is deliberately aligned, and the properties of the specific compiler that this code is designed for—the virtual memory architecture guarantees a different byte in the same aligned four- or eight-byte unit cannot have a different memory mapping.
(c) It is false that the only way to implement strlen correctly is the way it is written in the question. The C standard permits and invites extensions. It defines strictly conforming code to use only the features specified in the C standard but also defines a conforming program as one that is acceptable to a conforming implementation. It is correct to write conforming programs that use the features of their specific C implementation(s). C programs that use extensions may be correct C programs.
@EricPostpischil cool, perhaps you should write an answer then. By the way did you notice that this program was supposedly for an older version of Glibc that is supposed to complement GCC, and I showed that it was not acceptable to GCC.
@AnttiHaapala: First, whether the code is acceptable to the current GCC has no relevance to the falsity of the various statements in this answer. Second, yes, I did miss where you showed it was not acceptable to GCC. You showed that -fsanitize=undefined and -fsanitize=address produce diagnostics, but that does not mean the code is unacceptable to GCC, especially if it is library code deliberately intended for use with a specific implementation. Third, “perhaps you should write an answer then” does not remedy the defects in this answer.
If the statements in this answer were correct, the majority of commercially useful or otherwise productive C programs could not be used. Most such C programs use extensions of various sorts. It is essentially impossible to do anything other than pure abstract computing in strictly conforming C. If it were correct one should not use implementation-defined behavior or behavior not defined by the C standard, one could not link to libraries not written in C, nor write operating systems or parts of them in C, nor write programs to interact with devices. The position this answer takes is absurd.
It is one thing to use extensions of various sorts. Here the code is not using documented extensions but just got high hopes that it can get away with what ever dirty tricks it is doing.
You just lost the argument. Because now you are arguing about whether this particular code for strlen used documented extensions or not. And that is just a matter of whether this author used various information—not whether one “should never write code like that” or “you don’t need” it. I do not care about this particular strlen. I do care about spreading false information about the C standard and telling people it is only permissible to write fully-portable strictly conforming code. As I stated, the various statements in this answer I call out above are false.
12:10
Out of curiosity, have you tested the crazy strlen vs a more simple implementation, to see if all the magic numbers and bitwise logic and whatnot actually works (in the sense of being faster)? I've seen plenty of examples where the complicated "optimised" code is actually slower than writing straight-forward code and letting the compiler deal with it...
@SimonLundberg, it works, it's about ~7,6 to 7,8 times faster than the simple version on my machine (64-bit, surprise), the code is there, you can test it too if you want to. The source file says "This file is part of the GNU C Library." with dates from 1991 to 2003. I'd be very surprised if glibc included a broken implementation of strlen() for 12 years.
The code might be there but my computer here at work doesn't have a C compiler installed. I'm only doing Python and (horror of horrors) JavaScript at the moment, so I suppose there wasn't a need for it. Also, I was more thinking along the lines of compilers being better these days. Thanks for testing it!
it is faster, but not by 7.6-7.8 if you optimize. Maybe 2-3 times. But the compiler-builtin strlen is >4 times faster than this on my x86-64.
@AnttiHaapala, whoops, I forgot there's no sane default for -O, sorry.
@AnttiHaapala You haven't shown that it was not acceptable to GCC, just that it was not acceptable to ASan by default. ASan makes looser assumptions about addressability (i.e. C/C++ spec) while GCC developers are free to consider stronger guarantees that their own compiler provides, while writing a non-portable algorithm to be used with their own compiler. There are plenty of other builtins that fail ASan/MSan checks that are perfectly fine because they're tied to a compiler with particular guarantees.
12:10
There's a reason why this is actually defined code. The underlying platform for all platforms targeted by glibc of itself defines that overrunning the end of the string reads an indeterminate value rather than invoking undefined behavior immediately.
@joshua there is no such thing as "invoking undefined behaviour"
Re "TL;DR you don't need and you should never write code like that...", That is just plain wrong. It might be true for people who don't write code where performance is an issue, but that's far from being everyone. It would be better to say that you shouldn't do it unless you know why you need to.
user1143634
Diagnostics issued by -fsanitize=, valgrind and etc do not prove anything. All standard functions that operate on memory trigger various diagnostics. Valgrind solves this by adding them to the white list.
"it should not be used anywhere instead of the system-provided strlen" — well, this code is the system-provided strlen for quite a number of systems. It's taken straight from the GNU C library, after all.
@Joker_vD that's not my strlen. My strlen is the one written in assembly/the compiler intrinsic.
12:10
@Joker_vD: no, that's an old version of glibc's portable code. Every ISA glibc cares about will also have multiple hand-written asm implementations that it picks from at dynamic-link time based on the CPU. e.g. SSE2 vs. AVX2. Using portable bithacks is silly when targeting x86-64. SSE2 is baseline for that ISA, making it easy to check 16 bytes at a time. (Or even unroll and or together 4 vectors from one cache line). e.g. like this simple SIMD strlen for aligned buffers: Why is this code 6.5x slower with optimizations enabled?
Also related: Is it safe to read past the end of a buffer within the same page on x86 and x64? : yes in asm if you don't cross into an unmapped page, and sort of yes in C++ if you make sure the compiler doesn't see compile-time UB. An aligned load that contains any valid bytes can't fault. My answer there has links to glibc's various x86 strlen strategies.
Since it's part of the compiler package, it's obviously designed to work with how that specific compiler generates code, i.e. how it defines the behavior that is not defined by the standard. IOW, it's its own dialect of C that you could call "compilerese", not Standard C, and hence it better stay buried in the internals only (Heck, even in that case, it seems kind of scary to think that that thing is "lurking", in a sense, in every program made with that compiler).
@Peter Cordes : I think then that the safer and wiser approach would be that if you're going to exploit that many hardware-specific machine hacks, you'd be better off coding the library function in pure hand-written assembler. "pushq %%rbp" blahblah. Then you can make the compiler 100% strict Standard-compliant and hence robust.
@The_Sympathizer: Glibc and GCC are separate projects. e.g. glibc can (I think) be compiled by clang, and GCC can use different standard libraries (e.g. MinGW). It's more like it's a hack that "happens to work" on GCC when it can't inline into the caller and lead to strict-aliasing UB. I guess you can call that a dialect, but it's not like that code is even safe in general if it can inline.
@Peter Cordes : Yep, hence why I'd suggest better to nuke that puppdog and rewrite it in direct, pure assembler if you really want to try and "optimize" it using machine-specific assumptions. You already kill portability the moment you do that anyways, and you have to have a directory for each target architecture anyways...
Heck, sheesh! This could be a ticking bomb!
@The_Sympathizer: yes, like I said that's exactly what glibc does. e.g. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html has the SSE2 version using pminub (not por like I said earlier: you need to detect any zero, not all-zero. pminub does that nicely). You could also safely take advantage of x86 SIMD using Intel's C intrinsics, but hand-written asm lets you control the unrolling and also the branch layout. And asm makes C UB a non-issue.
@Peter Cordes : Yep. Then, is this code piece still used or not?
12:10
@The_Sympathizer: Looks like code.woboq.org/userspace/glibc/string/strlen.c.html is still present in current glibc source as a fallback. (At least it's still in the source tree; IDK if it ever gets actually used). It's still safe for use as libc strlen, though. Compilers can't inline code from shared libraries. When gcc does inline strlen, it's not this C source, it's GCC's own internal __builtin_strlen which is something different.
@Peter Cordes : Then I'd suggest that the fallback be replaced with a straight, sane implementation that is strictly Standard C compliant (i.e. only a few lines as others have pointed out).
Because, as I was going to tell @Lundin, the problem here is this thing is effectively, depending on how you approach it, either a ticking bug bomb if when changing the internals of the compiler you make the delicate balance of assumptions it rests upon break, or conversely a nasty little ball-and-chain that locks you in to those assumptions.
@The_Sympathizer: glibc has unit tests. If it breaks with a new compiler version, the self tests would (hopefully) fail. I don't think most people would be happy with a version that's 2 to 3x slower; gcc doesn't know how to auto-vectorize loops where the trip-count isn't known ahead of the first iteration. (i.e. it can't auto-vectorize a naive strlen). Until that changes, I don't think enough people would be willing to make glibc worse on the few ISAs without a hand-written strlen. I think you're greatly overestimating the possibility of actual breakage.
@The_Sympathizer: you mean like the Linux kernel's old memcpy that violated strict aliasing? gcc, strict-aliasing, and horror stories A new GCC version broke that code, but I think the bug was detected by developers before it caused any widespread harm. And that was when strict-aliasing optimization was new, and Linux was using a CPP macro.
The only way it's plausible for the strict-aliasing UB here to cause any problem is if you compiled glibc with link-time optimization and statically linked it into a program that you'd compiled with -fno-builtin-strlen. Nobody does that. (Normally gcc treats strlen as a builtin and only emits a call to the libc implementation when it's not going to inline. Strict-aliasing UB can't be a problem across asm call/ret boundaries because bytes in memory are just bytes.) It sounds like you know enough about compilers to be cautious but not enough to understand why this isn't very fragile.
What is more, a good compiler could even replace code written as <naive version of strlen> -> Would you mind showing a simple compiler which replaces that bit of code by a builtin version of strlen? Since when are whole ASTs replaced by completely independent ASTs that in the eye of humans are equivalent (and I don't mean strength reduction optimizations)? Also I vote -1, as this is a huge rant of questionable advice, and not a clear, concise answer as to why the long version of strlen is like that.
12:44
@jpa You really are asking for trouble, if you rely on Undefined behavior for efficiency. You have to be extra sure the behavior is actually, really defined by the compiler (which may be difficult, you basically need to find a compiler flag to enable the behavior). Otherwise, the moment you change optimization options or upgrade the compiler, the Undefined Behavior might be something completely different.
13:36
@EricPostpischil Can you stop with the lawyer bullying? You're being ignorant and unhelpful.
14:06
@SpiritBob: The false statements made in the answer are harmful and should be challenged. The present wrong information about how C can be and should be used—information that is not only wrong sometimes but is actually wrong in the MAJORITY of C programs outside of student assignments. This is not a matter of lawyering with no practical effect but of actual practice.
2
@SpiritBob: “The present” should be “They present”.

  last day (16 days later) »