Patchwork unordered profile mode patch

login
register
mail settings
Submitter François Dumont
Date May 6, 2013, 8 p.m.
Message ID <51880BD9.7060904@gmail.com>
Download mbox | patch
Permalink /patch/241768/
State New
Headers show

Comments

François Dumont - May 6, 2013, 8 p.m.
Hi

     Here is the patch to fix the unordered containers profile mode. 
There are a number of enhancements/fixes:
- Use inheritance to play code on instantiation/destruction. This way 
some constructors and assignment operators can be defaulted like in the 
normal implementation and then be deleted if the normal implementation 
has his special function deleted.
- Extend the Inefficient Hash diagnostic to the unordered_multiset and 
unordered_multimap. Surprisingly __profcxx_hashtable_destruct2 was 
called without __profcxx_hashtable_construct2 so having only the 
performance drawback without beneficing from the diagnostic result. I 
implemented it by simply ignoring equivalent elements.
- Do not collect data for the Inefficient Hash diagnostic if it is not 
On, it is a costly operation.
- Use an implementation detail, the cached hash code, when possible. 
This is good for performance and mandatory for robustness because the 
hash functor can throw and the code is called from the destructor. Some 
tests were failing because of that since I had the 
__gnu_cxx::throw_value_* hash functor to conditionally throw.
- Remove useless non-Standard insert(const value_type*, const 
value_type*) overloads.

I also add a missing & in the MoveOnly equality functor signature of 
55043.cc test file. I don't think it was intentional and it was a 
problem for the profile modes that uses it.

Regarding usage of cached hash code I realized that none of the Standard 
methods of the unordered containers allowed to benefit from it. There is 
no gate between iterator and local_iterator. Has a size_type 
bucket(const_iterator) signature been discussed ?

Tested on x86_64 linux profile mode.

2013-05-07  François Dumont <fdumont@gcc.gnu.org>

     * include/profile/unordered_base.h: New.
     * include/Makefile.am: Add new profile header.
     * include/Makefile.in: Regenerate.
     * include/profile/impl/profiler.h
     (__profcxx_inefficient_hash_is_on): New macro.
     * include/profile/unordered_map (std::profile::unordered_map<>):
     Use new _Unordered_profile base class. Use default implementations
     for special functions.
     (std::profile::unordered_multimap<>): Likewise.
     * include/profile/unordered_set (std::profile::unordered_set<>):
     Likewise.
     (std::profile::unordered_multiset<>): Likewise.
     * testsuite/23_containers/unordered_multiset/55043.cc: Fix
     MoveOnly equality operator signature.

Ok to commit ?

François
Paolo Carlini - May 7, 2013, 9:30 a.m.
Hi,

On 05/06/2013 10:00 PM, François Dumont wrote:
> Hi
>
>     Here is the patch to fix the unordered containers profile mode. 
> There are a number of enhancements/fixes:
> - Use inheritance to play code on instantiation/destruction. This way 
> some constructors and assignment operators can be defaulted like in 
> the normal implementation and then be deleted if the normal 
> implementation has his special function deleted.
> - Extend the Inefficient Hash diagnostic to the unordered_multiset and 
> unordered_multimap. Surprisingly __profcxx_hashtable_destruct2 was 
> called without __profcxx_hashtable_construct2 so having only the 
> performance drawback without beneficing from the diagnostic result. I 
> implemented it by simply ignoring equivalent elements.
> - Do not collect data for the Inefficient Hash diagnostic if it is not 
> On, it is a costly operation.
> - Use an implementation detail, the cached hash code, when possible. 
> This is good for performance and mandatory for robustness because the 
> hash functor can throw and the code is called from the destructor. 
> Some tests were failing because of that since I had the 
> __gnu_cxx::throw_value_* hash functor to conditionally throw.
> - Remove useless non-Standard insert(const value_type*, const 
> value_type*) overloads.
>
> I also add a missing & in the MoveOnly equality functor signature of 
> 55043.cc test file. I don't think it was intentional and it was a 
> problem for the profile modes that uses it.
Patch looks great to me. Thanks. Careful, another two or three of these 
and you risk being appointed profile-mode maintainer ;)

