From patchwork Wed Aug 18 11:34:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Thomas Schwinge X-Patchwork-Id: 1517996 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=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GqQp619b4z9sRf for ; Wed, 18 Aug 2021 21:36:14 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 043213850434 for ; Wed, 18 Aug 2021 11:36:12 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from esa2.mentor.iphmx.com (esa2.mentor.iphmx.com [68.232.141.98]) by sourceware.org (Postfix) with ESMTPS id 9CC35388B823; Wed, 18 Aug 2021 11:34:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9CC35388B823 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=codesourcery.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=mentor.com IronPort-SDR: LKQnly8YPHvc9UEBZ/tKKC2Wz4WnshcgFLVSeMsaY4KLZKa6IImnJjaHK/Sg2agx6w05FOM0di qS2m9fN0qt6sLMqFumVdsFx8WoM2Cao+G8/VLh7PMfjfW7h3Q6lSPV7kb8m87sS/JpY7BFl2Qa 0XOHiIu+fsNMK6rGmwdAWLVkmV4hPvAIw969Rztcrep9IWnxJuhb99DdgWgACzfYZcmx5CUP7A Vy89CzJP70uV0tWWGHzdCIdrKIzw18AaXhxbgu5rX2IbN6Va03L93tS1VL2P3C++U4Jx6cvnFy HIs4q5Jxup/olTZrgoZTUp5f X-IronPort-AV: E=Sophos;i="5.84,330,1620720000"; d="scan'208,223";a="64837057" Received: from orw-gwy-02-in.mentorg.com ([192.94.38.167]) by esa2.mentor.iphmx.com with ESMTP; 18 Aug 2021 03:34:36 -0800 IronPort-SDR: BaJXZvbJmCOC4/hhcnvUfg0GZual//iWRCRJmcUV+mk8gU2JWmc7MOIb5ig5G06xRgd1H+qkWr u9vt1pdPHgY0CfVxRFWaL835NkyrMQ8qEZgurR9qPIZ9dQ5cnkYIz/NWQPhbzTgsDSkOujUg93 KaUqA6uOGSh4AztWUvCAC9MK+wvDtjLjLwRiHI4vdNKhSy0dwhkWrYt5SOlNmdRavAreFf1jXx UK3i+vJngjRMiAeOQBARajiXmVAVP2cDBOTwgh1bQ+fSa6ivOu/C6wuuMpF6giFZ4I6MjaaUN9 Bfk= From: Thomas Schwinge To: Richard Biener , Martin Sebor , Subject: Add more self-tests for 'hash_map' with Value type with non-trivial constructor/destructor (was: Expensive selftests) In-Reply-To: References: <87r1f6qzmx.fsf@euler.schwinge.homeip.net> <87czqd7e4k.fsf@euler.schwinge.homeip.net> <55126f14-dda1-2040-0976-70b89582a60c@gmail.com> <874kbopoah.fsf@euler.schwinge.homeip.net> User-Agent: Notmuch/0.29.3+94~g74c3f1b (https://notmuchmail.org) Emacs/27.1 (x86_64-pc-linux-gnu) Date: Wed, 18 Aug 2021 13:34:28 +0200 Message-ID: <87v943nfzv.fsf@euler.schwinge.homeip.net> MIME-Version: 1.0 X-Originating-IP: [137.202.0.90] X-ClientProxiedBy: SVR-IES-MBX-08.mgc.mentorg.com (139.181.222.8) To svr-ies-mbx-01.mgc.mentorg.com (139.181.222.1) X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, SPF_HELO_PASS, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: gcc@gcc.gnu.org, Jonathan Wakely Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi! On 2021-08-17T10:57:36+0200, Richard Biener wrote: > On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge wrote: >> On 2021-08-16T14:10:00-0600, Martin Sebor wrote: >> > On 8/16/21 6:44 AM, Thomas Schwinge wrote: >> >> [...], to document the current behavior, I propose to >> >> "Add more self-tests for 'hash_map' with Value type with non-trivial >> >> constructor/destructor", see attached. OK to push to master branch? >> >> (Also cherry-pick into release branches, eventually?) >> > Adding more tests sounds like an excellent idea. I'm not sure about >> > the idea of adding loopy selftests that iterate as many times as in >> > the patch (looks like 1234 times two?) >> >> Correct, and I agree it's a sensible concern, generally. >> >> The current 1234 times two iterations is really arbitrary (should >> document that in the test case), just so that we trigger a few hash table >> expansions. > > You could lower N_init (the default init is just 13!), > even with just 128 inserted elements you'll trigger > expansions to 31, 61 and 127 elements. > I think the test is OK but it's also reasonable to lower > the '1234' times and add a comment as to the count should > trigger hashtable expansions "a few times". Did that as follows: /* Verify basic construction and destruction of Value objects. */ { /* Configure, arbitrary. */ const size_t N_init = 0; const int N_elem = 28; ..., and: /* Verify aspects of 'hash_table::expand'. */ static void test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline) { /* Configure, so that hash table expansion triggers a few times. */ const size_t N_init = 0; const int N_elem = 70; size_t expand_c_expected = 4; [...] if (expand) { ++expand_c; [...] ASSERT_EQ (expand_c, expand_c_expected); Given that it's all deterministic (as far as I can tell...), we may verify an exact number of hash table expansions. Pushed "Add more self-tests for 'hash_map' with Value type with non-trivial constructor/destructor" to master branch in commit e4f16e9f357a38ec702fb69a0ffab9d292a6af9b, see attached. Grüße Thomas ----------------- Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634 München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht München, HRB 106955 From e4f16e9f357a38ec702fb69a0ffab9d292a6af9b Mon Sep 17 00:00:00 2001 From: Thomas Schwinge Date: Fri, 13 Aug 2021 17:53:12 +0200 Subject: [PATCH] Add more self-tests for 'hash_map' with Value type with non-trivial constructor/destructor ... to document the current behavior. gcc/ * hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Extend. (test_map_of_type_with_ctor_and_dtor_expand): Add function. (hash_map_tests_c_tests): Call it. --- gcc/hash-map-tests.c | 152 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 152 insertions(+) diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c index 5b6b192cd28..257f2be0c26 100644 --- a/gcc/hash-map-tests.c +++ b/gcc/hash-map-tests.c @@ -278,6 +278,156 @@ test_map_of_type_with_ctor_and_dtor () ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor); } + + + /* Verify basic construction and destruction of Value objects. */ + { + /* Configure, arbitrary. */ + const size_t N_init = 0; + const int N_elem = 28; + + void *a[N_elem]; + for (size_t i = 0; i < N_elem; ++i) + a[i] = &a[i]; + + val_t::ndefault = 0; + val_t::ncopy = 0; + val_t::nassign = 0; + val_t::ndtor = 0; + Map m (N_init); + ASSERT_EQ (val_t::ndefault + + val_t::ncopy + + val_t::nassign + + val_t::ndtor, 0); + + for (int i = 0; i < N_elem; ++i) + { + m.get_or_insert (a[i]); + ASSERT_EQ (val_t::ndefault, 1 + i); + ASSERT_EQ (val_t::ncopy, 0); + ASSERT_EQ (val_t::nassign, 0); + ASSERT_EQ (val_t::ndtor, i); + + m.remove (a[i]); + ASSERT_EQ (val_t::ndefault, 1 + i); + ASSERT_EQ (val_t::ncopy, 0); + ASSERT_EQ (val_t::nassign, 0); + ASSERT_EQ (val_t::ndtor, 1 + i); + } + } +} + +/* Verify aspects of 'hash_table::expand'. */ + +static void +test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline) +{ + /* Configure, so that hash table expansion triggers a few times. */ + const size_t N_init = 0; + const int N_elem = 70; + size_t expand_c_expected = 4; + size_t expand_c = 0; + + void *a[N_elem]; + for (size_t i = 0; i < N_elem; ++i) + a[i] = &a[i]; + + typedef hash_map Map; + + /* Note that we are starting with a fresh 'Map'. Even if an existing one has + been cleared out completely, there remain 'deleted' elements, and these + would disturb the following logic, where we don't have access to the + actual 'm_n_deleted' value. */ + size_t m_n_deleted = 0; + + val_t::ndefault = 0; + val_t::ncopy = 0; + val_t::nassign = 0; + val_t::ndtor = 0; + Map m (N_init); + + /* In the following, in particular related to 'expand', we're adapting from + the internal logic of 'hash_table', glossing over "some details" not + relevant for this testing here. */ + + /* Per 'hash_table::hash_table'. */ + size_t m_size; + { + unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init); + m_size = prime_tab[size_prime_index_].prime; + } + + int n_expand_moved = 0; + + for (int i = 0; i < N_elem; ++i) + { + size_t elts = m.elements (); + + /* Per 'hash_table::find_slot_with_hash'. */ + size_t m_n_elements = elts + m_n_deleted; + bool expand = m_size * 3 <= m_n_elements * 4; + + m.get_or_insert (a[i]); + if (expand) + { + ++expand_c; + + /* Per 'hash_table::expand'. */ + { + unsigned int nindex = hash_table_higher_prime_index (elts * 2); + m_size = prime_tab[nindex].prime; + } + m_n_deleted = 0; + + /* All non-deleted elements have been moved. */ + n_expand_moved += i; + if (remove_some_inline) + n_expand_moved -= (i + 2) / 3; + } + + ASSERT_EQ (val_t::ndefault, 1 + i); + ASSERT_EQ (val_t::ncopy, n_expand_moved); + ASSERT_EQ (val_t::nassign, 0); + if (remove_some_inline) + ASSERT_EQ (val_t::ndtor, (i + 2) / 3); + else + ASSERT_EQ (val_t::ndtor, 0); + + /* Remove some inline. This never triggers an 'expand' here, but via + 'm_n_deleted' does influence any following one. */ + if (remove_some_inline + && !(i % 3)) + { + m.remove (a[i]); + /* Per 'hash_table::remove_elt_with_hash'. */ + m_n_deleted++; + + ASSERT_EQ (val_t::ndefault, 1 + i); + ASSERT_EQ (val_t::ncopy, n_expand_moved); + ASSERT_EQ (val_t::nassign, 0); + ASSERT_EQ (val_t::ndtor, 1 + (i + 2) / 3); + } + } + ASSERT_EQ (expand_c, expand_c_expected); + + int ndefault = val_t::ndefault; + int ncopy = val_t::ncopy; + int nassign = val_t::nassign; + int ndtor = val_t::ndtor; + + for (int i = 0; i < N_elem; ++i) + { + if (remove_some_inline + && !(i % 3)) + continue; + + m.remove (a[i]); + ++ndtor; + ASSERT_EQ (val_t::ndefault, ndefault); + ASSERT_EQ (val_t::ncopy, ncopy); + ASSERT_EQ (val_t::nassign, nassign); + ASSERT_EQ (val_t::ndtor, ndtor); + } } /* Test calling empty on a hash_map that has a key type with non-zero @@ -309,6 +459,8 @@ hash_map_tests_c_tests () test_map_of_strings_to_int (); test_map_of_int_to_strings (); test_map_of_type_with_ctor_and_dtor (); + test_map_of_type_with_ctor_and_dtor_expand (false); + test_map_of_type_with_ctor_and_dtor_expand (true); test_nonzero_empty_key (); } -- 2.30.2