Why is strlen so complex in C? | Hacker News Reader

Why is strlen so complex in C?

stackoverflow.com

63 pointsazhenley73 comments

The accepted answer fails to understand that the standard library is exempt from following the C standard and makes a number of false or overly prescriptive assertions. (It also doesn't answer the question, but that's par for the course on Stack Overflow…)

The first comment on that answer mentions this.

I would never take an answer on SO w/o a grain of salt w/o reading comments.

>that's par for the course on Stack Overflow

This is tangential to the meat of your comment but I feel compelled to nitpick based entirely on personal anecdote: I have been helped hundreds of times on StackOverflow by people who had nothing to gain from it and yet provided in depth, insightful answers. In my experience, the farther you get away from the big, overwhelmed tags, the better the quality is. But you don't want to get so obscure that you are just ignored.

The Racket community on SO is particularly fantastic, and (in my experience) the more 'web' related your question is, the worse answers you get.

Yes, I'm not saying that Stack Overflow doesn't have "birdies". For example, I really enjoy this user's consistently high quality answers: https://stackoverflow.com/users/224132/peter-cordes

He once answered a question of mine about recursion with x86!

Agreed. Parent commentor is statistically wrong. A large number of SO answers are helpful but he found an anecdote to wrongfully preach generalization. Also, OP's question violates SO guideline in the sense that answer to this question would be highly opinionated.

> The accepted answer fails to understand that the standard library is exempt from following the C standard

I didn't read it that way at all. Consider the audience: the questioner admits that they are new to C. Because of that, the author of the accepted answer wanted to make it crystal clear that code like this should never be written "especially if you're not a C compiler / standard library vendor". The answerer explicitly acknowledges that the code depends on implementation-defined behavior.

IMO, the answer is great. It starts with a strong warning to never write code like that in your own programs (which you shouldn't), and then explains how it works, and why it works in the context of where it's written.

s/especially/unless/: there is a good reason why the strlen is written that way; it's because it's fast and the standard library is allowed to make assumptions about the platform it's running on. But the answer instead dilutes itself and keeps saying things like "supposedly" and calling the code "bad", along with a long tangent by using the sanitizers to "prove" that the code is "wrong". For a beginner, I feel that this answer is much better than the one that's accepted: https://stackoverflow.com/a/57655203/5230900. It's not as long, so it would be nice to have more details about why the code does what it does, but it's not pushing an agenda.

> it's because it's fast

Is it? We have to ask a few questions:

1. Is it actually faster on today's CPUs? (Any linear memory access pattern is going to be detected by the prefetcher)

2. Would the compiler do the same or better? eg, could it be auto-vectorizing the loop if we didn't play tricks?

3. If we really care about trading complexity for speed, wouldn't a hand-written SSE/SSE2/AVX implementation be even faster? Why not spend our complexity budget there?

Honestly, I don't know: I trust that the glibc people know what they are doing. However, in an attempt answer some of your questions: there is an SSE2 implementation available that might be used on computers that support it: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/s... . Perhaps this version is for platforms that don't have a hand-optimized implementation? I'm not sure if the compiler is smart enough to auto-vectorize an arbitrary strlen implementation (or delegate it to a library call).

Most c libraries have architecture-specific, hand-written assembly copies of strlen and have had them for decades. This includes glibc, almost from the day this particular function was checked in.

In other words, there actually is an SSE/SSE2/AVX implementation in glibc.

This copy in plain C is the fall-back to if the porter didn't implement strlen in assembly for the architecture they were porting to.

It is a reasonable guess at a somewhat architecturally-independent fast implementation. If someone really cares about squeezing all the performance they could out of strlen, they implement the assembly version.

Beyond that, many architectures that gcc supports don't include prefetchers, vector units and all the rest. The world is not all x86.

1) Yes, about 4-6 times faster than byte-by-byte loop "in the long run", but not for short strings.

