<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr">On Wed, Jan 9, 2019 at 6:16 PM James Y Knight <<a href="mailto:jyknight@google.com" target="_blank">jyknight@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Jan 8, 2019 at 9:24 AM Clement Courbet <<a href="mailto:courbet@google.com" target="_blank">courbet@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jan 7, 2019 at 10:26 PM James Y Knight <<a href="mailto:jyknight@google.com" target="_blank">jyknight@google.com</a>> wrote: </div></div></div></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">I'm afraid about the "almost" and "generally": what about users who don't ?</div><div></div></div></div></div></div></div></blockquote><div><br></div><div>Even so, it should be fine to enable it for those platforms which do include it.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div>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.<br></div></div></div></div></blockquote><div><br></div><div>This might or might not be considered really an issue.</div></div></div></div></div></div></blockquote><div><br></div><div>Right, the issue is adding an effectively useless optimization in llvm.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div> - 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. </div><div> - In this proposal, they have to patch their libc, which might be slightly more painful depending on the system.</div></div></div></div></div></div></blockquote><div><br></div><div></div><div>Users may also include a function named bcmp in their binary, which will overrides the one from libc.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div>Here's a patch with this proposal to see what this looks like: <a href="https://reviews.llvm.org/D56436" target="_blank">https://reviews.llvm.org/D56436</a></div></div></div></div></div></div></blockquote><div><br></div><div>It feels like this optimization would be better done in llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp,</div></div></div></div></blockquote><div><br></div><div> I'll have a look at this approach.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div>and the presence/name checking done via TargetLibraryInfo.cpp.</div></div></div></div></blockquote><div><br></div><div>Yes, that's how it's done in this version.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div> 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. :)</div></div></div></div></blockquote><div><br></div><div>We were planning to contribute it to compiler-rt. Contributing a deprecated function to the libc sounds.... weird.</div></div></div></div></div></div></blockquote><div><br></div><div>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.</div></div></div></div></blockquote><div><br></div><div>Fair enough, let me give some numbers for this change.</div><div>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. </div><div>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 <a href="https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/algorithms.bench.cpp">family of benchmarks for `BM_StringRelational_Eq`)</a>, which I'm going to use here.</div><div><br></div><div>BM_StringRelational_Eq benchmarks comparison of strings of size 7 (Small), 63 (Large) and 5k (Huge) characters, in four scenarios (scenarii ?):</div><div> - The equal case (Control), which is theoretically the worst case as you have to prove that all bytes are equal.</div><div> - 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).</div><div><br></div><div>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.</div><div><br></div><div><div>```</div><div>#define UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64_t *>(_p))</div><div><br></div><div>extern "C" int bcmp(const void* p1, const void* p2, size_t n) throw() {</div><div>  const char* a = reinterpret_cast<const char*>(p1);</div><div>  const char* b = reinterpret_cast<const char*>(p2);</div><div>  if (n >= 8) {</div><div>    uint64_t u = UNALIGNED_LOAD64(a) ^ UNALIGNED_LOAD64(b);</div><div>    uint64_t v = UNALIGNED_LOAD64(a + n - 8) ^ UNALIGNED_LOAD64(b + n - 8);</div><div>    if ((u | v) != 0) {</div><div>      return 1;</div><div>    }</div><div>  }</div><div>  return memcmp(a, b, n);</div><div>}</div></div><div>```</div><div><br></div><div>Note that:</div><div> - there is a bit of noise in the results, but you'll see that this quite dumb bcmp() reasonably improves {<span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">Large,Huge}_{ChangeFirst,</span><span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">ChangeLast}</span> (note the the  improvement to {<span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">Large,Huge}_</span><span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">ChangeLast</span> cannot be achieved with the semantics of memcmp) without hurting the `<span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">ChangeMiddle` and `Control` cases.</span></div><div> - the small string case (size==7) is not modified by our change because there is a "fast path" for very small sizes on operator==.</div><div> - We are still experimenting with the final bcmp() implementation (in particular improving the `<span style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;font-size:13.3333px">Control` and `ChangeMiddle` cases by improving parallelism</span>). Our current version is better than memcmp() across the board on X86.</div><div><br></div><div><br></div><div><div><span style="font-size:13.3333px"><font face="monospace, monospace">                                                base (ns)   exp (ns)</font></span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Empty_Empty_Control      1.65        1.7</font></span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Empty_Small_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">      </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.37</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">        </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.4</font></span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Empty_Large_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">      </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.37</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.44</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Empty_Huge_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.38</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.44</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Small_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">      </span><span style="font-size:13.3333px"><font face="monospace, monospace">6.53</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">6.51</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Small_ChangeFirst  1.96</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.94</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Small_ChangeMiddle 5.06</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">4.95</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Small_ChangeLast   6.77</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">6.84</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Large_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">      </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.38</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.41</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Small_Huge_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-size:13.3333px"><font face="monospace, monospace">1.37</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.39</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Large_Large_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">      </span><span style="font-size:13.3333px"><font face="monospace, monospace">5.54</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">5.8</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Large_Large_ChangeFirst  6.25</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">3.06</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Large_Large_ChangeMiddle 5.5</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px">  </span><span style="font-family:monospace,monospace;font-size:13.3333px">5.94</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Large_Large_ChangeLast   6.04</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">3.42</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Large_Huge_Control </font></span><span style="font-family:monospace,monospace;font-size:13.3333px">     </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.1</span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px">  </span><span style="font-family:monospace,monospace;font-size:13.3333px">1.1</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Huge_Huge_Control</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">        </span><span style="font-size:13.3333px"><font face="monospace, monospace">118</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px">  </span><span style="font-family:monospace,monospace;font-size:13.3333px">118</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Huge_Huge_ChangeFirst</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">    </span><span style="font-size:13.3333px"><font face="monospace, monospace">5.65</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">3.02</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Huge_Huge_ChangeMiddle</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">   </span><span style="font-family:monospace,monospace;font-size:13.3333px">69.5</span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px"> </span><span style="font-family:monospace,monospace;font-size:13.3333px">66.9</span></div><div><span style="font-size:13.3333px"><font face="monospace, monospace">BM_StringRelational_Eq_Huge_Huge_ChangeLast</font></span><span style="font-family:monospace,monospace;font-size:13.3333px">     </span><span style="font-family:monospace,monospace;font-size:13.3333px">118</span><span style="font-family:monospace,monospace;font-size:13.3333px">       </span><span style="font-family:monospace,monospace;font-size:13.3333px">  </span><span style="font-family:monospace,monospace;font-size:13.3333px">3.43</span></div></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div> </div></div></div></div></div></div></div></div>