3 ms·

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

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

saagarjha 7y ago
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/strlen.S 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).
compiler-guy 7y ago
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.
BeeOnRope 7y ago
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.

saagarjha 7y ago

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/strlen.S 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).

compiler-guy 7y ago

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.

BeeOnRope 7y ago

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.