Author: ericwf Date: Fri Apr 15 19:23:12 2016 New Revision: 266498 URL: http://llvm.org/viewvc/llvm-project?rev=266498&view=rev Log: Teach map/unordered_map how to optimize 'emplace(Key, T)'.
In cases where emplace is called with two arguments and the first one matches the key_type we can Key to check for duplicates before allocating. This patch expands on work done by dexonsm...@apple.com. Modified: libcxx/trunk/include/__hash_table libcxx/trunk/include/__tree libcxx/trunk/include/type_traits libcxx/trunk/test/std/containers/map_allocator_requirement_test_templates.h libcxx/trunk/test/std/containers/set_allocator_requirement_test_templates.h libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp libcxx/trunk/test/support/container_test_types.h Modified: libcxx/trunk/include/__hash_table URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/__hash_table?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/include/__hash_table (original) +++ libcxx/trunk/include/__hash_table Fri Apr 15 19:23:12 2016 @@ -1056,6 +1056,17 @@ public: return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); } + + template <class _First, class _Second> + _LIBCPP_INLINE_VISIBILITY + typename enable_if< + __can_extract_map_key<_First, key_type, __container_value_type>::value, + pair<iterator, bool> + >::type __emplace_unique(_First&& __f, _Second&& __s) { + return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), + _VSTD::forward<_Second>(__s)); + } + template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique(_Args&&... __args) { Modified: libcxx/trunk/include/__tree URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/__tree?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/include/__tree (original) +++ libcxx/trunk/include/__tree Fri Apr 15 19:23:12 2016 @@ -1082,6 +1082,16 @@ public: __can_extract_key<_Pp, key_type>()); } + template <class _First, class _Second> + _LIBCPP_INLINE_VISIBILITY + typename enable_if< + __can_extract_map_key<_First, key_type, __container_value_type>::value, + pair<iterator, bool> + >::type __emplace_unique(_First&& __f, _Second&& __s) { + return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), + _VSTD::forward<_Second>(__s)); + } + template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique(_Args&&... __args) { @@ -1116,6 +1126,17 @@ public: __can_extract_key<_Pp, key_type>()); } + template <class _First, class _Second> + _LIBCPP_INLINE_VISIBILITY + typename enable_if< + __can_extract_map_key<_First, key_type, __container_value_type>::value, + iterator + >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { + return __emplace_hint_unique_key_args(__p, __f, + _VSTD::forward<_First>(__f), + _VSTD::forward<_Second>(__s)); + } + template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { Modified: libcxx/trunk/include/type_traits URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/type_traits?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/include/type_traits (original) +++ libcxx/trunk/include/type_traits Fri Apr 15 19:23:12 2016 @@ -4452,6 +4452,21 @@ template <class _Pair, class _Key, class struct __can_extract_key<_Pair, _Key, pair<_First, _Second>> : conditional<is_same<typename remove_const<_First>::type, _Key>::value, __extract_key_first_tag, __extract_key_fail_tag>::type {}; + +// __can_extract_map_key uses true_type/false_type instead of the tags. +// It returns true if _Key != _ContainerValueTy (the container is a map not a set) +// and _ValTy == _Key. +template <class _ValTy, class _Key, class _ContainerValueTy, + class _RawValTy = typename __unconstref<_ValTy>::type> +struct __can_extract_map_key + : integral_constant<bool, is_same<_RawValTy, _Key>::value> {}; + +// This specialization returns __extract_key_fail_tag for non-map containers +// because _Key == _ContainerValueTy +template <class _ValTy, class _Key, class _RawValTy> +struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy> + : false_type {}; + #endif _LIBCPP_END_NAMESPACE_STD Modified: libcxx/trunk/test/std/containers/map_allocator_requirement_test_templates.h URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/map_allocator_requirement_test_templates.h?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/test/std/containers/map_allocator_requirement_test_templates.h (original) +++ libcxx/trunk/test/std/containers/map_allocator_requirement_test_templates.h Fri Apr 15 19:23:12 2016 @@ -231,6 +231,62 @@ void testMapEmplace() assert(c.emplace(std::move(v2)).second == false); } } + { + CHECKPOINT("Testing C::emplace(const Key&, ConvertibleToMapped&&)"); + Container c; + const Key k(42); + cc->expect<Key const&, int&&>(); + assert(c.emplace(k, 1).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const Key k2(42); + assert(c.emplace(k2, 2).second == false); + } + } + { + CHECKPOINT("Testing C::emplace(Key&, Mapped&)"); + Container c; + Key k(42); + Mapped m(1); + cc->expect<Key&, Mapped&>(); + assert(c.emplace(k, m).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + Key k2(42); + assert(c.emplace(k2, m).second == false); + } + } + { + CHECKPOINT("Testing C::emplace(Key&&, Mapped&&)"); + Container c; + Key k(42); + Mapped m(1); + cc->expect<Key&&, Mapped&&>(); + assert(c.emplace(std::move(k), std::move(m)).second); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + Key k2(42); + Mapped m2(2); + assert(c.emplace(std::move(k2), std::move(m2)).second == false); + } + } + { + CHECKPOINT("Testing C::emplace(ConvertibleToKey&&, ConvertibleToMapped&&)"); + Container c; + cc->expect<int&&, int&&>(); + assert(c.emplace(42, 1).second); + assert(!cc->unchecked()); + { + // test that emplacing a duplicate item allocates. We cannot optimize + // this case because int&& does not match the type of key exactly. + cc->expect<int&&, int&&>(); + assert(c.emplace(42, 1).second == false); + assert(!cc->unchecked()); + } + } } @@ -347,6 +403,78 @@ void testMapEmplaceHint() assert(c.size() == 1); } } + { + CHECKPOINT("Testing C::emplace_hint(p, const Key&, ConvertibleToMapped&&)"); + Container c; + const Key k(42); + cc->expect<Key const&, int&&>(); + It ret = c.emplace_hint(c.end(), k, 42); + assert(ret != c.end()); + assert(c.size() == 1); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + const Key k2(42); + It ret2 = c.emplace_hint(c.begin(), k2, 1); + assert(&(*ret2) == &(*ret)); + assert(c.size() == 1); + } + } + { + CHECKPOINT("Testing C::emplace_hint(p, Key&, Mapped&)"); + Container c; + Key k(42); + Mapped m(1); + cc->expect<Key&, Mapped&>(); + It ret = c.emplace_hint(c.end(), k, m); + assert(ret != c.end()); + assert(c.size() == 1); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + Key k2(42); + Mapped m2(2); + It ret2 = c.emplace_hint(c.begin(), k2, m2); + assert(&(*ret2) == &(*ret)); + assert(c.size() == 1); + } + } + { + CHECKPOINT("Testing C::emplace_hint(p, Key&&, Mapped&&)"); + Container c; + Key k(42); + Mapped m(1); + cc->expect<Key&&, Mapped&&>(); + It ret = c.emplace_hint(c.end(), std::move(k), std::move(m)); + assert(ret != c.end()); + assert(c.size() == 1); + assert(!cc->unchecked()); + { + DisableAllocationGuard g; + Key k2(42); + Mapped m2(2); + It ret2 = c.emplace_hint(c.begin(), std::move(k2), std::move(m2)); + assert(&(*ret2) == &(*ret)); + assert(c.size() == 1); + } + } + { + CHECKPOINT("Testing C::emplace_hint(p, ConvertibleToKey&&, ConvertibleToMapped&&)"); + Container c; + cc->expect<int&&, int&&>(); + It ret = c.emplace_hint(c.end(), 42, 1); + assert(ret != c.end()); + assert(c.size() == 1); + assert(!cc->unchecked()); + { + cc->expect<int&&, int&&>(); + It ret2 = c.emplace_hint(c.begin(), 42, 2); + assert(&(*ret2) == &(*ret)); + assert(c.size() == 1); + assert(!cc->unchecked()); + } + } + } @@ -414,6 +542,7 @@ void testMultimapInsert() c.insert(std::begin(ValueList), std::end(ValueList)); assert(!cc->unchecked()); } + } -#endif \ No newline at end of file +#endif Modified: libcxx/trunk/test/std/containers/set_allocator_requirement_test_templates.h URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/set_allocator_requirement_test_templates.h?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/test/std/containers/set_allocator_requirement_test_templates.h (original) +++ libcxx/trunk/test/std/containers/set_allocator_requirement_test_templates.h Fri Apr 15 19:23:12 2016 @@ -351,6 +351,4 @@ void testMultisetInsert() } } - - -#endif \ No newline at end of file +#endif Modified: libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp (original) +++ libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/insert_and_emplace_allocator_requirements.pass.cpp Fri Apr 15 19:23:12 2016 @@ -26,4 +26,5 @@ int main() { testMapInsert<TCT::unordered_map<> >(); testMapEmplace<TCT::unordered_map<> >(); + testMapEmplaceHint<TCT::unordered_map<> >(); } Modified: libcxx/trunk/test/support/container_test_types.h URL: http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/support/container_test_types.h?rev=266498&r1=266497&r2=266498&view=diff ============================================================================== --- libcxx/trunk/test/support/container_test_types.h (original) +++ libcxx/trunk/test/support/container_test_types.h Fri Apr 15 19:23:12 2016 @@ -158,6 +158,11 @@ struct AllocatorConstructController { bool m_allow_unchecked; int m_expected_count; + void clear() { + m_expected_args = nullptr; + m_expected_count = -1; + } + // Check for and consume an expected construction added by 'expect'. // Return true if the construction was expected and false otherwise. // This should only be called by 'Allocator.construct'. _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits