Why is strlen so complex in C?

Re:Why is strlen so complex in C? by saagarjha on Monday August 26, 2019 @05:54PM (#20804171)

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.

[ Parent | on HN ]

Re:Why is strlen so complex in C? by xenadu02 on Monday August 26, 2019 @06:10PM (#20804285)

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

[ Parent | on HN ]

Re:Why is strlen so complex in C? by compiler-guy on Monday August 26, 2019 @06:36PM (#20804429)

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.

[ Parent | on HN ]

Re:Why is strlen so complex in C? by saagarjha on Monday August 26, 2019 @06:24PM (#20804369)

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

[ Parent | on HN ]

Re:Why is strlen so complex in C? by BeeOnRope on Monday August 26, 2019 @08:28PM (#20805107)

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.

[ Parent | on HN ]

Re:Why is strlen so complex in C? by kelnos on Wednesday September 04, 2019 @12:04AM (#20873901)

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.

[ Parent | on HN ]

Re:Why is strlen so complex in C? by saagarjha on Thursday September 05, 2019 @12:56PM (#20888576)

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

[ Parent | on HN ]