2) Mostly not. gcc and clans don't vectorize "search loops" i.e. loops that terminate early based on some condition. These loops are tricky to vectorize at least partly because of the reading-beyond-the-end issue mentioned in the accepted answer. icc does vectorize some search loops, not sure if it would do a good job on this one. I'm not sure about MSVC, but it's usually way behind on everything optimization related so I think we can assume not.

3. Yes definitely. glibc has such implementations for popular platforms like x86, so this code isn't actually being used on your PC say.

I agree with the answerer that the code is bad. If anyone wrote that anywhere in any code base where I have review responsibility, I would never +1 that.

For deep in the bowels of a compiler or libc, where developers might think it's useful to optimize code that has to be run in a huge variety of impossible-to-predict types of workloads, I'm more sympathetic, but it's objectively not good code. It might be useful and necessary in this very very narrow context, but it's far too clever to be good.

The answerer may have been a bit heavy-handed in knocking it down, but I think it was entirely appropriate when helping to educate someone who is new to C.

I agree that the other answer you link to is probably better, with the caveat that I'm disappointed that there's no warning against writing code like that in the general case. The sentence that starts with "They make assumptions..." is IMO not strong enough to point out that the strlen() code referenced relies on implementation-defined behavior and is not even remotely portable C.

FWIW, here's a better answer that was written later: https://stackoverflow.com/a/57676035/5230900.

The accepted answer fails to note that the subject code is a high-performance variant of strlen(), and has basically taken the ideas from many highly-optimized memcpy() routines.

There is nothing wrong with the simpler version, but it’s not as fast (for longer strings).

Optimization hacks aside, I swoon at the simple (and verified) seL4 implementation (note strNlen):

  word_t strnlen(const char *s, word_t maxlen)
  {
      word_t len;
      for (len = 0; len < maxlen && s[len]; len++);
      return len;
  }

http://sel4.systems/

https://github.com/seL4/seL4 (from file src/string.c)

The trailing semicolon on that for loop is quite load-bearing. I would have some code review feedback.

Looks very simple to me. I love it.

It can be replaced by continue; in this specific case.

Nope, for sure not.

A good implementation would stick to the standard (size_t nor word_t), and would inc the pointer, not the counter. Formatting would be better (the final ; ouch).

This is junior stuff.

Maybe verification tools choke on pointer incrementing?

Having worked on a variety of code bases and coding styles, I think if there are coding rules and they are consistent across all the source files, it becomes easy to read even with wierdnesses. I hated perl with @_ and $_, but after working with it enough they became known quantities.

And you can probably read all the lines of code in your lifetime, since the whole microkernel is ~30k lines of code.

It's worth pointing out that the author was reading an outdated implementation of strlen() from glibc. The generic implementation is still here with the same code, and would be complied if no ARCH-specific implementation is written, as seen here, https://github.com/bminor/glibc/blob/master/string/strlen.c.

But it's probably irrelevant to most systems today, as the assembly version is almost always used, e.g.

* i386: https://github.com/bminor/glibc/blob/master/sysdeps/i386/str...

* i586/i686: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i58...

* i686 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68...

* i686 w/ SSE2 + BSF: https://github.com/bminor/glibc/blob/master/sysdeps/i386/i68...

* x86_64 w/ SSE2: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/s...

* ARM: https://github.com/bminor/glibc/blob/master/sysdeps/arm/strl...

* ARMv6: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv...

* ARMv6T2: https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv...

* ARMv8a/AArch64: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/...

* ARMv8a/AArch64 w/ ASIMD: https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/...

etc.

I was wondering how it would compare to the code produced by auto-vectorization, I guess it doesn't matter with hand-crafted assembly.

https://godbolt.org/z/QP3H-d

There isn't any auto-vectorization. Clang & GCC both do basically the same thing here.

