[RFA 1/2] Speed up dict_hash

[RFA 1/2] Speed up dict_hash

[Tom Tromey]

This speeds up dict_hash a bit, by moving the "TKB" check into the
switch in the loop.

For "gdb -nx -readnow -batch gdb", this improves the time from ~9.8s
before to ~8.5s afterward.

gdb/ChangeLog
2017-11-04  Tom Tromey  <tom@tromey.com>

	* dictionary.c (dict_hash): Move "TKB" check into the "switch".
---
 gdb/ChangeLog    |  4 ++++
 gdb/dictionary.c | 32 ++++++++++++++++----------------
 2 files changed, 20 insertions(+), 16 deletions(-)

diff --git a/gdb/dictionary.c b/gdb/dictionary.c
index b2cfca28ab..702cd60c2a 100644
--- a/gdb/dictionary.c
+++ b/gdb/dictionary.c
@@ -796,17 +796,6 @@ dict_hash (const char *string0)
   hash = 0;
   while (*string)
     {
-      /* Ignore "TKB" suffixes.
-
-	 These are used by Ada for subprograms implementing a task body.
-	 For instance for a task T inside package Pck, the name of the
-	 subprogram implementing T's body is `pck__tTKB'.  We need to
-	 ignore the "TKB" suffix because searches for this task body
-	 subprogram are going to be performed using `pck__t' (the encoded
-	 version of the natural name `pck.t').  */
-      if (strcmp (string, "TKB") == 0)
-	return hash;
-
       switch (*string)
 	{
 	case '$':
@@ -828,14 +817,25 @@ dict_hash (const char *string0)
 		return hash;
 	      hash = 0;
 	      string += 2;
-	      break;
+	      continue;
 	    }
-	  /* FALL THROUGH */
-	default:
-	  hash = SYMBOL_HASH_NEXT (hash, *string);
-	  string += 1;
+	  break;
+	case 'T':
+	  /* Ignore "TKB" suffixes.
+
+	     These are used by Ada for subprograms implementing a task body.
+	     For instance for a task T inside package Pck, the name of the
+	     subprogram implementing T's body is `pck__tTKB'.  We need to
+	     ignore the "TKB" suffix because searches for this task body
+	     subprogram are going to be performed using `pck__t' (the encoded
+	     version of the natural name `pck.t').  */
+	  if (strcmp (string, "TKB") == 0)
+	    return hash;
 	  break;
 	}
+
+      hash = SYMBOL_HASH_NEXT (hash, *string);
+      string += 1;
     }
   return hash;
 }
-- 
2.13.6

[RFA 0/2] some minor symbol-reading performance improvements

[Tom Tromey]

This week I looked into symbol-reading performance a little bit.
Using callgrind, I found a couple of simple ways to improve
performance.

This series was regression tested by the buildbot.

Tom

[RFA 2/2] Simplify the psymbol hash function

[Tom Tromey]

This patch simplifies the psymbol_hash function, by changing it not to
examine the contents of the symbol's name.  This change just mirrors
what psymbol_compare already does -- it is checking for name equality,
which is presumably ok because symbol names are generally interned.

This change speeds up psymbol reading.  "gdb -nx -batch gdb"
previously took ~1.8 seconds on my machine, and with this patch it now
takes ~1.7 seconds.

gdb/ChangeLog
2017-11-04  Tom Tromey  <tom@tromey.com>

	* psymtab.c (psymbol_hash): Do not hash string contents.
---
 gdb/ChangeLog | 4 ++++
 gdb/psymtab.c | 2 +-
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index f848990867..d22f70a0c0 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -1515,7 +1515,7 @@ psymbol_hash (const void *addr, int length)
   h = hash_continue (&lang, sizeof (unsigned int), h);
   h = hash_continue (&domain, sizeof (unsigned int), h);
   h = hash_continue (&theclass, sizeof (unsigned int), h);
-  h = hash_continue (psymbol->ginfo.name, strlen (psymbol->ginfo.name), h);
+  h = hash_continue (&psymbol->ginfo.name, sizeof (psymbol->ginfo.name), h);
 
   return h;
 }
