[review] Create a correctly-sized demangled names hashtable

[review] Create a correctly-sized demangled names hashtable

[Christian Biesinger (Code Review)]

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................

Create a correctly-sized demangled names hashtable

If we have a minsym count, we know the demangled names hashtable will
be at least that big.  So use that count to create it, so we don't
have to resize/rehash it as much.

This is a 6% improvement in minsym loading time.

2019-11-18  Christian Biesinger  <cbiesinger@google.com>

	* symtab.c (create_demangled_names_hash): Use per_bfd->
	minimal_symbol_count as the initial size, if greater than
	our default size.

Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
---
M gdb/symtab.c
1 file changed, 9 insertions(+), 2 deletions(-)



diff --git a/gdb/symtab.c b/gdb/symtab.c
index 3502827..e4da065 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -769,10 +769,17 @@
   /* Choose 256 as the starting size of the hash table, somewhat arbitrarily.
      The hash table code will round this up to the next prime number.
      Choosing a much larger table size wastes memory, and saves only about
-     1% in symbol reading.  */
+     1% in symbol reading.  However, if the minsym count is already
+     initialized (e.g. because symbol name setting was deferred to
+     a background thread) we can initialize the hashtable with that
+     count, because we will almost certainly have at least that
+     many entries.  If we have a nonzero number but less than 256,
+     we still stay with 256 to have some space for psymbols, etc.  */
+
+  int count = std::max (per_bfd->minimal_symbol_count, 256);
 
   per_bfd->demangled_names_hash.reset (htab_create_alloc
-    (256, hash_demangled_name_entry, eq_demangled_name_entry,
+    (count, hash_demangled_name_entry, eq_demangled_name_entry,
      free_demangled_name_entry, xcalloc, xfree));
 }
 

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 1
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-MessageType: newchange

[review] Create a correctly-sized demangled names hashtable

[Christian Biesinger (Code Review)]

Christian Biesinger has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................


Patch Set 1:

I guess this patch doesn't *technically* depend on the threading changes; but it will have no benefit without them.


-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 1
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Comment-Date: Mon, 18 Nov 2019 23:19:04 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: No
Gerrit-MessageType: comment

[review] Create a correctly-sized demangled names hashtable

[Christian Biesinger (Code Review)]

Christian Biesinger has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................


Patch Set 1:

(1 comment)

| --- gdb/symtab.c
| +++ gdb/symtab.c
| @@ -771,10 +771,17 @@ create_demangled_names_hash (struct objfile_per_bfd_storage *per_bfd)
|       Choosing a much larger table size wastes memory, and saves only about
| -     1% in symbol reading.  */
| +     1% in symbol reading.  However, if the minsym count is already
| +     initialized (e.g. because symbol name setting was deferred to
| +     a background thread) we can initialize the hashtable with that
| +     count, because we will almost certainly have at least that
| +     many entries.  If we have a nonzero number but less than 256,
| +     we still stay with 256 to have some space for psymbols, etc.  */
| +
| +  int count = std::max (per_bfd->minimal_symbol_count, 256);

PS1, Line 779:

Looking at hashtab.c, I should perhaps do something like
((minimal_symbol_count+2)/3)*4, to more completely avoid hashtable
resizings. Let me know if you have thoughts on that.

|  
|    per_bfd->demangled_names_hash.reset (htab_create_alloc
| -    (256, hash_demangled_name_entry, eq_demangled_name_entry,
| +    (count, hash_demangled_name_entry, eq_demangled_name_entry,
|       free_demangled_name_entry, xcalloc, xfree));
|  }
|  
|  /* See symtab.h  */
|  

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 1
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Comment-Date: Mon, 18 Nov 2019 23:24:13 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
Gerrit-MessageType: comment

[review] Create a correctly-sized demangled names hashtable

[Simon Marchi (Code Review)]

Simon Marchi has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................


Patch Set 1:

