On Fri, Jul 06, 2012 at 05:31:14PM -0000, Howard Hinnant wrote: > Author: hhinnant > Date: Fri Jul 6 12:31:14 2012 > New Revision: 159836 > > URL: http://llvm.org/viewvc/llvm-project?rev=159836&view=rev > Log: > This commit establishes a new bucket_count policy in the unordered > containers: The policy now allows a power-of-2 number of buckets to > be requested (and that request honored) by the client. > And if the number of buckets is set to a power of 2, then the constraint > of the hash to the number of buckets uses & instead of %.
Does the standard place any constraints in this area? So with this change, power-of-two sized hash tables still have a conditional in the hot path. The only justification for using non-power-of-two hashes seems to be extremely poor user-provided hash functions, which sounds like a lame excuse. The complexity of computing primes basically just goes back to the argument that linear series with increments smaller than the prime itself are evenly distributed. The same or similar properties can be obtained using double-width-multiplication-and-mask universal hash functions (hash(x) = hi(dw(x) * T), where dw casts x to a type twice the size and hi gives the upper half). They are no more expensive to compute than the double multiplication version of the modulo and significant cheaper than using modulo directly on most (all?) platforms. So: why not kill the complexity and require power-of-two bucket counts and clients to use a sane hash function? Joerg _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
