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
