From fde79b40c21dc397a2524c728f4102260eceafed Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Thu, 17 Mar 2016 20:45:20 +0000 Subject: [PATCH] unord: Extract key to avoid preemptive mallocs in insert/emplace unordered_set::emplace and unordered_map::emplace construct a node, then try to insert it. If insertion fails, the node gets deleted. To avoid this unnecessary malloc traffic, check to see if the argument to emplace has the appropriate key_type. If so, we can use that key directly and delay the malloc until we're sure we're inserting something new. Test updates by Eric Fiselier, who rewrote the old allocation tests to include the new cases. There are two orthogonal future directions: 1. Apply the same optimization to set and map. 2. Extend the optimization to when the argument is not key_type, but can be converted to it without side effects. Ideally, we could do this whenever key_type is trivially destructible and the argument is trivially convertible to key_type, but in practise the relevant type traits "blow up sometimes". At least, we should catch a few simple cases (such as when both are primitive types). llvm-svn: 263746 --- libcxx/include/__hash_table | 58 ++++++++++- .../unord/unord.set/insert_dup_alloc.pass.cpp | 48 ---------- ...rt_and_emplace_allocator_requirements.pass.cpp} | 106 +++++++++++++++++++++ ...rt_and_emplace_allocator_requirements.pass.cpp} | 78 +++++++++++++++ 4 files changed, 240 insertions(+), 50 deletions(-) delete mode 100644 libcxx/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp rename libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/{insert_allocator_requirements.pass.cpp => insert_and_emplace_allocator_requirements.pass.cpp} (58%) rename libcxx/test/std/containers/unord/unord.set/{insert_allocator_requirements.pass.cpp => insert_and_emplace_allocator_requirements.pass.cpp} (66%) diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index e8cebe0..16a0f5e 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -100,6 +100,23 @@ __next_hash_pow2(size_t __n) return size_t(1) << (std::numeric_limits::digits - __clz(__n-1)); } +#ifndef _LIBCPP_CXX03_LANG +struct __extract_key_fail_tag {}; +struct __extract_key_self_tag {}; +struct __extract_key_first_tag {}; + +template ::type> +struct __can_extract_key + : conditional::value, __extract_key_self_tag, + __extract_key_fail_tag>::type {}; + +template +struct __can_extract_key<_Pair, _Key, pair<_First, _Second>> + : conditional::type, _Key>::value, + __extract_key_first_tag, __extract_key_fail_tag>::type {}; +#endif + template class __hash_table; template class _LIBCPP_TYPE_VIS_ONLY __hash_iterator; @@ -903,6 +920,7 @@ public: typedef typename _NodeTypes::__node_value_type __node_value_type; typedef typename _NodeTypes::__container_value_type __container_value_type; + typedef typename _NodeTypes::key_type key_type; typedef value_type& reference; typedef const value_type& const_reference; typedef typename __alloc_traits::pointer pointer; @@ -1041,13 +1059,49 @@ public: #ifndef _LIBCPP_CXX03_LANG template + _LIBCPP_INLINE_VISIBILITY pair __emplace_unique_key_args(_Key const& __k, _Args&&... __args); template - pair __emplace_unique(_Args&&... __args); + _LIBCPP_INLINE_VISIBILITY + pair __emplace_unique_impl(_Args&&... __args); + + template + _LIBCPP_INLINE_VISIBILITY + pair __emplace_unique(_Pp&& __x) { + return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), + __can_extract_key<_Pp, key_type>()); + } + template + _LIBCPP_INLINE_VISIBILITY + pair __emplace_unique(_Args&&... __args) { + return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); + } + + template + _LIBCPP_INLINE_VISIBILITY + pair + __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { + return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); + } + template + _LIBCPP_INLINE_VISIBILITY + pair + __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { + return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); + } + template + _LIBCPP_INLINE_VISIBILITY + pair + __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { + return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); + } + template + _LIBCPP_INLINE_VISIBILITY iterator __emplace_multi(_Args&&... __args); template + _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); @@ -1989,7 +2043,7 @@ __done: template template pair::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) { __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); pair __r = __node_insert_unique(__h.get()); diff --git a/libcxx/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp b/libcxx/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp deleted file mode 100644 index 76ceafed..0000000 --- a/libcxx/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp +++ /dev/null @@ -1,48 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is dual licensed under the MIT and the University of Illinois Open -// Source Licenses. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -// Check that we don't allocate when trying to insert a duplicate value into a -// unordered_set. See PR12999 http://llvm.org/bugs/show_bug.cgi?id=12999 - -#include -#include -#include "count_new.hpp" -#include "MoveOnly.h" - -int main() -{ - { - std::unordered_set s; - assert(globalMemCounter.checkNewCalledEq(0)); - - for(int i=0; i < 100; ++i) - s.insert(3); - - assert(s.size() == 1); - assert(s.count(3) == 1); - assert(globalMemCounter.checkNewCalledEq(2)); - } - assert(globalMemCounter.checkOutstandingNewEq(0)); - globalMemCounter.reset(); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - { - std::unordered_set s; - assert(globalMemCounter.checkNewCalledEq(0)); - - for(int i=0; i<100; i++) - s.insert(MoveOnly(3)); - - assert(s.size() == 1); - assert(s.count(MoveOnly(3)) == 1); - assert(globalMemCounter.checkNewCalledEq(2)); - } - assert(globalMemCounter.checkOutstandingNewEq(0)); - globalMemCounter.reset(); -#endif -} diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp similarity index 58% rename from libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp rename to libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp index e889ce3..a7df3e7 100644 --- a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp @@ -84,6 +84,19 @@ void testContainerInsert() } } { + PRINT("Testing C::insert(const value_type&&)"); + Container c; + const ValueTp v(42, 1); + cc->expect(); + assert(c.insert(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42, 1); + assert(c.insert(std::move(v2)).second == false); + } + } + { PRINT("Testing C::insert(std::initializer_list)"); Container c; std::initializer_list il = { ValueTp(1, 1), ValueTp(2, 1) }; @@ -137,7 +150,100 @@ void testContainerInsert() } +template +void testContainerEmplace() +{ + typedef typename Container::value_type ValueTp; + typedef typename Container::key_type Key; + typedef typename Container::mapped_type Mapped; + typedef typename std::pair NonConstKeyPair; + typedef Container C; + typedef std::pair R; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::emplace(const value_type&)"); + Container c; + const ValueTp v(42, 1); + cc->expect(); + assert(c.emplace(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42, 1); + assert(c.emplace(v2).second == false); + } + } + { + PRINT("Testing C::emplace(value_type&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + assert(c.emplace(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42, 1); + assert(c.emplace(v2).second == false); + } + } + { + PRINT("Testing C::emplace(value_type&&)"); + Container c; + ValueTp v(42, 1); + cc->expect(); + assert(c.emplace(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42, 1); + assert(c.emplace(std::move(v2)).second == false); + } + } + { + PRINT("Testing C::emplace(const value_type&&)"); + Container c; + const ValueTp v(42, 1); + cc->expect(); + assert(c.emplace(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42, 1); + assert(c.emplace(std::move(v2)).second == false); + } + } + { + PRINT("Testing C::emplace(pair const&)"); + Container c; + const NonConstKeyPair v(42, 1); + cc->expect(); + assert(c.emplace(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const NonConstKeyPair v2(42, 1); + assert(c.emplace(v2).second == false); + } + } + { + PRINT("Testing C::emplace(pair &&)"); + Container c; + NonConstKeyPair v(42, 1); + cc->expect(); + assert(c.emplace(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + NonConstKeyPair v2(42, 1); + assert(c.emplace(std::move(v2)).second == false); + } + } +} + + int main() { testContainerInsert >(); + testContainerEmplace >(); } diff --git a/libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp b/libcxx/test/std/containers/unord/unord.set/insert_and_emplace_allocator_requirements.pass.cpp similarity index 66% rename from libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp rename to libcxx/test/std/containers/unord/unord.set/insert_and_emplace_allocator_requirements.pass.cpp index f5a30c2..14e0892 100644 --- a/libcxx/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.set/insert_and_emplace_allocator_requirements.pass.cpp @@ -12,6 +12,7 @@ // class unordered_set // insert(...) +// emplace(...) // UNSUPPORTED: c++98, c++03 @@ -83,6 +84,19 @@ void testContainerInsert() } } { + PRINT("Testing C::insert(const value_type&&)"); + Container c; + const ValueTp v(42); + cc->expect(); + assert(c.insert(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42); + assert(c.insert(std::move(v2)).second == false); + } + } + { PRINT("Testing C::insert(std::initializer_list)"); Container c; std::initializer_list il = { ValueTp(1), ValueTp(2) }; @@ -136,7 +150,71 @@ void testContainerInsert() } +template +void testContainerEmplace() +{ + typedef typename Container::value_type ValueTp; + typedef Container C; + typedef std::pair R; + ConstructController* cc = getConstructController(); + cc->reset(); + { + PRINT("Testing C::emplace(const value_type&)"); + Container c; + const ValueTp v(42); + cc->expect(); + assert(c.emplace(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42); + assert(c.emplace(v2).second == false); + } + } + { + PRINT("Testing C::emplace(value_type&)"); + Container c; + ValueTp v(42); + cc->expect(); + assert(c.emplace(v).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42); + assert(c.emplace(v2).second == false); + } + } + { + PRINT("Testing C::emplace(value_type&&)"); + Container c; + ValueTp v(42); + cc->expect(); + assert(c.emplace(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + ValueTp v2(42); + assert(c.emplace(std::move(v2)).second == false); + } + } + { + PRINT("Testing C::emplace(const value_type&&)"); + Container c; + const ValueTp v(42); + cc->expect(); + assert(c.emplace(std::move(v)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const ValueTp v2(42); + assert(c.emplace(std::move(v2)).second == false); + } + } +} + + int main() { testContainerInsert >(); + testContainerEmplace >(); } -- 2.7.4