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

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>

On Wed, Jan 9, 2019 at 6:16 PM James Y Knight <jyknight at google.com>
wrote:
>
>
> 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,
>
 I'll have a look at this approach.

> and the presence/name checking done via TargetLibraryInfo.cpp.
>
Yes, that's how it's done in this 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. :)
>>>
>>
>> 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.
>
Fair enough, let me give some numbers for this change.
Before that, a caveat with any benchmarks for comparing strings is that the
results depend a lot the distribution of sizes and content of these
strings. So it makes more sense to benchmark an actual application, and we
have our own custom benchmarks.
That being said, one of the cases where we have found this optimization to
be impactful is `operator==(const string&, const string&)`. libcxx has a
family
of benchmarks for `BM_StringRelational_Eq`)
<https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/algorithms.bench.cpp>,
which I'm going to use here.

BM_StringRelational_Eq benchmarks comparison of strings of size 7 (Small),
63 (Large) and 5k (Huge) characters, in four scenarios (scenarii ?):
 - The equal case (Control), which is theoretically the worst case as you
have to prove that all bytes are equal.
 - The case when strings differ. In that case bcmp() only needs to prove
that one byte differs to return nonzero. Typical cases where strings differ
are at the start of the string (ChangeFirst), but also, interestingly, at
the end (ChangeLast, when you are comparing strings with a common prefix,
which happens frequently e.g. when comparing subsequent elements of a
sorted list of strings). Another interesting case is the case when the
change position is in the middle (ChangeMiddle).

