llvm dev - Jan 2019 - [RFC] Adding a -memeq-lib-function flag to allow the user to specify a memeq function.

On Mon, Jan 7, 2019 at 5:50 AM Clement Courbet <courbet at google.com>
wrote:
> On Fri, Jan 4, 2019 at 12:34 PM James Y Knight via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> This seems a somewhat odd and overcomplicated way to go about this.
>>>
>>> Given that bcmp was required in POSIX until relatively recently, I
will
>>> guess that almost all platforms support it already. From a quick
check,
>>> glibc, freebsd, netbsd, newlib, and musl all seem to contain it.
So,
>>> couldn't we just add bcmp to the runtime function list for
those platforms
>>> which support it? And, add an optimization to translate a call to
memcmp
>>> into bcmp if it exists?
>>>
>>
> That would indeed be much simpler, but this seems brittle to me. The
> approach you're suggesting works for us (google) because we fully
control
> our environment, but I'm afraid it will not work for others.
> For example, someone might distribute linux binaries built with LLVM to
> their users, but since there is nothing guaranteeing that bcmp is available
> on the user's libc, they won't be able to run it on their systems.
> Is there a precedent for that approach ?
>
There are many library functions that are only available on some platforms
and not others. LLVM can easily be told which do include it and which do
not, and emit a call only for those which do.

For Glibc Linux, we can be sure that bcmp is available on all systems -- is
is there now, it always has been, and always will be in the future (due to
backwards compatibility guarantees). It's just defined as an alias for
memcmp, however, so there's no advantage (nor, for that matter,
disadvantage) to using it.

But of course it's not _only_ glibc which has it -- it's present in
almost
every environment out there.

e.g. for Linux there's also a few other libc implementations that people
use:
musl: includes it, calls memcmp.
uclibc-ng: includes it, alias of memcmp (only if you compile
with UCLIBC_SUSV3_LEGACY, but "buildroot", the way one generally uses
uclibc, does so).
dietlibc: includes it, alias of memcmp.
Android bionic: doesn't include it.

Some other platforms:
RTEMS (newlib): includes it, calls memcmp.
NetBSD: includes it, separate optimized implementation.
FreeBSD: includes it, separate optimized implementation.
Darwin/macOS/iOS/etc: includes it, alias of memcmp.
Windows: doesn't include it.
Solaris: includes it (haven't checked impl).

I do note, sadly, that currently out of all these implementations, only
NetBSD and FreeBSD seem to actually define a separate more optimized bcmp
function. That does mean that this optimization would be effectively a
no-op, for the vast majority of people.

For Google's purposes, if a call to bcmp is emitted by the compiler, you
can of course just override it with a more optimal version. But if you can
show a similar performance win in public code, it'd be great to attempt to
push a more optimized version upstream at least to glibc. Some more precise
numbers than "very large improvement" are probably necessary to show
it's
actually worth it. :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190107/891b8046/attachment.html>

On Mon, Jan 7, 2019 at 10:26 PM James Y Knight <jyknight at google.com>
wrote:
> On Mon, Jan 7, 2019 at 5:50 AM Clement Courbet <courbet at
google.com> wrote:
>
>> On Fri, Jan 4, 2019 at 12:34 PM James Y Knight via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> This seems a somewhat odd and overcomplicated way to go about
this.
>>>>
>>>> Given that bcmp was required in POSIX until relatively
recently, I will
>>>> guess that almost all platforms support it already. From a
quick check,
>>>> glibc, freebsd, netbsd, newlib, and musl all seem to contain
it. So,
>>>> couldn't we just add bcmp to the runtime function list for
those platforms
>>>> which support it? And, add an optimization to translate a call
to memcmp
>>>> into bcmp if it exists?
>>>>
>>>
>> That would indeed be much simpler, but this seems brittle to me. The
>> approach you're suggesting works for us (google) because we fully
control
>> our environment, but I'm afraid it will not work for others.
>> For example, someone might distribute linux binaries built with LLVM to
>> their users, but since there is nothing guaranteeing that bcmp is
available
>> on the user's libc, they won't be able to run it on their
systems.
>> Is there a precedent for that approach ?
>>
>
> There are many library functions that are only available on some platforms
> and not others. LLVM can easily be told which do include it and which do
> not, and emit a call only for those which do.
>
> For Glibc Linux, we can be sure that bcmp is available on all systems --
> is is there now, it always has been, and always will be in the future (due
> to backwards compatibility guarantees). It's just defined as an alias
for
> memcmp, however, so there's no advantage (nor, for that matter,
> disadvantage) to using it.
>
> But of course it's not _only_ glibc which has it -- it's present in
almost
> every environment out there.
>
> e.g. for Linux there's also a few other libc implementations that
people
> use:
> musl: includes it, calls memcmp.
> uclibc-ng: includes it, alias of memcmp (only if you compile
> with UCLIBC_SUSV3_LEGACY, but "buildroot", the way one generally
uses
> uclibc, does so).
>
I'm afraid about the "almost" and "generally": what
about users who don't ?

