[Hashtable,1/6] Code simplification/optimization
diff mbox series

Message ID f52ec3c7-5116-9c0f-4a02-da1c91a922ad@gmail.com
State New
Headers show
Series
  • [Hashtable,1/6] Code simplification/optimization
Related show

Commit Message

François Dumont Nov. 17, 2019, 8:51 p.m. UTC
This patch simplifies a number of implementations.

It tries as much as possible to avoid computing hash code. This is 
especially true for the erase implementation in case of multi keys.


     * include/bits/hashtable_policy.h (_Map_base<>::at): Use
     _Hashtable<>::find.
(_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals):New.
     (_Hashtable_base<>::_M_node_equals): New, use latter.
     * include/bits/hashtable.h (_Hashtable<>::_M_update_bbegin): New.
     (_Hashtable<>::_M_assign): Use latter.
     (_Hashtable<>::_M_move_assign): Likewise.
     (_Hashtable<>(_Hashtable<>&&)): Likewise.
     (_Hashtable<>(_Hashtable<>&&, const allocator_type&)): Likewise.
     (_Hashtable<>::swap): Likewise.
     (_Hashtable<>::find): Build iterator directly from _M_find_node result.
     (_Hashtable<>::count): Use _Hashtable<>::find.
     (_Hashtable<>::equal_range): Likewise.
     (_Hashtable<>::_M_erase(false_type, const key_type&)): Use
     _M_node_equals.

Tested under Linux x86_64.

François

Patch
diff mbox series

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index ef71c090f3b..b8cfdde2f31 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -378,6 +378,20 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // numerous checks in the code to avoid 0 modulus.
       __bucket_type		_M_single_bucket	= nullptr;
 
+      void
+      _M_update_bbegin()
+      {
+	if (_M_begin())
+	  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      }
+
+      void
+      _M_update_bbegin(__node_type* __n)
+      {
+	_M_before_begin._M_nxt = __n;
+	_M_update_bbegin();
+      }
+
       bool
       _M_uses_single_bucket(__bucket_type* __bkts) const
       { return __builtin_expect(__bkts == &_M_single_bucket, false); }
@@ -674,7 +688,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __k) const;
 
-    protected:
+    private:
       // Bucket index computation helpers.
       size_type
       _M_bucket_index(__node_type* __n) const noexcept
@@ -1196,8 +1210,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      = __node_gen(__fwd_value(std::forward<_Ht>(__ht),
 				       __ht_n->_M_v()));
 	    this->_M_copy_code(__this_n, __ht_n);
-	    _M_before_begin._M_nxt = __this_n;
-	    _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
+	    _M_update_bbegin(__this_n);
 
 	    // Then deal with other nodes.
 	    __node_base* __prev_n = __this_n;
@@ -1259,15 +1272,14 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_buckets = &_M_single_bucket;
 	  _M_single_bucket = __ht._M_single_bucket;
 	}
+
       _M_bucket_count = __ht._M_bucket_count;
       _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
       _M_element_count = __ht._M_element_count;
       std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
 
-      // Fix buckets containing the _M_before_begin pointers that can't be
-      // moved.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      // Fix bucket containing the _M_before_begin pointer that can't be moved.
+      _M_update_bbegin();
       __ht._M_reset();
     }
 
@@ -1335,10 +1347,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_single_bucket = __ht._M_single_bucket;
 	}
 
-      // Update, if necessary, bucket pointing to before begin that hasn't
-      // moved.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      // Fix bucket containing the _M_before_begin pointer that can't be moved.
+      _M_update_bbegin();
 
       __ht._M_reset();
     }
@@ -1389,11 +1399,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  else
 	    _M_buckets = __ht._M_buckets;
 
-	  _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
-	  // Update, if necessary, bucket pointing to before begin that hasn't
+	  // Fix bucket containing the _M_before_begin pointer that can't be
 	  // moved.
-	  if (_M_begin())
-	    _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+	  _M_update_bbegin(__ht._M_begin());
+
 	  __ht._M_reset();
 	}
       else
@@ -1457,14 +1466,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::swap(_M_element_count, __x._M_element_count);
       std::swap(_M_single_bucket, __x._M_single_bucket);
 
-      // Fix buckets containing the _M_before_begin pointers that can't be
-      // swapped.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
-
-      if (__x._M_begin())
-	__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
-	  = &__x._M_before_begin;
+      // Fix bucket containing the _M_before_begin pointer that can't be swap.
+      _M_update_bbegin();
+      __x._M_update_bbegin();
     }
 
   template<typename _Key, typename _Value,