-- 
2.13.6

Re: [RFA 1/2] Speed up dict_hash

[Pedro Alves]

On 11/04/2017 04:13 PM, Tom Tromey wrote:
> This speeds up dict_hash a bit, by moving the "TKB" check into the
> switch in the loop.
> 
> For "gdb -nx -readnow -batch gdb", this improves the time from ~9.8s
> before to ~8.5s afterward.

Nice!

> +	case 'T':
> +	  /* Ignore "TKB" suffixes.
> +
> +	     These are used by Ada for subprograms implementing a task body.
> +	     For instance for a task T inside package Pck, the name of the
> +	     subprogram implementing T's body is `pck__tTKB'.  We need to
> +	     ignore the "TKB" suffix because searches for this task body
> +	     subprogram are going to be performed using `pck__t' (the encoded
> +	     version of the natural name `pck.t').  */
> +	  if (strcmp (string, "TKB") == 0)
> +	    return hash;

This looks good to me.

OOC, did you check whether

  'if (strcmp (string + 1, "KB") == 0)'

or even:

  if (string[1] == 'K' && string[2] == 'B' && string[3] == '\0')

made a difference?

Maybe there aren't enough 'T's in symbols to matter, or the
compiler is already inlining that strcmp...

Thanks,
Pedro Alves

Re: [RFA 2/2] Simplify the psymbol hash function

[Pedro Alves]

On 11/04/2017 04:13 PM, Tom Tromey wrote:
> This patch simplifies the psymbol_hash function, by changing it not to
> examine the contents of the symbol's name.  This change just mirrors
> what psymbol_compare already does -- it is checking for name equality,
> which is presumably ok because symbol names are generally interned.

Can you expand a bit more on the "presumably ok" part?  I think
it'd be nice to mention/explain this assumption in a comment
in the code.

> This change speeds up psymbol reading.  "gdb -nx -batch gdb"
> previously took ~1.8 seconds on my machine, and with this patch it now
> takes ~1.7 seconds.

That sounds great however I do wonder whether the bug is the other 
way around though.  What do the statistics say, e.g., debugging
gdb and firefox?  Do we end up deduping more or fewer
symbols in the bcache?

I read the original thread that added these custom functions,
and the original patch used strcmp in both hash and compare,
and then somehow the end result was what we have today.

See:
 https://sourceware.org/ml/gdb-patches/2010-08/msg00218.html
and:
 https://sourceware.org/ml/gdb-patches/2010-08/msg00242.html

So I'd love it that your patch is correct.  I'd just appreciate
a bit more detail since I'm not awfully familiar with this area.

Thanks,
Pedro Alves

Re: [RFA 2/2] Simplify the psymbol hash function

[Pedro Alves]

On 11/08/2017 11:12 AM, Pedro Alves wrote:
> On 11/04/2017 04:13 PM, Tom Tromey wrote:
>> This patch simplifies the psymbol_hash function, by changing it not to
>> examine the contents of the symbol's name.  This change just mirrors
>> what psymbol_compare already does -- it is checking for name equality,
>> which is presumably ok because symbol names are generally interned.
> 
> Can you expand a bit more on the "presumably ok" part?  I think
> it'd be nice to mention/explain this assumption in a comment
> in the code.
> 
>> This change speeds up psymbol reading.  "gdb -nx -batch gdb"
>> previously took ~1.8 seconds on my machine, and with this patch it now
>> takes ~1.7 seconds.
> 
> That sounds great however I do wonder whether the bug is the other 
> way around though.  What do the statistics say, e.g., debugging
> gdb and firefox?  Do we end up deduping more or fewer
> symbols in the bcache?

TBC, here I meant compared to changing the compare function
to do strcmp instead of the pointer comparison.

> 
> I read the original thread that added these custom functions,
> and the original patch used strcmp in both hash and compare,
> and then somehow the end result was what we have today.
> 
> See:
>  https://sourceware.org/ml/gdb-patches/2010-08/msg00218.html
> and:
>  https://sourceware.org/ml/gdb-patches/2010-08/msg00242.html
> 
> So I'd love it that your patch is correct.  I'd just appreciate
> a bit more detail since I'm not awfully familiar with this area.

