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

61–70 of 74 posts

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

#61

Post by scott_s »

tjr wrote: post #58
scott_s wrote: post #41

Earlier quoted context omitted.

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.

Possibly the original non-free version was similar to the OpenBSD, or perhaps the GlibC developers took applied this rule where not strictly necessary. Don't know; just offering a potential clue as to why the GNU version is so different.

When they say "Unix," I think they mean the original, proprietary implementation. I don't think this is the reason why they differ. The BSD implementation is the obvious one. The GNU library version is optimized for a 32-bit processor. Given their domains, that makes sense to me.

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

#63

Post by tptacek »

axod wrote: post #59
tptacek wrote: post #55

Earlier quoted context omitted.

I have no idea what points you're trying to make here. You can trade per-byte cycle counts for lower cost to invoke the routine, and for not evicting cache and BTB entries. On your second point, I assumed it was the "rep" part of the instruction that you were railing against. Apparently it's the "not knowing the difference between a byte and a dword" part. That's awesome. You can have the last word, if you'd like.

rep movsb/rep movsd works well for moving data. However, you obviously can't use that approach for searching for a 0. That's why the code is optimized as it was. My point is that using rep scasb is suboptimal. Don't know what you're talking about "lower cost to invoke the routine", and the cache/BTB entries would be negligible on a small routine like this. You seem kinda angry and bitter whenever you reply to me :/ C…

It costs cycles to call a C function. I seem angry and bitter all the time. But my point is just, there's an argument in favor of scasb.

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

#64

Post by jrg »

scott_s wrote: post #23
yan wrote: post #19

Earlier quoted context omitted.

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…

Of course, that's Knuth's warning that "Premature optimization is the root of all evil." I assumed we've all heard that before, and we're only thinking about applying optimizations after measurement.

which is a good time to mention the recent ACM Ubiquity article, "The Fallacy of Premature Optimization" (http://www.acm.org/ubiquity/volume_10/v10i3_hyde.html) by Randall Hyde.

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

#65

Post by axod »

tptacek wrote: post #63
axod wrote: post #59

Earlier quoted context omitted.

rep movsb/rep movsd works well for moving data. However, you obviously can't use that approach for searching for a 0. That's why the code is optimized as it was. My point is that using rep scasb is suboptimal. Don't know what you're talking about "lower cost to invoke the routine", and the cache/BTB entries would be negligible on a small routine like this. You seem kinda angry and bitter whenever you reply to me :/ C…

It costs cycles to call a C function. I seem angry and bitter all the time. But my point is just, there's an argument in favor of scasb.

So you're comparing inlined rep scasb, with non-inlined alternative. Interesting comparison I guess.

Sure, it would bloat the code a little to inline the optimized version, but it could be done in tight inner loops if required.

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

#66

Post by tptacek »

axod wrote: post #65
tptacek wrote: post #63

Earlier quoted context omitted.

It costs cycles to call a C function. I seem angry and bitter all the time. But my point is just, there's an argument in favor of scasb.

So you're comparing inlined rep scasb, with non-inlined alternative. Interesting comparison I guess. Sure, it would bloat the code a little to inline the optimized version, but it could be done in tight inner loops if required.

I'm assuming you're not inlining a function with a loop in it, but OK, you can also just expand the 7 insns everywhere you call strlen.

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

#67

Post by mitchellh »

there wrote: post #4

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

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.

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

#68

Post by dchest »

tptacek wrote: post #56
mynameishere wrote: post #46

It's faster if you just store the length in a separate memory location. This is very fast: getLength() { return length; }

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.

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

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

#69

Post by tptacek »

dchest wrote: post #68
tptacek wrote: post #56

Earlier quoted context omitted.

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.

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

Meh. Fair point.

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

#70

Post by tlrobinson »

lacker wrote: post #22

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

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

Post reply on HN