4 ms·

> 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 esse

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

Someone 7y ago
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.
- tedunangst 7y ago
  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.
  - saagarjha 7y ago
    The compiler will surely use a (most likely intrinsic) function with appropriate semantics in that case.
    - tedunangst 7y ago
      The release notes go on to say that you may need to provide your own implementation of bcmp, which does not sound very intrinsic.
      - saagarjha 7y ago
        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 https://bugs.llvm.org/show_bug.cgi?id=41035
      - Someone 7y ago
        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?
  - Someone 7y ago
    http://releases.llvm.org/9.0.0/docs/ReleaseNotes.html#noteworthy-optimizations 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/bcmp.c 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)
    - tedunangst 7y ago
      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.
      - deleted 7y ago
        [deleted]
      - ComputerGuru 7y ago
        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.
veddan 7y ago
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.
masklinn 7y ago
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 https://reviews.llvm.org/D56593
lvh 7y ago
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.
ndesaulniers 7y ago
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.

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

Someone 7y ago

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.

tedunangst 7y ago
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.
- saagarjha 7y ago
  The compiler will surely use a (most likely intrinsic) function with appropriate semantics in that case.
  - tedunangst 7y ago
    The release notes go on to say that you may need to provide your own implementation of bcmp, which does not sound very intrinsic.
    - saagarjha 7y ago
      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 https://bugs.llvm.org/show_bug.cgi?id=41035
    - Someone 7y ago
      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?
- Someone 7y ago
  http://releases.llvm.org/9.0.0/docs/ReleaseNotes.html#noteworthy-optimizations 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/bcmp.c 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)
  - tedunangst 7y ago
    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.
    - deleted 7y ago
      [deleted]
    - ComputerGuru 7y ago
      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.

veddan 7y ago

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.

masklinn 7y ago

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 https://reviews.llvm.org/D56593

lvh 7y ago

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.

ndesaulniers 7y ago

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.