(1 comment)

| --- gdb/symtab.c
| +++ gdb/symtab.c
| @@ -771,10 +771,17 @@ create_demangled_names_hash (struct objfile_per_bfd_storage *per_bfd)
|       Choosing a much larger table size wastes memory, and saves only about
| -     1% in symbol reading.  */
| +     1% in symbol reading.  However, if the minsym count is already
| +     initialized (e.g. because symbol name setting was deferred to
| +     a background thread) we can initialize the hashtable with that
| +     count, because we will almost certainly have at least that
| +     many entries.  If we have a nonzero number but less than 256,
| +     we still stay with 256 to have some space for psymbols, etc.  */
| +
| +  int count = std::max (per_bfd->minimal_symbol_count, 256);

PS1, Line 779:

> Looking at hashtab.c, I should perhaps do something like ((minimal_symbol_count+2)/3)*4, to more completely avoid hashtable resizings. Let me know if you have thoughts on that.

Not sure why the +2, but I think it's a good idea to size the
hashtable correctly from the start.  I'd be fine with the (.../3)*4
with the comment explaining why we do that.  This is performance
critical code, so it's normal to do tweaks like that.

Oh, is the +2 to make sure it rounds up the division by 3?

|  
|    per_bfd->demangled_names_hash.reset (htab_create_alloc
| -    (256, hash_demangled_name_entry, eq_demangled_name_entry,
| +    (count, hash_demangled_name_entry, eq_demangled_name_entry,
|       free_demangled_name_entry, xcalloc, xfree));
|  }
|  
|  /* See symtab.h  */
|  

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 1
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-Comment-Date: Wed, 20 Nov 2019 04:42:46 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
Comment-In-Reply-To: Christian Biesinger <cbiesinger@google.com>
Gerrit-MessageType: comment

[review v2] Create a correctly-sized demangled names hashtable

[Christian Biesinger (Code Review)]

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................

Create a correctly-sized demangled names hashtable

If we have a minsym count, we know the demangled names hashtable will
be at least that big.  So use that count to size it, so we don't
have to resize/rehash it as much.

This is a 6% improvement in minsym loading time.

2019-11-18  Christian Biesinger  <cbiesinger@google.com>

	* symtab.c (create_demangled_names_hash): Use per_bfd->
	minimal_symbol_count as the initial size, if greater than
	our default size.

Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
---
M gdb/symtab.c
1 file changed, 12 insertions(+), 2 deletions(-)



diff --git a/gdb/symtab.c b/gdb/symtab.c
index 3502827..e9dcc06 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -769,10 +769,20 @@
   /* Choose 256 as the starting size of the hash table, somewhat arbitrarily.
      The hash table code will round this up to the next prime number.
      Choosing a much larger table size wastes memory, and saves only about
-     1% in symbol reading.  */
+     1% in symbol reading.  However, if the minsym count is already
+     initialized (e.g. because symbol name setting was deferred to
+     a background thread) we can initialize the hashtable with a count
+     based on that, because we will almost certainly have at least that
+     many entries.  If we have a nonzero number but less than 256,
+     we still stay with 256 to have some space for psymbols, etc.  */
+
+  /* htab will expand the table when it is 3/4th full, so we account for that
+     here.  +2 to round up.  */
+  int minsym_based_count = (per_bfd->minimal_symbol_count + 2) / 3 * 4;
+  int count = std::max (per_bfd->minimal_symbol_count, minsym_based_count);
 
   per_bfd->demangled_names_hash.reset (htab_create_alloc
-    (256, hash_demangled_name_entry, eq_demangled_name_entry,
+    (count, hash_demangled_name_entry, eq_demangled_name_entry,
      free_demangled_name_entry, xcalloc, xfree));
 }
 

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-MessageType: newpatchset

[review v2] Create a correctly-sized demangled names hashtable

[Christian Biesinger (Code Review)]