While we are at it, the _M_profile_destruct seem very large to be inline...
> Regarding usage of cached hash code I realized that none of the 
> Standard methods of the unordered containers allowed to benefit from 
> it. There is no gate between iterator and local_iterator. Has a 
> size_type bucket(const_iterator) signature been discussed ?
Not to my best knowledge, I would recommend raising the issue on the 
isocpp forums or the library evolution reflector. By the way, are you 
already subscribed to the reflectors? In case, just send an email to 
Andrew Koenig http://www.open-std.org/jtc1/sc22/wg21/docs/contacts

Thanks,
Paolo.

Patch

Index: include/Makefile.am
===================================================================
--- include/Makefile.am	(revision 198608)
+++ include/Makefile.am	(working copy)
@@ -788,6 +788,7 @@ 
 profile_headers = \
 	${profile_srcdir}/array \
 	${profile_srcdir}/base.h \
+	${profile_srcdir}/unordered_base.h \
 	${profile_srcdir}/unordered_map \
 	${profile_srcdir}/unordered_set \
 	${profile_srcdir}/vector \
Index: include/profile/impl/profiler.h
===================================================================
--- include/profile/impl/profiler.h	(revision 198608)
+++ include/profile/impl/profiler.h	(working copy)
@@ -188,7 +188,7 @@ 
   _GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_invalid())
 #define __profcxx_is_on() \
   _GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_on())
-#define __profcxx__is_off() \
+#define __profcxx_is_off() \
   _GLIBCXX_PROFILE_REENTRANCE_GUARD(__gnu_profile::__is_off())
 #else
 #define __profcxx_report()
@@ -237,6 +237,8 @@ 
 
 // Turn on/off instrumentation for INEFFICIENT_HASH.
 #if defined(_GLIBCXX_PROFILE_INEFFICIENT_HASH)
+#define __profcxx_inefficient_hash_is_on() \
+  __gnu_profile::__is_on()
 #define __profcxx_hashtable_construct2(__x...) \
   _GLIBCXX_PROFILE_REENTRANCE_GUARD( \
       __gnu_profile::__trace_hash_func_construct(__x))
@@ -244,8 +246,9 @@ 
   _GLIBCXX_PROFILE_REENTRANCE_GUARD( \
       __gnu_profile::__trace_hash_func_destruct(__x))
 #else
-#define __profcxx_hashtable_destruct2(__x...) 
-#define __profcxx_hashtable_construct2(__x...)  
+#define __profcxx_inefficient_hash_is_on() false
+#define __profcxx_hashtable_destruct2(__x...)
+#define __profcxx_hashtable_construct2(__x...)
 #endif
 
 // Turn on/off instrumentation for VECTOR_TO_LIST.
Index: include/profile/unordered_set
===================================================================
--- include/profile/unordered_set	(revision 198608)
+++ include/profile/unordered_set	(working copy)
@@ -34,6 +34,7 @@ 
 # include <unordered_set>
 
 #include <profile/base.h>
+#include <profile/unordered_base.h>
 
 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
