gdb: reduce size of generated gdb-index file

I noticed in passing that out algorithm for generating the gdb-index
file is incorrect.  When building the hash table in add_index_entry we
count every incoming entry rehash when the number of entries gets too
large.  However, some of the incoming entries will be duplicates,
which don't actually result in new items being added to the hash
table.

As a result, we grow the gdb-index hash table far too often.

With an unmodified GDB, generating a gdb-index for GDB, I see a file
size of 90M, with a hash usage (in the generated index file) of just
2.6%.

With a patched GDB, generating a gdb-index for the _same_ GDB binary,
I now see a gdb-index file size of 30M, with a hash usage of 41.9%.

This is a 67% reduction in gdb-index file size.

Obviously, not every gdb-index file is going to see such big savings,
however, the larger a program, and the more symbols that are
duplicated between compilation units, the more GDB would over count,
and so, over-grow the index.

The gdb-index hash table we create has a minimum size of 1024, and
then we grow the hash when it is 75% full, doubling the hash table at
that time.  Given this, then we expect that either:

  a. The hash table is size 1024, and less than 75% full, or
  b. The hash table is between 37.5% and 75% full.

I've include a test that checks some of these constraints -- I've not
bothered to check the upper limit, and over full hash table isn't
really a problem here, but if the fill percentage is less than 37.5%
then this indicates that we've done something wrong (obviously, I also
check for the 1024 minimum size).

Approved-By: Tom Tromey <tom@tromey.com>

1 files changed, 19 insertions, 10 deletions

diff --git a/gdb/dwarf2/index-write.c b/gdb/dwarf2/index-write.c
index c086779..5960bac 100644
--- a/gdb/dwarf2/index-write.c
+++ b/gdb/dwarf2/index-write.c
@@ -256,20 +256,29 @@ add_index_entry (struct mapped_symtab *symtab, const char *name,
 		 int is_static, gdb_index_symbol_kind kind,
 		 offset_type cu_index)
 {
-  offset_type cu_index_and_attrs;
+  symtab_index_entry *slot = &find_slot (symtab, name);
+  if (slot->name == NULL)
+    {
+      /* This is a new element in the hash table.  */
+      ++symtab->n_elements;
 
-  ++symtab->n_elements;
-  if (4 * symtab->n_elements / 3 >= symtab->data.size ())
-    hash_expand (symtab);
+      /* We might need to grow the hash table.  */
+      if (4 * symtab->n_elements / 3 >= symtab->data.size ())
+	{
+	  hash_expand (symtab);
 
-  symtab_index_entry &slot = find_slot (symtab, name);
-  if (slot.name == NULL)
-    {
-      slot.name = name;
+	  /* This element will have a different slot in the new table.  */
+	  slot = &find_slot (symtab, name);
+
+	  /* But it should still be a new element in the hash table.  */
+	  gdb_assert (slot->name == nullptr);
+	}
+
+      slot->name = name;
       /* index_offset is set later.  */
     }
 
-  cu_index_and_attrs = 0;
+  offset_type cu_index_and_attrs = 0;
   DW2_GDB_INDEX_CU_SET_VALUE (cu_index_and_attrs, cu_index);
   DW2_GDB_INDEX_SYMBOL_STATIC_SET_VALUE (cu_index_and_attrs, is_static);
   DW2_GDB_INDEX_SYMBOL_KIND_SET_VALUE (cu_index_and_attrs, kind);
@@ -281,7 +290,7 @@ add_index_entry (struct mapped_symtab *symtab, const char *name,
      the last entry pushed), but a symbol could have multiple kinds in one CU.
      To keep things simple we don't worry about the duplication here and
      sort and uniquify the list after we've processed all symbols.  */
-  slot.cu_indices.push_back (cu_index_and_attrs);
+  slot->cu_indices.push_back (cu_index_and_attrs);
 }
 
 /* See symtab_index_entry.  */