5 ms·
Glibc's strlen implementation: Probably not what you'd guess
- axod 18y agoClever 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/0201914654/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1236711085&sr=8-1 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 18y agoHoly crap, all 15 reviews of that book are 5 stars! That's the best average I've ever seen on Amazon.
- axod 18y agoI'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 18y agoThe author's website has all the source code for download: http://www.hackersdelight.org/ http://www.hackersdelight.org/
- yan 18y agoIt'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.
- lacker 18y agoSure, 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.
- yan 18y agoI 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.
- axod 18y agoYou 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).
- yan 18y agoMy overall point was that it makes little sense for developers coming up for similar hacks on their own pet projects or apps. This is a linear runtime issue, and the efficiency-speed up here is trivial. Obviously, if you're maintaining gnu's libc, you probably know about this more than I do and in a better position to decide if this is needed, but to Joe Developer, it's just a side-track that obscures the end-goals.
- scott_s 18y agoSomeone 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.
- there 18y agofor comparison: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/strlen.c?rev=1.7;content-type=text%2Fplain http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/st...
- yan 18y agoAnd 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 18y ago[deleted]
- henning 18y agoThat'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. >_>
- tjr 18y agohttp://www.gnu.org/prep/standards/html_node/Reading-Non_002dFree-Code.html 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).
- briansmith 18y agoThat makes the X86 assembly version look straightforward: http://www.int80h.org/strlen/ 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 18y agoThat 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.)
- newt0311 18y agoSo... clever hack or premature optimization?
- jws 18y agoI'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.
- jws 18y agoAnd 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.
- DarkShikari 18y agoApple's libc is probably SIMD-optimized. You can make strlen a ton faster with some basic SSE instructions.
- hvdm 18y agoA 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 18y agoHN 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-strlen.html http://www.daemonology.net/blog/2008-06-05-faster-utf8-strle...
- huhtenberg 18y agoInteresting, 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.
- axod 18y agorep scasb is horribly slow.
- tptacek 18y agoIt'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.
- axod 18y agoGo 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?
- tptacek 18y agoFriendlier to the microarchitecture means: fewer branches, fewer BTB entries, less impact on the icache. Sorry, you wrote like you might have already known that. You know that VC++ does implement copies with movsd/movsb, right? Sorry, I don't read a lot of books and forums on assembly programming. Just the PRM. I'm just stuck reading/writing a lot of assembly on projects.
- lacker 18y agoThe lesson here is use library functions. Someone smarter than you has probably optimized the hell out of them.
- albemuth 18y agoThe glibc guys did not heed such advice :P
- sep332 18y agooh snap!
- tlrobinson 18y agoIndeed, 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 18y agoI 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 18y agoSorry 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 18y agoThe 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 18y agoNot directly related to your question, but see http://sourceware.org/bugzilla/show_bug.cgi?id=5807 http://sourceware.org/bugzilla/show_bug.cgi?id=5807 The ((longword - lomagic) & himagic) should be ((longword - lomagic) & ~longword & himagic)
- mynameishere 18y agoIt's faster if you just store the length in a separate memory location. This is very fast: getLength() { return length; }
- tptacek 18y agoI'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.
- AlexMeyer 18y agoA cool page is Paul Hsiehs' webpage. There you will find some good discussion on the trick used. http://www.azillionmonkeys.com/qed/asmexample.html http://www.azillionmonkeys.com/qed/asmexample.html Look for part 5: "A fast implementation of strlen()".