@@ -44,14 +45,22 @@ 
 {
   /** @brief Unordered_set wrapper with performance instrumentation.  */
   template<typename _Key, 
-	   typename _Hash  = std::hash<_Key>,
+	   typename _Hash = std::hash<_Key>,
 	   typename _Pred = std::equal_to<_Key>,
 	   typename _Alloc =  std::allocator<_Key> >
     class unordered_set
-    : public _GLIBCXX_STD_BASE
+    : public _GLIBCXX_STD_BASE,
+      public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
+				true>
     {
       typedef _GLIBCXX_STD_BASE _Base;
 
+      _Base&
+      _M_base() noexcept       { return *this; }
+
+      const _Base&
+      _M_base() const noexcept { return *this; }
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -71,11 +80,8 @@ 
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
-      : _Base(__n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	: _Base(__n, __hf, __eql, __a)
+      { }
 
       template<typename _InputIterator>
         unordered_set(_InputIterator __f, _InputIterator __l,
@@ -83,84 +89,64 @@ 
 		      const hasher& __hf = hasher(),
 		      const key_equal& __eql = key_equal(),
 		      const allocator_type& __a = allocator_type())
-      : _Base(__f, __l, __n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	  : _Base(__f, __l, __n, __hf, __eql, __a)
+      { }
 
-      unordered_set(const unordered_set& __x)
-      : _Base(__x) 
-      { 
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+      unordered_set(const unordered_set&) = default;
 
       unordered_set(const _Base& __x)
-      : _Base(__x) 
-      { 
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	: _Base(__x)
+      { }
 
-      unordered_set(unordered_set&& __x)
-      : _Base(std::move(__x)) 
-      { 
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+      unordered_set(unordered_set&&) = default;
 
+      explicit
+      unordered_set(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_set(const unordered_set& __uset,
+		    const allocator_type& __a)
+	: _Base(__uset._M_base(), __a)
+      { }
+
+      unordered_set(unordered_set&& __uset,
+		    const allocator_type& __a)
+	: _Base(std::move(__uset._M_base()), __a)
+      { }
+
       unordered_set(initializer_list<value_type> __l,
 		    size_type __n = 0,
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
-      : _Base(__l, __n, __hf, __eql, __a) { }
+      : _Base(__l, __n, __hf, __eql, __a)
+      { }
 
       unordered_set&
-      operator=(const unordered_set& __x)
-      {
-	*static_cast<_Base*>(this) = __x;
-	return *this;
-      }
+      operator=(const unordered_set&) = default;
 
       unordered_set&
-      operator=(unordered_set&& __x)
-      {
-	// NB: DR 1204.
-	// NB: DR 675.
-	this->clear();
-	this->swap(__x);
-	return *this;
-      }
+      operator=(unordered_set&&) = default;
 
       unordered_set&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
 	return *this;
       }
 
-      ~unordered_set() noexcept
-      {
-        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
-                                     _Base::size());
-        _M_profile_destruct();
-      }
-
       void
       swap(unordered_set& __x)
-      {
-        _Base::swap(__x);
-      }
+      noexcept( noexcept(__x._M_base().swap(__x)) )
+      { _Base::swap(__x); }
 
       void
       clear() noexcept
       {
         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
                                      _Base::size());
-        _M_profile_destruct();
+        this->_M_profile_destruct();
         _Base::clear();
       }
 
@@ -240,15 +226,8 @@ 
 	}
 
       void
-      insert(const value_type* __first, const value_type* __last)
+      rehash(size_type __n)
       {
-        size_type __old_size = _Base::bucket_count(); 
-        _Base::insert(__first, __last);
-        _M_profile_resize(__old_size); 
-      }
-     
-      void rehash(size_type __n)
-      {
         size_type __old_size = _Base::bucket_count();
         _Base::rehash(__n);
         _M_profile_resize(__old_size); 
@@ -262,29 +241,6 @@ 
 	if (__old_size != __new_size)
 	  __profcxx_hashtable_resize(this, __old_size, __new_size);
       }
-
-      void
-      _M_profile_destruct()
-      {
-	size_type __hops = 0, __lc = 0, __chain = 0;
-	iterator __it = this->begin();
-	while (__it != this->end())
-	  {
-	    size_type __bkt = this->bucket(*__it);
-	    auto __lit = this->begin(__bkt);
-	    auto __lend = this->end(__bkt);
-	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
-	      ++__chain;
-	    if (__chain)
-	      {
-		++__chain;
-		__lc = __lc > __chain ? __lc : __chain;
-		__hops += __chain * (__chain - 1) / 2;
-		__chain = 0;
-	      }
-	  }
-        __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
-      }
   };
 
   template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
@@ -312,14 +268,23 @@ 
 
   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
   template<typename _Value,
-       typename _Hash  = std::hash<_Value>,
-       typename _Pred = std::equal_to<_Value>,
-       typename _Alloc =  std::allocator<_Value> >
+	   typename _Hash = std::hash<_Value>,
+	   typename _Pred = std::equal_to<_Value>,
+	   typename _Alloc =  std::allocator<_Value> >
     class unordered_multiset
-    : public _GLIBCXX_STD_BASE
+    : public _GLIBCXX_STD_BASE,
+      public _Unordered_profile<unordered_multiset<_Value,
+						   _Hash, _Pred, _Alloc>,
+				false>
     {
       typedef _GLIBCXX_STD_BASE _Base;
 
+      _Base&
+      _M_base() noexcept       { return *this; }
+
+      const _Base&
+      _M_base() const noexcept { return *this; }
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -339,10 +304,8 @@ 
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())
-      : _Base(__n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	: _Base(__n, __hf, __eql, __a)
+      { }
 
       template<typename _InputIterator>
         unordered_multiset(_InputIterator __f, _InputIterator __l,
@@ -350,80 +313,64 @@ 
 			   const hasher& __hf = hasher(),
 			   const key_equal& __eql = key_equal(),
 			   const allocator_type& __a = allocator_type())
-      : _Base(__f, __l, __n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	  : _Base(__f, __l, __n, __hf, __eql, __a)
+      { }
 
-      unordered_multiset(const unordered_multiset& __x)
-      : _Base(__x)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+      unordered_multiset(const unordered_multiset&) = default;
 
       unordered_multiset(const _Base& __x)
-      : _Base(__x)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	: _Base(__x)
+      { }
 
-      unordered_multiset(unordered_multiset&& __x)
-      : _Base(std::move(__x))
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+      unordered_multiset(unordered_multiset&&) = default;
 
+      explicit
+      unordered_multiset(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_multiset(const unordered_multiset& __umset,
+			 const allocator_type& __a)
+	: _Base(__umset._M_base(), __a)
+      { }
+
+      unordered_multiset(unordered_multiset&& __umset,
+			 const allocator_type& __a)
+	: _Base(std::move(__umset._M_base()), __a)
+      { }
+
       unordered_multiset(initializer_list<value_type> __l,
 			 size_type __n = 0,
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())
-      : _Base(__l, __n, __hf, __eql, __a) { }
+	: _Base(__l, __n, __hf, __eql, __a)
+      { }
 
       unordered_multiset&
-      operator=(const unordered_multiset& __x)
-      {
-	*static_cast<_Base*>(this) = __x;
-	return *this;
-      }
+      operator=(const unordered_multiset&) = default;
 
       unordered_multiset&
-      operator=(unordered_multiset&& __x)
-      {
-	// NB: DR 1204.
-	// NB: DR 675.
-	this->clear();
-	this->swap(__x);
-	return *this;
-      }
+      operator=(unordered_multiset&&) = default;
 
       unordered_multiset&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
 	return *this;
       }
 
-      ~unordered_multiset() noexcept
-      {
-        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
-                                     _Base::size());
-        _M_profile_destruct();
-      }
-
       void
       swap(unordered_multiset& __x)
-      {
-        _Base::swap(__x);
-      }
+      noexcept( noexcept(__x._M_base().swap(__x)) )
+      { _Base::swap(__x); }
 
       void
       clear() noexcept
       {
         __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
                                      _Base::size());
-        _M_profile_destruct();
+        this->_M_profile_destruct();
         _Base::clear();
       }
 
@@ -502,15 +449,8 @@ 
 	}
 
       void
-      insert(const value_type* __first, const value_type* __last)
+      rehash(size_type __n)
       {
-        size_type __old_size = _Base::bucket_count(); 
-        _Base::insert(__first, __last);
-        _M_profile_resize(__old_size); 
-      }
-     
-      void rehash(size_type __n)
-      {
         size_type __old_size = _Base::bucket_count();
         _Base::rehash(__n);
         _M_profile_resize(__old_size); 
@@ -524,29 +464,6 @@ 
         if (__old_size != __new_size)
           __profcxx_hashtable_resize(this, __old_size, __new_size);
       }
-
-      void
-      _M_profile_destruct()
-      {
-	size_type __hops = 0, __lc = 0, __chain = 0;
-	iterator __it = this->begin();
-	while (__it != this->end())
-	  {
-	    size_type __bkt = this->bucket(*__it);
-	    auto __lit = this->begin(__bkt);
-	    auto __lend = this->end(__bkt);
-	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
-	      ++__chain;
-	    if (__chain)
-	      {
-		++__chain;
-		__lc = __lc > __chain ? __lc : __chain;
-		__hops += __chain * (__chain - 1) / 2;
-		__chain = 0;
-	      }
-	  }
-        __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
-      }
    };
 
   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
Index: include/profile/unordered_base.h
===================================================================
--- include/profile/unordered_base.h	(revision 0)
+++ include/profile/unordered_base.h	(revision 0)
@@ -0,0 +1,252 @@ 
+// Profiling unordered containers implementation details -*- C++ -*-
+
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+/** @file profile/unordered_base.h
+ *  This file is a GNU profile extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_PROFILE_UNORDERED
+#define _GLIBCXX_PROFILE_UNORDERED 1
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace __profile
+{
+  template<typename _UnorderedCont,
+	   typename _Value, bool _Cache_hash_code>
+    struct _Bucket_index_helper;
+
+  template<typename _UnorderedCont, typename _Value>
+    struct _Bucket_index_helper<_UnorderedCont, _Value, true>
+    {
+      static std::size_t
+      bucket(const _UnorderedCont& __uc,
+	     const __detail::_Hash_node<_Value, true>* __node)
+      { return __node->_M_hash_code % __uc.bucket_count(); }
+    };
+
+  template<typename _UnorderedCont, typename _Value>
+    struct _Bucket_index_helper<_UnorderedCont, _Value, false>
+    {
+      static std::size_t
+      bucket(const _UnorderedCont& __uc,
+	     const __detail::_Hash_node<_Value, false>* __node)
+      { return __uc.bucket(__node->_M_v()); }
+    };
+
+  template<typename _UnorderedCont, typename _Key, typename _Mapped>
+    struct _Bucket_index_helper<_UnorderedCont,
+				std::pair<const _Key, _Mapped>, false>
+    {
+      typedef std::pair<const _Key, _Mapped> _Value;
+
+      static std::size_t
+      bucket(const _UnorderedCont& __uc,
+	     const __detail::_Hash_node<_Value, false>* __node)
+      { return __uc.bucket(__node->_M_v().first); }
+    };
+
+  template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
+    std::size_t
+    __get_bucket_index(const _UnorderedCont& __uc,
+		       const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
+    {
+      using __bucket_index_helper
+	= _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
+      return __bucket_index_helper::bucket(__uc, __node);
+    }
+
+  template<typename _UnorderedCont,
+	   typename _Value, bool _Cache_hash_code>
+    struct _Equal_helper;
+
+  template<typename _UnorderedCont, typename _Value>
+    struct _Equal_helper<_UnorderedCont, _Value, true>
+    {
+      static std::size_t
+      are_equal(const _UnorderedCont& __uc,
+		const __detail::_Hash_node<_Value, true>* __lhs,
+		const __detail::_Hash_node<_Value, true>* __rhs)
+      {
+	return __lhs->_M_hash_code == __rhs->_M_hash_code
+	  && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
+      }
+    };
+
+  template<typename _UnorderedCont,
+	   typename _Value>
+    struct _Equal_helper<_UnorderedCont, _Value, false>
+    {
+      static std::size_t
+      are_equal(const _UnorderedCont& __uc,
+		const __detail::_Hash_node<_Value, false>* __lhs,
+		const __detail::_Hash_node<_Value, false>* __rhs)
+      { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
+    };
+
+  template<typename _UnorderedCont,
+	   typename _Key, typename _Mapped>
+    struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
+    {
+      typedef std::pair<const _Key, _Mapped> _Value;
+
+      static std::size_t
+      are_equal(const _UnorderedCont& __uc,
+		const __detail::_Hash_node<_Value, true>* __lhs,
+		const __detail::_Hash_node<_Value, true>* __rhs)
+      {
+	return __lhs->_M_hash_code == __rhs->_M_hash_code
+	  && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
+      }
+    };
+
+  template<typename _UnorderedCont,
+	   typename _Key, typename _Mapped>
+    struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
+    {
+      typedef std::pair<const _Key, _Mapped> _Value;
+
+      static std::size_t
+      are_equal(const _UnorderedCont& __uc,
+		const __detail::_Hash_node<_Value, false>* __lhs,
+		const __detail::_Hash_node<_Value, false>* __rhs)
+      { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
+    };
+
+  template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
+    bool
+    __are_equal(const _UnorderedCont& __uc,
+		const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
+		const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
+  {
+    using __equal_helper
+      = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
+    return __equal_helper::are_equal(__uc, __lhs, __rhs);
+  }
+
+  template<typename _UnorderedCont, bool _Unique_keys>
+    class _Unordered_profile
+    {
+      _UnorderedCont&
+      _M_conjure()
+      { return *(static_cast<_UnorderedCont*>(this)); }
+
+      using __unique_keys = std::integral_constant<bool, _Unique_keys>;
+
+    protected:
+      _Unordered_profile()
+      {
+	auto& __uc = _M_conjure();
+        __profcxx_hashtable_construct(&__uc, __uc.bucket_count());
+	__profcxx_hashtable_construct2(&__uc);
+      }
+      _Unordered_profile(const _Unordered_profile&)
+	: _Unordered_profile() { }
+      _Unordered_profile(_Unordered_profile&&)
+	: _Unordered_profile() { }
+
+      ~_Unordered_profile() noexcept
+      {
+	auto& __uc = _M_conjure();
+        __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size());
+        _M_profile_destruct();
+      }
+
+      _Unordered_profile&
+      operator=(const _Unordered_profile&) = default;
+
+      _Unordered_profile&
+      operator=(_Unordered_profile&&) = default;
+
+      void
+      _M_profile_destruct()
+      {
+	if (!__profcxx_inefficient_hash_is_on())
+	  return;
+
+	_M_profile_destruct(__unique_keys());
+      }
+
+    private:
+      void
+      _M_profile_destruct(std::true_type)
+      {
+	auto& __uc = _M_conjure();
+	std::size_t __hops = 0, __lc = 0, __chain = 0;
+	auto __it = __uc.begin();
+	while (__it != __uc.end())
+	  {
+	    auto __bkt = __get_bucket_index(__uc, __it._M_cur);
+	    auto __lit = __uc.begin(__bkt);
+	    auto __lend = __uc.end(__bkt);
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
+	      ++__chain;
+	    if (__chain)
+	      {
+		++__chain;
+		__lc = __lc > __chain ? __lc : __chain;
+		__hops += __chain * (__chain - 1) / 2;
+		__chain = 0;
+	      }
+	  }
+	__profcxx_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops);
+      }
+
+      void
+      _M_profile_destruct(std::false_type)
+      {
+	auto& __uc = _M_conjure();
+	std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;;
+	auto __it = __uc.begin();
+	while (__it != __uc.end())
+	  {
+	    auto __bkt = __get_bucket_index(__uc, __it._M_cur);
+	    auto __lit = __uc.begin(__bkt);
+	    auto __lend = __uc.end(__bkt);
+	    auto __pit = __it;
+	    ++__unique_size;
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
+	      {
+		if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
+		  {
+		    ++__chain;
+		    ++__unique_size;
+		    __pit = __it;
+		  }
+	      }
+	    if (__chain)
+	      {
+		++__chain;
+		__lc = __lc > __chain ? __lc : __chain;
+		__hops += __chain * (__chain - 1) / 2;
+		__chain = 0;
+	      }
+	  }
+	__profcxx_hashtable_destruct2(&__uc, __lc, __unique_size, __hops);
+      }
+    };
+
+} // namespace __profile
+} // namespace std
+
+#endif

Property changes on: include/profile/unordered_base.h
___________________________________________________________________
Added: svn:eol-style
   + native

Index: include/profile/unordered_map
===================================================================
--- include/profile/unordered_map	(revision 198608)
+++ include/profile/unordered_map	(working copy)
@@ -34,6 +34,7 @@ 
 # include <unordered_map>
 
 #include <profile/base.h>
+#include <profile/unordered_base.h>
 
 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
@@ -48,10 +49,18 @@ 
 	   typename _Pred = std::equal_to<_Key>,
 	   typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
     class unordered_map
-    : public _GLIBCXX_STD_BASE
+    : public _GLIBCXX_STD_BASE,
+      public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
+				true>
     {
       typedef typename _GLIBCXX_STD_BASE _Base;
 
+      _Base&
+      _M_base() noexcept       { return *this; }
+
+      const _Base&
+      _M_base() const noexcept { return *this; }
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -72,11 +81,8 @@ 
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
-      : _Base(__n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	: _Base(__n, __hf, __eql, __a)
+      { }
 
       template<typename _InputIterator>
         unordered_map(_InputIterator __f, _InputIterator __l,
@@ -84,85 +90,60 @@ 
 		      const hasher& __hf = hasher(),
 		      const key_equal& __eql = key_equal(),
 		      const allocator_type& __a = allocator_type())
-      : _Base(__f, __l, __n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	  : _Base(__f, __l, __n, __hf, __eql, __a)
+        { }
 
-      unordered_map(const unordered_map& __x)
-      : _Base(__x) 
-      { 
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+      unordered_map(const unordered_map&) = default;
 
       unordered_map(const _Base& __x)
-      : _Base(__x) 
-      { 
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+	: _Base(__x)
+      { }
 
-      unordered_map(unordered_map&& __x)
-      : _Base(std::move(__x)) 
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-        __profcxx_hashtable_construct2(this);
-      }
+      unordered_map(unordered_map&&) = default;
 
+      explicit
+      unordered_map(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_map(const unordered_map& __umap,
+		    const allocator_type& __a)
+	: _Base(__umap, __a)
+      { }
+
+      unordered_map(unordered_map&& __umap,
+		    const allocator_type& __a)
+	: _Base(std::move(__umap._M_base()), __a)
+      { }
+
       unordered_map(initializer_list<value_type> __l,
 		    size_type __n = 0,
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
-      : _Base(__l, __n, __hf, __eql, __a) { }
+	: _Base(__l, __n, __hf, __eql, __a)
+      { }
 
       unordered_map&
-      operator=(const unordered_map& __x)
-      {
-	*static_cast<_Base*>(this) = __x;
-	return *this;
-      }
+      operator=(const unordered_map&) = default;
 
       unordered_map&
-      operator=(unordered_map&& __x)
-      {
-	// NB: DR 1204.
-	// NB: DR 675.
-	this->clear();
-	this->swap(__x);
-	return *this;
-      }
+      operator=(unordered_map&&) = default;
 
       unordered_map&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
 	return *this;
       }
 
-      ~unordered_map() noexcept
-      {
-        __profcxx_hashtable_destruct(this, _Base::bucket_count(),
-				     _Base::size());
-        _M_profile_destruct();
-      }
-
-      _Base&
-      _M_base() noexcept       { return *this; }
-
-      const _Base&
-      _M_base() const noexcept { return *this; }
-
       void
       clear() noexcept
       {
         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 				     _Base::size());
-        _M_profile_destruct();
-        _Base::clear();
+        this->_M_profile_destruct();
+	_Base::clear();
       }
 
       template<typename... _Args>
@@ -247,14 +228,6 @@ 
 	  _M_profile_resize(__old_size); 
 	}
 
-      void
-      insert(const value_type* __first, const value_type* __last)
-      {
-        size_type __old_size = _Base::bucket_count(); 
-        _Base::insert(__first, __last);
-        _M_profile_resize(__old_size); 
-      }
-
       // operator[]
       mapped_type&
       operator[](const _Key& __k)
@@ -276,7 +249,8 @@ 
 
       void
       swap(unordered_map& __x)
-      { _Base::swap(__x); }
+      noexcept( noexcept(__x._M_base().swap(__x)) )
+      { _Base::swap(__x._M_base()); }
 
       void rehash(size_type __n)
       {
@@ -293,29 +267,6 @@ 
 	if (__old_size != __new_size)
 	  __profcxx_hashtable_resize(this, __old_size, __new_size);
       }
-
-      void
-      _M_profile_destruct()
-      {
-	size_type __hops = 0, __lc = 0, __chain = 0;
-	iterator __it = this->begin();
-	while (__it != this->end())
-	  {
-	    size_type __bkt = this->bucket(__it->first);
-	    auto __lit = this->begin(__bkt);
-	    auto __lend = this->end(__bkt);
-	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
-	      ++__chain;
-	    if (__chain)
-	      {
-		++__chain;
-		__lc = __lc > __chain ? __lc : __chain;
-		__hops += __chain * (__chain - 1) / 2;
-		__chain = 0;
-	      }
-	  }
-	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
-      }
   };
 
   template<typename _Key, typename _Tp, typename _Hash,
@@ -350,10 +301,19 @@ 
 	   typename _Pred = std::equal_to<_Key>,
 	   typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
     class unordered_multimap
-    : public _GLIBCXX_STD_BASE
+    : public _GLIBCXX_STD_BASE,
+      public _Unordered_profile<unordered_multimap<_Key, _Tp,
+						   _Hash, _Pred, _Alloc>,
+				false>
     {      
       typedef typename _GLIBCXX_STD_BASE _Base;
 
+      _Base&
+      _M_base() noexcept       { return *this; }
+
+      const _Base&
+      _M_base() const noexcept { return *this; }
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -373,85 +333,69 @@ 
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())
-      : _Base(__n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	: _Base(__n, __hf, __eql, __a)
+      { }
+
       template<typename _InputIterator>
         unordered_multimap(_InputIterator __f, _InputIterator __l,
 			   size_type __n = 0,
 			   const hasher& __hf = hasher(),
 			   const key_equal& __eql = key_equal(),
 			   const allocator_type& __a = allocator_type())
-      : _Base(__f, __l, __n, __hf, __eql, __a)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	  : _Base(__f, __l, __n, __hf, __eql, __a)
+      { }
 
-      unordered_multimap(const unordered_multimap& __x)
-      : _Base(__x)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+      unordered_multimap(const unordered_multimap&) = default;
 
       unordered_multimap(const _Base& __x)
-      : _Base(__x)
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+	: _Base(__x)
+      { }
 
-      unordered_multimap(unordered_multimap&& __x)
-      : _Base(std::move(__x))
-      {
-        __profcxx_hashtable_construct(this, _Base::bucket_count());
-      }
+      unordered_multimap(unordered_multimap&&) = default;
 
+      explicit
+      unordered_multimap(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_multimap(const unordered_multimap& __ummap,
+			 const allocator_type& __a)
+	: _Base(__ummap._M_base(), __a)
+      { }
+
+      unordered_multimap(unordered_multimap&& __ummap,
+			 const allocator_type& __a)
+	: _Base(std::move(__ummap._M_base()), __a)
+      { }
+
       unordered_multimap(initializer_list<value_type> __l,
 			 size_type __n = 0,
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())
-      : _Base(__l, __n, __hf, __eql, __a) { }
+      : _Base(__l, __n, __hf, __eql, __a)
+      { }
 
       unordered_multimap&
-      operator=(const unordered_multimap& __x)
-      {
-	*static_cast<_Base*>(this) = __x;
-	return *this;
-      }
+      operator=(const unordered_multimap&) = default;
 
       unordered_multimap&
-      operator=(unordered_multimap&& __x)
-      {
-	// NB: DR 1204.
-	// NB: DR 675.
-	this->clear();
-	this->swap(__x);
-	return *this;
-      }
+      operator=(unordered_multimap&&) = default;
 
       unordered_multimap&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
 	return *this;
       }
 
-      ~unordered_multimap() noexcept
-      {
-        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
-				     _Base::size());
-        _M_profile_destruct();
-      }
-
       void
       clear() noexcept
       {
-        __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
+	__profcxx_hashtable_destruct(this, _Base::bucket_count(), 
 				     _Base::size());
-        _M_profile_destruct();
-        _Base::clear();
+	this->_M_profile_destruct();
+	_Base::clear();
       }
 
       template<typename... _Args>
@@ -536,18 +480,12 @@ 
 	}
 
       void
-      insert(const value_type* __first, const value_type* __last)
-      {
-        size_type __old_size = _Base::bucket_count(); 
-        _Base::insert(__first, __last);
-        _M_profile_resize(__old_size); 
-      }
-
-      void
       swap(unordered_multimap& __x)
-      { _Base::swap(__x); }
+      noexcept( noexcept(__x._M_base().swap(__x)) )
+      { _Base::swap(__x._M_base()); }
 
-      void rehash(size_type __n)
+      void
+      rehash(size_type __n)
       {
         size_type __old_size = _Base::bucket_count();
         _Base::rehash(__n);
@@ -562,29 +500,6 @@ 
         if (__old_size != __new_size)
           __profcxx_hashtable_resize(this, __old_size, __new_size);
       }
-
-      void
-      _M_profile_destruct()
-      {
-	size_type __hops = 0, __lc = 0, __chain = 0;
-	iterator __it = this->begin();
-	while (__it != this->end())
-	  {
-	    size_type __bkt = this->bucket(__it->first);
-	    auto __lit = this->begin(__bkt);
-	    auto __lend = this->end(__bkt);
-	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
-	      ++__chain;
-	    if (__chain)
-	      {
-		++__chain;
-		__lc = __lc > __chain ? __lc : __chain;
-		__hops += __chain * (__chain - 1) / 2;
-		__chain = 0;
-	      }
-	  }
-	__profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
-      }
   };
 
   template<typename _Key, typename _Tp, typename _Hash,
Index: testsuite/23_containers/unordered_multiset/55043.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/55043.cc	(revision 198608)
+++ testsuite/23_containers/unordered_multiset/55043.cc	(working copy)
@@ -30,7 +30,7 @@ 
 };
 
 struct equal {
-  bool operator()(const MoveOnly&, const MoveOnly) const { return true; }
+  bool operator()(const MoveOnly&, const MoveOnly&) const { return true; }
 };
 struct hash {
   std::size_t operator()(const MoveOnly&) const { return 0; }