> NetBSD: includes it, separate optimized implementation.
>
Quoting from the NetBSD man page
<http://netbsd.gw.com/cgi-bin/man-cgi?bcmp+9+NetBSD-current>:
"The bcmp() interface is obsolete.  Do not add new code using it.  It will
soon be purged.  Use memcmp(9) instead.  (The bcmp() function is now a
macro for memcmp(9).)"

> I do note, sadly, that currently out of all these implementations, only
> NetBSD and FreeBSD seem to actually define a separate more optimized bcmp
> function. That does mean that this optimization would be effectively a
> no-op, for the vast majority of people.
>
This might or might not be considered really an issue.
 - In my original proposal, people have to explicitly opt-in to the feature
and link to their memcmp implementation, they do not get the improvement
automatically.
 - In this proposal, they have to patch their libc, which might be slightly
more painful depending on the system.

Here's a patch with this proposal to see what this looks like:
https://reviews.llvm.org/D56436

> For Google's purposes, if a call to bcmp is emitted by the compiler,
you
> can of course just override it with a more optimal version.
>
For our purpose anything is fine because we fully control our environment.
I'm trying to make sure that we do not create pain for other users.

>  But if you can show a similar performance win in public code, it'd be
> great to attempt to push a more optimized version upstream at least to
> glibc. Some more precise numbers than "very large improvement"
are probably
> necessary to show it's actually worth it. :)
>
We were planning to contribute it to compiler-rt. Contributing a deprecated
function to the libc sounds.... weird.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190108/52484eae/attachment.html>

On Tue, Jan 8, 2019 at 9:24 AM Clement Courbet <courbet at google.com>
wrote:
>
>
> On Mon, Jan 7, 2019 at 10:26 PM James Y Knight <jyknight at
google.com>
> wrote:
>
I'm afraid about the "almost" and "generally": what
about users who don't ?
>
Even so, it should be fine to enable it for those platforms which do
include it.

I do note, sadly, that currently out of all these implementations,
only
>> NetBSD and FreeBSD seem to actually define a separate more optimized
bcmp
>> function. That does mean that this optimization would be effectively a
>> no-op, for the vast majority of people.
>>
>
> This might or might not be considered really an issue.
>
Right, the issue is adding an effectively useless optimization in llvm.

 - In my original proposal, people have to explicitly opt-in to the
feature
> and link to their memcmp implementation, they do not get the improvement
> automatically.
>  - In this proposal, they have to patch their libc, which might be
> slightly more painful depending on the system.
>
Users may also include a function named bcmp in their binary, which will
overrides the one from libc.

Here's a patch with this proposal to see what this looks
like:
> https://reviews.llvm.org/D56436
>
It feels like this optimization would be better done in
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp, and the presence/name
checking done via TargetLibraryInfo.cpp.

 But if you can show a similar performance win in public code, it'd
be
>> great to attempt to push a more optimized version upstream at least to
>> glibc. Some more precise numbers than "very large
improvement" are probably
>> necessary to show it's actually worth it. :)
>>
>
> We were planning to contribute it to compiler-rt. Contributing a
> deprecated function to the libc sounds.... weird.
>
Yes, contributing an optimization for a deprecated function is indeed
weird. Thus the importance of reliable performance numbers justifying the
importance -- I'd never have thought that the performance cost of returning
an ordering from memcmp would be important, and I suspect nobody else did.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190109/cdaa5f8f/attachment.html>