The compiler can't autovectorize because it can't assume it's okay to read past the end of the string. Only the human or the machine can make that determination, using special knowledge about the environment, such as that when locating the NUL byte out-of-bounds reads are okay so long as they don't cross a page boundary. And "okay" is a stretch because tools like Valgrind ship with huge lists of manually maintained suppressions to account for hacks like this that violate the standard rules.

But in this case a human applied their special knowledge in glibc, what's stopping the human applying the same knowledge to the compiler itself for this specific OS/arch?

Primarily because it would make it more difficult to detect and debug out-of-bounds reads, so at the very least it's not something you'd want to do by default, even at high optimization levels.

Possibly it might also be an awkward, complex, or dangerous (as in risk of unintended consequences) optimization to selectively violate the memory model that way. But I'm not familiar with the internals of optimizing compilers, so that's just conjecture.

Have there been any efforts to add real string types and maybe arrays to C? Seems a lot of complications come from the primitive/not existing implementation of strings and arrays.

It's such a shame that C gets some things like strings so wrong.

Writing in C shouldn't have to be so painful, but I guess they were the pioneers in a lot of things and the "high level assembly" idea stuck. (Premature optimization?)

Also having objects and method calls, even if it's syntactic sugar deep down, is the best kind of syntactic sugar

I think you're looking for C++, or maybe Rust.

There was nothing "premature" about C's "high-level assembly" idea. It is somewhat archaic now, but C took off because it was so, so much better than normal assembly.

If handling strings in plain C is hard, handling them in assembly is 10x as hard.

repne scasb disagrees with you :)

As would many other assembly instructions on many other architectures.... and thereby proving my point. :-)

This is kind of the point of C. It maps directly to the hardware. There are very few decisions the compiler has to make about the code. And it is for that reason that C does not allow for higher level abstractions. On one hand, it is a pain to write. On the other hand, you know exactly what is going on under the hood and nothing is ever going to stop you from shooting yourself in a body part of your choice :)

> This is kind of the point of C. It maps directly to the hardware.

No it doesn't. It didn't in the past, it was a high-level abstraction. And it doesn't today, because CPUs don't behave at all like C's defined virtual machine.

> CPUs don't behave at all like C's defined virtual machine

What "virtual machine" are you referring to?

The one defined in the standard.

One that ISO 9899 refers to as its abstract machine.

C gives the illusion of mapping to the hardware. Hardware manufacturers have moved heaven and earth to help maintain the illusion. It finally got too hard and they had to admit atomics and cores ro the model. The next watershed will be along soon enough, but the ability to present as a C machine has long been the gateway to success or failure of a new hardware architecture. Myriads of arguably superior machine designs have foundered on "but can I code for it in C?"

How can it map directly to the hardware and be portable at the same time?

C's model is great for implementing complex, efficient data structures. Pointers are an amazing abstraction. But in many respects strings are the antithesis of a data structure, and unsurprisingly C falters hard. The problem is that most programmers don't build data structures; they build Rube Goldberg machines for munging strings, even when they're using low-level languages.

Data structures to most programmers are things you import into your Rube Goldberg machine. They don't understand that good programs are made of layers of meticulously crafted, bespoke data structures where the final product is effectively one giant data structure tailored for a particular task, with interfaces to match.

It follows that good C programs don't do very much strings munging even if all they do is process text. The text is systematically atomized from the very beginning. The same is true for good programs in any other language.

"It's such a shame that human beings get some concepts like strings so wrong." - C language

Strings are "unnatural" to the binary system, it's a human concept.

None that have succeeded, obviously. There are a number of alternative string libraries, though; here's one: https://github.com/antirez/sds. And I'm sure some programmers would suggest C++ as the real "effort to add real string types and maybe arrays to C" ;)

I, in fact, do suggest C++ as the right answer, where it is not precluded for practical or silly reasons.

It is generally quite easy to compile a C program with a C++ compiler, and then the sky's the limit on code improvements. I recommend it, and suggest starting with improvements to memory safety.

