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

51–60 of 74 posts

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

#51

Post by tptacek »

axod wrote: post #49
tptacek wrote: post #36

Earlier quoted context omitted.

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. Che…

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

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

#52

Post by axod »

tptacek wrote: post #51
axod wrote: post #49

Earlier quoted context omitted.

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. Che…

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

>> Friendlier to the microarchitecture means: fewer branches, fewer BTB entries, less impact on the icache. Sorry, you wrote like you might have already known that.

If it's less clock cycles to do branching and comparing by dword (which it is for medium to long strings) than doing rep scasb, then what else matters...?

>> You know that VC++ does implement copies with movsd/movsb, right?

I've stepped through VC++ string copy code in softice many a time thanks.

Notice how I was asking about 'movsb', and you replied with 'movsd/movdb'. Notice the difference?

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

#53

Post by tptacek »

dchest wrote: post #47
there wrote: post #4

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

You're missing the architecture-dependent implementations. Here's one for i386: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/i386...

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

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

#54

Post by shmoo »

tgos wrote: post #25

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…

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)

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

#55

Post by tptacek »

axod wrote: post #52
tptacek wrote: post #51

Earlier quoted context omitted.

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

>> Friendlier to the microarchitecture means: fewer branches, fewer BTB entries, less impact on the icache. Sorry, you wrote like you might have already known that. If it's less clock cycles to do branching and comparing by dword (which it is for medium to long strings) than doing rep scasb, then what else matters...? >> You know that VC++ does implement copies with movsd/movsb, right? I've stepped through VC++ strin…

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.

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

#56

Post by tptacek »

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.

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

#57

Post by dchest »

tptacek wrote: post #53
dchest wrote: post #47

Earlier quoted context omitted.

You're missing the architecture-dependent implementations. Here's one for i386: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/i386...

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

Their x86-64 implementation is in amd64 tree:

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

It uses repne scasb.

Comment in x86-65 directory says:

"change amd64's MACHINE_ARCH from x86_64 to amd64. There are many many reasons for this, quite a few of them technical, and not all of them in response to Intel's broken ia32e crud. The gcc toolchain stays at x86_64 for now."

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

#58

Post by tjr »

scott_s wrote: post #41
tjr wrote: post #20

Earlier quoted context omitted.

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.

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.

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

#59

Post by axod »

tptacek wrote: post #55
axod wrote: post #52

Earlier quoted context omitted.

>> Friendlier to the microarchitecture means: fewer branches, fewer BTB entries, less impact on the icache. Sorry, you wrote like you might have already known that. If it's less clock cycles to do branching and comparing by dword (which it is for medium to long strings) than doing rep scasb, then what else matters...? >> You know that VC++ does implement copies with movsd/movsb, right? I've stepped through VC++ strin…

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 :/ Chill out eh.

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

#60

Post by tptacek »

dchest wrote: post #57
tptacek wrote: post #53

Earlier quoted context omitted.

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

Their x86-64 implementation is in amd64 tree: http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/amd6... It uses repne scasb. Comment in x86-65 directory says: "change amd64's MACHINE_ARCH from x86_64 to amd64. There are many many reasons for this, quite a few of them technical, and not all of them in response to Intel's broken ia32e crud. The gcc toolchain stays at x86_64 for now."

Weird, I wonder why I thought it wasn't. I'll go look. Thanks!
Post reply on HN