Hi Howard, Thanks for the advice. I'll make sure to performance test these changes without moving forward. I also appreciate the insight.
> 0 is a valid bucket count. An upward bump of 0 buckets goes to 2. 1 is considered not a power of 2, but it rounded up to 2. 2 is considered prime, not a power of 2. Thus a upward bump off bucket size 2 goes to 5, not 4. Are you referring to the input/output from the __next_power2 function? Passing 1 to __next_power2 causes undefined behavior because it passes 0 to __clz. I'll consider just backing out these changes and renaming the functions so they don't imply mathematical accuracy. Thanks On Sun, Aug 17, 2014 at 7:13 PM, Howard Hinnant <[email protected]> wrote: > Just a word of caution: > > These functions were not intended to be mathematically accurate. They > were intended to make the unordered containers as fast as possible. > Performance tests (not checked in) were used to tune these functions. Put > one too many branches in a hot path, and you can easily destroy the > performance gains that were intended by allowing power-of-2 bucket sizes. > I’m not saying this patch does this. I’m just saying, you are in danger of > doing so if you haven’t performance tested these changes. > > Also, for the purpose of the libc++ unordered containers: > > 0 is a valid bucket count. An upward bump of 0 buckets goes to 2. > 1 is considered not a power of 2, but it rounded up to 2. > 2 is considered prime, not a power of 2. Thus a upward bump off bucket > size 2 goes to 5, not 4. > > For all other bucket sizes, it is unambiguous as to whether one is dealing > with a prime or power of 2. > > These definitions are intended to promote best practices for the libc++ > unordered containers, as opposed to being mathematically accurate. > > Howard > > On Aug 17, 2014, at 8:46 PM, Eric Fiselier <[email protected]> wrote: > > > I've abstracted the changes to __hash_table to call __is_rehash_power2. > As for internal API testing, there currently is none. there has been some > offline discussion about changing that and (this being a motivating case). > I'll bring it up with Marshall again when he gets back. > > > > http://reviews.llvm.org/D4948 > > > > Files: > > include/__hash_table > > > > Index: include/__hash_table > > =================================================================== > > --- include/__hash_table > > +++ include/__hash_table > > @@ -63,7 +63,7 @@ > > bool > > __is_power2(size_t __bc) > > { > > - return __bc > 2 && !(__bc & (__bc - 1)); > > + return __bc && !(__bc & (__bc - 1)); > > } > > > > inline _LIBCPP_INLINE_VISIBILITY > > @@ -74,10 +74,17 @@ > > } > > > > inline _LIBCPP_INLINE_VISIBILITY > > +bool __is_rehash_power2(size_t __bc) > > +{ > > + return __bc > 2 && __is_power2(__bc); > > +} > > + > > +inline _LIBCPP_INLINE_VISIBILITY > > size_t > > __next_pow2(size_t __n) > > { > > - return size_t(1) << (std::numeric_limits<size_t>::digits - > __clz(__n-1)); > > + return __n < 2 ? __n + 1 > > + : size_t(1) << (std::numeric_limits<size_t>::digits - > __clz(__n-1)); > > } > > > > template <class _Tp, class _Hash, class _Equal, class _Alloc> class > __hash_table; > > @@ -1615,7 +1622,7 @@ > > { > > if (size()+1 > __bc * max_load_factor() || __bc == 0) > > { > > - rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), > > + rehash(_VSTD::max<size_type>(2 * __bc + > __is_rehash_power2(__bc), > > size_type(ceil(float(size() + 1) / > max_load_factor())))); > > __bc = bucket_count(); > > __chash = __constrain_hash(__nd->__hash_, __bc); > > @@ -1658,7 +1665,7 @@ > > size_type __bc = bucket_count(); > > if (size()+1 > __bc * max_load_factor() || __bc == 0) > > { > > - rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), > > + rehash(_VSTD::max<size_type>(2 * __bc + > __is_rehash_power2(__bc), > > size_type(ceil(float(size() + 1) / > max_load_factor())))); > > __bc = bucket_count(); > > } > > @@ -1728,7 +1735,7 @@ > > size_type __bc = bucket_count(); > > if (size()+1 > __bc * max_load_factor() || __bc == 0) > > { > > - rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), > > + rehash(_VSTD::max<size_type>(2 * __bc + > __is_rehash_power2(__bc), > > size_type(ceil(float(size() + 1) / > max_load_factor())))); > > __bc = bucket_count(); > > } > > @@ -1776,7 +1783,7 @@ > > __node_holder __h = __construct_node(__x, __hash); > > if (size()+1 > __bc * max_load_factor() || __bc == 0) > > { > > - rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), > > + rehash(_VSTD::max<size_type>(2 * __bc + > __is_rehash_power2(__bc), > > size_type(ceil(float(size() + 1) / > max_load_factor())))); > > __bc = bucket_count(); > > __chash = __constrain_hash(__hash, __bc); > > @@ -1946,8 +1953,9 @@ > > __n = _VSTD::max<size_type> > > ( > > __n, > > - __is_power2(__bc) ? > __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : > > - > __next_prime(size_t(ceil(float(size()) / max_load_factor()))) > > + (__is_rehash_power2(__bc)) > > + ? __next_pow2(size_t(ceil(float(size()) / > max_load_factor()))) > > + : __next_prime(size_t(ceil(float(size()) / > max_load_factor()))) > > ); > > if (__n < __bc) > > __rehash(__n); > > <D4948.12598.patch>_______________________________________________ > > cfe-commits mailing list > > [email protected] > > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits > >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
