From 2514d7f1ffa6049efcf198c373c4d13cef266b03 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Wed, 25 Jul 2012 19:32:48 +0000 Subject: [PATCH] re PR libstdc++/54075 ([4.7.1] unordered_map insert still slower than 4.6.2) MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 2012-07-25 François Dumont PR libstdc++/54075 * include/bits/hashtable.h (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator, size_type, ...): Remove std::max usage to guarantee that hashtable state is consistent with hash policy state. (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid the hashtable to be shrinking on next insertion. * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New. * testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New. * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New. * testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New. From-SVN: r189863 --- libstdc++-v3/ChangeLog | 14 ++++++ libstdc++-v3/include/bits/hashtable.h | 28 +++++++---- .../unordered_map/modifiers/reserve.cc | 47 ++++++++++++++++++ .../unordered_multimap/modifiers/reserve.cc | 48 +++++++++++++++++++ .../unordered_multiset/modifiers/reserve.cc | 48 +++++++++++++++++++ .../unordered_set/modifiers/reserve.cc | 47 ++++++++++++++++++ 6 files changed, 223 insertions(+), 9 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/reserve.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 7c78a82af6b2..a56f1e77f2fb 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2012-07-25 François Dumont + + PR libstdc++/54075 + * include/bits/hashtable.h + (_Hashtable<>::_Hashtable(_InputIterator, _InputIterator, + size_type, ...): Remove std::max usage to guarantee that hashtable + state is consistent with hash policy state. + (_Hashtable<>::rehash): Likewise. Set _M_prev_resize to 0 to avoid + the hashtable to be shrinking on next insertion. + * testsuite/23_containers/unordered_set/modifiers/reserve.cc: New. + * testsuite/23_containers/unordered_multiset/modifiers/reserve.cc: New. + * testsuite/23_containers/unordered_map/modifiers/reserve.cc: New. + * testsuite/23_containers/unordered_multimap/modifiers/reserve.cc: New. + 2012-07-20 Chip Salzenberg Jonathan Wakely diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index f5bc3583f22a..2faf0b3bd889 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -803,11 +803,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count(0), _M_rehash_policy() { - _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), - _M_rehash_policy. - _M_bkt_for_elements(__detail:: - __distance_fw(__f, - __l))); + _M_bucket_count = + _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f, + __l)); + if (_M_bucket_count <= __bucket_hint) + _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); // We don't want the rehash policy to ask for the hashtable to // shrink on the first insertion so we need to reset its @@ -1609,10 +1609,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION rehash(size_type __n) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), - _M_rehash_policy._M_bkt_for_elements(_M_element_count - + 1)), - __saved_state); + std::size_t __buckets + = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1); + if (__buckets <= __n) + __buckets = _M_rehash_policy._M_next_bkt(__n); + + if (__buckets != _M_bucket_count) + { + _M_rehash(__buckets, __saved_state); + + // We don't want the rehash policy to ask for the hashtable to shrink + // on the next insertion so we need to reset its previous resize + // level. + _M_rehash_policy._M_prev_resize = 0; + } } template. + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_map Map; + Map m; + m.reserve(N); + + std::size_t bkts = m.bucket_count(); + for (int i = 0; i != N; ++i) + { + m.insert(std::make_pair(i, i)); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( m.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc new file mode 100644 index 000000000000..44a59189aed8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/reserve.cc @@ -0,0 +1,48 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_multimap MMap; + MMap m; + m.reserve(N * 2); + + std::size_t bkts = m.bucket_count(); + for (int i = 0; i != N; ++i) + { + m.insert(std::make_pair(i, i)); + m.insert(std::make_pair(i, i)); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( m.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc new file mode 100644 index 000000000000..6106b3336ff5 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/reserve.cc @@ -0,0 +1,48 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_multiset MSet; + MSet s; + s.reserve(N * 2); + + std::size_t bkts = s.bucket_count(); + for (int i = 0; i != N; ++i) + { + s.insert(i); + s.insert(i); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( s.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc new file mode 100644 index 000000000000..aba6f771d819 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/reserve.cc @@ -0,0 +1,47 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include + +bool test __attribute__((unused)) = true; + +void test01() +{ + const int N = 1000; + + typedef std::unordered_set Set; + Set s; + s.reserve(N); + + std::size_t bkts = s.bucket_count(); + for (int i = 0; i != N; ++i) + { + s.insert(i); + // As long as we insert less than the reserved number of elements we + // shouldn't experiment any rehash. + VERIFY( s.bucket_count() == bkts ); + } +} + +int main() +{ + test01(); + return 0; +} -- 2.39.5