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.
Glibc's strlen implementation: Probably not what you'd guess
11–20 of 74 posts
Re: Glibc's strlen implementation: Probably not what you'd guess
#12Earlier quoted context omitted.
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.
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).
Re: Glibc's strlen implementation: Probably not what you'd guess
#13Earlier 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).
My 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.
Re: Glibc's strlen implementation: Probably not what you'd guess
#14HN 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...
Re: Glibc's strlen implementation: Probably not what you'd guess
#15for comparison: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/st...
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. >_>
Re: Glibc's strlen implementation: Probably not what you'd guess
#16Clever 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.
Holy crap, all 15 reviews of that book are 5 stars! That's the best average I've ever seen on Amazon.
Re: Glibc's strlen implementation: Probably not what you'd guess
#17Interesting, 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.
Re: Glibc's strlen implementation: Probably not what you'd guess
#18Earlier quoted context omitted.
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).
My 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.
Someone 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.
Re: Glibc's strlen implementation: Probably not what you'd guess
#19Earlier quoted context omitted.
My 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.
Someone 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.
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 (in which case there are better running time algorithms, not just low-level hacks).
I love these as much as the next person, but early and misappropriated optimization, in my opinion, is suboptimal as a practice.
Re: Glibc's strlen implementation: Probably not what you'd guess
#20for 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 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).