BTW, I didn't quite get it the first time, but I think Sami's
comment at:
 https://sourceware.org/ml/gdb-patches/2010-08/msg00242.html

> "that explains how the old hash function worked"

is related to this:
  https://sourceware.org/ml/gdb-patches/2010-08/msg00245.html

> "A previous patch of mine introduced a bcache regression :D. The
> patch made cplus_specifc a pointer to an allocated struct. This is
> because we wanted to store more information in cplus_specific without
> penalizing the other other languages. With cplus_specific being a
> pointer hashing the whole symbol didn't work anymore. This patch is
> an attempt to fix that.

So before Sami's "previous patch", it sounds like we were already doing
pointer comparisons, simply because we hashed the whole symbol as a
block of memory.

So now I'm thinking that your patch must be correct.  I'd still
like to learn more about where is it that we intern the symbol
names, though, and I still think it'd be great to add a comment
to the code.

Thanks,
Pedro Alves

Re: [RFA 1/2] Speed up dict_hash

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <palves@redhat.com> writes:

>> For "gdb -nx -readnow -batch gdb", this improves the time from ~9.8s
>> before to ~8.5s afterward.

Pedro> Nice!

I rebuilt today and the baseline times were higher -- now it starts at
~14.1s for an unmodified gdb, down to ~12.2 with my patch.  I'm not sure
if this is due to some other patch, or if the additional time is because
I configured differently (I enabled guile, python, and all targets in
this most recent build).  If so, 4 seconds (comparing to the ~10 seconds
last time around) seems awfully expensive for those features...

Pedro> OOC, did you check whether
Pedro>   'if (strcmp (string + 1, "KB") == 0)'
Pedro> or even:
Pedro>   if (string[1] == 'K' && string[2] == 'B' && string[3] == '\0')
Pedro> made a difference?

I tried these and they didn't make a difference.

Tom

Re: [RFA 2/2] Simplify the psymbol hash function

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <palves@redhat.com> writes:

Pedro> So now I'm thinking that your patch must be correct.  I'd still
Pedro> like to learn more about where is it that we intern the symbol
Pedro> names, though, and I still think it'd be great to add a comment
Pedro> to the code.

It happens via symbol_set_names.  There is some subtlety here in that
sometimes a name won't be copied (this saves memory by referring to
strings in the mapped debuginfo), and also IIRC Ada adds some
complexities too.

I can add comments to the psymbol hash and comparison functions to
mention this.

Tom

Re: [RFA 1/2] Speed up dict_hash

[Pedro Alves]

On 11/08/2017 06:44 PM, Tom Tromey wrote:
>>>>>> "Pedro" == Pedro Alves <palves@redhat.com> writes:
> 
>>> For "gdb -nx -readnow -batch gdb", this improves the time from ~9.8s
>>> before to ~8.5s afterward.
> 
> Pedro> Nice!
> 
> I rebuilt today and the baseline times were higher -- now it starts at
> ~14.1s for an unmodified gdb, down to ~12.2 with my patch.  I'm not sure
> if this is due to some other patch, or if the additional time is because
> I configured differently (I enabled guile, python, and all targets in
> this most recent build).  If so, 4 seconds (comparing to the ~10 seconds
> last time around) seems awfully expensive for those features...

I'm seeing a lot of time (24%!) spent in gettext, via complaints...
perf shows:

-   86.23%     0.00%  gdb      gdb                     [.] gdb_main
   - gdb_main
      - 85.60% catch_command_errors
           symbol_file_add_main_adapter
           symbol_file_add_main
           symbol_file_add_main_1
           symbol_file_add
         - symbol_file_add_with_addrs
            - 84.31% dw2_expand_all_symtabs
               - dw2_instantiate_symtab
                  - 83.79% dw2_do_instantiate_symtab
                     - 70.85% process_die
                        - 41.11% dwarf_decode_macros
                           - 41.09% dwarf_decode_macro_bytes
                              - 39.74% dwarf_decode_macro_bytes
                                 + 24.75% __dcigettext
                                 + 7.37% macro_define_object_internal
                                 + 3.16% macro_define_function
                                   0.77% splay_tree_insert
                                 + 0.76% savestring
                                 + 0.58% free
                                   0.53% read_indirect_string_at_offset_from
                                0.54% macro_define_object_internal
                                0.51% macro_start_file
                        + 25.57% process_die
                        + 4.07% dwarf_decode_lines
                     + 4.28% compute_delayed_physnames
                     + 3.85% end_symtab_from_static_block
                     + 3.38% load_cu
                     + 1.29% end_symtab_get_static_block
                  + 0.52% do_my_cleanups
            + 1.29% read_symbols
      + 0.54% gdb_init

Maybe you were building with --disable-intl before?

The problem is that we're computing the arguments to
pass to complaint, including passing the format strings
through gettext, even when complaints are disabled...  

The patch below, improves "gdb -nx -readnow -batch gdb"
from ~11.s to ~7.8s, for me (gcc 5.3.1, -O2, x86_64).

From c171f5097e05fa25553d92b9f9d14bf46207edc2 Mon Sep 17 00:00:00 2001
From: Pedro Alves <palves@redhat.com>
Date: Wed, 8 Nov 2017 21:03:15 +0000
Subject: [PATCH] complaints

---
 gdb/complaints.c |  4 ++--
 gdb/complaints.h | 17 ++++++++++++++---
 2 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/gdb/complaints.c b/gdb/complaints.c