Christian Biesinger has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................


Patch Set 2:

(1 comment)

BTW, thoughts on me pushing this even without the threading changes, so that I have fewer patches to keep track of? Shouldn't hurt anything.

| --- gdb/symtab.c
| +++ gdb/symtab.c
| @@ -771,10 +771,17 @@ create_demangled_names_hash (struct objfile_per_bfd_storage *per_bfd)
|       Choosing a much larger table size wastes memory, and saves only about
| -     1% in symbol reading.  */
| +     1% in symbol reading.  However, if the minsym count is already
| +     initialized (e.g. because symbol name setting was deferred to
| +     a background thread) we can initialize the hashtable with that
| +     count, because we will almost certainly have at least that
| +     many entries.  If we have a nonzero number but less than 256,
| +     we still stay with 256 to have some space for psymbols, etc.  */
| +
| +  int count = std::max (per_bfd->minimal_symbol_count, 256);

PS1, Line 779:

Yes, +2 is for rounding. Done and added a comment for that.

|  
|    per_bfd->demangled_names_hash.reset (htab_create_alloc
| -    (256, hash_demangled_name_entry, eq_demangled_name_entry,
| +    (count, hash_demangled_name_entry, eq_demangled_name_entry,
|       free_demangled_name_entry, xcalloc, xfree));
|  }
|  
|  /* See symtab.h  */
|  

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-Comment-Date: Wed, 20 Nov 2019 05:34:46 +0000
Gerrit-HasComments: Yes
Gerrit-Has-Labels: No
Comment-In-Reply-To: Christian Biesinger <cbiesinger@google.com>
Comment-In-Reply-To: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-MessageType: comment

[review v2] Create a correctly-sized demangled names hashtable

[Kevin Buettner (Code Review)]

Kevin Buettner has posted comments on this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................


Patch Set 2: Code-Review+2

> Patch Set 2:
> 
> (1 comment)
> 
> BTW, thoughts on me pushing this even without the threading changes, so that I have fewer patches to keep track of? Shouldn't hurt anything.

I think it makes sense to push this patch ahead of the rest of the series.


-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 2
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Kevin Buettner <kevinb@redhat.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-Comment-Date: Fri, 22 Nov 2019 02:50:56 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: Yes
Gerrit-MessageType: comment

[pushed] Create a correctly-sized demangled names hashtable

[Sourceware to Gerrit sync (Code Review)]

Sourceware to Gerrit sync has submitted this change.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................

Create a correctly-sized demangled names hashtable

If we have a minsym count, we know the demangled names hashtable will
be at least that big.  So use that count to size it, so we don't
have to resize/rehash it as much.

This is a 6% improvement in minsym loading time.

2019-11-22  Christian Biesinger  <cbiesinger@google.com>

	* symtab.c (create_demangled_names_hash): Use per_bfd->
	minimal_symbol_count for computing the initial size, if greater
	than our default size.

Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
---
M gdb/ChangeLog
M gdb/symtab.c
2 files changed, 18 insertions(+), 2 deletions(-)


diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 93258c3..838262e 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,9 @@
+2019-11-22  Christian Biesinger  <cbiesinger@google.com>
+
+	* symtab.c (create_demangled_names_hash): Use per_bfd->
+	minimal_symbol_count for computing the initial size, if greater
+	than our default size.
+
 2019-11-22  Tom de Vries  <tdevries@suse.de>
 
 	* contrib/words.sh: Improve words extraction.
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 0064800..6affdef 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -770,10 +770,20 @@
   /* Choose 256 as the starting size of the hash table, somewhat arbitrarily.
      The hash table code will round this up to the next prime number.
      Choosing a much larger table size wastes memory, and saves only about
-     1% in symbol reading.  */
+     1% in symbol reading.  However, if the minsym count is already
+     initialized (e.g. because symbol name setting was deferred to
+     a background thread) we can initialize the hashtable with a count
+     based on that, because we will almost certainly have at least that
+     many entries.  If we have a nonzero number but less than 256,
+     we still stay with 256 to have some space for psymbols, etc.  */
+
+  /* htab will expand the table when it is 3/4th full, so we account for that
+     here.  +2 to round up.  */
+  int minsym_based_count = (per_bfd->minimal_symbol_count + 2) / 3 * 4;
+  int count = std::max (per_bfd->minimal_symbol_count, minsym_based_count);
 
   per_bfd->demangled_names_hash.reset (htab_create_alloc
-    (256, hash_demangled_name_entry, eq_demangled_name_entry,
+    (count, hash_demangled_name_entry, eq_demangled_name_entry,
      free_demangled_name_entry, xcalloc, xfree));
 }
 

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 3
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Kevin Buettner <kevinb@redhat.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-MessageType: merged

