Expensive selftests (was: 'hash_map<tree, hash_map<tree, tree>>')

[Thomas Schwinge <thomas@codesourcery.com>]

[-- Attachment #1: Type: text/plain, Size: 2542 bytes --]

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.


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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-more-self-tests-for-hash_map-with-Value-type-wit.patch --]
[-- Type: text/x-diff, Size: 4953 bytes --]

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