index 58b6b7b..22a5f69 100644
--- a/gdb/complaints.c
+++ b/gdb/complaints.c
@@ -148,7 +148,7 @@ find_complaint (struct complaints *complaints, const char *file,
    before we stop whining about it?  Default is no whining at all,
    since so many systems have ill-constructed symbol files.  */
 
-static int stop_whining = 0;
+int stop_whining = 0;
 
 /* Print a complaint, and link the complaint block into a chain for
    later handling.  */
@@ -236,7 +236,7 @@ vcomplaint (struct complaints **c, const char *file,
 }
 
 void
-complaint (struct complaints **complaints, const char *fmt, ...)
+complaint_1 (struct complaints **complaints, const char *fmt, ...)
 {
   va_list args;
 
diff --git a/gdb/complaints.h b/gdb/complaints.h
index 54c2b18..b6fa0e2 100644
--- a/gdb/complaints.h
+++ b/gdb/complaints.h
@@ -29,9 +29,20 @@ struct complaints;
 extern struct complaints *symfile_complaints;
 
 /* Register a complaint.  */
-extern void complaint (struct complaints **complaints,
-		       const char *fmt,
-		       ...) ATTRIBUTE_PRINTF (2, 3);
+extern void complaint_1 (struct complaints **complaints,
+			 const char *fmt,
+			 ...) ATTRIBUTE_PRINTF (2, 3);
+
+#define complaint(COMPLAINTS, FMT, ...)				\
+  do								\
+    {								\
+      extern int stop_whining;					\
+								\
+      if (stop_whining > 0)					\
+	complaint_1 (COMPLAINTS, FMT, ##__VA_ARGS__);		\
+    }								\
+  while (0)
+
 extern void internal_complaint (struct complaints **complaints,
 				const char *file, int line,
 				const char *fmt,
-- 
2.5.5

Re: [RFA 1/2] Speed up dict_hash

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <palves@redhat.com> writes:

Pedro> I'm seeing a lot of time (24%!) spent in gettext, via complaints...

Hmm, that sounds familiar somehow.

Pedro> Maybe you were building with --disable-intl before?

Not intentionally but perhaps I was missing a dependency.

Pedro> The patch below, improves "gdb -nx -readnow -batch gdb"
Pedro> from ~11.s to ~7.8s, for me (gcc 5.3.1, -O2, x86_64).

Seems like a good idea.  -readnow isn't really used, of course, but I
use it as a simpler-to-measure proxy for CU expansion time, which does
matter occasionally.

Tom

Re: [RFA 1/2] Speed up dict_hash

[Pedro Alves]

On 11/08/2017 11:01 PM, Tom Tromey wrote:

> Pedro> The patch below, improves "gdb -nx -readnow -batch gdb"
> Pedro> from ~11.s to ~7.8s, for me (gcc 5.3.1, -O2, x86_64).
> 
> Seems like a good idea.  -readnow isn't really used, of course, but I
> use it as a simpler-to-measure proxy for CU expansion time, which does
> matter occasionally.

Right.  Alright, I cleaned it up a bit, ran the testsuite,
fixed gdb.gdb/complaints.exp, and pushed it in now:
 https://sourceware.org/ml/gdb-patches/2017-11/msg00197.html

Thanks,
Pedro Alves

Re: [RFA 2/2] Simplify the psymbol hash function

[Tom Tromey]

>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:

Tom> I can add comments to the psymbol hash and comparison functions to
Tom> mention this.

How's this?

Tom

commit a042125cb391b1b489f272353a4c90068fc92954
Author: Tom Tromey <tom@tromey.com>
Date:   Thu Nov 2 12:48:44 2017 -0600

    Simplify the psymbol hash function
    
    This patch simplifies the psymbol_hash function, by changing it not to
    examine the contents of the symbol's name.  This change just mirrors
    what psymbol_compare already does -- it is checking for name equality,
    which is ok because symbol names are interned in symbol_set_names.
    
    This change speeds up psymbol reading.  "gdb -nx -batch gdb"
    previously took ~1.8 seconds on my machine, and with this patch it now
    takes ~1.7 seconds.
    
    gdb/ChangeLog
    2017-11-09  Tom Tromey  <tom@tromey.com>
    
            * psymtab.c (psymbol_hash): Do not hash string contents.
            (psymbol_compare): Add comment.

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 03ccf9d57c..014ae04a3d 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,8 @@
+2017-11-09  Tom Tromey  <tom@tromey.com>
+
+	* psymtab.c (psymbol_hash): Do not hash string contents.
+	(psymbol_compare): Add comment.
+
 2017-11-04  Tom Tromey  <tom@tromey.com>
 
 	* dictionary.c (dict_hash): Move "TKB" check into the "switch".
diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index 29d40dcc04..06a65bf26e 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -1548,7 +1548,9 @@ psymbol_hash (const void *addr, int length)
   h = hash_continue (&lang, sizeof (unsigned int), h);
   h = hash_continue (&domain, sizeof (unsigned int), h);
   h = hash_continue (&theclass, sizeof (unsigned int), h);
-  h = hash_continue (psymbol->ginfo.name, strlen (psymbol->ginfo.name), h);
+  /* Note that psymbol names are interned via symbol_set_names, so
+     there's no need to hash the contents of the name here.  */
+  h = hash_continue (&psymbol->ginfo.name, sizeof (psymbol->ginfo.name), h);
 
   return h;
 }
@@ -1568,6 +1570,9 @@ psymbol_compare (const void *addr1, const void *addr2, int length)
 	  && sym1->ginfo.language == sym2->ginfo.language
           && PSYMBOL_DOMAIN (sym1) == PSYMBOL_DOMAIN (sym2)
           && PSYMBOL_CLASS (sym1) == PSYMBOL_CLASS (sym2)
+	  /* Note that psymbol names are interned via
+	     symbol_set_names, so there's no need to compare the
+	     contents of the name here.  */
           && sym1->ginfo.name == sym2->ginfo.name);
 }
 

Re: [RFA 2/2] Simplify the psymbol hash function

[Pedro Alves]

On 11/09/2017 02:09 PM, Tom Tromey wrote:
>>>>>> "Tom" == Tom Tromey <tom@tromey.com> writes:
> 
> Tom> I can add comments to the psymbol hash and comparison functions to
> Tom> mention this.
> 
> How's this?

LGTM.

Thanks,
Pedro Alves