There is really no excuse for writing a new C program anymore.

An 8-bit microcontroller where memory is constrained and all the vendor libraries are written in C, is a good example.

Your 32-bit ARM M3/M4 cores are probably crossing that line where the memory cost of using C++ is worth it, but I would say there are still real world reasons to use C.

Though I would love to see more microcontroller vendors (or any) support C++ or Rust as part of they HAL libraries, but I think you will still find C to be perfectly viable for the low cost microcontroller application.

If it's too small for C++, it's also too small for C. Arduino is 8 bits, and it's C++ from here to the horizon.

On ARM it is no contest, at any size.

Funny little $.10 PICcy things may not have a C++ compiler available. Then, the C compiler is better than asm, if you can fit. Otherwise, no excuse.

On Arduino, from my experience, it is easy to run into memory constraints, especially when using dynamically allocated memory like strings. And I'm taking about both the flash memory for code and the ram for data, stack, and heap.

I don't think C is always a win, but to say to never use for new projects seems overly biased. Why is your opinion about C so strong? I am curious.

Simply this: if you write C code, it produces the same instructions compiling with a C or C++ compiler.

But a C compiler restricts you to the C subset. Many of the most useful features of C++ generate no extra instructions, but make the code more maintainable. There are libraries that compile to no code except exactly what you call, optimized down to exactly the circumstances of the call, wholly inexpressible in C, that you would have to open-code directly in C, gaining no benefit from the maturity of a library.

In other words, in the absolute worst case, you write the program using only C features, and get the same program. But there is never a reason to opt for the absolute worst case when you have a better choice.

Okay, I think this reply helps frame your stance much better. You are not necessarily proposing no C ever, but saying at least start a new project with a C++ compiler / IDE and if there are reasons to use C code or rules like "don't use dynamic memory allocation", when there is a substantial reason, then that is acceptable

There is no connection between C++ and dynamic memory allocation. Most of my C++ programs allocate memory at startup, then run for weeks or months (on machines with 200+ GB of RAM) never allocating ever again. C programs routinely allocate dynamic memory, except where there is reason not to; likewise C++.

So, no, there is never a reason to confine yourself to the C subset, in a new program. "for (auto e : v)" is universally better than "for (i = 0; i != N; ++i)". Zero cost, better code.

But I would never, ever suggest using an IDE, under any circumstances, for any language.

We had that effort in C++. As we saw it backfired. C++ stdlib strings are so overengineered that they are much slower and bigger in the general case.

What? C++ strings have an overhead of 16 bytes+the space left in the backing buffer. That’s really not all that much.

16 bytes is in no way guaranteed by the standard.

Of course–the implementation is free to do whatever it likes. But all reasonable ones will either use a three pointer (or some combination of a base pointer and pointers/integers representation bounds) or include a small buffer for SSO that overlaps with the storage for heap bounds.

Sure, Microsoft has added plenty of them over the years...

- BSTR

- CString

- bstr_t

- basic_string

- and a bunch of typedefs...

In theory the standards committee could decide to add _array_ref to the language (or some variation on pointer+length). &myArray[10] could create an _array_ref where sizeof works against it and attempts to take a slice past the end of the array abort. I can even imagine compatibility shims like __attribute__((array_ref(1,2))) similar to printf-style format decorators that tell the compiler how to map function parameters of pointer+length to _array_ref.

There are many technical details to be worked out and choices to be made but there is no fundamental intractable problem preventing it. We'd have incremental adoption over many years. Maybe some legacy code would never be updated.

The primary blocker is getting the committee members to admit this is a problem that should be solved. That is difficult enough here on HN, where some people are still arguing that C is fine as-is and we just need to invent better programmers / better tools.

Ultimately C's lack of better string support comes from its lack of better array support. That comes from a certain subset of the programmer community that believes the status-quo is fine and isn't interested in such changes.

