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

Glibc's strlen implementation: Probably not what you'd guess

sources.redhat.com

Post reply on HN
Print view View original

21–30 of 74 posts

Re: Glibc's strlen implementation: Probably not what you'd guess

#21

Post by tptacek »

axod wrote: post #12
yan wrote: post #8

Earlier quoted context omitted.

I agree, but I'm sure a gigantic portion of developers never have to worry about this. Also, most architectures have efficient SIMD instructions to handle things like strlen. I'm just curious if the speed-up of this hack was ever benchmarked. Or if anyone spent a while tracking down a source of bottlenecks, and found it to be an inefficient strlen implementation.

You could do this on x86 as a single instruction rep scasb Unfortunately though, this is slower than comparing 4 bytes at a time yourself. Working bytes 1 at a time is pretty expensive. 4 at a time is great on a 32 bit cpu (As long as they're aligned).

For short strings (the common case), scasb performs the same as a smarter C loop, reduces code size, and saves branches (which is good for caching), which is why most compilers compile strlen to it automatically. But this is kind of a silly point since performant code doesn't call stlen often.

Re: Glibc's strlen implementation: Probably not what you'd guess

#23

Post by scott_s »

yan wrote: post #19
scott_s wrote: post #18

Earlier quoted context omitted.

Someone posted numbers that showed this is a 2x speedup over the naive implementation. That's not "trivial." Most developers don't have to worry about such optimizations. But this is Hacker News, and a lot of hackers do.

Point taken, and you're right. The speed-up I was referring to howeverwasn't "strlen speedup" but "your entire app running with naive strlen implementation, vs your entire app with clever strlen." I also wasn't saying this has no place in it. I was trying to add that these hacks aren't usually what makes your app execute twice as fast or feel more 'snappy', unless the bread and butter of your app is string processin…

Of course, that's Knuth's warning that "Premature optimization is the root of all evil." I assumed we've all heard that before, and we're only thinking about applying optimizations after measurement.

Re: Glibc's strlen implementation: Probably not what you'd guess

#24

Post by jws »

jws wrote: post #10

I'm not done, but I thought I'd share my quick benchmarks: 1 million strlens on the same random 100 byte string: Atom 330, 1.6GHz, gcc 4.3.2 (Debian Lenny) glibc: 1.3ns/char easy: 3.4ns/char obsd: 3.4ns/char Core2 Duo, 2.8GHz, gcc version 4.0.1 (Apple Inc. build 5484) libc: 0.12ns/char glibc: 0.39ns/char easy: 0.58ns/char obsd: 0.60ns/char easy: while ( *p++) c++; obsd: openbsd, for (s = str; *s; ++s); return s-str;…

And to add more mystery:

  1 million strlens on the same random 100 byte string:
    Pentium 4 3.0GHz, gcc 4.3.2 (Debian Lenny)
      glibc:   0.52ns/char
      libc:    0.60ns/char ???
      easy:    0.94/char
      obsd:    0.94/char
I would expect libc and glibc to match being a Debian machine, and they matched on the Atom 330. I can't account for the difference here, perhaps the difference in the Debian library compilation flags and my -O3 make a difference on this processor.

Don't tell the Gentoo crowd, you'll only encourage them.

Re: Glibc's strlen implementation: Probably not what you'd guess

#25

Post by tgos »

Sorry for asking such a stupid question, but isn't that code horribly broken? It assumes that the next 3 byte after a string are readable. What if I malloc'ed memory for the string in such a way, that the \0 is the last byte of the memory page and the next byte after \0 is on the next page, which is not mapped into my VM space? In such a case the CPU will throw a page-fault and the process will die because of SIGSERV or SIGBUS. Or is the glibc version of malloc padding all memory to have at least 3 byte beyond its last byte?

Re: Glibc's strlen implementation: Probably not what you'd guess

#26

Post by whughes »

yan wrote: post #19
scott_s wrote: post #18

Earlier quoted context omitted.

Someone posted numbers that showed this is a 2x speedup over the naive implementation. That's not "trivial." Most developers don't have to worry about such optimizations. But this is Hacker News, and a lot of hackers do.

Point taken, and you're right. The speed-up I was referring to howeverwasn't "strlen speedup" but "your entire app running with naive strlen implementation, vs your entire app with clever strlen." I also wasn't saying this has no place in it. I was trying to add that these hacks aren't usually what makes your app execute twice as fast or feel more 'snappy', unless the bread and butter of your app is string processin…

I think you're making a good point, but it's misguided here. We're talking about a 2x speedup for strlen on pretty much every Linux system and probably other systems as well. That's millions of machines. This optimization has probably saved untold amounts of computing time.

Re: Glibc's strlen implementation: Probably not what you'd guess

#27

Post by axod »

pchristensen wrote: post #16
axod wrote: post #2

Clever stuff. If you're interested in such things, best book I've seen is "Hackers Delight" http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201... Author covers really clever techniques to count bits, count non zero bytes like this etc etc. Bit manipulation at its best.

Holy crap, all 15 reviews of that book are 5 stars! That's the best average I've ever seen on Amazon.

I'd give it 5 also. It's a ridiculously clever fun book.

I agree with some of the reviewers though, the title probably means less people manage to find it than if it was called "Bit manipulation bible" or something.

Re: Glibc's strlen implementation: Probably not what you'd guess

#28

Post by gjm11 »

tgos wrote: post #25

Sorry for asking such a stupid question, but isn't that code horribly broken? It assumes that the next 3 byte after a string are readable. What if I malloc'ed memory for the string in such a way, that the \0 is the last byte of the memory page and the next byte after \0 is on the next page, which is not mapped into my VM space? In such a case the CPU will throw a page-fault and the process will die because of SIGSERV…

The glibc strlen begins by checking the first few bytes, if necessary, so that it can continue with the assumption that the string is 4-byte or 8-byte aligned. So no, it's not horribly broken: all the reads are aligned, and you're not going to get a page boundary in the middle of the word.

(Also, you're not going to be reading off the end of a malloc'ed block, because essentially all malloc implementations, including the one in glibc, return blocks whose start address and size are multiples of the architecture's word size.)

Re: Glibc's strlen implementation: Probably not what you'd guess

#30

Post by axod »

huhtenberg wrote: post #17

Interesting, but this is somewhat pointless if you ask me. It relies on certain assumptions that are not the part of the C standard, so while this code works on the majority of platforms, this is not a portable C code. In which case going all the way down to the assembly level makes more sense. Especially considering there are typically dedicated CPU instructions for the exact purpose of searching a zero in a contigu…

rep scasb is horribly slow.
Post reply on HN