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

#1

Post by aston » Tue, Mar 10, 2009, 6:21 PM UTC

Glibc's strlen implementation: Probably not what you'd guess
sources.redhat.com

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

#2

Post by axod » Tue, Mar 10, 2009, 6:53 PM UTC

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.

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

#3

Post by yan » Tue, Mar 10, 2009, 7:16 PM UTC

It's cute.

Will I employ similar technique in my own code? Absolutely not. It hinders readability and byte comparison instructions in consecutive memory addresses are so stupidly fast that I'll probably save less CPU time combined in all executions of my program than the total amount of time it took me to think this hack up.

If you're a maintainer of glibc though (which is known for its exceptionally clear and straight-forward code,) then I might consider accepting a patch from someone who thought it up.

edit: I thought similarly of DJB's loop unrolling when I saw it in qmail. It's cute, but will it make any noticeable difference today? Probably not.

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

#4

Post by there » Tue, Mar 10, 2009, 7:18 PM UTC

for comparison: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/st...

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

#5

Post by yan » Tue, Mar 10, 2009, 7:21 PM UTC

there wrote: post #4

for comparison: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/st...

And this is why I read (free|open)bsd's cvsweb repo when I'm curious as to how things are implemented. I used to visit that repo in university when I was bored just to read some clear, concise, well-documented code.

I used to use and love FreeBSD (Since switched to OS X as desktop os, still run FreeBSD servers), but OpenBSD source code just looked more approachable.

McKusicks' wonderful book and video course helped.

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

#6

Post by briansmith » Tue, Mar 10, 2009, 7:26 PM UTC

That makes the X86 assembly version look straightforward: http://www.int80h.org/strlen/. I think it is just a fallback implementation that is used when no optimized version has been created for the target processor. Every time I've looked my compiler has used a hand-optimized version for every platform. Quite possibly, this is 100% dead code.

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

#7

Post by lacker » Tue, Mar 10, 2009, 7:28 PM UTC

yan wrote: post #3

It's cute. Will I employ similar technique in my own code? Absolutely not. It hinders readability and byte comparison instructions in consecutive memory addresses are so stupidly fast that I'll probably save less CPU time combined in all executions of my program than the total amount of time it took me to think this hack up. If you're a maintainer of glibc though (which is known for its exceptionally clear and straig…

Sure, but... you're not writing glibc. How many computers run that code? At some point, if it's faster and correct, it's worth it.

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

#8

Post by yan » Tue, Mar 10, 2009, 7:32 PM UTC

lacker wrote: post #7

yan wrote: post #3

It's cute. Will I employ similar technique in my own code? Absolutely not. It hinders readability and byte comparison instructions in consecutive memory addresses are so stupidly fast that I'll probably save less CPU time combined in all executions of my program than the total amount of time it took me to think this hack up. If you're a maintainer of glibc though (which is known for its exceptionally clear and straig…

Sure, but... you're not writing glibc. How many computers run that code? At some point, if it's faster and correct, it's worth it.

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.

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

#9

Post by newt0311 » Tue, Mar 10, 2009, 7:40 PM UTC

So... clever hack or premature optimization?

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

#10

Post by jws » Tue, Mar 10, 2009, 7:52 PM UTC

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;

The preliminary conclusions are:

The glibc strlen is something like twice as fast as the naive implementation, but there is something else out there that knocks its socks off.

Secondary conclusion would be: remember not to compare GHz across different processors.