@@ -1479,8 +1483,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
-      return __p ? iterator(__p) : end();
+      return iterator(_M_find_node(__bkt, __k, __code));
     }
 
   template<typename _Key, typename _Value,
@@ -1495,8 +1498,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
-      return __p ? const_iterator(__p) : end();
+      return const_iterator(_M_find_node(__bkt, __k, __code));
     }
 
   template<typename _Key, typename _Value,
@@ -1509,25 +1511,22 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     count(const key_type& __k) const
     -> size_type
     {
-      __hash_code __code = this->_M_hash_code(__k);
-      std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_bucket_begin(__bkt);
-      if (!__p)
+      auto __it = find(__k);
+      if (!__it._M_cur)
 	return 0;
 
-      std::size_t __result = 0;
-      for (;; __p = __p->_M_next())
-	{
-	  if (this->_M_equals(__k, __code, __p))
-	    ++__result;
-	  else if (__result)
-	    // All equivalent values are next to each other, if we
-	    // found a non-equivalent value after an equivalent one it
-	    // means that we won't find any new equivalent value.
-	    break;
-	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
-	    break;
-	}
+      if (__unique_keys::value)
+	return 1;
+
+      // All equivalent values are next to each other, if we find a
+      // non-equivalent value after an equivalent one it means that we won't
+      // find any new equivalent value.
+      size_type __result = 1;
+      for (auto __ref = __it++;
+	   __it._M_cur && this->_M_node_equals(__ref._M_cur, __it._M_cur);
+	   ++__it)
+	++__result;
+
       return __result;
     }
 
@@ -1541,21 +1540,21 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(const key_type& __k)
     -> pair<iterator, iterator>
     {
-      __hash_code __code = this->_M_hash_code(__k);
-      std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      auto __ite = find(__k);
+      if (!__ite._M_cur)
+	return { __ite, __ite };
 
-      if (__p)
-	{
-	  __node_type* __p1 = __p->_M_next();
-	  while (__p1 && _M_bucket_index(__p1) == __bkt
-		 && this->_M_equals(__k, __code, __p1))
-	    __p1 = __p1->_M_next();
+      auto __beg = __ite++;
+      if (__unique_keys::value)
+	return { __beg, __ite };
 
-	  return std::make_pair(iterator(__p), iterator(__p1));
-	}
-      else
-	return std::make_pair(end(), end());
+      // All equivalent values are next to each other, if we find a
+      // non-equivalent value after an equivalent one it means that we won't
+      // find any new equivalent value.
+      while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur))
+	++__ite;
+
+      return { __beg, __ite };
     }
 
   template<typename _Key, typename _Value,
@@ -1568,25 +1567,25 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(const key_type& __k) const
     -> pair<const_iterator, const_iterator>
     {
-      __hash_code __code = this->_M_hash_code(__k);
-      std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      auto __ite = find(__k);
+      if (!__ite._M_cur)
+	return { __ite, __ite };
 
-      if (__p)
-	{
-	  __node_type* __p1 = __p->_M_next();
-	  while (__p1 && _M_bucket_index(__p1) == __bkt
-		 && this->_M_equals(__k, __code, __p1))
-	    __p1 = __p1->_M_next();
+      auto __beg = __ite++;
+      if (__unique_keys::value)
+	return { __beg, __ite };
 
-	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
-	}
-      else
-	return std::make_pair(end(), end());
+      // All equivalent values are next to each other, if we find a
+      // non-equivalent value after an equivalent one it means that we won't
+      // find any new equivalent value.
+      while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur))
+	++__ite;
+
+      return { __beg, __ite };
     }
 
-  // Find the node whose key compares equal to k in the bucket bkt.
-  // Return nullptr if no node is found.
+  // Find the node before the one whose key compares equal to k in the bucket
+  // bkt. Return nullptr if no node is found.
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
@@ -1612,6 +1611,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    break;
 	  __prev_p = __p;
 	}
+
       return nullptr;
     }
 
@@ -1638,10 +1638,12 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  // contain _M_before_begin pointer.
 	  __node->_M_nxt = _M_before_begin._M_nxt;
 	  _M_before_begin._M_nxt = __node;
