Hacker News Reader

Hacker News

Comment by nitwit005 | Hacker News Reader

Parent Full thread

nitwit005

> The optimizer will now convert calls to memcmp into a calls to bcmp in some circumstances.

What is the improvement from that change? I thought they were essentially the same.

View on HN

memcmp has to find the first offset where the buffers differ, and check which of them is larger.

bcmp only has to figure out whether the buffers differ. It doesn’t have to figure out where they differ.

For example, for s=1024, bcmp can do (at most) 128 64-bit compares (using vector registers, it could even use larger steps)

memcmp could do the same, with an additional “figure out where in the last 8-byte parts compared the difference lies”.

That’s an amount of work that’s independent of the buffer sizes, so it wouldn’t add much, relatively, _if_ the buffers compared are large and the difference (if any) most of the time is near the end of the buffers. I doubt those ifs often hold, though.

This would be true, except bcmp has been removed from posix some years ago. There's no particular requirement that a function called bcmp does what you expect.

http://releases.llvm.org/9.0.0/docs/ReleaseNotes.html#notewo...:

”The optimizer will now convert calls to memcmp into a calls to bcmp in some circumstances. Users who are building freestanding code (not depending on the platform’s libc) without specifying -ffreestanding may need to either pass -fno-builtin-bcmp, or provide a bcmp* function.”*

So, he’s, you may have to provide it yourself. I expect you can fairly easily copy-paste it from various BSD-licensed libraries, though (example: https://github.com/freebsd/freebsd/blob/master/sys/libkern/b..., but be warned about that “I don't believe this is a problem since AFAIK, objects are not protected at smaller than longword boundaries”. That likely is, but may not be true on your platform)

So the problem here is I may already have a function in my program called bcmp, which takes no arguments and prints "better consider more possibilities" to standard output. This is all fine and legal. My program also uses memcmp, because of course it does. But now calls to memcmp are going to be replaced to with calls to bcmp, which does not have the same effect at all.

That’s nothing new, though. If you have a memcmp that isn’t memcmp (and don’t explicitly call a lib-provided memcmp anywhere) and build without libc, your memcmp will incorrectly be used, too.

MSVC is even more notorious for this kind of issue, silently adding a number of function calls it assumes the standard library will provide even when your code doesn’t use the standard library at all.

The compiler will surely use a (most likely intrinsic) function with appropriate semantics in that case.

The release notes go on to say that you may need to provide your own implementation of bcmp, which does not sound very intrinsic.

Huh, interesting. I was assuming that the compiler would statically link in a bcmp in that case, but it looks like it will literally replace it with a call to bcmp in certain cases (as defined by the remainder of that point in the release notes). Apparently this was brought up and brushed aside as not an issue: https://bugs.llvm.org/show_bug.cgi?id=41035

You may if you’re building freestanding code (code that doesn’t use the standard library), but do not specify that you are. I think that’s reasonable.

I do wonder why this is a LLVM feature, though, and not a clang one. The system should only make this change if it came from a C(++) compiler and the source included the system header (<string.h> or <cstring>) to get memcmp.

How can LLVM know that the symbol memcmp it sees came from that header, and not from user C code that may do something different, or even from, say, a Cobol compiler?

IIRC, Google engineers used fleetwide profiling to see that many cycles were being spent in memcmp() == 0 calls. They weren't checking the return value was anything other than zero. If you don't care where two buffers mismatched, you can speed thing up by converting that idiom into a call to bcmp during optimization.

memcmp returns the lexicographic ordering of the parameters (<, = or >) while bcmp only returns equality (anything nonzero is difference so memcmp is a suitable bcmp), so the LLVM folks believe worst case scenario bcmp will alias to memcmp, and possibly it'll have better performances since it has to do less: https://reviews.llvm.org/D56593

bcmp just tells you "equal" or "not equal", while memcmp tells you "lesser", "equal", or "greater".

I don't really know, but I suppose it might be possible to make bcmp faster since you have less strict requirements on the return value.

memcmp promises a nonzero return value tells you something about the lexicographic ordering. bcmp does not: so if you only care if it's exactly equal or not, it might be faster.

Reply on news.ycombinator.com