FYI, I recommitted the previously removed optimization in r275734. I believe it should fix the LNT performance regression. The benchmarks I used to test this change can be found in D22240 (https://reviews.llvm.org/D22240#3266819f )
/Eric On Sun, Jul 17, 2016 at 3:09 PM, Eric Fiselier <e...@efcs.ca> wrote: > > > On Sun, Jul 17, 2016 at 2:54 PM, Arthur O'Dwyer <arthur.j.odw...@gmail.com > > wrote: > >> Given that this patch is basically Chandler's talk from CppCon 2015 ( >> https://www.youtube.com/watch?v=nXaxk27zwlk), I'm surprised that the >> commit message isn't explicitly mentioning that; and surprised that >> Chandler himself isn't weighing in on either the "this is a good idea" or >> "this is a bad idea" side. >> > > > The commit message should have been clearer. Hopefully Chandler will weigh > in one way or another. > > >> >> IMHO, if replacing "%" with "fastmod" in general-purpose code like this >> were a good idea, >> (A) libc++ should introduce a helper function __fastmod(m,n) for the >> purpose, not repeat the same patch everywhere there's currently a "%" >> operator; and/or >> (B) someone with authority over the Clang x86 backend >> (*cough*Chandler*cough*) should look into improving the codegen for "%" by >> auto-detecting when it might make sense to use this heuristic. >> >> The alleged existence of performance regressions on this patch as it >> stands seems like evidence for doing (B), IMHO, even if it takes longer. >> > > The performance regressions are almost certainly related to the > optimization I removed/replaced in this patch. Previously when > __hash_table::find was walking the bucket elements it would only > re-computer the constrained hash > if the unconstrained hash didn't match that of the element being searched > for. I removed this optimization in this patch with the intent of > re-implementing it in the very near future (it was only in-tree for about a > week). > > What I'm curious about if this performance regression was cause by (1) the > removal of this 2 week old optimization or (2) the implementation of "fast > mod". I suspect it's because of (1). > > I'm writing more benchmarks as we speak to figure this out. > > > >> >> It's also counterintuitive to me that (__h < __bc) would be true any >> significant fraction of the time, on a 64-bit platform. Does this happen >> because __bc is often astronomically high, or because __h is often >> astronomically low (presumably due to bad hash functions, such as "always >> hash to constant 0")? >> > > It happens due to bad hash functions. Primarily because integral types use > the identify hash function. > > >> >> my $.02, >> Arthur >> >> >> On Sun, Jul 17, 2016 at 1:11 PM, Eric Fiselier via cfe-commits < >> cfe-commits@lists.llvm.org> wrote: >> >>> Hi Duncan, >>> >>> It's possibly expected. It depends on what operation it's performing. I >>> expected a bit of a performance drop in some cases but I have a plan to fix >>> those. >>> Do you have a link to LNT? >>> >>> On Wed, Jul 13, 2016 at 6:41 PM, Duncan P. N. Exon Smith < >>> dexonsm...@apple.com> wrote: >>> >>>> Hmm. I implied there were other regressions, but I just finished >>>> scanning them. Shootout-C++/hash2 is the only major one. The others were >>>> small, and only at -O0. >>>> >>>> > On 2016-Jul-13, at 17:38, Duncan P. N. Exon Smith via cfe-commits < >>>> cfe-commits@lists.llvm.org> wrote: >>>> > >>>> > We saw mixed results from this on LNT, including some major >>>> regressions. For example, on x86_64, >>>> SingleSource/Benchmarks/Shootout-C++/hash2 regressed 18.5% at -O3 and over >>>> 20% at -Os. >>>> > >>>> > Is this expected? >>>> >>>> ^ Still interested in an answer, though ;). >>>> >>>> > >>>> >> On 2016-Jul-11, at 15:02, Eric Fiselier via cfe-commits < >>>> cfe-commits@lists.llvm.org> wrote: >>>> >> >>>> >> Author: ericwf >>>> >> Date: Mon Jul 11 17:02:02 2016 >>>> >> New Revision: 275114 >>>> >> >>>> >> URL: http://llvm.org/viewvc/llvm-project?rev=275114&view=rev >>>> >> Log: >>>> >> Don't compute modulus of hash if it is smaller than the bucket count. >>>> >> >>>> >> This cleans up a previous optimization attempt in hash, and results >>>> in >>>> >> additional performance improvements over that previous attempt. >>>> Additionally >>>> >> this new optimization does not hinder the power of 2 bucket count >>>> optimization. >>>> >> >>>> >> Modified: >>>> >> libcxx/trunk/include/__hash_table >>>> >> >>>> >> Modified: libcxx/trunk/include/__hash_table >>>> >> URL: >>>> http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/__hash_table?rev=275114&r1=275113&r2=275114&view=diff >>>> >> >>>> ============================================================================== >>>> >> --- libcxx/trunk/include/__hash_table (original) >>>> >> +++ libcxx/trunk/include/__hash_table Mon Jul 11 17:02:02 2016 >>>> >> @@ -90,7 +90,8 @@ inline _LIBCPP_INLINE_VISIBILITY >>>> >> size_t >>>> >> __constrain_hash(size_t __h, size_t __bc) >>>> >> { >>>> >> - return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; >>>> >> + return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : >>>> >> + (__h < __bc ? __h : __h % __bc); >>>> >> } >>>> >> >>>> >> inline _LIBCPP_INLINE_VISIBILITY >>>> >> @@ -2201,8 +2202,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc> >>>> >> if (__nd != nullptr) >>>> >> { >>>> >> for (__nd = __nd->__next_; __nd != nullptr && >>>> >> - (__hash == __nd->__hash_ >>>> >> - || __constrain_hash(__nd->__hash_, __bc) == >>>> __chash); >>>> >> + __constrain_hash(__nd->__hash_, __bc) == __chash; >>>> >> __nd = >>>> __nd->__next_) >>>> >> { >>>> >> if ((__nd->__hash_ == __hash) && >>>> key_eq()(__nd->__value_, __k)) >>>> >> @@ -2231,8 +2231,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc> >>>> >> if (__nd != nullptr) >>>> >> { >>>> >> for (__nd = __nd->__next_; __nd != nullptr && >>>> >> - (__hash == __nd->__hash_ >>>> >> - || __constrain_hash(__nd->__hash_, __bc) == >>>> __chash); >>>> >> + __constrain_hash(__nd->__hash_, __bc) == __chash; >>>> >> __nd = >>>> __nd->__next_) >>>> >> { >>>> >> if ((__nd->__hash_ == __hash) && >>>> key_eq()(__nd->__value_, __k)) >>>> >> >>>> >> >>>> >> _______________________________________________ >>>> >> cfe-commits mailing list >>>> >> cfe-commits@lists.llvm.org >>>> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits >>>> > >>>> > _______________________________________________ >>>> > cfe-commits mailing list >>>> > cfe-commits@lists.llvm.org >>>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits >>>> >>>> >>> >>> _______________________________________________ >>> cfe-commits mailing list >>> cfe-commits@lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits >>> >>> >> >
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
