| Message ID | 874kbopoah.fsf@euler.schwinge.homeip.net |
|---|---|
| State | New |
| Headers | show |
| Series | Expensive selftests (was: 'hash_map<tree, hash_map<tree, tree>>') | expand |
On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote: > > Hi! > > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> 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. 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. > 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? Yes. 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". Richard. > 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
On 8/17/21 12:40 AM, Thomas Schwinge wrote: > Hi! > > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> 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. I think the right design is to move all these basic building blocks (at a minimum, all containers, but ultimately even higher level general-purpose APIs) into a standalone library with its own unit tests run independently of GCC. I'm fine with adding these tests if no one else is concerned about the overhead, especially with a lower number of iterations like Richard suggests (as long as it still exercises the expansion, of course). Thanks Martin > > > 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 >
This causes a bootstrap failure for me. PR/101959 On Tue, Aug 17, 2021 at 5:00 AM Richard Biener via Gcc <gcc@gcc.gnu.org> wrote: > > On Tue, Aug 17, 2021 at 8:40 AM Thomas Schwinge <thomas@codesourcery.com> wrote: > > > > Hi! > > > > On 2021-08-16T14:10:00-0600, Martin Sebor <msebor@gmail.com> 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. > > 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. > > > 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? > > Yes. 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". > > Richard. > > > 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 <thomas@codesourcery.com> 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 <void *, val_t> 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