+
 	  if (__node->_M_nxt)
 	    // We must update former begin bucket that is pointing to
 	    // _M_before_begin.
 	    _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
+
 	  _M_buckets[__bkt] = &_M_before_begin;
 	}
     }
@@ -1968,16 +1970,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // them so that the key stays valid during the first loop. It might be
       // invalidated indirectly when destroying nodes.
       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
-      __node_type* __n_last = __n;
-      std::size_t __n_last_bkt = __bkt;
-      do
-	{
-	  __n_last = __n_last->_M_next();
-	  if (!__n_last)
-	    break;
-	  __n_last_bkt = _M_bucket_index(__n_last);
-	}
-      while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
+      __node_type* __n_last = __n->_M_next();
+      while (__n_last && this->_M_node_equals(__n, __n_last))
+	__n_last = __n_last->_M_next();
+
+      std::size_t __n_last_bkt = __n_last ? _M_bucket_index(__n_last) : __bkt;
 
       // Deallocate nodes.
       size_type __result = 0;
@@ -1987,13 +1984,13 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  this->_M_deallocate_node(__n);
 	  __n = __p;
 	  ++__result;
-	  --_M_element_count;
 	}
       while (__n != __n_last);
 
+      _M_element_count -= __result;
       if (__prev_n == _M_buckets[__bkt])
 	_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
-      else if (__n_last && __n_last_bkt != __bkt)
+      else if (__n_last_bkt != __bkt)
 	_M_buckets[__n_last_bkt] = __prev_n;
       __prev_n->_M_nxt = __n_last;
       return __result;
@@ -2139,6 +2136,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
 	      __new_buckets[__bkt]->_M_nxt = __p;
 	    }
+
 	  __p = __next;
 	}
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index b9320506bb2..f6c40be3b91 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -770,13 +770,11 @@  namespace __detail
     -> mapped_type&
     {
       __hashtable* __h = static_cast<__hashtable*>(this);
-      __hash_code __code = __h->_M_hash_code(__k);
-      std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
+      auto __ite = __h->find(__k);
 
-      if (!__p)
+      if (!__ite._M_cur)
 	__throw_out_of_range(__N("_Map_base::at"));
-      return __p->_M_v().second;
+      return __ite->second;
     }
 
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -789,13 +787,11 @@  namespace __detail
     -> const mapped_type&
     {
       const __hashtable* __h = static_cast<const __hashtable*>(this);
-      __hash_code __code = __h->_M_hash_code(__k);
-      std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
+      auto __ite = __h->find(__k);
 
-      if (!__p)
+      if (!__ite._M_cur)
 	__throw_out_of_range(__N("_Map_base::at"));
-      return __p->_M_v().second;
+      return __ite->second;
     }
 
   /**
@@ -1796,17 +1792,26 @@  namespace __detail
     template<typename _NodeT>
       struct _Equal_hash_code
       {
-       static bool
-       _S_equals(__hash_code, const _NodeT&)
-       { return true; }
+	static bool
+	_S_equals(__hash_code, const _NodeT&)
+	{ return true; }
+
+	static bool
+	_S_node_equals(const _NodeT&, const _NodeT&)
+	{ return true; }
       };
 
     template<typename _Ptr2>
       struct _Equal_hash_code<_Hash_node<_Ptr2, __hash_cached_t>>
       {
-       static bool
-       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n)
-       { return __c == __n._M_hash_code; }
+	static bool
+	_S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n)
+	{ return __c == __n._M_hash_code; }
+
+	static bool
+	_S_node_equals(const _Hash_node<_Ptr2, __hash_cached_t>& __lhn,
+		       const _Hash_node<_Ptr2, __hash_cached_t>& __rhn)
+	{ return __lhn._M_hash_code == __rhn._M_hash_code; }
       };
 
   protected:
@@ -1817,7 +1822,7 @@  namespace __detail
     { }
 
     bool
-    _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
+    _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const
     {
       static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
 	  "key equality predicate must be invocable with two arguments of "
@@ -1826,6 +1831,14 @@  namespace __detail
 	&& _M_eq()(__k, this->_M_extract()(__n->_M_v()));
     }
 
+    bool
+    _M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const
+    {
+      return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn)
+	&& _M_eq()(this->_M_extract()(__lhn->_M_v()),
+		   this->_M_extract()(__rhn->_M_v()));
+    }
+
     void
     _M_swap(_Hashtable_base& __x)
     {