[Boost-commit] svn:boost r52292 - in trunk: boost/asio/detail libs/asio/doc

Subject: [Boost-commit] svn:boost r52292 - in trunk: boost/asio/detail libs/asio/doc
From: chris_at_[hidden]
Date: 2009-04-09 08:09:17

Author: chris_kohlhoff
Date: 2009-04-09 08:09:16 EDT (Thu, 09 Apr 2009)
New Revision: 52292
URL: http://svn.boost.org/trac/boost/changeset/52292

Log:
Implement automatic resizing of the bucket array in the internal hash maps.
This is to improve performance for very large numbers of asynchronous
operations and also to reduce memory usage for very small numbers. A new
macro BOOST_ASIO_HASH_MAP_BUCKETS may be used to tweak the sizes used for the
bucket arrays.

Text files modified: 
   trunk/boost/asio/detail/hash_map.hpp |    77 +++++++++++++++++++++++++++++++++------ 
   trunk/libs/asio/doc/using.qbk        |    21 ++++++++++                              
   2 files changed, 86 insertions(+), 12 deletions(-)

Modified: trunk/boost/asio/detail/hash_map.hpp
==============================================================================
--- trunk/boost/asio/detail/hash_map.hpp	(original)
+++ trunk/boost/asio/detail/hash_map.hpp	2009-04-09 08:09:16 EDT (Thu, 09 Apr 2009)
@@ -21,6 +21,7 @@
 #include <cassert>
 #include <list>
 #include <utility>
+#include <vector>
 #include <boost/functional/hash.hpp>
 #include <boost/asio/detail/pop_options.hpp>
 
@@ -61,10 +62,9 @@
 
   // Constructor.
   hash_map()
+    : size_(0)
   {
-    // Initialise all buckets to empty.
-    for (size_t i = 0; i < num_buckets; ++i)
-      buckets_[i].first = buckets_[i].last = values_.end();
+    rehash(hash_size(0));
   }
 
   // Get an iterator for the beginning of the map.
