On Sat, 25 Dec 2021 at 21:39, François Dumont <frs.dum...@gmail.com> wrote:
> On 23/12/21 2:03 pm, Jonathan Wakely wrote:
> > On 21/12/21 07:07 +0100, François Dumont wrote:
> >> Hi
> >>
> >> ??? Is there a chance for this patch to be integrated for next gcc
> >> release ?
> >
> > Yes, I think this can still make it for GCC 12 (the patch was first
> > posted long ago in stage 1 and it's just me being slow to review it).
> >
> > But I have some questions and comments ...
> >
> >
> >> diff --git a/libstdc++-v3/include/bits/hashtable.h
> >> b/libstdc++-v3/include/bits/hashtable.h
> >> index 6e2d4c10cfe..6b2c6b99fef 100644
> >> --- a/libstdc++-v3/include/bits/hashtable.h
> >> +++ b/libstdc++-v3/include/bits/hashtable.h
> >> @@ -419,6 +419,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> _M_uses_single_bucket() const
> >> { return _M_uses_single_bucket(_M_buckets); }
> >>
> >> + static constexpr size_t
> >> + __small_size_threshold()
> >> + {
> >> + return
> >> + __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
> >> + }
> >> +
> I've added the noexcept qualification as you asked.
> >> __hashtable_alloc&
> >> _M_base_alloc() { return *this; }
> >>
> >> @@ -788,6 +795,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> _M_bucket_index(__hash_code __c) const
> >> { return __hash_code_base::_M_bucket_index(__c,
> >> _M_bucket_count); }
> >>
> >> + __node_base_ptr
> >> + _M_find_before_node(const key_type&);
> >> +
> >> // Find and insert helper functions and types
> >> // Find the node before the one matching the criteria.
> >> __node_base_ptr
> >> @@ -831,6 +841,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> __node_base_ptr
> >> _M_get_previous_node(size_type __bkt, __node_ptr __n);
> >>
> >> + pair<const_iterator, __hash_code>
> >> + _M_compute_hash_code(const_iterator __hint, const key_type&
> >> __k) const;
> >> +
> >> // Insert node __n with hash code __code, in bucket __bkt if no
> >> // rehash (assumes no element with same key already present).
> >> // Takes ownership of __n if insertion succeeds, throws otherwise.
> >> @@ -1126,7 +1139,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> void _M_rehash(size_type __bkt_count, const __rehash_state&
> >> __state);
> >> };
> >>
> >> -
> >> // Definitions of class template _Hashtable's out-of-line member
> >> functions.
> >> template<typename _Key, typename _Value, typename _Alloc,
> >> typename _ExtractKey, typename _Equal,
> >> @@ -1628,6 +1640,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> find(const key_type& __k)
> >> -> iterator
> >> {
> >> + if (size() <= __small_size_threshold())
> >> + {
> >> + for (auto __it = begin(); __it != end(); ++__it)
> >> + if (this->_M_key_equals(__k, *__it._M_cur))
> >> + return __it;
> >> + return end();
> >> + }
> >
> > This loop is repeated a few times, would it be better factored out
> > into its own function? _M_find_loop or something? The return type is
> > different in some cases, so maybe it's OK like this.
> Yes, I also thought about that but there is often small changes from one
> loop to another as you noticed.
> >
> >
> >
> >> +
> >> __hash_code __code = this->_M_hash_code(__k);
> >> std::size_t __bkt = _M_bucket_index(__code);
> >> return iterator(_M_find_node(__bkt, __k, __code));
> >> @@ -1643,6 +1663,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> find(const key_type& __k) const
> >> -> const_iterator
> >> {
> >> + if (size() <= __small_size_threshold())
> >> + {
> >> + for (auto __it = begin(); __it != end(); ++__it)
> >> + if (this->_M_key_equals(__k, *__it._M_cur))
> >> + return __it;
> >> + return end();
> >> + }
> >> +
> >> __hash_code __code = this->_M_hash_code(__k);
> >> std::size_t __bkt = _M_bucket_index(__code);
> >> return const_iterator(_M_find_node(__bkt, __k, __code));
> >> @@ -1855,6 +1883,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> }
> >> #endif
> >>
> >> + // Find the node before the one whose key compares equal to k.
> >> + // Return nullptr if no node is found.
> >> + template<typename _Key, typename _Value, typename _Alloc,
> >> + typename _ExtractKey, typename _Equal,
> >> + typename _Hash, typename _RangeHash, typename _Unused,
> >> + typename _RehashPolicy, typename _Traits>
> >> + auto
> >> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
> >> + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
> >> + _M_find_before_node(const key_type& __k)
> >> + -> __node_base_ptr
> >> + {
> >> + __node_base_ptr __prev_p = &_M_before_begin;
> >
> > This is OK now, but would need to be std::__addressof(_M_before_begin)
> > if/when the _Hash_code_base type becomes dependent on the allocator's
> > pointer.
> Yes, maybe after gcc release we will talk about those fancy pointer
> types again.
> >
> > __n_last = __n_last->_M_next();
> >> diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
> >> b/libstdc++-v3/include/bits/hashtable_policy.h
> >> index 0b5443fc187..b4a8af081ce 100644
> >> --- a/libstdc++-v3/include/bits/hashtable_policy.h
> >> +++ b/libstdc++-v3/include/bits/hashtable_policy.h
> >> @@ -246,6 +246,20 @@ namespace __detail
> >> using __unique_keys = __bool_constant<_Unique_keys>;
> >> };
> >>
> >> + /**
> >> + * struct _Hashtable_hash_traits
> >> + *
> >> + * Important traits for hash tables depending on associated hasher.
> >> + *
> >> + */
> >> + template<typename _Hash>
> >> + struct _Hashtable_hash_traits
> >> + {
> >> + static constexpr std::size_t
> >> + __small_size_threshold()
> >> + { return std::__is_fast_hash<_Hash>::value ? 0 : 20; }
> >> + };
> >
> > Yet another trait that nobody is ever going to specialize make me sad.
> > I don't have a better idea though.
>
> Sure, but maybe I can document it ?
>
> I also wonder why you did not propose to make it a constant rather than
> requesting to add the noexcept.
>
> >
> > {
> >> @@ -1263,6 +1279,14 @@ namespace __detail
> >> const _Hash_node_value<_Value, __cache_hash_code>& __n) const
> >> { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
> >>
> >> + __hash_code
> >> + _M_hash_code(const _Hash_node_value<_Value, false>& __n) const
> >> + { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
> >> +
> >> + __hash_code
> >> + _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
> >> + { return __n._M_hash_code; }
> >> +
> >> std::size_t
> >> _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
> >> { return _RangeHash{}(__c, __bkt_count); }
> >> @@ -1273,17 +1297,14 @@ namespace __detail
> >> noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
> >> && noexcept(declval<const _RangeHash&>()((__hash_code)0,
> >> (std::size_t)0)) )
> >> - {
> >> - return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
> >> - __bkt_count);
> >> - }
> >> + { return _M_bucket_index(_M_hash_code(__n), __bkt_count); }
> >
> > Why add this extra level of indirection (and overload resolution)?
> >
> > We know this is a _Hash_node_value<V, false>, why call _M_hash_code to
> > decide how to get the hash code for it?
>
> Just to avoid code duplication but indeed it introduces overload
> resolution so I reverted it.
>
> >
> >
> >> diff --git a/libstdc++-v3/testsuite/util/testsuite_performance.h
> >> b/libstdc++-v3/testsuite/util/testsuite_performance.h
> >> index cba3a0d4b17..4ca15ab0e71 100644
> >> --- a/libstdc++-v3/testsuite/util/testsuite_performance.h
> >> +++ b/libstdc++-v3/testsuite/util/testsuite_performance.h
> >> @@ -239,7 +239,7 @@ namespace __gnu_test
> >> out << std::setw(4) << t.real_time() << "r" << space;
> >> out << std::setw(4) << t.user_time() << "u" << space;
> >> out << std::setw(4) << t.system_time() << "s" << space;
> >> - out << std::setw(8) << r.allocated_memory() << "mem" << space;
> >> + out << std::setw(9) << r.allocated_memory() << "mem" << space;
> >
> > One day I need to figure out why the reported memory is garbage so
> > often
>
>
> Ok with those changes ?
>
>
Yes, thanks very much (and bonne année).
