From patchwork Fri Nov 8 15:30:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 2008611 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=WfFKAdTM; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XlNlS3Lsqz1xxq for ; Sat, 9 Nov 2024 02:53:40 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B46983858CDA for ; Fri, 8 Nov 2024 15:53:38 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id 71433385841C for ; Fri, 8 Nov 2024 15:46:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 71433385841C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 71433385841C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731080809; cv=none; b=S129klg2cqBJ6jB/H7lQiUJapmEBSz8GTT+0qLMmK+wix8yE+nXQ2C5tbha4ki8sGNA1ERO7h2bsNLqNE4luc+xxJjUiFulRHYHug7TeSGHAhKIXUgyJ59RswiI/7++Qe2EWKjipNsDJx095ScCAKbj4zuwJSGy7Ch1MjdeN1yw= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731080809; c=relaxed/simple; bh=k+yOc8NogLlBg2jR468xLSz4iV7X/+O/TPTE5vnThqA=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=nDCJ8xquzSSLCYo8kVBKZrFuRoN1liw3Jyd35OA867RxUuOyQl7EvC1Q3zcBWgAiBLZr6m17SMGRGT/m61Kh2VmlvkmhofrX/oNpLbM4/EvQxBn6N3Rm5MPj53zzq0U+CJAdr8RXIUgtjlzg/FCSkecxp3kTwDSj1Die9geYYDg= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1731080790; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=YL1Tn4CoSHvL60kgFjkeBqya7tQ5rpFWJcPQ8mEt+tY=; b=WfFKAdTMjSDOz/7BTCRcW5SxXs6L+tOHdBNUT47pAc+VPC7+j7R91p5CrADScb/QzeoJUw QbLr2/moF1g98NxoDe8TmPY56GpV5d2n4QXgDZZdm00Jn7Ra3MuwXaidTjlUfEUzc93RAn rdTf+UWkx4DT+TRsWFPf/s8nxKE+18U= Received: from mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-505-yZWgmU92PlCePwHE8znKxw-1; Fri, 08 Nov 2024 10:46:27 -0500 X-MC-Unique: yZWgmU92PlCePwHE8znKxw-1 X-Mimecast-MFC-AGG-ID: yZWgmU92PlCePwHE8znKxw Received: from mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.12]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 06E061954B1C; Fri, 8 Nov 2024 15:46:26 +0000 (UTC) Received: from localhost (unknown [10.22.64.104]) by mx-prod-int-03.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 8C804195E480; Fri, 8 Nov 2024 15:46:25 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH 12/12] libstdc++: Add _Hashtable::_M_locate(const key_type&) Date: Fri, 8 Nov 2024 15:30:22 +0000 Message-ID: <20241108154548.813315-13-jwakely@redhat.com> In-Reply-To: <20241108154548.813315-1-jwakely@redhat.com> References: <20241108154548.813315-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.0 on 10.30.177.12 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: SLWIBGN9bZWyJkeb1_3hUwLhBLegUanUOhA7yLmql04_1731080786 X-Mimecast-Originator: redhat.com X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org We have two overloads of _M_find_before_node but they have quite different performance characteristics, which isn't necessarily obvious. The original version, _M_find_before_node(bucket, key, hash_code), looks only in the specified bucket, doing a linear search within that bucket for an element that compares equal to the key. This is the typical fast lookup for hash containers, assuming the load factor is low so that each bucket isn't too large. The newer _M_find_before_node(key) was added in r12-6272-ge3ef832a9e8d6a and could be naively assumed to calculate the hash code and bucket for key and then call the efficient _M_find_before_node(bkt, key, code) function. But in fact it does a linear search of the entire container. This is potentially very slow and should only be used for a suitably small container, as determined by the __small_size_threshold() function. We don't even have a comment pointing out this O(N) performance of the newer overload. Additionally, the newer overload is only ever used in exactly one place, which would suggest it could just be removed. However there are several places that do the linear search of the whole container with an explicit loop each time. This adds a new member function, _M_locate, and uses it to replace most uses of _M_find_node and the loops doing linear searches. This new member function does both forms of lookup, the linear search for small sizes and the _M_find_node(bkt, key, code) lookup within a single bucket. The new function returns a __location_type which is a struct that contains a pointer to the first node matching the key (if such a node is present), or the hash code and bucket index for the key. The hash code and bucket index allow the caller to know where a new node with that key should be inserted, for the cases where the lookup didn't find a matching node. The result struct actually contains a pointer to the node *before* the one that was located, as that is needed for it to be useful in erase and extract members. There is a member function that returns the found node, i.e. _M_before->_M_nxt downcast to __node_ptr, which should be used in most cases. This new function greatly simplifies the functions that currently have to do two kinds of lookup and explicitly check the current size against the small size threshold. Additionally, now that try_emplace is defined directly in _Hashtable (not in _Insert_base) we can use _M_locate in there too, to speed up some try_emplace calls. Previously it did not do the small-size linear search. It would be possible to add a function to get a __location_type from an iterator, and then rewrite some functions like _M_erase and _M_extract_node to take a __location_type parameter. While that might be conceptually nice, it wouldn't really make the code any simpler or more readable than it is now. That isn't done in this change. libstdc++-v3/ChangeLog: * include/bits/hashtable.h (__location_type): New struct. (_M_locate): New member function. (_M_find_before_node(const key_type&)): Remove. (_M_find_node): Move variable initialization into condition. (_M_find_node_tr): Likewise. (operator=(initializer_list), try_emplace, _M_reinsert_node) (_M_merge_unique, find, erase(const key_type&)): Use _M_locate for lookup. --- libstdc++-v3/include/bits/hashtable.h | 333 +++++++++++--------------- 1 file changed, 145 insertions(+), 188 deletions(-) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index aca431ae216..6a2da121ab9 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -596,28 +596,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (_M_bucket_count < __l_bkt_count) rehash(__l_bkt_count); - _ExtractKey __ex; + __hash_code __code; + size_type __bkt; for (auto& __e : __l) { - const key_type& __k = __ex(__e); + const key_type& __k = _ExtractKey{}(__e); if constexpr (__unique_keys::value) - if (this->size() <= __small_size_threshold()) - { - auto __it = _M_begin(); - for (; __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - break; - if (__it) - continue; // Found existing element with equivalent key - } - - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__code); - - if constexpr (__unique_keys::value) - if (_M_find_node(__bkt, __k, __code)) - continue; // Found existing element with equivalent key + { + if (auto __loc = _M_locate(__k)) + continue; // Found existing element with equivalent key + else + { + __code = __loc._M_hash_code; + __bkt = __loc._M_bucket_index; + } + } + else + { + __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + } _M_insert_unique_node(__bkt, __code, __roan(__e)); } @@ -809,10 +808,8 @@ _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 _M_find_before_node(size_type, const key_type&, __hash_code) const; @@ -821,12 +818,57 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_find_before_node_tr(size_type, const _Kt&, __hash_code) const; + // A pointer to a particular node and/or a hash code and bucket index + // where such a node would be found in the container. + struct __location_type + { + // True if _M_node() is a valid node pointer. + explicit operator bool() const noexcept + { return static_cast(_M_before); } + + // An iterator that refers to the node, or end(). + explicit operator iterator() const noexcept + { return iterator(_M_node()); } + + // A const_iterator that refers to the node, or cend(). + explicit operator const_iterator() const noexcept + { return const_iterator(_M_node()); } + + // A pointer to the node, or null. + __node_ptr _M_node() const + { + if (_M_before) + return static_cast<__node_ptr>(_M_before->_M_nxt); + return __node_ptr(); + } + + __node_base_ptr _M_before{}; // Must only be used to get _M_nxt + __hash_code _M_hash_code{}; // Only valid if _M_bucket_index != -1 + size_type _M_bucket_index = size_type(-1); + }; + + // Adaptive lookup to find key, or which bucket it would be in. + // For a container smaller than the small size threshold use a linear + // search through the whole container, just testing for equality. + // Otherwise, calculate the hash code and bucket index for the key, + // and search in that bucket. + // The return value will have a pointer to the node _before_ the first + // node matching the key, if any such node exists. Returning the node + // before the desired one allows the result to be used for erasure. + // If no matching element is present, the hash code and bucket for the + // key will be set, allowing a new node to be inserted at that location. + // (The hash code and bucket might also be set when a node is found.) + // The _M_before pointer might point to _M_before_begin, so must not be + // cast to __node_ptr, and it must not be used to modify *_M_before + // except in non-const member functions, such as erase. + __location_type + _M_locate(const key_type& __k) const; + __node_ptr _M_find_node(size_type __bkt, const key_type& __key, __hash_code __c) const { - __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c); - if (__before_n) + if (__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c)) return static_cast<__node_ptr>(__before_n->_M_nxt); return nullptr; } @@ -836,8 +878,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_find_node_tr(size_type __bkt, const _Kt& __key, __hash_code __c) const { - auto __before_n = _M_find_before_node_tr(__bkt, __key, __c); - if (__before_n) + if (auto __before_n = _M_find_before_node_tr(__bkt, __key, __c)) return static_cast<__node_ptr>(__before_n->_M_nxt); return nullptr; } @@ -1004,10 +1045,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair try_emplace(const_iterator, _KType&& __k, _Args&&... __args) { - auto __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__code); - if (auto __node = _M_find_node(__bkt, __k, __code)) - return { iterator(__node), false }; + __hash_code __code; + size_type __bkt; + if (auto __loc = _M_locate(__k)) + return { iterator(__loc), false }; + else + { + __code = __loc._M_hash_code; + __bkt = __loc._M_bucket_index; + } _Scoped_node __node { this, @@ -1101,38 +1147,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); - __node_ptr __n = nullptr; - const key_type& __k = __nh._M_key(); - const size_type __size = size(); - if (__size <= __small_size_threshold()) - { - for (__n = _M_begin(); __n; __n = __n->_M_next()) - if (this->_M_key_equals(__k, *__n)) - break; - } - - __hash_code __code; - size_type __bkt; - if (!__n) - { - __code = this->_M_hash_code(__k); - __bkt = _M_bucket_index(__code); - if (__size > __small_size_threshold()) - __n = _M_find_node(__bkt, __k, __code); - } - - if (__n) + if (auto __loc = _M_locate(__nh._M_key())) { __ret.node = std::move(__nh); - __ret.position = iterator(__n); + __ret.position = iterator(__loc); __ret.inserted = false; } else { + auto __code = __loc._M_hash_code; + auto __bkt = __loc._M_bucket_index; __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); - __nh.release(); + = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); __ret.inserted = true; + __nh.release(); } } return __ret; @@ -1218,7 +1246,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __src.get_allocator()); - auto __size = size(); auto __n_elt = __src.size(); size_type __first = 1; // For a container of identical type we can use its private members. @@ -1229,31 +1256,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __p = __p->_M_next(); const auto& __node = *__p; const key_type& __k = _ExtractKey{}(__node._M_v()); - if (__size <= __small_size_threshold()) - { - auto __n = _M_begin(); - for (; __n; __n = __n->_M_next()) - if (this->_M_key_equals(__k, *__n)) - break; - if (__n) - continue; - } + auto __loc = _M_locate(__k); + if (__loc) + continue; - __hash_code __code - = _M_src_hash_code(__src.hash_function(), __k, __node); - size_type __bkt = _M_bucket_index(__code); - if (__size > __small_size_threshold()) - if (_M_find_node(__bkt, __k, __code) != nullptr) - continue; - - __hash_code __src_code = __src.hash_function()(__k); - size_type __src_bkt = __src._M_bucket_index(__src_code); + size_type __src_bkt + = __src._M_bucket_index(__src.hash_function()(__k)); auto __nh = __src._M_extract_node(__src_bkt, __prev); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, - __first * __n_elt + 1); + _M_insert_unique_node(__loc._M_bucket_index, __loc._M_hash_code, + __nh._M_ptr, __first * __n_elt + 1); __nh.release(); __first = 0; - ++__size; __p = __prev; } } @@ -1267,7 +1280,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); - auto __size = size(); auto __n_elt = __src.size(); size_type __first = 1; // For a compatible container we can only use the public API, @@ -1277,29 +1289,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION --__n_elt; auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); - if (__size <= __small_size_threshold()) - { - auto __n = _M_begin(); - for (; __n; __n = __n->_M_next()) - if (this->_M_key_equals(__k, *__n)) - break; - if (__n) - continue; - } - - __hash_code __code - = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); - size_type __bkt = _M_bucket_index(__code); - if (__size > __small_size_threshold()) - if (_M_find_node(__bkt, __k, __code) != nullptr) - continue; + const auto __loc = _M_locate(__k); + if (__loc) + continue; auto __nh = __src.extract(__pos); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, + _M_insert_unique_node(__loc._M_bucket_index, + __loc._M_hash_code, __nh._M_ptr, __first * __n_elt + 1); __nh.release(); __first = 0; - ++__size; } } @@ -1864,19 +1863,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: find(const key_type& __k) -> iterator - { - if (size() <= __small_size_threshold()) - { - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return iterator(__it); - return end(); - } - - __hash_code __code = this->_M_hash_code(__k); - std::size_t __bkt = _M_bucket_index(__code); - return iterator(_M_find_node(__bkt, __k, __code)); - } + { return iterator(_M_locate(__k)); } template:: find(const key_type& __k) const -> const_iterator - { - if (size() <= __small_size_threshold()) - { - for (auto __it = _M_begin(); __it; __it = __it->_M_next()) - if (this->_M_key_equals(__k, *__it)) - return const_iterator(__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)); - } + { return const_iterator(_M_locate(__k)); } #if __cplusplus > 201703L template - 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; - if (!__prev_p->_M_nxt) - return nullptr; - - for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt); - __p != nullptr; - __p = __p->_M_next()) - { - if (this->_M_key_equals(__k, *__p)) - return __prev_p; - - __prev_p = __p; - } - - return nullptr; - } - // Find the node before the one whose key compares equal to k in the bucket // bkt. Return nullptr if no node is found. template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_locate(const key_type& __k) const + -> __location_type + { + __location_type __loc; + const auto __size = size(); + + if (__size <= __small_size_threshold()) + { + __loc._M_before = pointer_traits<__node_base_ptr>:: + pointer_to(const_cast<__node_base&>(_M_before_begin)); + while (__loc._M_before->_M_nxt) + { + if (this->_M_key_equals(__k, *__loc._M_node())) + return __loc; + __loc._M_before = __loc._M_before->_M_nxt; + } + __loc._M_before = nullptr; // Didn't find it. + } + + __loc._M_hash_code = this->_M_hash_code(__k); + __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code); + + if (__size > __small_size_threshold()) + __loc._M_before = _M_find_before_node(__loc._M_bucket_index, __k, + __loc._M_hash_code); + + return __loc; + } + template_M_next()) - if (this->_M_key_equals(*__kp, *__it)) - // There is already an equivalent node, no insertion. - return { iterator(__it), false }; + __code = __loc._M_hash_code; + __bkt = __loc._M_bucket_index; } - __code = this->_M_hash_code(*__kp); - __bkt = _M_bucket_index(__code); - - if (__size > __small_size_threshold()) - if (__node_ptr __p = _M_find_node(__bkt, *__kp, __code)) - // There is already an equivalent node, no insertion. - return { iterator(__p), false }; - if (!__node._M_node) __node._M_node = this->_M_allocate_node(std::forward<_Args>(__args)...); @@ -2570,32 +2544,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION erase(const key_type& __k) -> size_type { - __node_base_ptr __prev_n; - __node_ptr __n; - std::size_t __bkt; - if (size() <= __small_size_threshold()) - { - __prev_n = _M_find_before_node(__k); - if (!__prev_n) - return 0; + auto __loc = _M_locate(__k); + if (!__loc) + return 0; - // We found a matching node, erase it. - __n = static_cast<__node_ptr>(__prev_n->_M_nxt); - __bkt = _M_bucket_index(*__n); - } - else - { - __hash_code __code = this->_M_hash_code(__k); - __bkt = _M_bucket_index(__code); - - // Look for the node before the first matching node. - __prev_n = _M_find_before_node(__bkt, __k, __code); - if (!__prev_n) - return 0; - - // We found a matching node, erase it. - __n = static_cast<__node_ptr>(__prev_n->_M_nxt); - } + __node_base_ptr __prev_n = __loc._M_before; + __node_ptr __n = __loc._M_node(); + auto __bkt = __loc._M_bucket_index; + if (__bkt == size_type(-1)) + __bkt = _M_bucket_index(*__n); if constexpr (__unique_keys::value) {