Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why is strlen so complex in C?

stackoverflow.com

Post reply on HN
Print view View original

21–30 of 74 posts

Re: Why is strlen so complex in C?

#21

Post by kevin_thibedeau »

user5994461 wrote: post #19
Ididntdothis wrote: post #2

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.

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…

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

Re: Why is strlen so complex in C?

#22

Post by compiler-guy »

xenadu02 wrote: post #16
saagarjha wrote: post #14

Earlier quoted context omitted.

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 t…

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

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.

Re: Why is strlen so complex in C?

#23

Post by bcaa7f3a8bbc »

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.

Re: Why is strlen so complex in C?

#24

Post by MadWombat »

raverbashing wrote: post #4
Ididntdothis wrote: post #2

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

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

Re: Why is strlen so complex in C?

#25

Post by bjourne »

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.

Re: Why is strlen so complex in C?

#26

Post by pornel »

xenadu02 wrote: post #18
Ididntdothis wrote: post #2

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.

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 paramet…

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.

Re: Why is strlen so complex in C?

#27

Post by zamalek »

bcaa7f3a8bbc wrote: post #23

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:…

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

Re: Why is strlen so complex in C?

#28

Post by slovenlyrobot »

bjourne wrote: post #25

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…

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

Re: Why is strlen so complex in C?

#29

Post by kllrnohj »

zamalek wrote: post #27
bcaa7f3a8bbc wrote: post #23

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:…

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.

Re: Why is strlen so complex in C?

#30

Post by kllrnohj »

MadWombat wrote: post #24
raverbashing wrote: post #4

Earlier quoted context omitted.

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

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.

Post reply on HN