From 3eb5aec61f684e59439c30849f73dae8298f5056 Mon Sep 17 00:00:00 2001 From: Eric Fiselier Date: Thu, 1 Aug 2019 19:48:29 +0000 Subject: [PATCH] Change default bucket count in hash_set/hash_map. Previously these types rehashed to a table of 193 elements upon construction. But this is non-ideal, first because default constructors should not allocate unless necessary, and second because 193 is big and can waste a bunch of memory. This number had previously been chosen to match GCC's implementation. llvm-svn: 367605 --- libcxx/include/ext/hash_map | 19 ++++++------ libcxx/include/ext/hash_set | 6 ++-- .../libcxx/containers/gnu_cxx/hash_map.pass.cpp | 30 +++++++++--------- .../gnu_cxx/hash_map_name_lookup.pass.cpp | 36 ++++++++++++++++++++++ .../libcxx/containers/gnu_cxx/hash_set.pass.cpp | 30 +++++++++--------- .../gnu_cxx/hash_set_name_lookup.pass.cpp | 34 ++++++++++++++++++++ 6 files changed, 113 insertions(+), 42 deletions(-) create mode 100644 libcxx/test/libcxx/containers/gnu_cxx/hash_map_name_lookup.pass.cpp create mode 100644 libcxx/test/libcxx/containers/gnu_cxx/hash_set_name_lookup.pass.cpp diff --git a/libcxx/include/ext/hash_map b/libcxx/include/ext/hash_map index 24823c6..20f778b 100644 --- a/libcxx/include/ext/hash_map +++ b/libcxx/include/ext/hash_map @@ -39,14 +39,17 @@ public: typedef /unspecified/ iterator; typedef /unspecified/ const_iterator; - explicit hash_map(size_type n = 193, const hasher& hf = hasher(), + hash_map(); + explicit hash_map(size_type n, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); template - hash_map(InputIterator f, InputIterator l, - size_type n = 193, const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()); + hash_map(InputIterator f, InputIterator l); + template + hash_map(InputIterator f, InputIterator l, + size_type n, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); hash_map(const hash_map&); ~hash_map(); hash_map& operator=(const hash_map&); @@ -502,7 +505,7 @@ public: typedef __hash_map_iterator iterator; typedef __hash_map_const_iterator const_iterator; - _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);} + _LIBCPP_INLINE_VISIBILITY hash_map() { } explicit hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); hash_map(size_type __n, const hasher& __hf, @@ -623,7 +626,6 @@ template hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( _InputIterator __first, _InputIterator __last) { - __table_.rehash(193); insert(__first, __last); } @@ -775,7 +777,7 @@ public: typedef __hash_map_const_iterator const_iterator; _LIBCPP_INLINE_VISIBILITY - hash_multimap() {__table_.rehash(193);} + hash_multimap() { } explicit hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); hash_multimap(size_type __n, const hasher& __hf, @@ -890,7 +892,6 @@ template hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( _InputIterator __first, _InputIterator __last) { - __table_.rehash(193); insert(__first, __last); } diff --git a/libcxx/include/ext/hash_set b/libcxx/include/ext/hash_set index e514182..f0ba8d8 100644 --- a/libcxx/include/ext/hash_set +++ b/libcxx/include/ext/hash_set @@ -237,7 +237,7 @@ public: typedef typename __table::const_iterator const_iterator; _LIBCPP_INLINE_VISIBILITY - hash_set() {__table_.rehash(193);} + hash_set() { } explicit hash_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, @@ -347,7 +347,6 @@ template hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( _InputIterator __first, _InputIterator __last) { - __table_.rehash(193); insert(__first, __last); } @@ -459,7 +458,7 @@ public: typedef typename __table::const_iterator const_iterator; _LIBCPP_INLINE_VISIBILITY - hash_multiset() {__table_.rehash(193);} + hash_multiset() { } explicit hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); hash_multiset(size_type __n, const hasher& __hf, @@ -569,7 +568,6 @@ template hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( _InputIterator __first, _InputIterator __last) { - __table_.rehash(193); insert(__first, __last); } diff --git a/libcxx/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp b/libcxx/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp index bfcb8ae..2c72acd 100644 --- a/libcxx/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp +++ b/libcxx/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp @@ -6,31 +6,31 @@ // //===----------------------------------------------------------------------===// + // Prevent emission of the deprecated warning. #ifdef __clang__ #pragma clang diagnostic ignored "-W#warnings" #endif -// Poison the std:: names we might use inside __gnu_cxx to ensure they're -// properly qualified. -struct allocator; -struct pair; -struct equal_to; -struct unique_ptr; #include +#include #include "test_macros.h" +#include "count_new.hpp" - -namespace __gnu_cxx { -template class hash_map; +void test_default_does_not_allocate() { + DisableAllocationGuard g; + ((void)g); + { + __gnu_cxx::hash_map h; + assert(h.bucket_count() == 0); + } + { + __gnu_cxx::hash_multimap h; + assert(h.bucket_count() == 0); + } } int main(int, char**) { - typedef __gnu_cxx::hash_map Map; - Map m; - Map m2(m); - ((void)m2); - - return 0; + test_default_does_not_allocate(); } diff --git a/libcxx/test/libcxx/containers/gnu_cxx/hash_map_name_lookup.pass.cpp b/libcxx/test/libcxx/containers/gnu_cxx/hash_map_name_lookup.pass.cpp new file mode 100644 index 0000000..bfcb8ae --- /dev/null +++ b/libcxx/test/libcxx/containers/gnu_cxx/hash_map_name_lookup.pass.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// Prevent emission of the deprecated warning. +#ifdef __clang__ +#pragma clang diagnostic ignored "-W#warnings" +#endif + +// Poison the std:: names we might use inside __gnu_cxx to ensure they're +// properly qualified. +struct allocator; +struct pair; +struct equal_to; +struct unique_ptr; +#include + +#include "test_macros.h" + + +namespace __gnu_cxx { +template class hash_map; +} + +int main(int, char**) { + typedef __gnu_cxx::hash_map Map; + Map m; + Map m2(m); + ((void)m2); + + return 0; +} diff --git a/libcxx/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp b/libcxx/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp index b3e1e19..6626fc6 100644 --- a/libcxx/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp +++ b/libcxx/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp @@ -6,29 +6,31 @@ // //===----------------------------------------------------------------------===// + // Prevent emission of the deprecated warning. #ifdef __clang__ #pragma clang diagnostic ignored "-W#warnings" #endif -// Poison the std:: names we might use inside __gnu_cxx to ensure they're -// properly qualified. -struct allocator; -struct pair; -struct equal_to; -struct unique_ptr; + #include +#include #include "test_macros.h" +#include "count_new.hpp" -namespace __gnu_cxx { -template class hash_set; +void test_default_does_not_allocate() { + DisableAllocationGuard g; + ((void)g); + { + __gnu_cxx::hash_set h; + assert(h.bucket_count() == 0); + } + { + __gnu_cxx::hash_multiset h; + assert(h.bucket_count() == 0); + } } int main(int, char**) { - typedef __gnu_cxx::hash_set Set; - Set s; - Set s2(s); - ((void)s2); - - return 0; + test_default_does_not_allocate(); } diff --git a/libcxx/test/libcxx/containers/gnu_cxx/hash_set_name_lookup.pass.cpp b/libcxx/test/libcxx/containers/gnu_cxx/hash_set_name_lookup.pass.cpp new file mode 100644 index 0000000..b3e1e19 --- /dev/null +++ b/libcxx/test/libcxx/containers/gnu_cxx/hash_set_name_lookup.pass.cpp @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// Prevent emission of the deprecated warning. +#ifdef __clang__ +#pragma clang diagnostic ignored "-W#warnings" +#endif +// Poison the std:: names we might use inside __gnu_cxx to ensure they're +// properly qualified. +struct allocator; +struct pair; +struct equal_to; +struct unique_ptr; +#include + +#include "test_macros.h" + +namespace __gnu_cxx { +template class hash_set; +} + +int main(int, char**) { + typedef __gnu_cxx::hash_set Set; + Set s; + Set s2(s); + ((void)s2); + + return 0; +} -- 2.7.4