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

41–50 of 74 posts

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

#41

Post by scott_s »

tjr wrote: post #20
there wrote: post #4

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

http://www.gnu.org/prep/standards/html_node/Reading-Non_002d... Don't in any circumstances refer to Unix source code for or during your work on GNU! (Or to any other proprietary programs.) If you have a vague recollection of the internals of a Unix program, this does not absolutely mean you can't write an imitation of it, but do try to organize the imitation internally along different lines, because this is likely to…

I'm confused. What are you getting at? The code linked is from OpenBSD, which is under a BSD-style license which is considered GPL compatible.

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

#42

Post by scott_s »

yan wrote: post #39
scott_s wrote: post #37

Earlier quoted context omitted.

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.

I don't think there's anything left to say, really. We're making orthogonal points.

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

#43

Post by tlb »

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…

In places where I've done this sort of thing, I prefer

  #ifdef NO_CLEVER_OPTIMIZATIONS
      obvious version
  #else
      complicated fast version
  #endif
It's good as documentation, good as a test case, and good for isolating weird problems like compiler optimization bugs.

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

#44

Post by [deleted] »

yan wrote: post #5
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.

[deleted]

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

#45

Post by dchest »

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.

Here's the source code for Apple's implementation (i386): http://www.opensource.apple.com/darwinsource/10.5.5/Libc-498...

(requires registration, here's gist link: http://gist.github.com/77178)

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

#48

Post by dchest »

jwilliams wrote: post #38
DarkShikari wrote: post #34

Earlier quoted context omitted.

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.

Nope, the have implementations for different architectures, you can find them here:

http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/

The linked code is for the case when there's no arch-specific implementation.

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

#49

Post by axod »

tptacek wrote: post #36
axod wrote: post #30

Earlier quoted context omitted.

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.

Go have the argument with glibc then (And all the other people who use optimizations like this).

"friendlier to the micro-architecture" doesn't even make sense. Check the chip timings for rep scasb. It's not friendly.

We're not really discussing wether you should be using strlen on large strings or not, but even if it's used say a million times on strings of length 80 or so, you'd see an improvement worth having.

Check any assembly language forum, book, etc and there will be discussion on why rep scasb/movsb/cmpsb are lame.

Would you implement string copy with rep movsb as well?

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

#50

Post by jwilliams »

dchest wrote: post #48
jwilliams wrote: post #38

Earlier quoted context omitted.

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

Nope, the have implementations for different architectures, you can find them here: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/ The linked code is for the case when there's no arch-specific implementation.

Thanks - sort of what I meant though :)
Post reply on HN