* [patch] libstdc++/61143 make unordered containers usable after move
@ 2014-05-15 20:20 François Dumont
2014-05-15 20:31 ` Paolo Carlini
2014-05-15 20:52 ` Jonathan Wakely
0 siblings, 2 replies; 6+ messages in thread
From: François Dumont @ 2014-05-15 20:20 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 788 bytes --]
Hi
Here is a proposal to fix PR 61143. As explained in the PR I
finally prefer to leave the container in a valid state that is to say
with a non zero number of bucket, that is to say 1, after a move. This
bucket is stored directly in the container so not allocated to leave the
move operations noexcept qualified. With this evolution we could even
make the default constructor noexcept but I don't think it has any interest.
2014-05-15 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/61143
* include/bits/hashtable.h: Fix move semantic to leave hashtable in a
usable state.
* testsuite/23_containers/unordered_set/61143.cc: New.
I run unordered containers test for the moment with no error. I
will run the others before to commit.
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 16444 bytes --]
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 210479)
+++ include/bits/hashtable.h (working copy)
@@ -316,14 +316,37 @@
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
+ // A single bucket used when only need 1 bucket. After move the hashtable
+ // is left with only 1 bucket which is not allocated so that we can have a
+ // noexcept move constructor.
+ // Note that we can't leave hashtable with 0 bucket without adding
+ // numerous checks in the code to avoid 0 modulus.
+ __bucket_type _M_single_bucket;
+
__hashtable_alloc&
_M_base_alloc() { return *this; }
- using __hashtable_alloc::_M_deallocate_buckets;
+ __bucket_type*
+ _M_allocate_buckets(size_type __n)
+ {
+ if (__builtin_expect(__n == 1, false))
+ return &_M_single_bucket;
+ return __hashtable_alloc::_M_allocate_buckets(__n);
+ }
+
void
+ _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+ {
+ if (__builtin_expect(__bkts == &_M_single_bucket, false))
+ return;
+
+ __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+ }
+
+ void
_M_deallocate_buckets()
- { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
@@ -703,11 +726,7 @@
size_type
erase(const key_type& __k)
- {
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
- return _M_erase(__unique_keys(), __k);
- }
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -768,7 +787,7 @@
_M_rehash_policy()
{
_M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
}
template<typename _Key, typename _Value,
@@ -796,7 +815,7 @@
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -833,9 +852,9 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
- _M_reset();
+ _M_before_begin._M_nxt = nullptr;
+ _M_deallocate_buckets();
+ _M_buckets = nullptr;
std::__alloc_on_copy(__this_alloc, __that_alloc);
__hashtable_base::operator=(__ht);
_M_bucket_count = __ht._M_bucket_count;
@@ -867,7 +886,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -885,8 +904,7 @@
[&__roan](const __node_type* __n)
{ return __roan(__n->_M_v()); });
if (__former_buckets)
- this->_M_deallocate_buckets(__former_buckets,
- __former_bucket_count);
+ _M_deallocate_buckets(__former_buckets, __former_bucket_count);
}
__catch(...)
{
@@ -917,7 +935,7 @@
{
__bucket_type* __buckets = nullptr;
if (!_M_buckets)
- _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
@@ -964,8 +982,9 @@
_M_reset() noexcept
{
_M_rehash_policy._M_reset();
- _M_bucket_count = 0;
- _M_buckets = nullptr;
+ _M_bucket_count = 1;
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = nullptr;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -980,12 +999,16 @@
_M_move_assign(_Hashtable&& __ht, std::true_type)
{
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
-
+ _M_deallocate_buckets();
__hashtable_base::operator=(std::move(__ht));
_M_rehash_policy = __ht._M_rehash_policy;
- _M_buckets = __ht._M_buckets;
+ if (__builtin_expect(__ht._M_buckets != &__ht._M_single_bucket, true))
+ _M_buckets = __ht._M_buckets;
+ else
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
_M_bucket_count = __ht._M_bucket_count;
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
@@ -1019,7 +1042,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1093,10 +1116,18 @@
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
+ // Update, if necessary, buckets if __ht is using its single bucket.
+ if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
@@ -1139,7 +1170,14 @@
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
- _M_buckets = __ht._M_buckets;
+ if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+ else
+ _M_buckets = __ht._M_buckets;
+
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1193,11 +1231,21 @@
std::swap(_M_bucket_count, __x._M_bucket_count);
std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
+ std::swap(_M_single_bucket, __x._M_single_bucket);
+ // Fix buckets if any is pointing to its single bucket that can't be
+ // swapped.
+ if (_M_buckets == &__x._M_single_bucket)
+ _M_buckets = &_M_single_bucket;
+
+ if (__x._M_buckets == &_M_single_bucket)
+ __x._M_buckets = &__x._M_single_bucket;
+
// Fix buckets containing the _M_before_begin pointers that can't be
// swapped.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
if (__x._M_begin())
__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
= &__x._M_before_begin;
@@ -1230,9 +1278,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1250,9 +1295,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1270,9 +1312,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
count(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_bucket_begin(__n);
@@ -1311,9 +1350,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1347,9 +1383,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1944,7 +1977,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
@@ -1969,8 +2002,7 @@
__p = __next;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
@@ -1986,7 +2018,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::false_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
@@ -2060,8 +2092,7 @@
__new_buckets[__next_bkt] = __prev_p;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy_assign.cc (revision 210479)
+++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc (working copy)
@@ -17,6 +17,7 @@
// { dg-options "-std=c++11" }
+#include <iostream>
#include <unordered_map>
#include <testsuite_hooks.h>
#include <testsuite_allocator.h>
@@ -56,22 +57,37 @@
void test02()
{
bool test __attribute__((unused)) = true;
- typedef propagating_allocator<T, true> alloc_type;
- typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
- test_type v1(alloc_type(1));
- v1.emplace(std::piecewise_construct,
- std::make_tuple(T()), std::make_tuple(T()));
- test_type v2(alloc_type(2));
- v2.emplace(std::piecewise_construct,
- std::make_tuple(T()), std::make_tuple(T()));
- v2 = v1;
- VERIFY(1 == v1.get_allocator().get_personality());
- VERIFY(1 == v2.get_allocator().get_personality());
+ {
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ std::cout << "Instantiate v1" << std::endl;
+ test_type v1(alloc_type(1));
+ std::cout << "Emplace in v1" << std::endl;
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ {
+ std::cout << "Instantiate v2" << std::endl;
+ test_type v2(alloc_type(2));
+ std::cout << "Emplace in v2" << std::endl;
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ std::cout << "v2 = v1" << std::endl;
+ v2 = v1;
+ std::cout << "Done" << std::endl;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+ }
+ std::cout << "v2 destroyed" << std::endl;
+ }
+ std::cout << "v1 destroyed" << std::endl;
}
int main()
{
+ std::cout << "Running test01" << std::endl;
test01();
+ std::cout << "Running test02" << std::endl;
test02();
+ std::cout << "Done" << std::endl;
return 0;
}
Index: testsuite/23_containers/unordered_set/61143.cc
===================================================================
--- testsuite/23_containers/unordered_set/61143.cc (revision 0)
+++ testsuite/23_containers/unordered_set/61143.cc (working copy)
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2014 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/61143
+
+#include <unordered_set>
+
+void test01()
+{
+ std::unordered_set<int> us1, us2;
+ us1.insert(1);
+
+ us2 = std::move(us1);
+
+ us1.insert(1);
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/Makefile.in
===================================================================
--- testsuite/Makefile.in (revision 210479)
+++ testsuite/Makefile.in (working copy)
@@ -1,9 +1,9 @@
-# Makefile.in generated by automake 1.11.1 from Makefile.am.
+# Makefile.in generated by automake 1.11.6 from Makefile.am.
# @configure_input@
# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
-# 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation,
-# Inc.
+# 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software
+# Foundation, Inc.
# This Makefile.in is free software; the Free Software Foundation
# gives unlimited permission to copy and/or distribute it,
# with or without modifications, as long as this notice is preserved.
@@ -15,6 +15,23 @@
@SET_MAKE@
VPATH = @srcdir@
+am__make_dryrun = \
+ { \
+ am__dry=no; \
+ case $$MAKEFLAGS in \
+ *\\[\ \ ]*) \
+ echo 'am--echo: ; @echo "AM" OK' | $(MAKE) -f - 2>/dev/null \
+ | grep '^AM OK$$' >/dev/null || am__dry=yes;; \
+ *) \
+ for am__flg in $$MAKEFLAGS; do \
+ case $$am__flg in \
+ *=*|--*) ;; \
+ *n*) am__dry=yes; break;; \
+ esac; \
+ done;; \
+ esac; \
+ test $$am__dry = yes; \
+ }
pkgdatadir = $(datadir)/@PACKAGE@
pkgincludedir = $(includedir)/@PACKAGE@
pkglibdir = $(libdir)/@PACKAGE@
@@ -67,6 +84,11 @@
depcomp =
am__depfiles_maybe =
SOURCES =
+am__can_run_installinfo = \
+ case $$AM_UPDATE_INFO_DIR in \
+ n|no|NO) false;; \
+ *) (install-info --version) >/dev/null 2>&1;; \
+ esac
ABI_TWEAKS_SRCDIR = @ABI_TWEAKS_SRCDIR@
ACLOCAL = @ACLOCAL@
ALLOCATOR_H = @ALLOCATOR_H@
@@ -360,6 +382,7 @@
echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \
cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \
esac;
+$(top_srcdir)/fragment.am:
$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES)
cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
@@ -395,10 +418,15 @@
installcheck: installcheck-am
install-strip:
- $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
- install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
- `test -z '$(STRIP)' || \
- echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install
+ if test -z '$(STRIP)'; then \
+ $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+ install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+ install; \
+ else \
+ $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+ install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+ "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \
+ fi
mostlyclean-generic:
clean-generic:
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch] libstdc++/61143 make unordered containers usable after move
2014-05-15 20:20 [patch] libstdc++/61143 make unordered containers usable after move François Dumont
@ 2014-05-15 20:31 ` Paolo Carlini
2014-05-15 20:52 ` Jonathan Wakely
1 sibling, 0 replies; 6+ messages in thread
From: Paolo Carlini @ 2014-05-15 20:31 UTC (permalink / raw)
To: François Dumont, libstdc++, gcc-patches
Hi,
On 05/15/2014 10:20 PM, François Dumont wrote:
> Hi
>
> Here is a proposal to fix PR 61143. As explained in the PR I
> finally prefer to leave the container in a valid state that is to say
> with a non zero number of bucket, that is to say 1, after a move. This
> bucket is stored directly in the container so not allocated to leave
> the move operations noexcept qualified. With this evolution we could
> even make the default constructor noexcept but I don't think it has
> any interest.
Well, FWIW my opinion (I didn't follow the issue in detail), I think it
would be a very nice improvement, not only because of the noexcept, but
because of the avoided dynamic memory allocation, thus performance. I'm
sure many other implementors agree ;)
Paolo.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch] libstdc++/61143 make unordered containers usable after move
2014-05-15 20:20 [patch] libstdc++/61143 make unordered containers usable after move François Dumont
2014-05-15 20:31 ` Paolo Carlini
@ 2014-05-15 20:52 ` Jonathan Wakely
2014-05-19 20:27 ` François Dumont
1 sibling, 1 reply; 6+ messages in thread
From: Jonathan Wakely @ 2014-05-15 20:52 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 15/05/14 22:20 +0200, François Dumont wrote:
>Hi
>
> Here is a proposal to fix PR 61143. As explained in the PR I
>finally prefer to leave the container in a valid state that is to say
>with a non zero number of bucket, that is to say 1, after a move. This
>bucket is stored directly in the container so not allocated to leave
>the move operations noexcept qualified.
Thanks for fixing this, I like the direction very much. I have a few
comments below ...
> With this evolution we could
>even make the default constructor noexcept but I don't think it has
>any interest.
I tend to agree with Paolo that a noexcept default constructor might
be useful, but let's fix the bug first and consider that later.
>Index: include/bits/hashtable.h
>===================================================================
>--- include/bits/hashtable.h (revision 210479)
>+++ include/bits/hashtable.h (working copy)
>@@ -316,14 +316,37 @@
> size_type _M_element_count;
> _RehashPolicy _M_rehash_policy;
>
>+ // A single bucket used when only need 1 bucket. After move the hashtable
>+ // is left with only 1 bucket which is not allocated so that we can have a
>+ // noexcept move constructor.
>+ // Note that we can't leave hashtable with 0 bucket without adding
>+ // numerous checks in the code to avoid 0 modulus.
>+ __bucket_type _M_single_bucket;
Does this get initialized in the constructors?
Would it make sense to give it an initializer?
__bucket_type _M_single_bucket = nullptr;
>@@ -980,12 +999,16 @@
> _M_move_assign(_Hashtable&& __ht, std::true_type)
> {
> this->_M_deallocate_nodes(_M_begin());
>- if (__builtin_expect(_M_bucket_count != 0, true))
>- _M_deallocate_buckets();
>-
>+ _M_deallocate_buckets();
> __hashtable_base::operator=(std::move(__ht));
> _M_rehash_policy = __ht._M_rehash_policy;
>- _M_buckets = __ht._M_buckets;
>+ if (__builtin_expect(__ht._M_buckets != &__ht._M_single_bucket, true))
>+ _M_buckets = __ht._M_buckets;
What is the value of this->_M_single_bucket now?
Should it be set to nullptr, if only to help debugging?
>+ if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
This check appears in a few places, I wonder if it is worth creating a
private member function to hide the details:
bool _M_moved_from() const noexcept
{
return __builtin_expect(_M_buckets == &_M_single_bucket, false);
}
Then just test if (__ht._M_moved_from())
Usually I would think the __builtin_expect should not be inside the
member function, so the caller decides what the expected result is,
but I think in all cases the result is expected to be false. That
matches how move semantics are designed: the object that gets moved
from is expected to be going out of scope, and so will be reused in a
minority of cases.
>@@ -1139,7 +1170,14 @@
> {
> if (__ht._M_node_allocator() == this->_M_node_allocator())
> {
>- _M_buckets = __ht._M_buckets;
>+ if (__builtin_expect(__ht._M_buckets == &__ht._M_single_bucket, false))
This could be if (__ht._M_moved_from())
>@@ -1193,11 +1231,21 @@
> std::swap(_M_bucket_count, __x._M_bucket_count);
> std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
> std::swap(_M_element_count, __x._M_element_count);
>+ std::swap(_M_single_bucket, __x._M_single_bucket);
>
>+ // Fix buckets if any is pointing to its single bucket that can't be
>+ // swapped.
>+ if (_M_buckets == &__x._M_single_bucket)
>+ _M_buckets = &_M_single_bucket;
>+
>+ if (__x._M_buckets == &_M_single_bucket)
>+ __x._M_buckets = &__x._M_single_bucket;
>+
Does this do more work than necessary, swapping the _M_buckets
members, then updating them again?
How about removing the std::swap(_M_buckets, __x._M_buckets) above and
doing (untested):
if (this->_M_moved_from())
{
if (__x._M_moved_from())
_M_buckets = &_M_single_bucket;
else
_M_buckets = __x._M_buckets;
__x._M_buckets = &__x._M_single_bucket;
}
else if (__x._M_moved_from())
{
__x._M_buckets = _M_buckets;
_M_buckets = &_M_single_bucket;
}
else
std::swap(_M_buckets, __x._M_buckets);
Is that worth it? I'm not sure.
>Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc
>===================================================================
>--- testsuite/23_containers/unordered_map/allocator/copy_assign.cc (revision 210479)
>+++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc (working copy)
The changes to this file are not listed in the ChangeLog entry, and we
don't want writes to stdout in the testsuite.
Did you intend to include this in the patch?
>Index: testsuite/Makefile.in
>===================================================================
>--- testsuite/Makefile.in (revision 210479)
>+++ testsuite/Makefile.in (working copy)
Same question for this file.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch] libstdc++/61143 make unordered containers usable after move
2014-05-15 20:52 ` Jonathan Wakely
@ 2014-05-19 20:27 ` François Dumont
2014-05-20 19:36 ` Jonathan Wakely
0 siblings, 1 reply; 6+ messages in thread
From: François Dumont @ 2014-05-19 20:27 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 5738 bytes --]
On 15/05/2014 22:52, Jonathan Wakely wrote:
> On 15/05/14 22:20 +0200, François Dumont wrote:
>> Hi
>>
>> Here is a proposal to fix PR 61143. As explained in the PR I
>> finally prefer to leave the container in a valid state that is to say
>> with a non zero number of bucket, that is to say 1, after a move.
>> This bucket is stored directly in the container so not allocated to
>> leave the move operations noexcept qualified.
>
> Thanks for fixing this, I like the direction very much. I have a few
> comments below ...
>
>> With this evolution we could even make the default constructor
>> noexcept but I don't think it has any interest.
>
> I tend to agree with Paolo that a noexcept default constructor might
> be useful, but let's fix the bug first and consider that later.
ok, we will have to review the hint values but it should be easy.
>
>> Index: include/bits/hashtable.h
>> ===================================================================
>> --- include/bits/hashtable.h (revision 210479)
>> +++ include/bits/hashtable.h (working copy)
>> @@ -316,14 +316,37 @@
>> size_type _M_element_count;
>> _RehashPolicy _M_rehash_policy;
>>
>> + // A single bucket used when only need 1 bucket. After move
>> the hashtable
>> + // is left with only 1 bucket which is not allocated so that
>> we can have a
>> + // noexcept move constructor.
>> + // Note that we can't leave hashtable with 0 bucket without
>> adding
>> + // numerous checks in the code to avoid 0 modulus.
>> + __bucket_type _M_single_bucket;
>
> Does this get initialized in the constructors?
> Would it make sense to give it an initializer?
>
> __bucket_type _M_single_bucket = nullptr;
This bucket is replacing those normally allocated and when they are
allocated they are 0 initialised. So, you were right, there were one
place where this initialization was missing which is fixed in this new
patch. So I don't think this additional initialization is necessary.
>
>> @@ -980,12 +999,16 @@
>> _M_move_assign(_Hashtable&& __ht, std::true_type)
>> {
>> this->_M_deallocate_nodes(_M_begin());
>> - if (__builtin_expect(_M_bucket_count != 0, true))
>> - _M_deallocate_buckets();
>> -
>> + _M_deallocate_buckets();
>> __hashtable_base::operator=(std::move(__ht));
>> _M_rehash_policy = __ht._M_rehash_policy;
>> - _M_buckets = __ht._M_buckets;
>> + if (__builtin_expect(__ht._M_buckets !=
>> &__ht._M_single_bucket, true))
>> + _M_buckets = __ht._M_buckets;
>
> What is the value of this->_M_single_bucket now?
>
> Should it be set to nullptr, if only to help debugging?
We are not resetting buckets to null when rehashing so unless I add more
checks I won't be able to reset it each time.
>
>> + if (__builtin_expect(__ht._M_buckets ==
>> &__ht._M_single_bucket, false))
>
> This check appears in a few places, I wonder if it is worth creating a
> private member function to hide the details:
>
> bool _M_moved_from() const noexcept
> {
> return __builtin_expect(_M_buckets == &_M_single_bucket, false);
> }
>
> Then just test if (__ht._M_moved_from())
>
> Usually I would think the __builtin_expect should not be inside the
> member function, so the caller decides what the expected result is,
> but I think in all cases the result is expected to be false. That
> matches how move semantics are designed: the object that gets moved
> from is expected to be going out of scope, and so will be reused in a
> minority of cases.
>
>> @@ -1139,7 +1170,14 @@
>> {
>> if (__ht._M_node_allocator() == this->_M_node_allocator())
>> {
>> - _M_buckets = __ht._M_buckets;
>> + if (__builtin_expect(__ht._M_buckets ==
>> &__ht._M_single_bucket, false))
>
> This could be if (__ht._M_moved_from())
I hesitated in doing so and finally do so. I only prefer
_M_use_single_bucket as we might not limit its usage to moved instances.
>
>> @@ -1193,11 +1231,21 @@
>> std::swap(_M_bucket_count, __x._M_bucket_count);
>> std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
>> std::swap(_M_element_count, __x._M_element_count);
>> + std::swap(_M_single_bucket, __x._M_single_bucket);
>>
>> + // Fix buckets if any is pointing to its single bucket that
>> can't be
>> + // swapped.
>> + if (_M_buckets == &__x._M_single_bucket)
>> + _M_buckets = &_M_single_bucket;
>> +
>> + if (__x._M_buckets == &_M_single_bucket)
>> + __x._M_buckets = &__x._M_single_bucket;
>> +
>
> Does this do more work than necessary, swapping the _M_buckets
> members, then updating them again?
>
> How about removing the std::swap(_M_buckets, __x._M_buckets) above and
> doing (untested):
>
> if (this->_M_moved_from())
> {
> if (__x._M_moved_from())
> _M_buckets = &_M_single_bucket;
> else
> _M_buckets = __x._M_buckets;
> __x._M_buckets = &__x._M_single_bucket;
> }
> else if (__x._M_moved_from())
> {
> __x._M_buckets = _M_buckets;
> _M_buckets = &_M_single_bucket;
> }
> else
> std::swap(_M_buckets, __x._M_buckets);
>
> Is that worth it? I'm not sure.
Yes, with the newly introduced _M_use_single_bucket it worth it I think
and is what I have done.
Here is the new patch limited to what I really want to commit this time.
2014-05-20 François Dumont <fdumont@gcc.gnu.org>
PR libstdc++/61143
* include/bits/hashtable.h: Fix move semantic to leave hashtable in a
usable state.
* testsuite/23_containers/unordered_set/61143.cc: New.
* testsuite/23_containers/unordered_set/modifiers/swap.cc: New.
Tested under Linux x86_64, ok to commit ?
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 14247 bytes --]
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 210479)
+++ include/bits/hashtable.h (working copy)
@@ -316,14 +316,49 @@
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
+ // A single bucket used when only need for 1 bucket. Especially
+ // interesting in move semantic to leave hashtable with only 1 buckets
+ // which is not allocated so that we can have those operations noexcept
+ // qualified.
+ // Note that we can't leave hashtable with 0 bucket without adding
+ // numerous checks in the code to avoid 0 modulus.
+ __bucket_type _M_single_bucket;
+
+ bool
+ _M_use_single_bucket(__bucket_type* __bkts) const
+ { return __builtin_expect(_M_buckets == &_M_single_bucket, false); }
+
+ bool
+ _M_use_single_bucket() const
+ { return _M_use_single_bucket(_M_buckets); }
+
__hashtable_alloc&
_M_base_alloc() { return *this; }
- using __hashtable_alloc::_M_deallocate_buckets;
+ __bucket_type*
+ _M_allocate_buckets(size_type __n)
+ {
+ if (__builtin_expect(__n == 1, false))
+ {
+ _M_single_bucket = nullptr;
+ return &_M_single_bucket;
+ }
+ return __hashtable_alloc::_M_allocate_buckets(__n);
+ }
+
void
+ _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+ {
+ if (_M_use_single_bucket(__bkts))
+ return;
+
+ __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+ }
+
+ void
_M_deallocate_buckets()
- { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
@@ -703,11 +738,7 @@
size_type
erase(const key_type& __k)
- {
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
- return _M_erase(__unique_keys(), __k);
- }
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -768,7 +799,7 @@
_M_rehash_policy()
{
_M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
}
template<typename _Key, typename _Value,
@@ -796,7 +827,7 @@
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -833,9 +864,9 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
- _M_reset();
+ _M_before_begin._M_nxt = nullptr;
+ _M_deallocate_buckets();
+ _M_buckets = nullptr;
std::__alloc_on_copy(__this_alloc, __that_alloc);
__hashtable_base::operator=(__ht);
_M_bucket_count = __ht._M_bucket_count;
@@ -867,7 +898,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -885,8 +916,7 @@
[&__roan](const __node_type* __n)
{ return __roan(__n->_M_v()); });
if (__former_buckets)
- this->_M_deallocate_buckets(__former_buckets,
- __former_bucket_count);
+ _M_deallocate_buckets(__former_buckets, __former_bucket_count);
}
__catch(...)
{
@@ -917,7 +947,7 @@
{
__bucket_type* __buckets = nullptr;
if (!_M_buckets)
- _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
@@ -964,8 +994,9 @@
_M_reset() noexcept
{
_M_rehash_policy._M_reset();
- _M_bucket_count = 0;
- _M_buckets = nullptr;
+ _M_bucket_count = 1;
+ _M_single_bucket = nullptr;
+ _M_buckets = &_M_single_bucket;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -980,12 +1011,16 @@
_M_move_assign(_Hashtable&& __ht, std::true_type)
{
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
-
+ _M_deallocate_buckets();
__hashtable_base::operator=(std::move(__ht));
_M_rehash_policy = __ht._M_rehash_policy;
- _M_buckets = __ht._M_buckets;
+ if (!__ht._M_use_single_bucket())
+ _M_buckets = __ht._M_buckets;
+ else
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
_M_bucket_count = __ht._M_bucket_count;
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
@@ -1019,7 +1054,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1093,10 +1128,18 @@
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
+ // Update, if necessary, buckets if __ht is using its single bucket.
+ if (__ht._M_use_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
@@ -1139,7 +1182,14 @@
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
- _M_buckets = __ht._M_buckets;
+ if (__ht._M_use_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+ else
+ _M_buckets = __ht._M_buckets;
+
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1189,15 +1239,32 @@
std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
std::swap(_M_rehash_policy, __x._M_rehash_policy);
- std::swap(_M_buckets, __x._M_buckets);
+
+ // Deal properly with potentially moved instances.
+ if (!_M_use_single_bucket() && !__x._M_use_single_bucket())
+ std::swap(_M_buckets, __x._M_buckets);
+ else
+ if (!_M_use_single_bucket())
+ {
+ __x._M_buckets = _M_buckets;
+ _M_buckets = &_M_single_bucket;
+ }
+ else if (!__x._M_use_single_bucket())
+ {
+ _M_buckets = __x._M_buckets;
+ __x._M_buckets = &__x._M_single_bucket;
+ }
+
std::swap(_M_bucket_count, __x._M_bucket_count);
std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
+ std::swap(_M_single_bucket, __x._M_single_bucket);
// Fix buckets containing the _M_before_begin pointers that can't be
// swapped.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
if (__x._M_begin())
__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
= &__x._M_before_begin;
@@ -1230,9 +1297,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1250,9 +1314,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1270,9 +1331,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
count(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_bucket_begin(__n);
@@ -1287,7 +1345,7 @@
else if (__result)
// All equivalent values are next to each other, if we
// found a non-equivalent value after an equivalent one it
- // means that we won't find any more equivalent values.
+ // means that we won't find any new equivalent value.
break;
if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
@@ -1311,9 +1369,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1347,9 +1402,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1944,7 +1996,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
@@ -1969,8 +2021,7 @@
__p = __next;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
@@ -1986,7 +2037,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::false_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
@@ -2060,8 +2111,7 @@
__new_buckets[__next_bkt] = __prev_p;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
Index: testsuite/23_containers/unordered_set/61143.cc
===================================================================
--- testsuite/23_containers/unordered_set/61143.cc (revision 0)
+++ testsuite/23_containers/unordered_set/61143.cc (working copy)
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2014 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/61143
+
+#include <unordered_set>
+
+void test01()
+{
+ std::unordered_set<int> us1, us2;
+ us1.insert(1);
+
+ us2 = std::move(us1);
+
+ us1.insert(1);
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/modifiers/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/modifiers/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/modifiers/swap.cc (working copy)
@@ -0,0 +1,65 @@
+// Copyright (C) 2014 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ std::unordered_set<int> us1 { 0, 1 };
+ {
+ std::unordered_set<int> us2(std::move(us1));
+
+ us1.swap(us2);
+
+ VERIFY( us1.find(0) != us1.end() );
+
+ us1.insert(2);
+
+ VERIFY( us1.size() == 3 );
+
+ us2.swap(us1);
+
+ VERIFY( us2.size() == 3 );
+ VERIFY( us2.find(2) != us2.end() );
+
+ us1 = { 3, 4, 5 };
+
+ VERIFY( us1.size() == 3 );
+ VERIFY( us1.bucket_count() >= 3 );
+
+ std::unordered_set<int> us3(std::move(us1));
+ us3 = std::move(us2);
+
+ us1.swap(us2);
+
+ VERIFY( us1.empty() );
+ VERIFY( us2.empty() );
+ }
+
+ us1 = { 0, 1 };
+ VERIFY( us1.size() == 2 );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch] libstdc++/61143 make unordered containers usable after move
2014-05-19 20:27 ` François Dumont
@ 2014-05-20 19:36 ` Jonathan Wakely
2014-05-20 20:37 ` François Dumont
0 siblings, 1 reply; 6+ messages in thread
From: Jonathan Wakely @ 2014-05-20 19:36 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 19/05/14 22:27 +0200, François Dumont wrote:
>On 15/05/2014 22:52, Jonathan Wakely wrote:
>>Does this get initialized in the constructors?
>>Would it make sense to give it an initializer?
>>
>> __bucket_type _M_single_bucket = nullptr;
>
> This bucket is replacing those normally allocated and when they
>are allocated they are 0 initialised. So, you were right, there were
>one place where this initialization was missing which is fixed in this
>new patch. So I don't think this additional initialization is
>necessary.
OK
>>>@@ -980,12 +999,16 @@
>>> _M_move_assign(_Hashtable&& __ht, std::true_type)
>>> {
>>> this->_M_deallocate_nodes(_M_begin());
>>>- if (__builtin_expect(_M_bucket_count != 0, true))
>>>- _M_deallocate_buckets();
>>>-
>>>+ _M_deallocate_buckets();
>>> __hashtable_base::operator=(std::move(__ht));
>>> _M_rehash_policy = __ht._M_rehash_policy;
>>>- _M_buckets = __ht._M_buckets;
>>>+ if (__builtin_expect(__ht._M_buckets !=
>>>&__ht._M_single_bucket, true))
>>>+ _M_buckets = __ht._M_buckets;
>>
>>What is the value of this->_M_single_bucket now?
>>
>>Should it be set to nullptr, if only to help debugging?
>
>We are not resetting buckets to null when rehashing so unless I add
>more checks I won't be able to reset it each time.
OK
>>
>>>+ if (__builtin_expect(__ht._M_buckets ==
>>>&__ht._M_single_bucket, false))
>>
>>This check appears in a few places, I wonder if it is worth creating a
>>private member function to hide the details:
>>
>> bool _M_moved_from() const noexcept
>> {
>> return __builtin_expect(_M_buckets == &_M_single_bucket, false);
>> }
>>
>>Then just test if (__ht._M_moved_from())
>>
>>Usually I would think the __builtin_expect should not be inside the
>>member function, so the caller decides what the expected result is,
>>but I think in all cases the result is expected to be false. That
>>matches how move semantics are designed: the object that gets moved
>>from is expected to be going out of scope, and so will be reused in a
>>minority of cases.
>>
>>>@@ -1139,7 +1170,14 @@
>>> {
>>> if (__ht._M_node_allocator() == this->_M_node_allocator())
>>> {
>>>- _M_buckets = __ht._M_buckets;
>>>+ if (__builtin_expect(__ht._M_buckets ==
>>>&__ht._M_single_bucket, false))
>>
>>This could be if (__ht._M_moved_from())
>
>I hesitated in doing so and finally do so. I only prefer
>_M_use_single_bucket as we might not limit its usage to moved
>instances.
Good point.
I think it should be called _M_uses_single_bucket() or
_M_using_single_bucket() though, otherwise it sounds more like it
answers the question "should I use a single bucket?" rather than "am I
using the single bucket?"
>>How about removing the std::swap(_M_buckets, __x._M_buckets) above and
>>doing (untested):
>>
>> if (this->_M_moved_from())
>> {
>> if (__x._M_moved_from())
>> _M_buckets = &_M_single_bucket;
>> else
>> _M_buckets = __x._M_buckets;
>> __x._M_buckets = &__x._M_single_bucket;
>> }
>> else if (__x._M_moved_from())
>> {
>> __x._M_buckets = _M_buckets;
>> _M_buckets = &_M_single_bucket;
>> }
>> else
>> std::swap(_M_buckets, __x._M_buckets);
>>
>>Is that worth it? I'm not sure.
>
>Yes, with the newly introduced _M_use_single_bucket it worth it I
>think and is what I have done.
OK. My sketch above avoided calling _M_moved_from() more than once per
object, but the compiler should be able to optimise your version to
avoid multiple calls anyway.
>Here is the new patch limited to what I really want to commit this time.
Great. Please commit to trunk and the 4.9 branch - thanks!
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [patch] libstdc++/61143 make unordered containers usable after move
2014-05-20 19:36 ` Jonathan Wakely
@ 2014-05-20 20:37 ` François Dumont
0 siblings, 0 replies; 6+ messages in thread
From: François Dumont @ 2014-05-20 20:37 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 641 bytes --]
On 20/05/2014 21:36, Jonathan Wakely wrote:
>
> OK. My sketch above avoided calling _M_moved_from() more than once per
> object, but the compiler should be able to optimise your version to
> avoid multiple calls anyway.
>
>> Here is the new patch limited to what I really want to commit this time.
>
> Great. Please commit to trunk and the 4.9 branch - thanks!
>
>
As I have integrated your remarks I won't have time to commit this
evening. So I submit this update here, just in case you want to see it
again and I will commit tomorrow.
I finally use a simplified version of your sketch in the swap
implementation.
François
[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 14250 bytes --]
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 210657)
+++ include/bits/hashtable.h (working copy)
@@ -316,14 +316,49 @@
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
+ // A single bucket used when only need for 1 bucket. Especially
+ // interesting in move semantic to leave hashtable with only 1 buckets
+ // which is not allocated so that we can have those operations noexcept
+ // qualified.
+ // Note that we can't leave hashtable with 0 bucket without adding
+ // numerous checks in the code to avoid 0 modulus.
+ __bucket_type _M_single_bucket;
+
+ bool
+ _M_uses_single_bucket(__bucket_type* __bkts) const
+ { return __builtin_expect(_M_buckets == &_M_single_bucket, false); }
+
+ bool
+ _M_uses_single_bucket() const
+ { return _M_uses_single_bucket(_M_buckets); }
+
__hashtable_alloc&
_M_base_alloc() { return *this; }
- using __hashtable_alloc::_M_deallocate_buckets;
+ __bucket_type*
+ _M_allocate_buckets(size_type __n)
+ {
+ if (__builtin_expect(__n == 1, false))
+ {
+ _M_single_bucket = nullptr;
+ return &_M_single_bucket;
+ }
+ return __hashtable_alloc::_M_allocate_buckets(__n);
+ }
+
void
+ _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+ {
+ if (_M_uses_single_bucket(__bkts))
+ return;
+
+ __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+ }
+
+ void
_M_deallocate_buckets()
- { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
@@ -703,11 +738,7 @@
size_type
erase(const key_type& __k)
- {
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
- return _M_erase(__unique_keys(), __k);
- }
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -768,7 +799,7 @@
_M_rehash_policy()
{
_M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
}
template<typename _Key, typename _Value,
@@ -796,7 +827,7 @@
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -833,9 +864,9 @@
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
- _M_reset();
+ _M_before_begin._M_nxt = nullptr;
+ _M_deallocate_buckets();
+ _M_buckets = nullptr;
std::__alloc_on_copy(__this_alloc, __that_alloc);
__hashtable_base::operator=(__ht);
_M_bucket_count = __ht._M_bucket_count;
@@ -867,7 +898,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -885,8 +916,7 @@
[&__roan](const __node_type* __n)
{ return __roan(__n->_M_v()); });
if (__former_buckets)
- this->_M_deallocate_buckets(__former_buckets,
- __former_bucket_count);
+ _M_deallocate_buckets(__former_buckets, __former_bucket_count);
}
__catch(...)
{
@@ -917,7 +947,7 @@
{
__bucket_type* __buckets = nullptr;
if (!_M_buckets)
- _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
@@ -964,8 +994,9 @@
_M_reset() noexcept
{
_M_rehash_policy._M_reset();
- _M_bucket_count = 0;
- _M_buckets = nullptr;
+ _M_bucket_count = 1;
+ _M_single_bucket = nullptr;
+ _M_buckets = &_M_single_bucket;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -980,12 +1011,16 @@
_M_move_assign(_Hashtable&& __ht, std::true_type)
{
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
-
+ _M_deallocate_buckets();
__hashtable_base::operator=(std::move(__ht));
_M_rehash_policy = __ht._M_rehash_policy;
- _M_buckets = __ht._M_buckets;
+ if (!__ht._M_uses_single_bucket())
+ _M_buckets = __ht._M_buckets;
+ else
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
_M_bucket_count = __ht._M_bucket_count;
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
@@ -1019,7 +1054,7 @@
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1093,10 +1128,18 @@
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
+ // Update, if necessary, buckets if __ht is using its single bucket.
+ if (__ht._M_uses_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
@@ -1139,7 +1182,14 @@
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
- _M_buckets = __ht._M_buckets;
+ if (__ht._M_uses_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+ else
+ _M_buckets = __ht._M_buckets;
+
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1189,15 +1239,34 @@
std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
std::swap(_M_rehash_policy, __x._M_rehash_policy);
- std::swap(_M_buckets, __x._M_buckets);
+
+ // Deal properly with potentially moved instances.
+ if (this->_M_uses_single_bucket())
+ {
+ if (!__x._M_uses_single_bucket())
+ {
+ _M_buckets = __x._M_buckets;
+ __x._M_buckets = &__x._M_single_bucket;
+ }
+ }
+ else if (__x._M_uses_single_bucket())
+ {
+ __x._M_buckets = _M_buckets;
+ _M_buckets = &_M_single_bucket;
+ }
+ else
+ std::swap(_M_buckets, __x._M_buckets);
+
std::swap(_M_bucket_count, __x._M_bucket_count);
std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
+ std::swap(_M_single_bucket, __x._M_single_bucket);
// Fix buckets containing the _M_before_begin pointers that can't be
// swapped.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
if (__x._M_begin())
__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
= &__x._M_before_begin;
@@ -1230,9 +1299,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1250,9 +1316,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1270,9 +1333,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
count(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_bucket_begin(__n);
@@ -1287,7 +1347,7 @@
else if (__result)
// All equivalent values are next to each other, if we
// found a non-equivalent value after an equivalent one it
- // means that we won't find any more equivalent values.
+ // means that we won't find any new equivalent value.
break;
if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
@@ -1311,9 +1371,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1347,9 +1404,6 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1944,7 +1998,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
@@ -1969,8 +2023,7 @@
__p = __next;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
@@ -1986,7 +2039,7 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::false_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
@@ -2060,8 +2113,7 @@
__new_buckets[__next_bkt] = __prev_p;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
Index: testsuite/23_containers/unordered_set/61143.cc
===================================================================
--- testsuite/23_containers/unordered_set/61143.cc (revision 0)
+++ testsuite/23_containers/unordered_set/61143.cc (working copy)
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2014 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
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/61143
+
+#include <unordered_set>
+
+void test01()
+{
+ std::unordered_set<int> us1, us2;
+ us1.insert(1);
+
+ us2 = std::move(us1);
+
+ us1.insert(1);
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/modifiers/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/modifiers/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/modifiers/swap.cc (working copy)
@@ -0,0 +1,65 @@
+// Copyright (C) 2014 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
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ std::unordered_set<int> us1 { 0, 1 };
+ {
+ std::unordered_set<int> us2(std::move(us1));
+
+ us1.swap(us2);
+
+ VERIFY( us1.find(0) != us1.end() );
+
+ us1.insert(2);
+
+ VERIFY( us1.size() == 3 );
+
+ us2.swap(us1);
+
+ VERIFY( us2.size() == 3 );
+ VERIFY( us2.find(2) != us2.end() );
+
+ us1 = { 3, 4, 5 };
+
+ VERIFY( us1.size() == 3 );
+ VERIFY( us1.bucket_count() >= 3 );
+
+ std::unordered_set<int> us3(std::move(us1));
+ us3 = std::move(us2);
+
+ us1.swap(us2);
+
+ VERIFY( us1.empty() );
+ VERIFY( us2.empty() );
+ }
+
+ us1 = { 0, 1 };
+ VERIFY( us1.size() == 2 );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2014-05-20 20:37 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-15 20:20 [patch] libstdc++/61143 make unordered containers usable after move François Dumont
2014-05-15 20:31 ` Paolo Carlini
2014-05-15 20:52 ` Jonathan Wakely
2014-05-19 20:27 ` François Dumont
2014-05-20 19:36 ` Jonathan Wakely
2014-05-20 20:37 ` François Dumont
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).