[pushed] Create a correctly-sized demangled names hashtable

[Sourceware to Gerrit sync (Code Review)]

The original change was created by Christian Biesinger.

Change URL: https://gnutoolchain-gerrit.osci.io/r/c/binutils-gdb/+/686
......................................................................

Create a correctly-sized demangled names hashtable

If we have a minsym count, we know the demangled names hashtable will
be at least that big.  So use that count to size it, so we don't
have to resize/rehash it as much.

This is a 6% improvement in minsym loading time.

2019-11-22  Christian Biesinger  <cbiesinger@google.com>

	* symtab.c (create_demangled_names_hash): Use per_bfd->
	minimal_symbol_count for computing the initial size, if greater
	than our default size.

Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
---
M gdb/ChangeLog
M gdb/symtab.c
2 files changed, 18 insertions(+), 2 deletions(-)



diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 93258c3..838262e 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,9 @@
+2019-11-22  Christian Biesinger  <cbiesinger@google.com>
+
+	* symtab.c (create_demangled_names_hash): Use per_bfd->
+	minimal_symbol_count for computing the initial size, if greater
+	than our default size.
+
 2019-11-22  Tom de Vries  <tdevries@suse.de>
 
 	* contrib/words.sh: Improve words extraction.
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 0064800..6affdef 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -770,10 +770,20 @@
   /* Choose 256 as the starting size of the hash table, somewhat arbitrarily.
      The hash table code will round this up to the next prime number.
      Choosing a much larger table size wastes memory, and saves only about
-     1% in symbol reading.  */
+     1% in symbol reading.  However, if the minsym count is already
+     initialized (e.g. because symbol name setting was deferred to
+     a background thread) we can initialize the hashtable with a count
+     based on that, because we will almost certainly have at least that
+     many entries.  If we have a nonzero number but less than 256,
+     we still stay with 256 to have some space for psymbols, etc.  */
+
+  /* htab will expand the table when it is 3/4th full, so we account for that
+     here.  +2 to round up.  */
+  int minsym_based_count = (per_bfd->minimal_symbol_count + 2) / 3 * 4;
+  int count = std::max (per_bfd->minimal_symbol_count, minsym_based_count);
 
   per_bfd->demangled_names_hash.reset (htab_create_alloc
-    (256, hash_demangled_name_entry, eq_demangled_name_entry,
+    (count, hash_demangled_name_entry, eq_demangled_name_entry,
      free_demangled_name_entry, xcalloc, xfree));
 }
 

-- 
Gerrit-Project: binutils-gdb
Gerrit-Branch: master
Gerrit-Change-Id: I1f074d38e1d90af58705ec852f90c84cc034cd2e
Gerrit-Change-Number: 686
Gerrit-PatchSet: 3
Gerrit-Owner: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Christian Biesinger <cbiesinger@google.com>
Gerrit-Reviewer: Kevin Buettner <kevinb@redhat.com>
Gerrit-CC: Simon Marchi <simon.marchi@polymtl.ca>
Gerrit-MessageType: newpatchset