From patchwork Sun Nov 17 20:51:10 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1196448 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513850-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="u28592ZG"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="Kw1RYaUt"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47GPQ825cSz9sP4 for ; Mon, 18 Nov 2019 07:51:26 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=OH/i6GTv46/PpXPfeVaIISGRHSCILkdrem5UcSiWCyTJ/eP307 hS391zGLI7C5V29A+fwa2UO1fzq/GniEvRpC8ZEudDJQI8kaIFxashMxLYCNKTmH MUllPbNC0y04gDVaL33L8avkLwK9dlxhEKHKorkouwtEEdNmdFaITFyqc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=Gwem9r78AiMVqKUJrE/ZaGWKNac=; b=u28592ZGdcm6ugIy4dKG /GrLWLSkRvWcygMPFdHZRi2/XVt1i4yV24ufDKSeqlStSdAsXNFFTfJaQqh9CLgi 61QP4royh/W/ZwcXwFdpUURuDnFdyFastshINiE9gK1UvtnNLq4pu2IXozkKJx4G HPvYmXygGTUpaoS2kzhGsiw= Received: (qmail 37758 invoked by alias); 17 Nov 2019 20:51:18 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 37740 invoked by uid 89); 17 Nov 2019 20:51:17 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mail-wr1-f42.google.com Received: from mail-wr1-f42.google.com (HELO mail-wr1-f42.google.com) (209.85.221.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 17 Nov 2019 20:51:15 +0000 Received: by mail-wr1-f42.google.com with SMTP id i12so17093033wro.5; Sun, 17 Nov 2019 12:51:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=7wdwDPZ0aYVrBYpr//ANGRDRKX+Bj00picQEOTNeb58=; b=Kw1RYaUtuMj0NWW7R8zIUlLSscBnvbsFRJzSHNgmtwNKZw9iELVC6FdytNyPQg2HgX JxCeLXlcjOHE0lBBzvXwXF978El6AMb8gG4GDsPdDC7TgwryrdDxukVI9h4jJVMQWfW3 0LwP/JFtNIPWQADBlhCpatutq9HdYg/A6bjaC+ulezQlGgLwQtKS7Iu6lvIL7nL7jw5+ 4P97if7a2TNrExS/JUMxH6XEhXkqCCFXCoY4ziq+bRJIn8s8I345S2EVUwyJwx0MKQA2 CDSuQBwG6D0dOH6oBEjvToPbGWYNcvEX0VMo4scNEewIErHRgAjQrFvDMcb6raIHzKEE R+0A== Received: from ?IPv6:2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396? ([2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396]) by smtp.googlemail.com with ESMTPSA id 19sm23163837wrc.47.2019.11.17.12.51.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Nov 2019 12:51:11 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH][Hashtable 1/6] Code simplification/optimization Message-ID: Date: Sun, 17 Nov 2019 21:51:10 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 This patch simplifies a number of implementations. It tries as much as possible to avoid computing hash code. This is especially true for the erase implementation in case of multi keys.     * include/bits/hashtable_policy.h (_Map_base<>::at): Use     _Hashtable<>::find. (_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals):New.     (_Hashtable_base<>::_M_node_equals): New, use latter.     * include/bits/hashtable.h (_Hashtable<>::_M_update_bbegin): New.     (_Hashtable<>::_M_assign): Use latter.     (_Hashtable<>::_M_move_assign): Likewise.     (_Hashtable<>(_Hashtable<>&&)): Likewise.     (_Hashtable<>(_Hashtable<>&&, const allocator_type&)): Likewise.     (_Hashtable<>::swap): Likewise.     (_Hashtable<>::find): Build iterator directly from _M_find_node result.     (_Hashtable<>::count): Use _Hashtable<>::find.     (_Hashtable<>::equal_range): Likewise.     (_Hashtable<>::_M_erase(false_type, const key_type&)): Use     _M_node_equals. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index ef71c090f3b..b8cfdde2f31 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -378,6 +378,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // numerous checks in the code to avoid 0 modulus. __bucket_type _M_single_bucket = nullptr; + void + _M_update_bbegin() + { + if (_M_begin()) + _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + } + + void + _M_update_bbegin(__node_type* __n) + { + _M_before_begin._M_nxt = __n; + _M_update_bbegin(); + } + bool _M_uses_single_bucket(__bucket_type* __bkts) const { return __builtin_expect(__bkts == &_M_single_bucket, false); } @@ -674,7 +688,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair equal_range(const key_type& __k) const; - protected: + private: // Bucket index computation helpers. size_type _M_bucket_index(__node_type* __n) const noexcept @@ -1196,8 +1210,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = __node_gen(__fwd_value(std::forward<_Ht>(__ht), __ht_n->_M_v())); this->_M_copy_code(__this_n, __ht_n); - _M_before_begin._M_nxt = __this_n; - _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; + _M_update_bbegin(__this_n); // Then deal with other nodes. __node_base* __prev_n = __this_n; @@ -1259,15 +1272,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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; std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator()); - // Fix buckets containing the _M_before_begin pointers that can't be - // moved. - if (_M_begin()) - _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + // Fix bucket containing the _M_before_begin pointer that can't be moved. + _M_update_bbegin(); __ht._M_reset(); } @@ -1335,10 +1347,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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; + // Fix bucket containing the _M_before_begin pointer that can't be moved. + _M_update_bbegin(); __ht._M_reset(); } @@ -1389,11 +1399,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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 + // Fix bucket containing the _M_before_begin pointer that can't be // moved. - if (_M_begin()) - _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; + _M_update_bbegin(__ht._M_begin()); + __ht._M_reset(); } else @@ -1457,14 +1466,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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; + // Fix bucket containing the _M_before_begin pointer that can't be swap. + _M_update_bbegin(); + __x._M_update_bbegin(); } template_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__k, __code); - __node_type* __p = _M_find_node(__bkt, __k, __code); - return __p ? iterator(__p) : end(); + return iterator(_M_find_node(__bkt, __k, __code)); } template_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__k, __code); - __node_type* __p = _M_find_node(__bkt, __k, __code); - return __p ? const_iterator(__p) : end(); + return const_iterator(_M_find_node(__bkt, __k, __code)); } template size_type { - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); - __node_type* __p = _M_bucket_begin(__bkt); - if (!__p) + auto __it = find(__k); + if (!__it._M_cur) return 0; - std::size_t __result = 0; - for (;; __p = __p->_M_next()) - { - if (this->_M_equals(__k, __code, __p)) - ++__result; - 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 new equivalent value. - break; - if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) - break; - } + if (__unique_keys::value) + return 1; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + size_type __result = 1; + for (auto __ref = __it++; + __it._M_cur && this->_M_node_equals(__ref._M_cur, __it._M_cur); + ++__it) + ++__result; + return __result; } @@ -1541,21 +1540,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION equal_range(const key_type& __k) -> pair { - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); - __node_type* __p = _M_find_node(__bkt, __k, __code); + auto __ite = find(__k); + if (!__ite._M_cur) + return { __ite, __ite }; - if (__p) - { - __node_type* __p1 = __p->_M_next(); - while (__p1 && _M_bucket_index(__p1) == __bkt - && this->_M_equals(__k, __code, __p1)) - __p1 = __p1->_M_next(); + auto __beg = __ite++; + if (__unique_keys::value) + return { __beg, __ite }; - return std::make_pair(iterator(__p), iterator(__p1)); - } - else - return std::make_pair(end(), end()); + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur)) + ++__ite; + + return { __beg, __ite }; } template pair { - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__k, __code); - __node_type* __p = _M_find_node(__bkt, __k, __code); + auto __ite = find(__k); + if (!__ite._M_cur) + return { __ite, __ite }; - if (__p) - { - __node_type* __p1 = __p->_M_next(); - while (__p1 && _M_bucket_index(__p1) == __bkt - && this->_M_equals(__k, __code, __p1)) - __p1 = __p1->_M_next(); + auto __beg = __ite++; + if (__unique_keys::value) + return { __beg, __ite }; - return std::make_pair(const_iterator(__p), const_iterator(__p1)); - } - else - return std::make_pair(end(), end()); + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + while (__ite._M_cur && this->_M_node_equals(__beg._M_cur, __ite._M_cur)) + ++__ite; + + return { __beg, __ite }; } - // Find the node whose key compares equal to k in the bucket bkt. - // Return nullptr if no node is found. + // Find the node before the one whose key compares equal to k in the bucket + // bkt. Return nullptr if no node is found. template_M_nxt = _M_before_begin._M_nxt; _M_before_begin._M_nxt = __node; + if (__node->_M_nxt) // We must update former begin bucket that is pointing to // _M_before_begin. _M_buckets[_M_bucket_index(__node->_M_next())] = __node; + _M_buckets[__bkt] = &_M_before_begin; } } @@ -1968,16 +1970,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // them so that the key stays valid during the first loop. It might be // invalidated indirectly when destroying nodes. __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); - __node_type* __n_last = __n; - std::size_t __n_last_bkt = __bkt; - do - { - __n_last = __n_last->_M_next(); - if (!__n_last) - break; - __n_last_bkt = _M_bucket_index(__n_last); - } - while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); + __node_type* __n_last = __n->_M_next(); + while (__n_last && this->_M_node_equals(__n, __n_last)) + __n_last = __n_last->_M_next(); + + std::size_t __n_last_bkt = __n_last ? _M_bucket_index(__n_last) : __bkt; // Deallocate nodes. size_type __result = 0; @@ -1987,13 +1984,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION this->_M_deallocate_node(__n); __n = __p; ++__result; - --_M_element_count; } while (__n != __n_last); + _M_element_count -= __result; if (__prev_n == _M_buckets[__bkt]) _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); - else if (__n_last && __n_last_bkt != __bkt) + else if (__n_last_bkt != __bkt) _M_buckets[__n_last_bkt] = __prev_n; __prev_n->_M_nxt = __n_last; return __result; @@ -2139,6 +2136,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; __new_buckets[__bkt]->_M_nxt = __p; } + __p = __next; } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index b9320506bb2..f6c40be3b91 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -770,13 +770,11 @@ namespace __detail -> mapped_type& { __hashtable* __h = static_cast<__hashtable*>(this); - __hash_code __code = __h->_M_hash_code(__k); - std::size_t __bkt = __h->_M_bucket_index(__k, __code); - __node_type* __p = __h->_M_find_node(__bkt, __k, __code); + auto __ite = __h->find(__k); - if (!__p) + if (!__ite._M_cur) __throw_out_of_range(__N("_Map_base::at")); - return __p->_M_v().second; + return __ite->second; } template const mapped_type& { const __hashtable* __h = static_cast(this); - __hash_code __code = __h->_M_hash_code(__k); - std::size_t __bkt = __h->_M_bucket_index(__k, __code); - __node_type* __p = __h->_M_find_node(__bkt, __k, __code); + auto __ite = __h->find(__k); - if (!__p) + if (!__ite._M_cur) __throw_out_of_range(__N("_Map_base::at")); - return __p->_M_v().second; + return __ite->second; } /** @@ -1796,17 +1792,26 @@ namespace __detail template struct _Equal_hash_code { - static bool - _S_equals(__hash_code, const _NodeT&) - { return true; } + static bool + _S_equals(__hash_code, const _NodeT&) + { return true; } + + static bool + _S_node_equals(const _NodeT&, const _NodeT&) + { return true; } }; template struct _Equal_hash_code<_Hash_node<_Ptr2, __hash_cached_t>> { - static bool - _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n) - { return __c == __n._M_hash_code; } + static bool + _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n) + { return __c == __n._M_hash_code; } + + static bool + _S_node_equals(const _Hash_node<_Ptr2, __hash_cached_t>& __lhn, + const _Hash_node<_Ptr2, __hash_cached_t>& __rhn) + { return __lhn._M_hash_code == __rhn._M_hash_code; } }; protected: @@ -1817,7 +1822,7 @@ namespace __detail { } bool - _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const + _M_equals(const _Key& __k, __hash_code __c, const __node_type* __n) const { static_assert(__is_invocable{}, "key equality predicate must be invocable with two arguments of " @@ -1826,6 +1831,14 @@ namespace __detail && _M_eq()(__k, this->_M_extract()(__n->_M_v())); } + bool + _M_node_equals(const __node_type* __lhn, const __node_type* __rhn) const + { + return _Equal_hash_code<__node_type>::_S_node_equals(*__lhn, *__rhn) + && _M_eq()(this->_M_extract()(__lhn->_M_v()), + this->_M_extract()(__rhn->_M_v())); + } + void _M_swap(_Hashtable_base& __x) {