[llvm-dev] [RFC] Adding a -memeq-lib-function flag to allow the user to specify a memeq function. (original) (raw)

Clement Courbet via llvm-dev llvm-dev at lists.llvm.org
Mon Feb 4 23:28:44 PST 2019

I'd like to move forward with this. Since there are no objections to the approach suggested by James, I've tentatively sent the corresponding v5 implementation (https://reviews.llvm.org/D56593) for review.

On Fri, Jan 11, 2019 at 1:45 PM Clement Courbet <courbet at google.com> wrote:

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 BMStringRelationalEq) <https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/algorithms.bench.cpp>, which I'm going to use here. BMStringRelationalEq 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 X8664), that shows how we can take advantage of the observations above to optimize typical cases. _ _#define UNALIGNEDLOAD64(p) (*reinterpretcast<const uint64t *>(p))_ _extern "C" int bcmp(const void* p1, const void* p2, sizet n) throw() {_ _const char* a = reinterpretcast<const char*>(p1);_ _const char* b = reinterpretcast<const char*>(p2);_ _if (n >= 8) {_ _uint64t u = UNALIGNEDLOAD64(a) ^ UNALIGNEDLOAD64(b);_ _uint64t v = UNALIGNEDLOAD64(a + n - 8) ^ UNALIGNEDLOAD64(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) BMStringRelationalEqEmptyEmptyControl 1.65 1.7 BMStringRelationalEqEmptySmallControl 1.37 1.4 BMStringRelationalEqEmptyLargeControl 1.37 1.44 BMStringRelationalEqEmptyHugeControl 1.38 1.44 BMStringRelationalEqSmallSmallControl 6.53 6.51 BMStringRelationalEqSmallSmallChangeFirst 1.96 1.94 BMStringRelationalEqSmallSmallChangeMiddle 5.06 4.95 BMStringRelationalEqSmallSmallChangeLast 6.77 6.84 BMStringRelationalEqSmallLargeControl 1.38 1.41 BMStringRelationalEqSmallHugeControl 1.37 1.39 BMStringRelationalEqLargeLargeControl 5.54 5.8 BMStringRelationalEqLargeLargeChangeFirst 6.25 3.06 BMStringRelationalEqLargeLargeChangeMiddle 5.5 5.94 BMStringRelationalEqLargeLargeChangeLast 6.04 3.42 BMStringRelationalEqLargeHugeControl 1.1 1.1 BMStringRelationalEqHugeHugeControl 118 118 BMStringRelationalEqHugeHugeChangeFirst 5.65 3.02 BMStringRelationalEqHugeHugeChangeMiddle 69.5 66.9 BMStringRelationalEqHugeHugeChangeLast 118 3.43 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190205/a5db76d0/attachment.html>

More information about the llvm-dev mailing list