From patchwork Thu Nov 23 21:58:56 2023 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: 1867987 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=fQt4RGPw; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; 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 [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 4SbsV43btvz1yS0 for ; Fri, 24 Nov 2023 08:59:56 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0FF123838F08 for ; Thu, 23 Nov 2023 21:59:54 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) by sourceware.org (Postfix) with ESMTPS id 99F4A38582B1; Thu, 23 Nov 2023 21:58:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 99F4A38582B1 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 99F4A38582B1 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::42e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776741; cv=none; b=hnu6YyOJjGuhnBLmU3H6qXiLbTHYInmRDF1mjD6qQ3+5VW1rKL2f6jWMfrLRFkR28vIXtqz6o962EhiAp+hkgfua3zQxScouPs5CLBd4FHOtDv7ojgTuJg9X5lTb9cfO2m27Kt04sZlCPxag2xrQn/SnCr0AyA7Rm+Y9+17pIZE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776741; c=relaxed/simple; bh=VDONBI+jMCCYt+ZZ6rmIwvSmtNZl7KNloXe0JZG7NaU=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=svNJEkAK+sBT3ZNm9SlSCcHMnWKo3tzhNF6Q25AdBq1XzTID1JkuqbsRrXgI+srwigWrB3/0zOWAw1uOxuP8dVUgSs4ZtWm+AEBBRbg3iYeFvFgdYCJxZRWIOfZNdUXnYFjRp4UcRPFfs4FG7plQeY+wxPSttVh0p/1YUyXqYOs= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wr1-x42e.google.com with SMTP id ffacd0b85a97d-32deb2809daso840902f8f.3; Thu, 23 Nov 2023 13:58:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776737; x=1701381537; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=K6jR/1SwepJehWBq5T9g315UngWcYYg3UiaWcBEHsIs=; b=fQt4RGPwFXHGeA5EWxPCRnjDTaGKVjkCs9oLi0+meQBH0HT/v7EziauuUc4i0lBo2x JrpkdtUQP7SnONz6nwA5nISJJ1BMdPCRgiU1OflmSVrB6r/a5vJ8u/jxH5k+/7AGiFcK lf7+mLpkH/EJ4Hs+0wkXQI63DfSJ5TuubLf5nl88cXNKyJGhVQfCOywFdJqdyImZ4x6P dsbJMWbSU/okOp5GZxijsMaViJOSGCnds7lYVhwv42PnXHiXxW237NDCaafrALMc84Qa StE9MaY9i0GzVW2ssnmlq+/GiTCQKjIV+0ol2r94Gh2Qx+9Ja8iYcUf7tFzklqqYwD/l yn0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776737; x=1701381537; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=K6jR/1SwepJehWBq5T9g315UngWcYYg3UiaWcBEHsIs=; b=aM2SvRZi6IjlEGpbBy/zHPHrGc6dsvdYTHCL4e/++ajUsAuQyTN3VyiS2Y4sxQRWH0 66LPVmPX4me4KCy2K8A1HD1TVacSFrW7Fx/Cj7xeU09DbZNXG5Phvdsciq8RXqFIDAw8 LAJKd1dnklgBOvkJU5EVfWo0P7gEP2hf9Emuy6P3I6YtNuPND6gLpmD/sbjX7G7WBz4U O1Zmz8LWvBfbWXbvbTehVwXAFq7Hhtun4NB+5KccmX6UktI3LudrPHZFZvzIBIJ2nh0f vAdIhepOmAuSPhmXuCrc212Smu7GPNd3HGkdBlGeFyz4yN0ZBvq0hEe93q29SyD1JIsN 5qeA== X-Gm-Message-State: AOJu0YwPjHLCd1V+Of/C0TPy3T+y9VrnfdtEw4r1jOO9hnRaAI+8RK6P joyynSu1pScyIG4h6+EdKfCo7oJK41g= X-Google-Smtp-Source: AGHT+IENCuOYVReASfg0J1r/7hGjcfakAu1lu/0OtsIhRLz/p4xHVs7dIUjtsJYi44rlw7u971yGuw== X-Received: by 2002:adf:f48d:0:b0:332:e4cc:6a38 with SMTP id l13-20020adff48d000000b00332e4cc6a38mr496164wro.57.1700776737450; Thu, 23 Nov 2023 13:58:57 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.56 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:56 -0800 (PST) Message-ID: <6472c80c-7ea1-427c-9046-d46fd1121f34@gmail.com> Date: Thu, 23 Nov 2023 22:58:56 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 4/5][_Hashtable] Generalize the small size optimization To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org 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 libstdc++: [_Hashtable] Extend the small size optimization     A number of methods were still not using the small size optimization which     is to prefer an O(N) research to a hash computation as long as N is small.     libstdc++-v3/ChangeLog:             * include/bits/hashtable.h: Move comment about all equivalent values             being next to each other in the class documentation header.             (_M_reinsert_node, _M_merge_unique): Implement small size optimization.             (_M_find_tr, _M_count_tr, _M_equal_range_tr): Likewise. Tested under Linux x64 Ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 771ed9968f7..aec77c34a58 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -152,6 +152,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * _M_before_begin, if any, is updated to point to its new before * begin node. * + * Note that all equivalent values, if any, 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. + * * On erase, the simple iterator design requires using the hash * functor to get the index of the bucket to update. For this * reason, when __cache_hash_code is set to false the hash functor must @@ -1054,10 +1058,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { __glibcxx_assert(get_allocator() == __nh.get_allocator()); + __node_ptr __n = nullptr; const key_type& __k = __nh._M_key(); - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__code); - if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) + 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) { __ret.node = std::move(__nh); __ret.position = iterator(__n); @@ -1161,11 +1182,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; + const size_type __size = size(); const key_type& __k = _ExtractKey{}(*__pos); + if (__size <= __small_size_threshold()) + { + bool __found = false; + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals(__k, *__n)) + { + __found = true; + break; + } + + if (__found) + { + if (__n_elt != 1) + --__n_elt; + continue; + } + } + __hash_code __code = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur); size_type __bkt = _M_bucket_index(__code); - if (_M_find_node(__bkt, __k, __code) == nullptr) + if (__size <= __small_size_threshold() + || _M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); @@ -1743,6 +1784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_find_tr(const _Kt& __k) -> iterator { + if (size() <= __small_size_threshold()) + { + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return iterator(__n); + return end(); + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); return iterator(_M_find_node_tr(__bkt, __k, __code)); @@ -1759,6 +1808,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_find_tr(const _Kt& __k) const -> const_iterator { + if (size() <= __small_size_threshold()) + { + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + if (this->_M_key_equals_tr(__k, *__n)) + return const_iterator(__n); + return end(); + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); return const_iterator(_M_find_node_tr(__bkt, __k, __code)); @@ -1782,9 +1839,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION 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); @@ -1806,15 +1860,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_count_tr(const _Kt& __k) const -> size_type { + if (size() <= __small_size_threshold()) + { + size_type __result = 0; + for (auto __n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + ++__result; + continue; + } + + if (__result) + break; + } + + return __result; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); if (!__n) return 0; - // 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. iterator __it(__n); size_type __result = 1; for (++__it; @@ -1844,9 +1913,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__unique_keys::value) return { __beg, __ite }; - // 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; @@ -1871,9 +1937,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__unique_keys::value) return { __beg, __ite }; - // 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; @@ -1892,6 +1955,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_equal_range_tr(const _Kt& __k) -> pair { + if (size() <= __small_size_threshold()) + { + __node_ptr __n, __beg = nullptr; + for (__n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + if (!__beg) + __beg = __n; + continue; + } + + if (__beg) + break; + } + + return { iterator(__beg), iterator(__n) }; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); @@ -1899,9 +1981,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__n) return { __ite, __ite }; - // 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. auto __beg = __ite++; while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) ++__ite; @@ -1920,6 +1999,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_equal_range_tr(const _Kt& __k) const -> pair { + if (size() <= __small_size_threshold()) + { + __node_ptr __n, __beg = nullptr; + for (__n = _M_begin(); __n; __n = __n->_M_next()) + { + if (this->_M_key_equals_tr(__k, *__n)) + { + if (!__beg) + __beg = __n; + continue; + } + + if (__beg) + break; + } + + return { const_iterator(__beg), const_iterator(__n) }; + } + __hash_code __code = this->_M_hash_code_tr(__k); std::size_t __bkt = _M_bucket_index(__code); auto __n = _M_find_node_tr(__bkt, __k, __code); @@ -1927,9 +2025,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__n) return { __ite, __ite }; - // 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. auto __beg = __ite++; while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) ++__ite; @@ -2058,7 +2153,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First build the node to get access to the hash code _Scoped_node __node { this, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); - if (size() <= __small_size_threshold()) + const size_type __size = size(); + if (__size <= __small_size_threshold()) { for (auto __it = _M_begin(); __it; __it = __it->_M_next()) if (this->_M_key_equals(__k, *__it)) @@ -2068,7 +2164,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__code); - if (size() > __small_size_threshold()) + if (__size > __small_size_threshold()) if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) // There is already an equivalent node, no insertion return { iterator(__p), false }; @@ -2231,7 +2327,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _NodeGenerator& __node_gen) -> pair { - if (size() <= __small_size_threshold()) + const size_type __size = size(); + if (__size <= __small_size_threshold()) for (auto __it = _M_begin(); __it; __it = __it->_M_next()) if (this->_M_key_equals_tr(__k, *__it)) return { iterator(__it), false }; @@ -2239,7 +2336,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hash_code __code = this->_M_hash_code_tr(__k); size_type __bkt = _M_bucket_index(__code); - if (size() > __small_size_threshold()) + if (__size > __small_size_threshold()) if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code)) return { iterator(__node), false };