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

http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/string/strlen.c?rev=1.1.2.1&content-type=text/x-cvsweb-markup&cvsroot=glibc

by aston • 17 years ago

127 70 17 years ago

sources.redhat.com

axod8• 17 years ago

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.

pchristensen• 17 years ago

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

axod8• 17 years ago

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.

yters• 17 years ago

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

http://www.hackersdelight.org/

yan7• 17 years ago

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.

lacker2• 17 years ago

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.

yan7• 17 years ago

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.

tlb2• 17 years ago

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.

path• 17 years ago

Agreed, that's a great way to handle the case

there• 17 years ago

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

yan7• 17 years ago

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.

henning• 17 years ago

That's the basic definition you might ask someone to write on a whiteboard in a job interview.

How do they stack up in benchmarks?

Edit: See other posts in this discussion for actual benchmarks. >_>

tjr2• 17 years ago

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 make the details of the Unix version irrelevant and dissimilar to your results.

For example, Unix utilities were generally optimized to minimize memory use; if you go for speed instead, your program will be very different. You could keep the entire input file in memory and scan it there instead of using stdio. Use a smarter algorithm discovered more recently than the Unix program. Eliminate use of temporary files. Do it in one pass instead of two (we did this in the assembler).

scott_s6• 17 years ago

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.

dchest5• 17 years ago

You're missing the architecture-dependent implementations. Here's one for i386:

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

tptacek10• 17 years ago

Note that this doesn't get used on x86-64, where the repne scasb sequence is apparently penalized.

mitchellh• 17 years ago

The architecture independent versions aside, I'm afraid a lot of people will take from this comment the BSD version is "cleaner" and therefore "better." While it is cleaner, the BSD version requires very many more jumps (4 times more if I remember correctly, I haven't looked at glibc in quite awhile).

The glibc version is written in such a way to minimize the jumps in the assembly and therefore produce faster code. Besides reading 4 bytes at a time, it does some clever (and very nontrivial) "magic." But again, all to reduce the number of jumps.

briansmith• 17 years ago

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.

sketerpot• 17 years ago

That looks like a pretty straightforward translation of the basic while (d++ = s++); code. It uses higher-level instructions, but those probably get microcoded to the same thing anyway. (Note: my information on the inner workings of x86 CPUs may be a bit dated.)

jws3• 17 years ago

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.

jws3• 17 years ago

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.

jfarmer• 17 years ago

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

DarkShikari• 17 years ago

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

jwilliams2• 17 years ago

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

dchest5• 17 years ago

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)

hvdm• 17 years ago

A very quick test shows that the glibc version is more than 3 times faster for strings of length 80 compared to the bsd version.

aminuit• 17 years ago

HN has a strange fascination with strlen implementations. For anyone who missed it a few months ago, cperciva put up an interesting article about strlen for UTF-8 (variable character width) strings.

http://www.daemonology.net/blog/2008-06-05-faster-utf8-strle...

huhtenberg• 17 years ago

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 contiguous block of memory. Something like "rep scasb" on x86.

axod8• 17 years ago

rep scasb is horribly slow.

tptacek10• 17 years ago

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.

lacker2• 17 years ago

The lesson here is use library functions. Someone smarter than you has probably optimized the hell out of them.

albemuth• 17 years ago

The glibc guys did not heed such advice :P

tlrobinson• 17 years ago

Indeed, in college I was interviewing for a job, and the interviewer asked how I would determine the length of a null terminated string, and I thought I nailed it by giving a typical "while(*(str++)) c++;" implementation.

The "right" answer was just to use strlen()...

nostrademons• 17 years ago

I had a job interview once where the question was "find all descendants of a DOM node with a certain tag name, and return them in document order." I thought for about 30 seconds, and then wrote up on the board:

    element.getElementsByTagName(tagName);

That was what he was looking for. ;-) Of course, then he had me do it out as if getElementsByTagName didn't exist.

tgos• 17 years ago

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?

gjm11• 17 years ago

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

shmoo• 17 years ago

Not directly related to your question, but see http://sourceware.org/bugzilla/show_bug.cgi?id=5807

The ((longword - lomagic) & himagic) should be ((longword - lomagic) & ~longword & himagic)

mynameishere• 17 years ago

It's faster if you just store the length in a separate memory location. This is very fast:

  getLength()
  {
    return length;
  }

tptacek10• 17 years ago

I'm worried nobody's going to mod this up because it doesn't talk about bit twiddling hacks or assembly cycle counts, but it is in fact that real answer to this problem. Don't use ASCIIZ when string processing is a bottleneck.

dchest5• 17 years ago

Probably because it's not a real answer to _this_ problem (counting the number of bytes in a null-terminated string)?

AlexMeyer• 17 years ago

A cool page is Paul Hsiehs' webpage. There you will find some good discussion on the trick used. http://www.azillionmonkeys.com/qed/asmexample.html Look for part 5: "A fast implementation of strlen()".

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

Related Stories