@@ -100,7 +100,7 @@
   // Find an entry in the map.
   iterator find(const K& k)
   {
-    size_t bucket = calculate_hash_value(k) % num_buckets;
+    size_t bucket = calculate_hash_value(k) % buckets_.size();
     iterator it = buckets_[bucket].first;
     if (it == values_.end())
       return values_.end();
@@ -118,7 +118,7 @@
   // Find an entry in the map.
   const_iterator find(const K& k) const
   {
-    size_t bucket = calculate_hash_value(k) % num_buckets;
+    size_t bucket = calculate_hash_value(k) % buckets_.size();
     const_iterator it = buckets_[bucket].first;
     if (it == values_.end())
       return it;
@@ -136,12 +136,15 @@
   // Insert a new entry into the map.
   std::pair<iterator, bool> insert(const value_type& v)
   {
-    size_t bucket = calculate_hash_value(v.first) % num_buckets;
+    if (size_ + 1 >= buckets_.size())
+      rehash(hash_size(size_ + 1));
+    size_t bucket = calculate_hash_value(v.first) % buckets_.size();
     iterator it = buckets_[bucket].first;
     if (it == values_.end())
     {
       buckets_[bucket].first = buckets_[bucket].last =
         values_insert(values_.end(), v);
+      ++size_;
       return std::pair<iterator, bool>(buckets_[bucket].last, true);
     }
     iterator end = buckets_[bucket].last;
@@ -153,6 +156,7 @@
       ++it;
     }
     buckets_[bucket].last = values_insert(end, v);
+    ++size_;
     return std::pair<iterator, bool>(buckets_[bucket].last, true);
   }
 
@@ -161,7 +165,7 @@
   {
     assert(it != values_.end());
 
-    size_t bucket = calculate_hash_value(it->first) % num_buckets;
+    size_t bucket = calculate_hash_value(it->first) % buckets_.size();
     bool is_first = (it == buckets_[bucket].first);
     bool is_last = (it == buckets_[bucket].last);
     if (is_first && is_last)
@@ -172,6 +176,7 @@
       --buckets_[bucket].last;
 
     values_erase(it);
+    --size_;
   }
 
   // Remove all entries from the map.
@@ -179,13 +184,61 @@
   {
     // Clear the values.
     values_.clear();
+    size_ = 0;
 
     // Initialise all buckets to empty.
-    for (size_t i = 0; i < num_buckets; ++i)
+    for (size_t i = 0; i < buckets_.size(); ++i)
       buckets_[i].first = buckets_[i].last = values_.end();
   }
 
 private:
+  // Calculate the hash size for the specified number of elements.
+  static std::size_t hash_size(std::size_t num_elems)
+  {
+    static std::size_t sizes[] =
+    {
+#if defined(BOOST_ASIO_HASH_MAP_BUCKETS)
+      BOOST_ASIO_HASH_MAP_BUCKETS
+#else // BOOST_ASIO_HASH_MAP_BUCKETS
+      3, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
+      49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
+      12582917, 25165843
+#endif // BOOST_ASIO_HASH_MAP_BUCKETS
+    };
+    const std::size_t nth_size = sizeof(sizes) / sizeof(std::size_t) - 1;
+    for (std::size_t i = 0; i < nth_size; ++i)
+      if (num_elems < sizes[i])
+        return sizes[i];
+    return sizes[nth_size];
+  }
+
+  // Re-initialise the hash from the values already contained in the list.
+  void rehash(std::size_t num_buckets)
+  {
+    iterator end = values_.end();
+
+    // Update number of buckets and initialise all buckets to empty.
+    buckets_.resize(num_buckets);
+    for (std::size_t i = 0; i < buckets_.size(); ++i)
+      buckets_[i].first = buckets_[i].last = end;
+
+    // Put all values back into the hash.
+    iterator iter = values_.begin();
+    while (iter != end)
+    {
+      std::size_t bucket = calculate_hash_value(iter->first) % buckets_.size();
+      if (buckets_[bucket].last == end)
+      {
+        buckets_[bucket].first = buckets_[bucket].last = iter++;
+      }
+      else
+      {
+        values_.splice(++buckets_[bucket].last, values_, iter++);
+        --buckets_[bucket].last;
+      }
+    }
+  }
+
   // Insert an element into the values list by splicing from the spares list,
   // if a spare is available, and otherwise by inserting a new element.
   iterator values_insert(iterator it, const value_type& v)
@@ -209,6 +262,9 @@
     spares_.splice(spares_.begin(), values_, it);
   }
 
+  // The number of elements in the hash.
+  std::size_t size_;
+
   // The list of all values in the hash map.
   std::list<value_type> values_;
 
@@ -223,11 +279,8 @@
     iterator last;
   };
 
-  // The number of buckets in the hash.
-  enum { num_buckets = 1021 };
-
   // The buckets in the hash.
-  bucket_type buckets_[num_buckets];
+  std::vector<bucket_type> buckets_;
 };
 
 } // namespace detail

Modified: trunk/libs/asio/doc/using.qbk
==============================================================================
--- trunk/libs/asio/doc/using.qbk	(original)
+++ trunk/libs/asio/doc/using.qbk	2009-04-09 08:09:16 EDT (Thu, 09 Apr 2009)
@@ -269,6 +269,27 @@
       automatically if `BOOST_NO_TYPEID` is defined.
     ]
   ]
+  [
+    [`BOOST_ASIO_HASH_MAP_BUCKETS`]
+    [
+      Determines the number of buckets in Boost.Asio's internal `hash_map`
+      objects. The value should be a comma separated list of prime numbers, in
+      ascending order. The `hash_map` implementation will automatically
+      increase the number of buckets as the number of elements in the map
+      increases.
+
+      Some examples:
+
+      * Defining `BOOST_ASIO_HASH_MAP_BUCKETS` to `1021` means that the
+        `hash_map` objects will always contain 1021 buckets, irrespective of
+        the number of elements in the map.
+
+      * Defining `BOOST_ASIO_HASH_MAP_BUCKETS` to `53,389,1543` means that the
+        `hash_map` objects will initially contain 53 buckets. The number of
+        buckets will be increased to 389 and then 1543 as elements are added to
+        the map.
+    ]
+  ]
 ]
 
 [heading Mailing List]