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

31–40 of 74 posts

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

#31

Post by jfarmer »

jws wrote: post #24
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 differ…

A mean isn't helpful without standard deviation. The difference could be due to chance.

Also, http://funroll-loops.info/ for those who haven't seen it.

And I used to use Gentoo exclusively. :)

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

#32

Post by jws »

jfarmer wrote: post #31
jws wrote: post #24

Earlier quoted context omitted.

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

A mean isn't helpful without standard deviation. The difference could be due to chance. Also, http://funroll-loops.info/ for those who haven't seen it. And I used to use Gentoo exclusively. :)

Standard deviation is below my chosen two digits.

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

#33

Post by yan »

whughes wrote: post #26
yan wrote: post #19

Earlier quoted context omitted.

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.

I'd really like to retire this argument, but I don't exactly agree.

My point is basically as follows:

1) Yes, it probably makes sense for GNU libc to use the optimized implementation.

2) Yes, it's really interesting to dissect when you're looking for clever implementations and hacks.

3) These "2x" speed-up numbers I feel are all nice metrics, but in the end, don't amount to much. Outside of this argument, I feel people misunderstand how long something takes in a computer. The relative time a network or hard drive read takes, a memory read takes, a CPU instruction cache miss takes, and a dumb comparing of bytes via a single instruction are all a magnitude of difference apart.

So let's say you're writing your http caching server and you're using the new strlen algorithm. The amount of time your code will spend fetching the item from memory and putting it on the wire will completely eclipse the speedup you get from this fancy strlen. Not to mention if you're writing this in a high-level language, the nanoseconds you save on a linear algorithm will simply not matter.

So you can make the argument that over the last few years, the total time and energy spent by all Linux machines saved by using the new algorithm is worth it. I don't exactly buy it because most of modern computers' lives are dictated by waiting for input, processing it in burst and then more waiting. Most CPUs are sitting around the world with single-digit utilization. If we all loaded up a bunch of work to do in 1990 and the world's CPU power spent time crunching it, we might arrive at an answer a few hours or days sooner. But all it means in realistic terms, is that your Linux box will arrive at answer a few nanoseconds sooner and get to finally start waiting for its next batch sooner (whether this entails serving http requests or waiting for your next key stroke)

I'm all for optimization, but I think it has to be appropriate and measured. It probably makes sense to spend time on nano-optimizations for maintainers of one of the most-used libraries in the world, but all I'm trying to say, that for most readers of HN, it's better to spend time working on algorithm run-time optimization or caching policies than looking for getting side-tracked with strlen implementations.

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

#34

Post by DarkShikari »

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

Apple's libc is probably SIMD-optimized. You can make strlen a ton faster with some basic SSE instructions.

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

#35

Post by yters »

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.

The author's website has all the source code for download:

http://www.hackersdelight.org/

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

#36

Post by tptacek »

axod wrote: post #30
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.

It's 2x slower per iteration, but much faster to invoke, and friendlier to the microarchitecture. It's not as simple as you're making it out to be.

Also, using strlen() on a 4k string at all borders on malpractice.

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

#37

Post by scott_s »

yan wrote: post #33
whughes wrote: post #26

Earlier quoted context omitted.

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.

I'd really like to retire this argument, but I don't exactly agree. My point is basically as follows: 1) Yes, it probably makes sense for GNU libc to use the optimized implementation. 2) Yes, it's really interesting to dissect when you're looking for clever implementations and hacks. 3) These "2x" speed-up numbers I feel are all nice metrics, but in the end, don't amount to much. Outside of this argument, I feel peop…

As I pointed out below, I think we can assume "measure before optimize" in this community.

But per your main point, I think you're wrong in assuming that where your time is best spent is true for most HN readers. My research project is a compiler that generates code for the Cell. This kind of optimization - which in general is a vectorization - is directly applicable to what I do. And, yes, in the kinds of applications I target, the difference when this kind of optimization is applied is measurable and significant.

HN has different kinds of hackers. Something that is outside of your scope might be in someone else's scope.

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

#38

Post by jwilliams »

DarkShikari wrote: post #34
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;…

Apple's libc is probably SIMD-optimized. You can make strlen a ton faster with some basic SSE instructions.

... Yep - And OpenBSD is intended to run on as much hardware as possible - hence this simpler form might suit their purposes.

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

#39

Post by yan »

scott_s wrote: post #37
yan wrote: post #33

Earlier quoted context omitted.

I'd really like to retire this argument, but I don't exactly agree. My point is basically as follows: 1) Yes, it probably makes sense for GNU libc to use the optimized implementation. 2) Yes, it's really interesting to dissect when you're looking for clever implementations and hacks. 3) These "2x" speed-up numbers I feel are all nice metrics, but in the end, don't amount to much. Outside of this argument, I feel peop…

As I pointed out below, I think we can assume "measure before optimize" in this community. But per your main point, I think you're wrong in assuming that where your time is best spent is true for most HN readers. My research project is a compiler that generates code for the Cell. This kind of optimization - which in general is a vectorization - is directly applicable to what I do. And, yes, in the kinds of applicatio…

Let's continue this on IRC tonight or via email? If you care or are interested, that is.

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

#40

Post by tlb »

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

The advantage of 'rep scasb' is that some future version of the intel processor will be more clever and handle a word per cycle.

An advantage of optimizing the hell out of the library version is that nobody will be tempted to roll their own string compare in their application code. Slow APIs are terrible because they force application developers to work around them. So the answer isn't just to write something slow, then measure. You'll find performance doesn't matter because everyone has avoided using it.

Post reply on HN