Speeding up type lookup

[Martin v. Loewis]

When profiling gcc, I noticed that a measurable amount of time is
spent in type_hash_lookup. Upon further investigation, I found that
this is due to the large number of collisions in the hash table, which
requires a deeper analysis of the types to determine equality. In one
of my examples, there where 250 types for a single hash bucket; for a
trivial 'int main(){}' c++ program, there are up to three collisions.

This patch adds a statistics function printing usage of the hash
table, and increases the size of the hash table. In one example, it
reduced compilation time from 46 seconds to 44 seconds (approx 4%).

The full bootstrap + testsuite was made on i586-pc-linux-gnu, with no
regressions.

Regards,
Martin

2000-03-18  Martin v. Löwis  <loewis@informatik.hu-berlin.de>

	* tree.c (print_type_hash_statistics): New function.
	(dump_tree_statistics): Call it.
	(TYPE_HASH_SIZE): Increase to 1009.

Index: tree.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/tree.c,v
retrieving revision 1.125
diff -u -p -r1.125 tree.c
--- tree.c	2000/03/17 22:40:45	1.125
+++ tree.c	2000/03/18 17:30:35
@@ -269,13 +269,14 @@ struct type_hash
    While all these live in the same table, they are completely independent,
    and the hash code is computed differently for each of these.  */
 
-#define TYPE_HASH_SIZE 59
+#define TYPE_HASH_SIZE 1009
 struct type_hash *type_hash_table[TYPE_HASH_SIZE];
 
 static void build_real_from_int_cst_1 PARAMS ((PTR));
 static void set_type_quals PARAMS ((tree, int));
 static void append_random_chars PARAMS ((char *));
 static void mark_type_hash PARAMS ((void *));
+static void print_type_hash_statistics PARAMS((void));
 
 /* If non-null, these are language-specific helper functions for
    unsave_expr_now.  If present, LANG_UNSAVE is called before its
@@ -4077,6 +4078,29 @@ mark_type_hash (arg)
     }
 }
 
+static void
+print_type_hash_statistics ()
+{
+  int min, max=0, total = 0;
+  int i;
+  for (i = 0; i < TYPE_HASH_SIZE; i++)
+    {
+      int count = 0;
+      struct type_hash *it;
+      for (it = type_hash_table[i]; it; it = it->next)
+	count++;
+      if (i == 0)
+	min = count;
+      else if (count < min)
+	min = count;
+      if (count > max)
+	max = count;
+      total += count;
+    }
+  fprintf (stderr, "Type hash: minimum %d, maximum %d, average %f\n",
+	   min, max, 1.0 * total / TYPE_HASH_SIZE);
+}
+
 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
    by adding the hash codes of the individual attributes.  */
@@ -5247,6 +5271,7 @@ dump_tree_statistics ()
   print_obstack_statistics ("temporary_obstack", &temporary_obstack);
   print_obstack_statistics ("momentary_obstack", &momentary_obstack);
   print_obstack_statistics ("temp_decl_obstack", &temp_decl_obstack);
+  print_type_hash_statistics ();
   print_lang_statistics ();
 }