From patchwork Tue Aug 17 06:40:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Thomas Schwinge X-Patchwork-Id: 1517566 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=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GphHd0Dk3z9sRN for ; Tue, 17 Aug 2021 16:40:43 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 35122396E03F for ; Tue, 17 Aug 2021 06:40:40 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from esa1.mentor.iphmx.com (esa1.mentor.iphmx.com [68.232.129.153]) by sourceware.org (Postfix) with ESMTPS id 7737F384780E; Tue, 17 Aug 2021 06:40:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7737F384780E 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: ytO4et168qayEoS9/XBFpCZdB7P+SPKhcyznXItcgCKJDjftngyASl5rbnmsATtmR/iG/0eSP6 zc5PRUm1T5YYDd2OroiIelFKQneuHKfkBjuBlfCk7APWulKbQoMRkwbhSqpUE3wWAonuO1Hkis kbeqD1o40NzzDtC+ZPIlNJI7+h/fijj+AKlMaFOFgqANpnH2UpTtNEu5iuDtBv+Iot5FTjVY4N Ao5JBxsCA5GDXSSt0jts/YrhQ0eTzSHXQNzVq1nU2ofInjBVlksptSSCDPVzmmKWTXkMVV1bwj gKIfUFjBSxmmzQGY+3MXsiWH X-IronPort-AV: E=Sophos;i="5.84,328,1620720000"; d="scan'208,223";a="67263648" Received: from orw-gwy-01-in.mentorg.com ([192.94.38.165]) by esa1.mentor.iphmx.com with ESMTP; 16 Aug 2021 22:40:14 -0800 IronPort-SDR: dZv1TxeuXoZ8E4dn4z+kSp+WG4Eo/BkQVK8ALp8KmTnI17k7bI3r4gVeO9n220DwzlsNjRuv0m gkS66xytxhPOqL3jgkiErHr8MxJSdDQp5SBGxR+kfN49YFLES6B5JqTgT8kCNBg8XC66//5Is0 HukYrDH0A2awhscgt6Qd1g2SxVt8oOBih0VCwU25y0mx5fQGtQeveZh+FvSOg1bBpTiBWJf1AV 8O/YAsRz0K4LYBxXfyUouYdYR22R83nhntEQ1VPSlEkhpriz9wxjWMzpPujgLvcy4bFPhJ6GbE vTQ= From: Thomas Schwinge To: Martin Sebor , David Malcolm Subject: Expensive selftests (was: 'hash_map>') In-Reply-To: <55126f14-dda1-2040-0976-70b89582a60c@gmail.com> References: <87r1f6qzmx.fsf@euler.schwinge.homeip.net> <87czqd7e4k.fsf@euler.schwinge.homeip.net> <55126f14-dda1-2040-0976-70b89582a60c@gmail.com> User-Agent: Notmuch/0.29.3+94~g74c3f1b (https://notmuchmail.org) Emacs/27.1 (x86_64-pc-linux-gnu) Date: Tue, 17 Aug 2021 08:40:06 +0200 Message-ID: <874kbopoah.fsf@euler.schwinge.homeip.net> MIME-Version: 1.0 X-Originating-IP: [137.202.0.90] X-ClientProxiedBy: svr-ies-mbx-09.mgc.mentorg.com (139.181.222.9) 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 , gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi! 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?) (Attached again, for easy reference.) > 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. For 'selftest-c', we've got originally: -fself-test: 74775 pass(es) in 0.309299 seconds -fself-test: 74775 pass(es) in 0.366041 seconds -fself-test: 74775 pass(es) in 0.356663 seconds -fself-test: 74775 pass(es) in 0.355009 seconds -fself-test: 74775 pass(es) in 0.367575 seconds -fself-test: 74775 pass(es) in 0.320406 seconds ..., and with my changes we've got: -fself-test: 94519 pass(es) in 0.327755 seconds -fself-test: 94519 pass(es) in 0.369522 seconds -fself-test: 94519 pass(es) in 0.355531 seconds -fself-test: 94519 pass(es) in 0.362179 seconds -fself-test: 94519 pass(es) in 0.363176 seconds -fself-test: 94519 pass(es) in 0.318930 seconds So it really seems to be all in the noise? Yet: > Selftests run each time GCC > builds (i.e., even during day to day development). It seems to me > that it might be better to run such selftests only as part of > the bootstrap process. I'd rather have thought about a '--param self-test-expensive' (or similar), and then invoke the selftests via a new 'gcc/testsuite/selftests/expensive.exp' (or similar). Or, adapt 'gcc/testsuite/gcc.dg/plugin/expensive_selftests_plugin.c', that is, invoke them via the GCC plugin mechanism, which also seems to be easy enough? I don't have a strong opinion about where/when these tests get run, so will happily take any suggestions. 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 12fda2ece45ea477cdc9a697b5efc6e51c9da229 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 | 142 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 142 insertions(+) diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c index 5b6b192cd28..3c79a13c1a8 100644 --- a/gcc/hash-map-tests.c +++ b/gcc/hash-map-tests.c @@ -278,6 +278,146 @@ 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. */ + { + const int N_elem = 1234; + void *a[N_elem]; + for (int i = 0; i < N_elem; ++i) + a[i] = &a[i]; + + const int N_init = 44; + + 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 'hash_table::expand'. */ + +static void +test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline) +{ + 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; + + const int N_elem = 1234; + void *a[N_elem]; + for (int i = 0; i < N_elem; ++i) + a[i] = &a[i]; + + const int N_init = 4; + + 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. */ + + 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) + { + int 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) + { + /* 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', but does + influence any following via 'm_n_deleted'. */ + 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); + } + } + + 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 +449,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