For this comparison, I'm using as base the call to `memcmp`, and as
experiment the following crude bcmp() implementation (I'm assuming X86_64),
that shows how we can take advantage of the observations above to optimize
typical cases.

```
#define UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64_t *>(_p))

extern "C" int bcmp(const void* p1, const void* p2, size_t n) throw()
{
  const char* a = reinterpret_cast<const char*>(p1);
  const char* b = reinterpret_cast<const char*>(p2);
  if (n >= 8) {
    uint64_t u = UNALIGNED_LOAD64(a) ^ UNALIGNED_LOAD64(b);
    uint64_t v = UNALIGNED_LOAD64(a + n - 8) ^ UNALIGNED_LOAD64(b + n - 8);
    if ((u | v) != 0) {
      return 1;
    }
  }
  return memcmp(a, b, n);
}
```

Note that:
 - there is a bit of noise in the results, but you'll see that this quite
dumb bcmp() reasonably improves {Large,Huge}_{ChangeFirst,ChangeLast} (note
the the  improvement to {Large,Huge}_ChangeLast cannot be achieved with the
semantics of memcmp) without hurting the `ChangeMiddle` and `Control` cases.
 - the small string case (size==7) is not modified by our change because
there is a "fast path" for very small sizes on operator==.
 - We are still experimenting with the final bcmp() implementation (in
particular improving the `Control` and `ChangeMiddle` cases by improving
parallelism). Our current version is better than memcmp() across the board
on X86.


                                                base (ns)   exp (ns)
BM_StringRelational_Eq_Empty_Empty_Control      1.65        1.7
BM_StringRelational_Eq_Empty_Small_Control      1.37        1.4
BM_StringRelational_Eq_Empty_Large_Control      1.37        1.44
BM_StringRelational_Eq_Empty_Huge_Control       1.38        1.44
BM_StringRelational_Eq_Small_Small_Control      6.53        6.51
BM_StringRelational_Eq_Small_Small_ChangeFirst  1.96        1.94
BM_StringRelational_Eq_Small_Small_ChangeMiddle 5.06        4.95
BM_StringRelational_Eq_Small_Small_ChangeLast   6.77        6.84
BM_StringRelational_Eq_Small_Large_Control      1.38        1.41
BM_StringRelational_Eq_Small_Huge_Control       1.37        1.39
BM_StringRelational_Eq_Large_Large_Control      5.54        5.8
BM_StringRelational_Eq_Large_Large_ChangeFirst  6.25        3.06
BM_StringRelational_Eq_Large_Large_ChangeMiddle 5.5         5.94
BM_StringRelational_Eq_Large_Large_ChangeLast   6.04        3.42
BM_StringRelational_Eq_Large_Huge_Control       1.1         1.1
BM_StringRelational_Eq_Huge_Huge_Control        118         118
BM_StringRelational_Eq_Huge_Huge_ChangeFirst    5.65        3.02
BM_StringRelational_Eq_Huge_Huge_ChangeMiddle   69.5        66.9
BM_StringRelational_Eq_Huge_Huge_ChangeLast     118         3.43
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190110/889200d6/attachment.html>

On Thu, Jan 10, 2019 at 4:47 PM Clement Courbet <courbet at google.com>
wrote:
>
>
> On Wed, Jan 9, 2019 at 6:16 PM James Y Knight <jyknight at
google.com> wrote:
>
>>
>>
>> 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,
>>
>
>  I'll have a look at this approach.
>
You're right, that's a better place to do this indeed:
https://reviews.llvm.org/D56593


>
>
>>
>>  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.
>>
>
> Fair enough, let me give some numbers for this change.
> Before that, a caveat with any benchmarks for comparing strings is that
> the results depend a lot the distribution of sizes and content of these
> strings. So it makes more sense to benchmark an actual application, and we
> have our own custom benchmarks.
> That being said, one of the cases where we have found this optimization to
> be impactful is `operator==(const string&, const string&)`. libcxx
has a family
> of benchmarks for `BM_StringRelational_Eq`)
>
<https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/algorithms.bench.cpp>,
> which I'm going to use here.
>
> BM_StringRelational_Eq benchmarks comparison of strings of size 7 (Small),
> 63 (Large) and 5k (Huge) characters, in four scenarios (scenarii ?):
>  - The equal case (Control), which is theoretically the worst case as you
> have to prove that all bytes are equal.
>  - The case when strings differ. In that case bcmp() only needs to prove
> that one byte differs to return nonzero. Typical cases where strings differ
> are at the start of the string (ChangeFirst), but also, interestingly, at
> the end (ChangeLast, when you are comparing strings with a common prefix,
> which happens frequently e.g. when comparing subsequent elements of a
> sorted list of strings). Another interesting case is the case when the
> change position is in the middle (ChangeMiddle).
>
> For this comparison, I'm using as base the call to `memcmp`, and as
> experiment the following crude bcmp() implementation (I'm assuming
X86_64),
> that shows how we can take advantage of the observations above to optimize
> typical cases.
>
> ```
> #define UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64_t
*>(_p))
>
> extern "C" int bcmp(const void* p1, const void* p2, size_t n)
throw() {
>   const char* a = reinterpret_cast<const char*>(p1);
>   const char* b = reinterpret_cast<const char*>(p2);
>   if (n >= 8) {
>     uint64_t u = UNALIGNED_LOAD64(a) ^ UNALIGNED_LOAD64(b);
>     uint64_t v = UNALIGNED_LOAD64(a + n - 8) ^ UNALIGNED_LOAD64(b + n - 8);
>     if ((u | v) != 0) {
>       return 1;
>     }
>   }
>   return memcmp(a, b, n);
> }
> ```
>
> Note that:
>  - there is a bit of noise in the results, but you'll see that this
quite
> dumb bcmp() reasonably improves {Large,Huge}_{ChangeFirst,ChangeLast} (note
> the the  improvement to {Large,Huge}_ChangeLast cannot be achieved with
> the semantics of memcmp) without hurting the `ChangeMiddle` and `Control`
> cases.
>  - the small string case (size==7) is not modified by our change because
> there is a "fast path" for very small sizes on operator==.
>  - We are still experimenting with the final bcmp() implementation (in
> particular improving the `Control` and `ChangeMiddle` cases by improving
> parallelism). Our current version is better than memcmp() across the
> board on X86.
>
>
>                                                 base (ns)   exp (ns)
> BM_StringRelational_Eq_Empty_Empty_Control      1.65        1.7
> BM_StringRelational_Eq_Empty_Small_Control      1.37        1.4
> BM_StringRelational_Eq_Empty_Large_Control      1.37        1.44
> BM_StringRelational_Eq_Empty_Huge_Control       1.38        1.44
> BM_StringRelational_Eq_Small_Small_Control      6.53        6.51
> BM_StringRelational_Eq_Small_Small_ChangeFirst  1.96        1.94
> BM_StringRelational_Eq_Small_Small_ChangeMiddle 5.06        4.95
> BM_StringRelational_Eq_Small_Small_ChangeLast   6.77        6.84
> BM_StringRelational_Eq_Small_Large_Control      1.38        1.41
> BM_StringRelational_Eq_Small_Huge_Control       1.37        1.39
> BM_StringRelational_Eq_Large_Large_Control      5.54        5.8
> BM_StringRelational_Eq_Large_Large_ChangeFirst  6.25        3.06
> BM_StringRelational_Eq_Large_Large_ChangeMiddle 5.5         5.94
> BM_StringRelational_Eq_Large_Large_ChangeLast   6.04        3.42
> BM_StringRelational_Eq_Large_Huge_Control       1.1         1.1
> BM_StringRelational_Eq_Huge_Huge_Control        118         118
> BM_StringRelational_Eq_Huge_Huge_ChangeFirst    5.65        3.02
> BM_StringRelational_Eq_Huge_Huge_ChangeMiddle   69.5        66.9
> BM_StringRelational_Eq_Huge_Huge_ChangeLast     118         3.43
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190111/d3fc3a68/attachment.html>