[Boost-commit] svn:boost r86608 - trunk/libs/unordered/doc

Subject: [Boost-commit] svn:boost r86608 - trunk/libs/unordered/doc
From: dnljms_at_[hidden]
Date: 2013-11-10 18:26:21

Author: danieljames
Date: 2013-11-10 18:26:21 EST (Sun, 10 Nov 2013)
New Revision: 86608
URL: http://svn.boost.org/trac/boost/changeset/86608

Log:
Update the unordered rationale.

I just noticed that it wan't updated for the changes on 64 bit platforms.
Not very good, but I don't want to spend too long on this.  I'm tempted to just
delete it.

Text files modified: 
   trunk/libs/unordered/doc/rationale.qbk |    19 ++++++++++++-------                     
   1 files changed, 12 insertions(+), 7 deletions(-)

Modified: trunk/libs/unordered/doc/rationale.qbk
==============================================================================
--- trunk/libs/unordered/doc/rationale.qbk	Sun Nov 10 18:25:54 2013	(r86607)
+++ trunk/libs/unordered/doc/rationale.qbk	2013-11-10 18:26:21 EST (Sun, 10 Nov 2013)	(r86608)
@@ -85,7 +85,8 @@
 
 Using a prime number of buckets, and choosing a bucket by using the modulus
 of the hash function's result will usually give a good result. The downside
-is that the required modulus operation is fairly expensive.
+is that the required modulus operation is fairly expensive. This is what the
+containers do in most cases.
 
 Using a power of 2 allows for much quicker selection of the bucket
 to use, but at the expense of loosing the upper bits of the hash value.
@@ -95,12 +96,16 @@
 
 To avoid this a transformation could be applied to the hash function, for an
 example see __wang__.  Unfortunately, a transformation like Wang's requires
-knowledge of the number of bits in the hash value, so it isn't portable enough.
-This leaves more expensive methods, such as Knuth's Multiplicative Method
-(mentioned in Wang's article). These don't tend to work as well as taking the
-modulus of a prime, and the extra computation required might negate
-efficiency advantage of power of 2 hash tables.
+knowledge of the number of bits in the hash value, so it isn't portable enough
+to use as a default. It can applicable in certain cases so the containers
+have a policy based implementation that can use this alternative technique.
 
-So, this implementation uses a prime number for the hash table size.
+Currently this is only done on 64 bit architecures, where prime number
+modulus can be expensive. Although this varies depending on the architecture,
+so I probably should revisit it.
+
+I'm also thinking of introducing a mechanism whereby a hash function can
+indicate that it's safe to be used directly with power of 2 buckets, in
+which case a faster plain power of 2 implementation can be used.
 
 [endsect]