It would be so nice if C had "fat pointers" (ptr+len). It's such an obvious small change that would have a massive impact on usability and safety.

Unfortunately, C is dead. Microsoft thinks C is dead, and intentionally keeps their compiler awful. Even ISO WG doesn't seem to have a vision for C's future and have been rearranging deck chairs for the last 20 years.

We already know C's future.

The people using old C are self-selected as those who like it the way it is. They accepted atomics because of new hardware. The place to ask for new, better stuff is at the C++ desk, and it has lots already.

Well, it has. You just said so, it's (ptr+len).

...it's the philosophy of the C language: There's minimal bloat on the upside, but you have to know what you're doing and how to be able get it on the downside.

That's like saying C doesn't need pointers in the type system, because it already has pointer-sized integers (BCPL actually had that philosophy).

Slices greatly improve interfaces. Especially if you want to return a (sub)slice of something, C doesn't have any non-clunky solution.

I wouldn't call ASCIIZ arrays "strings" anymore. Strings need to be nowadays all unicode, where most use utf-8. None of that is in the standard. Only very minor unicode support and no utf-8.

If you mean string as in text string, it's not done and I doubt it could ever be achieved in C++. It's too complicated because of unicode and string encoding aspects.

The new type wouldn't be usable either, because it would have to be converted down to another representation all the time when calling functions and libraries that are not aware of it. Think of C string to C++ string to boost string to whatever.

I think the closest usable thing is QString if you are using Qt.

Length counted, sliceable arrays would be sufficient to upgrade C. D has these.

As for arrays, I frequently find implementations of hash maps and linked lists that come with macros for iteration, appending, etc. libnih is the first to come to mind (GPLv2 only), but I also know that the LXC project has some similar code floating around in there... probably LGPLv2+.

It wouldn't surprise me if the "unoptimized" strlen is just as fast or even faster on modern x86 hw. Both algorithms need to process the same amount of data. Thus they will fetch exactly the same number of cache lines from main memory. Likely, the cost of fetching those cache lines dominates, meaning that it doesn't matter that the "unoptimized" version does more processing per byte. Only way to find out for sure is to run the benchmarks.

Curious to know if this still holds for hyperthreads (i.e. all? modern clouds)

I would expect a vectorized implementation to perform better than this one.

The optimized implementation might use less power, though. With a slower algorithm, the CPU isn't the bottleneck, but it might still have more work to do.

At least on one ARM platform, I can clear/copy memory faster (perhaps 2-3x) with NEON intrinsics than with a byte adressing inside a for() loop.

It's not even close. A per-byte loop is going to be be 4-6 times slower than the 8-byte chunks + a little math shown in the question.

Let's say that all the stars align and you process an entire iteration of the byte-by-byte loop in 1 cycle. On a 4 GHz machine thats ... 4 GB/s. That's paltry compared to main memory bandwidth of 30-100 GB/s [1], not to mention say L1 bandwidth of ~ 256 GB/s (available to a single core).

This idea that everything is memory limited it just false: it's pretty hard to write code efficient enough that it can be limited by memory _bandwidth_ on a single core.

---

[1] Admittedly, a single core can usually only access 20-30 GB/s of that, but that's still >> 4 GB/s.

Did you benchmark it? I did and found that on a Core-M with MSVC, the optimized strlen beats the naive one by about 20% and on Xeon with gcc, by about 40%. Depending on string length and other parameters. I would expect the difference to be smaller on more recent processors. But without benchmarking I don't think you can say.

Yes, I have benchmarked it in the past which is where I got the 4-6x figure from. Maybe it's worth a revisit, but unless the compiler is doing something special with the byte version, I would be surprised if the speedup was much less.

You may have to unroll both to get max speed.

If you could share your benchmark I would be interested to look at it.

Benchmarks are always worth revisits. Mine is here https://github.com/bjourne/c-examples/blob/master/programs/s...

Reply on news.ycombinator.com