Re: [patch] fix libstdc++/56267 - local iterator requirements
On 20 January 2014 21:11, François Dumont frs.dum...@gmail.com wrote: On 01/20/2014 04:53 PM, Jonathan Wakely wrote: With this new design couldn't we change the conditions that are used to decide when to cache the hash code. I haven't study it in detail but it looks like the default constructible constraint could be removed, no ? Ah yes, I forgot about that part, I'll update the __cache_default definition. Thanks.
Re: [patch] fix libstdc++/56267 - local iterator requirements
On 21 January 2014 10:00, Jonathan Wakely wrote: On 20 January 2014 21:11, François Dumont frs.dum...@gmail.com wrote: On 01/20/2014 04:53 PM, Jonathan Wakely wrote: With this new design couldn't we change the conditions that are used to decide when to cache the hash code. I haven't study it in detail but it looks like the default constructible constraint could be removed, no ? Ah yes, I forgot about that part, I'll update the __cache_default definition. Thanks. Like so. Tested x86_64-linux, committed to trunk. 2014-01-21 Jonathan Wakely jwak...@redhat.com PR libstdc++/56267 * include/bits/hashtable.h (__cache_default): Do not depend on whether the hash function is DefaultConstructible or CopyAssignable. (_Hashtable): Adjust static assertions. * doc/xml/manual/containers.xml (containers.unordered.cache): Update. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error line number. * testsuite/23_containers/unordered_set/ not_default_constructible_hash_neg.cc: Remove. commit 0efc402079788226108bce180c478d4c85924fd4 Author: Jonathan Wakely jwak...@redhat.com Date: Tue Jan 21 18:20:24 2014 + PR libstdc++/56267 * include/bits/hashtable.h (__cache_default): Do not depend on whether the hash function is DefaultConstructible or CopyAssignable. (_Hashtable): Adjust static assertions. * doc/xml/manual/containers.xml (containers.unordered.cache): Update. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error line number. * testsuite/23_containers/unordered_set/ not_default_constructible_hash_neg.cc: Remove. diff --git a/libstdc++-v3/doc/xml/manual/containers.xml b/libstdc++-v3/doc/xml/manual/containers.xml index 9791953..653033d 100644 --- a/libstdc++-v3/doc/xml/manual/containers.xml +++ b/libstdc++-v3/doc/xml/manual/containers.xml @@ -420,7 +420,7 @@ the hash code every time it's needed can improve performance, but the additional memory overhead can also reduce performance, so whether an unordered associative container caches the hash code or not depends on - a number of factors. The caching policy for GCC 4.8 is described below. + the properties described below. /para para The C++ standard requires that codeerase/code and codeswap/code @@ -432,23 +432,8 @@ or codethrow()/code. /para para - Secondly, libstdc++ also needs the hash code in the implementation of - codelocal_iterator/code and codeconst_local_iterator/code in - order to know when the iterator has reached the end of the bucket. - This means that the local iterator types will embed a copy of the hash - function when possible. - Because the local iterator types must be DefaultConstructible and - CopyAssignable, if the hash function type does not model those concepts - then it cannot be embedded and so the hash code must be cached. - Note that a hash function might not be safe to use when - default-constructed (e.g if it a function pointer) so a hash - function that is contained in a local iterator won't be used until - the iterator is valid, so the hash function has been copied from a - correctly-initialized object. -/para -para - If the hash function is non-throwing, DefaultConstructible and - CopyAssignable then libstdc++ doesn't need to cache the hash code for + If the hash function is non-throwing then libstdc++ doesn't need to + cache the hash code for correctness, but might still do so for performance if computing a hash code is an expensive operation, as it may be for arbitrarily long strings. diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index e427c7f..4297c5f 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -42,10 +42,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __cache_default = __not___and_// Do not cache for fast hasher. __is_fast_hash_Hash, - // Mandatory to make local_iterator default - // constructible and assignable. - is_default_constructible_Hash, - is_copy_assignable_Hash, // Mandatory to have erase not throwing. __detail::__is_noexcept_hash_Tp, _Hash; @@ -282,22 +278,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION Functor used to map hash code to bucket index must be default constructible); - // When hash codes are not cached local iterator inherits from - // __hash_code_base above to compute node bucket index so it has to be - // default constructible. - static_assert(__if_hash_not_cached -
Re: [patch] fix libstdc++/56267 - local iterator requirements
On 17 January 2014 15:11, Jonathan Wakely wrote: The issue in PR 56267 is that unordered_xxx::local_iterator sometimes inherits from the user-defined hash function (via _Hash_code_base, which inherits from the hash function to use the EBO), and local_iterator must be DefaultConstructible and Assignable, even when the hash function isn't. My solution is to remove the inheritance from _Hash_code_base, and instead construct/destroy the _Hash_code_base in a block of uninitialized memory (via __gnu_cxx::__aligned_buffer). This would mean we can't use the EBO and increase the size of local_iterator, and past measurements have shown that the unordered containers' performance is sensitive to such changes, so there's a partial specialization that doesn't have the __aligned_buffer member for the case where the _Hash_code_base is empty and needs no storage. François, do you have any comments on this? Can you see a better solution? While working on this I decided I didn't like everything in _Local_iterator_base being public, so I added some accessors to the only members that are needed by unrelated types. Tested x86_64-linux and committed to trunk. 2014-01-20 Jonathan Wakely jwak...@redhat.com PR libstdc++/56267 * include/bits/hashtable_policy.h (_Hash_code_base... false): Grant friendship to _Local_iterator_base..., false. (_Local_iterator_base): Give protected access to all existing members. (_Local_iterator_base::_M_curr()): New public accessor. (_Local_iterator_base::_M_get_bucket()): New public accessor. (_Local_iterator_base..., false::_M_init()): New function to manage the lifetime of the _Hash_code_base explicitly. (_Local_iterator_base..., false::_M_destroy()): Likewise. (_Local_iterator_base..., false): Define copy constructor and copy assignment operator that use new functions to manage _Hash_code_base. (operator==(const _Local_iterator_base, const _Local_iterator_base), operator==(const _Local_iterator_base, const _Local_iterator_base)): Use public API for _Local_iterator_base. * include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise. * include/debug/unordered_map (__debug::unordered_map::erase(), __debug::unordered_multimap::erase()): Likewise. * include/debug/unordered_set (__debug::unordered_set::erase(), __debug::unordered_multiset::erase()): Likewise. * testsuite/23_containers/unordered_set/56267-2.cc: New test.
Re: [patch] fix libstdc++/56267 - local iterator requirements
On 01/20/2014 04:53 PM, Jonathan Wakely wrote: On 17 January 2014 15:11, Jonathan Wakely wrote: The issue in PR 56267 is that unordered_xxx::local_iterator sometimes inherits from the user-defined hash function (via _Hash_code_base, which inherits from the hash function to use the EBO), and local_iterator must be DefaultConstructible and Assignable, even when the hash function isn't. My solution is to remove the inheritance from _Hash_code_base, and instead construct/destroy the _Hash_code_base in a block of uninitialized memory (via __gnu_cxx::__aligned_buffer). This would mean we can't use the EBO and increase the size of local_iterator, and past measurements have shown that the unordered containers' performance is sensitive to such changes, so there's a partial specialization that doesn't have the __aligned_buffer member for the case where the _Hash_code_base is empty and needs no storage. François, do you have any comments on this? Can you see a better solution? While working on this I decided I didn't like everything in _Local_iterator_base being public, so I added some accessors to the only members that are needed by unrelated types. Tested x86_64-linux and committed to trunk. 2014-01-20 Jonathan Wakely jwak...@redhat.com PR libstdc++/56267 * include/bits/hashtable_policy.h (_Hash_code_base... false): Grant friendship to _Local_iterator_base..., false. (_Local_iterator_base): Give protected access to all existing members. (_Local_iterator_base::_M_curr()): New public accessor. (_Local_iterator_base::_M_get_bucket()): New public accessor. (_Local_iterator_base..., false::_M_init()): New function to manage the lifetime of the _Hash_code_base explicitly. (_Local_iterator_base..., false::_M_destroy()): Likewise. (_Local_iterator_base..., false): Define copy constructor and copy assignment operator that use new functions to manage _Hash_code_base. (operator==(const _Local_iterator_base, const _Local_iterator_base), operator==(const _Local_iterator_base, const _Local_iterator_base)): Use public API for _Local_iterator_base. * include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise. * include/debug/unordered_map (__debug::unordered_map::erase(), __debug::unordered_multimap::erase()): Likewise. * include/debug/unordered_set (__debug::unordered_set::erase(), __debug::unordered_multiset::erase()): Likewise. * testsuite/23_containers/unordered_set/56267-2.cc: New test. I considered that it was an acceptable constraint on the hash functor but if it is not Standard compliant then the solution is good and I cannot think about another one. With this new design couldn't we change the conditions that are used to decide when to cache the hash code. I haven't study it in detail but it looks like the default constructible constraint could be removed, no ? François
[patch] fix libstdc++/56267 - local iterator requirements
The issue in PR 56267 is that unordered_xxx::local_iterator sometimes
inherits from the user-defined hash function (via _Hash_code_base,
which inherits from the hash function to use the EBO), and
local_iterator must be DefaultConstructible and Assignable, even when
the hash function isn't.
My solution is to remove the inheritance from _Hash_code_base, and
instead construct/destroy the _Hash_code_base in a block of
uninitialized memory (via __gnu_cxx::__aligned_buffer). This would
mean we can't use the EBO and increase the size of local_iterator, and
past measurements have shown that the unordered containers'
performance is sensitive to such changes, so there's a partial
specialization that doesn't have the __aligned_buffer member for the
case where the _Hash_code_base is empty and needs no storage.
François, do you have any comments on this? Can you see a better solution?
While working on this I decided I didn't like everything in
_Local_iterator_base being public, so I added some accessors to the
only members that are needed by unrelated types.
2014-01-17 Jonathan Wakely jwak...@redhat.com
PR libstdc++/56267
* include/bits/hashtable_policy.h (_Local_iterator_base): Give
protected access to all existing members.
(_Local_iterator_base::_M_curr()): New public accessor.
(_Local_iterator_base::_M_get_bucket()): New public accessor.
(_Local_iterator_base..., false::_M_init()): New function to manage
the lifetime of the _Hash_code_base explicitly.
(_Local_iterator_base..., false::_M_destroy()): Likewise.
(_Local_iterator_base..., false): Define copy constructor and copy
assignment operator that use new functions to manage _Hash_code_base.
(operator==(const _Local_iterator_base, const _Local_iterator_base),
operator==(const _Local_iterator_base, const _Local_iterator_base)):
Use public API for _Local_iterator_base.
* include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
* include/debug/unordered_map (__debug::unordered_map::erase(),
__debug::unordered_multimap::erase()): Likewise.
* include/debug/unordered_set (__debug::unordered_set::erase(),
__debug::unordered_multiset::erase()): Likewise.
* testsuite/23_containers/unordered_set/56267-2.cc: New test.
commit f9c852223230da4e4fc761f72905c7acacfa4399
Author: Jonathan Wakely jwak...@redhat.com
Date: Fri Jan 17 15:10:48 2014 +
PR libstdc++/56267
* include/bits/hashtable_policy.h (_Local_iterator_base): Give
protected access to all existing members.
(_Local_iterator_base::_M_curr()): New public accessor.
(_Local_iterator_base::_M_get_bucket()): New public accessor.
(operator==(const _Local_iterator_base, const _Local_iterator_base),
operator==(const _Local_iterator_base, const _Local_iterator_base)):
Use public API for _Local_iterator_base.
* include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
* include/debug/unordered_map (__debug::unordered_map::erase(),
__debug::unordered_multimap::erase()): Likewise.
* include/debug/unordered_set (__debug::unordered_set::erase(),
__debug::unordered_multiset::erase()): Likewise.
* testsuite/23_containers/unordered_set/56267-2.cc: New test.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index f64d2d3..817b190 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1145,6 +1145,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __ebo_h1 = _Hashtable_ebo_helper1, _H1;
using __ebo_h2 = _Hashtable_ebo_helper2, _H2;
+ // Gives the local iterator implementation access to _M_bucket_index().
+ friend struct _Local_iterator_base_Key, _Value, _ExtractKey, _H1, _H2,
+_Default_ranged_hash, false;
+
public:
typedef _H1 hasher;
@@ -1225,7 +1229,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
private _Hashtable_ebo_helper2, _H2
{
private:
- // Gives access to _M_h2() to the local iterator implementation.
+ // Gives the local iterator implementation access to _M_h2().
friend struct _Local_iterator_base_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, true;
@@ -1331,7 +1335,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
- /// Specialization.
+ /// Partial specialization used when nodes contain a cached hash code.
templatetypename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash
struct _Local_iterator_base_Key, _Value, _ExtractKey,
@@ -1343,7 +1347,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using __hash_code_base = _Hash_code_base_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true;
-public:
