Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

[- gdb, + gdb-patches]

On Mon, Jul 9, 2012 at 11:51 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Mon, Jul 9, 2012 at 8:10 PM, Doug Evans <dje@google.com> wrote:
>> Hi.
>>
>> filename_seen in gdb does a linear search, this patch changes it
>> to use a hash table.
>>
>> Ok to check in?
>
> Why not just use htab_hash_string? The file name canonicalization can
> be put in gdb itself.
>
> Ciao!
> Steven

[blech, my first reply got turned into rich html]

Hi.
Given that filename_cmp.c lives in libiberty, putting related
functions together makes it easier to maintain them.
If you're suggesting writing a function that takes a file name and
returns a canonicalized name that will then work with
htab_hash_string, that's more expensive and I don't see the benefit.

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

Hi.  "ping" [for the libiberty part]

[The gdb part needs to be updated due to recent changes there, but I'm
going to wait until the libiberty part is approved.]

On Mon, Jul 9, 2012 at 11:10 AM, Doug Evans <dje@google.com> wrote:
> Hi.
>
> filename_seen in gdb does a linear search, this patch changes it
> to use a hash table.
>
> Ok to check in?
>
> I couldn't think of a good reason to put filename_hash,filename_eq in gdb,
> and I like placing them close to where hashtab.c and filename_cmp are defined.
> I also couldn't think of a sufficient reason to put them in a file by
> themselves.  Ergo adding them to filename_cmp.c, filenames.h.
> [It's possible there's a program that uses filename_cmp and already
> defines functions with the same names (thus this will introduce a build
> failure), but that's always a risk.  I couldn't find any in gdb,binutils,gcc.
> Technically speaking, it's also possible that adding the #include "hashtab.h"
> to filenames.h could introduce a build failure (e.g., some file has a static
> symbol that collides with one used in hashtab.h).  I'm hoping that's more of
> a theoretical concern.]
>
> 2012-07-09  Doug Evans  <dje@google.com>
>
>         include/
>         * filenames.h: #include "hashtab.h".
>         (filename_hash, filename_eq): Declare.
>
>         libiberty/
>         * filename_cmp.c (filename_hash, filename_eq): New functions.
>
>         gdb/
>         * symtab.c (filename_seen): Rewrite to use a hash table.
>
> Index: include/filenames.h
> ===================================================================
> RCS file: /cvs/src/src/include/filenames.h,v
> retrieving revision 1.10
> diff -u -p -r1.10 filenames.h
> --- include/filenames.h 1 Jul 2011 18:24:38 -0000       1.10
> +++ include/filenames.h 9 Jul 2012 17:24:53 -0000
> @@ -26,6 +26,8 @@ Foundation, Inc., 51 Franklin Street - F
>  #ifndef FILENAMES_H
>  #define FILENAMES_H
>
> +#include "hashtab.h" /* for hashval_t */
> +
>  #ifdef __cplusplus
>  extern "C" {
>  #endif
> @@ -84,6 +86,10 @@ extern int filename_cmp (const char *s1,
>  extern int filename_ncmp (const char *s1, const char *s2,
>                           size_t n);
>
> +extern hashval_t filename_hash (const void *s);
> +
> +extern int filename_eq (const void *s1, const void *s2);
> +
>  #ifdef __cplusplus
>  }
>  #endif
> Index: libiberty/filename_cmp.c
> ===================================================================
> RCS file: /cvs/src/src/libiberty/filename_cmp.c,v
> retrieving revision 1.6
> diff -u -p -r1.6 filename_cmp.c
> --- libiberty/filename_cmp.c    1 Jul 2011 18:24:39 -0000       1.6
> +++ libiberty/filename_cmp.c    9 Jul 2012 17:24:53 -0000
> @@ -141,3 +141,52 @@ filename_ncmp (const char *s1, const cha
>    return 0;
>  #endif
>  }
> +
> +/*
> +
> +@deftypefn Extension hashval_t filename_hash (const void *@var{s})
> +
> +Return the hash value for file name @var{s} that will be compared
> +using filename_cmp.
> +This function is for use with hashtab.c hash tables.
> +
> +@end deftypefn
> +
> +*/
> +
> +hashval_t
> +filename_hash (const void *s)
> +{
> +  /* The cast is for -Wc++-compat.  */
> +  const unsigned char *str = (const unsigned char *) s;
> +  hashval_t r = 0;
> +  unsigned char c;
> +
> +  while ((c = *str++) != 0)
> +    {
> +      if (c == '\\')
> +       c = '/';
> +      c = TOLOWER (c);
> +      r = r * 67 + c - 113;
> +    }
> +
> +  return r;
> +}
> +
> +/*
> +
> +@deftypefn Extension int filename_eq (const void *@var{s1}, const void *@var{s2})
> +
> +Return non-zero if file names @var{s1} and @var{s2} are equivalent.
> +This function is for use with hashtab.c hash tables.
> +
> +@end deftypefn
> +
> +*/
> +
> +int
> +filename_eq (const void *s1, const void *s2)
> +{
> +  /* The casts are for -Wc++-compat.  */
> +  return filename_cmp ((const char *) s1, (const char *) s2) == 0;
> +}
> Index: gdb/symtab.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/symtab.c,v
> retrieving revision 1.316
> diff -u -p -r1.316 symtab.c
> --- gdb/symtab.c        29 Jun 2012 22:46:45 -0000      1.316
> +++ gdb/symtab.c        9 Jul 2012 17:24:54 -0000
> @@ -3108,44 +3108,34 @@ operator_chars (char *p, char **end)
>  /* If FILE is not already in the table of files, return zero;
>     otherwise return non-zero.  Optionally add FILE to the table if ADD
>     is non-zero.  If *FIRST is non-zero, forget the old table
> -   contents.  */
> +   contents.
> +
> +   NOTE: We don't manage space for FILE, we assume FILE lives as long
> +   as the caller needs.  */
>
>  static int
>  filename_seen (const char *file, int add, int *first)
>  {
>    /* Table of files seen so far.  */
> -  static const char **tab = NULL;
> -  /* Allocated size of tab in elements.
> -     Start with one 256-byte block (when using GNU malloc.c).
> -     24 is the malloc overhead when range checking is in effect.  */
> -  static int tab_alloc_size = (256 - 24) / sizeof (char *);
> -  /* Current size of tab in elements.  */
> -  static int tab_cur_size;
> -  const char **p;
> +  static htab_t files_seen;
> +  void **slot;
>
>    if (*first)
>      {
> -      if (tab == NULL)
> -       tab = (const char **) xmalloc (tab_alloc_size * sizeof (*tab));
> -      tab_cur_size = 0;
> +      if (files_seen != NULL)
> +       htab_delete (files_seen);
> +      files_seen = htab_create_alloc (10, filename_hash, filename_eq,
> +                                     NULL, xcalloc, xfree);
>      }
>
>    /* Is FILE in tab?  */
> -  for (p = tab; p < tab + tab_cur_size; p++)
> -    if (filename_cmp (*p, file) == 0)
> -      return 1;
> +  slot = htab_find_slot (files_seen, file, add ? INSERT : NO_INSERT);
> +  if (*slot != NULL)
> +    return 1;
>
>    /* No; maybe add it to tab.  */
>    if (add)
> -    {
> -      if (tab_cur_size == tab_alloc_size)
> -       {
> -         tab_alloc_size *= 2;
> -         tab = (const char **) xrealloc ((char *) tab,
> -                                         tab_alloc_size * sizeof (*tab));
> -       }
> -      tab[tab_cur_size++] = file;
> -    }
> +    *slot = (char *) file;
>
>    return 0;
>  }

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[DJ Delorie]

I think it's confusing to have filename_cmp and filename_eq that do
basically the same thing.  Perhaps filename_eq should be
filename_cmp_v or filename_cmp_hash or something, to indicate that
it's *supposed* to be the same functionality as filename_cmp but with
a different signature?

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

On Fri, Jul 13, 2012 at 12:21 PM, DJ Delorie <dj@redhat.com> wrote:
>
> I think it's confusing to have filename_cmp and filename_eq that do
> basically the same thing.  Perhaps filename_eq should be
> filename_cmp_v or filename_cmp_hash or something, to indicate that
> it's *supposed* to be the same functionality as filename_cmp but with
> a different signature?

To be clear, filename_cmp is to strcmp as filename_eq is to streq.

ref: STREQ in libiberty/regex.c:
# define STREQ(s1, s2) ((strcmp (s1, s2) == 0))

Given that, I think the names are fine as is, but I'm happy to change them.
I like "eq", it's what hashtab uses (e.g. htab_eq_pointer).
How about filename_eq_hash?

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[DJ Delorie]

If there's precedent, I'm not worried about it.

Ok to check in.

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Eli Zaretskii]

> Date: Fri, 13 Jul 2012 12:36:44 -0700
> From: Doug Evans <dje@google.com>
> Cc: gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
> 
> On Fri, Jul 13, 2012 at 12:21 PM, DJ Delorie <dj@redhat.com> wrote:
> >
> > I think it's confusing to have filename_cmp and filename_eq that do
> > basically the same thing.  Perhaps filename_eq should be
> > filename_cmp_v or filename_cmp_hash or something, to indicate that
> > it's *supposed* to be the same functionality as filename_cmp but with
> > a different signature?
> 
> To be clear, filename_cmp is to strcmp as filename_eq is to streq.
> 
> ref: STREQ in libiberty/regex.c:
> # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
> 
> Given that, I think the names are fine as is, but I'm happy to change them.

Sorry if I'm missing something, but why do we need to advertise such a
function at all?  Given that libiberty already provides filename_cmp,
isn't it trivial to write something like filename_eq whenever someone
needs to use hashes of file names?

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

On Fri, Jul 13, 2012 at 12:47 PM, Eli Zaretskii <eliz@gnu.org> wrote:
>> Date: Fri, 13 Jul 2012 12:36:44 -0700
>> From: Doug Evans <dje@google.com>
>> Cc: gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
>>
>> On Fri, Jul 13, 2012 at 12:21 PM, DJ Delorie <dj@redhat.com> wrote:
>> >
>> > I think it's confusing to have filename_cmp and filename_eq that do
>> > basically the same thing.  Perhaps filename_eq should be
>> > filename_cmp_v or filename_cmp_hash or something, to indicate that
>> > it's *supposed* to be the same functionality as filename_cmp but with
>> > a different signature?
>>
>> To be clear, filename_cmp is to strcmp as filename_eq is to streq.
>>
>> ref: STREQ in libiberty/regex.c:
>> # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
>>
>> Given that, I think the names are fine as is, but I'm happy to change them.
>
> Sorry if I'm missing something, but why do we need to advertise such a
> function at all?  Given that libiberty already provides filename_cmp,
> isn't it trivial to write something like filename_eq whenever someone
> needs to use hashes of file names?

It's a "matched set" with filename_hash.
The hashtab.c constructors take a hash_f function pointer and an eq_f
function pointer.

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Eli Zaretskii]

> Date: Fri, 13 Jul 2012 14:26:15 -0700
> From: Doug Evans <dje@google.com>
> Cc: dj@redhat.com, gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
> 
> > Sorry if I'm missing something, but why do we need to advertise such a
> > function at all?  Given that libiberty already provides filename_cmp,
> > isn't it trivial to write something like filename_eq whenever someone
> > needs to use hashes of file names?
> 
> It's a "matched set" with filename_hash.
> The hashtab.c constructors take a hash_f function pointer and an eq_f
> function pointer.

I understand all that, but why would the eq_f function need to be an
external function on its own?

E.g., if we were to write a qsort replacement, would we have a
suitable string comparison function declared extern, when it is a
trivial wrapper around strcmp?

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Tom Tromey]

>>>>> "Eli" == Eli Zaretskii <eliz@gnu.org> writes:

Eli> I understand all that, but why would the eq_f function need to be an
Eli> external function on its own?

It is just to avoid other users having to write their own.

Eli> E.g., if we were to write a qsort replacement, would we have a
Eli> suitable string comparison function declared extern, when it is a
Eli> trivial wrapper around strcmp?

Yes.

We have streq for this, for use in hash tables and elsewhere.  It would
have been better if this were in libiberty, since currently there is a
copy of this function in gdb and like 3 or 4 in gcc.

Tom

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

On Fri, Jul 13, 2012 at 11:52 AM, Doug Evans <dje@google.com> wrote:
> Hi.  "ping" [for the libiberty part]
>
> [The gdb part needs to be updated due to recent changes there, but I'm
> going to wait until the libiberty part is approved.]
>
> On Mon, Jul 9, 2012 at 11:10 AM, Doug Evans <dje@google.com> wrote:
>> Hi.
>>
>> filename_seen in gdb does a linear search, this patch changes it
>> to use a hash table.
>>
>> Ok to check in?
>>
>> I couldn't think of a good reason to put filename_hash,filename_eq in gdb,
>> and I like placing them close to where hashtab.c and filename_cmp are defined.
>> I also couldn't think of a sufficient reason to put them in a file by
>> themselves.  Ergo adding them to filename_cmp.c, filenames.h.
>> [It's possible there's a program that uses filename_cmp and already
>> defines functions with the same names (thus this will introduce a build
>> failure), but that's always a risk.  I couldn't find any in gdb,binutils,gcc.
>> Technically speaking, it's also possible that adding the #include "hashtab.h"
>> to filenames.h could introduce a build failure (e.g., some file has a static
>> symbol that collides with one used in hashtab.h).  I'm hoping that's more of
>> a theoretical concern.]
>>
>> 2012-07-09  Doug Evans  <dje@google.com>
>>
>>         include/
>>         * filenames.h: #include "hashtab.h".
>>         (filename_hash, filename_eq): Declare.
>>
>>         libiberty/
>>         * filename_cmp.c (filename_hash, filename_eq): New functions.
>>
>>         gdb/
>>         * symtab.c (filename_seen): Rewrite to use a hash table.

With the libiberty part done, here's the updated gdb side.

As data, using my standard large app for exercising gdb issues, and
after running it a few times to warm the disk cache (for the fullname
conversion):

gdb $program # uses .gdb_index v7
(gdb) mt time 1
(gdb) info sources #1
(gdb) info sources #2

Before (best of 3):
#1: 18.100000 (cpu), 18.666510 (wall)
#2: 7.580000 (cpu), 7.936617 (wall)

After (best of 3):
#1: 10.060000 (cpu), 10.912673 (wall)
#2: 0.280000 (cpu), 2.746012 (wall)

Ok to check in?

2012-07-13  Doug Evans  <dje@google.com>

        * symtab.c (filename_seen_cache): Delete members "tab_alloc_size",
        "tab_cur_size".  Change member "tab" to be a htab_t.
        (create_filename_seen_cache): Update.
        (clear_filename_seen_cache, delete_filename_seen_cache): Update.
        (filename_seen): Update.

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Tom Tromey]

>>>>> "Doug" == Doug Evans <dje@google.com> writes:

Doug> Ok to check in?

Doug> 2012-07-13  Doug Evans  <dje@google.com>

Doug>         * symtab.c (filename_seen_cache): Delete members "tab_alloc_size",
Doug>         "tab_cur_size".  Change member "tab" to be a htab_t.
Doug>         (create_filename_seen_cache): Update.
Doug>         (clear_filename_seen_cache, delete_filename_seen_cache): Update.
Doug>         (filename_seen): Update.

No patch attached, but I already know it is ok.

Tom

[RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Doug Evans]

[Blech, sent to right list this time.  Already sent to gcc-patches@.]

Hi.

filename_seen in gdb does a linear search, this patch changes it
to use a hash table.

Ok to check in?

I couldn't think of a good reason to put filename_hash,filename_eq in gdb,
and I like placing them close to where hashtab.c and filename_cmp are defined.
I also couldn't think of a sufficient reason to put them in a file by
themselves.  Ergo adding them to filename_cmp.c, filenames.h.
[It's possible there's a program that uses filename_cmp and already
defines functions with the same names (thus this will introduce a build
failure), but that's always a risk.  I couldn't find any in gdb,binutils,gcc.
Technically speaking, it's also possible that adding the #include "hashtab.h"
to filenames.h could introduce a build failure (e.g., some file has a static
symbol that collides with one used in hashtab.h).  I'm hoping that's more of
a theoretical concern.]

2012-07-09  Doug Evans  <dje@google.com>

	include/
	* filenames.h: #include "hashtab.h".
	(filename_hash, filename_eq): Declare.

	libiberty/
	* filename_cmp.c (filename_hash, filename_eq): New functions.

	gdb/
	* symtab.c (filename_seen): Rewrite to use a hash table.

Index: include/filenames.h
===================================================================
RCS file: /cvs/src/src/include/filenames.h,v
retrieving revision 1.10
diff -u -p -r1.10 filenames.h
--- include/filenames.h	1 Jul 2011 18:24:38 -0000	1.10
+++ include/filenames.h	9 Jul 2012 17:24:53 -0000
@@ -26,6 +26,8 @@ Foundation, Inc., 51 Franklin Street - F
 #ifndef FILENAMES_H
 #define FILENAMES_H
 
+#include "hashtab.h" /* for hashval_t */
+
 #ifdef __cplusplus
 extern "C" {
 #endif
@@ -84,6 +86,10 @@ extern int filename_cmp (const char *s1,
 extern int filename_ncmp (const char *s1, const char *s2,
 			  size_t n);
 
+extern hashval_t filename_hash (const void *s);
+
+extern int filename_eq (const void *s1, const void *s2);
+
 #ifdef __cplusplus
 }
 #endif
Index: libiberty/filename_cmp.c
===================================================================
RCS file: /cvs/src/src/libiberty/filename_cmp.c,v
retrieving revision 1.6
diff -u -p -r1.6 filename_cmp.c
--- libiberty/filename_cmp.c	1 Jul 2011 18:24:39 -0000	1.6
+++ libiberty/filename_cmp.c	9 Jul 2012 17:24:53 -0000
@@ -141,3 +141,52 @@ filename_ncmp (const char *s1, const cha
   return 0;
 #endif
 }
+
+/*
+
+@deftypefn Extension hashval_t filename_hash (const void *@var{s})
+
+Return the hash value for file name @var{s} that will be compared
+using filename_cmp.
+This function is for use with hashtab.c hash tables.
+
+@end deftypefn
+
+*/
+
+hashval_t
+filename_hash (const void *s)
+{
+  /* The cast is for -Wc++-compat.  */
+  const unsigned char *str = (const unsigned char *) s;
+  hashval_t r = 0;
+  unsigned char c;
+
+  while ((c = *str++) != 0)
+    {
+      if (c == '\\')
+	c = '/';
+      c = TOLOWER (c);
+      r = r * 67 + c - 113;
+    }
+
+  return r;
+}
+
+/*
+
+@deftypefn Extension int filename_eq (const void *@var{s1}, const void *@var{s2})
+
+Return non-zero if file names @var{s1} and @var{s2} are equivalent.
+This function is for use with hashtab.c hash tables.
+
+@end deftypefn
+
+*/
+
+int
+filename_eq (const void *s1, const void *s2)
+{
+  /* The casts are for -Wc++-compat.  */
+  return filename_cmp ((const char *) s1, (const char *) s2) == 0;
+}
Index: gdb/symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.316
diff -u -p -r1.316 symtab.c
--- gdb/symtab.c	29 Jun 2012 22:46:45 -0000	1.316
+++ gdb/symtab.c	9 Jul 2012 17:24:54 -0000
@@ -3108,44 +3108,34 @@ operator_chars (char *p, char **end)
 /* If FILE is not already in the table of files, return zero;
    otherwise return non-zero.  Optionally add FILE to the table if ADD
    is non-zero.  If *FIRST is non-zero, forget the old table
-   contents.  */
+   contents.
+
+   NOTE: We don't manage space for FILE, we assume FILE lives as long
+   as the caller needs.  */
 
 static int
 filename_seen (const char *file, int add, int *first)
 {
   /* Table of files seen so far.  */
-  static const char **tab = NULL;
-  /* Allocated size of tab in elements.
-     Start with one 256-byte block (when using GNU malloc.c).
-     24 is the malloc overhead when range checking is in effect.  */
-  static int tab_alloc_size = (256 - 24) / sizeof (char *);
-  /* Current size of tab in elements.  */
-  static int tab_cur_size;
-  const char **p;
+  static htab_t files_seen;
+  void **slot;
 
   if (*first)
     {
-      if (tab == NULL)
-	tab = (const char **) xmalloc (tab_alloc_size * sizeof (*tab));
-      tab_cur_size = 0;
+      if (files_seen != NULL)
+	htab_delete (files_seen);
+      files_seen = htab_create_alloc (10, filename_hash, filename_eq,
+				      NULL, xcalloc, xfree);
     }
 
   /* Is FILE in tab?  */
-  for (p = tab; p < tab + tab_cur_size; p++)
-    if (filename_cmp (*p, file) == 0)
-      return 1;
+  slot = htab_find_slot (files_seen, file, add ? INSERT : NO_INSERT);
+  if (*slot != NULL)
+    return 1;
 
   /* No; maybe add it to tab.  */
   if (add)
-    {
-      if (tab_cur_size == tab_alloc_size)
-	{
-	  tab_alloc_size *= 2;
-	  tab = (const char **) xrealloc ((char *) tab,
-					  tab_alloc_size * sizeof (*tab));
-	}
-      tab[tab_cur_size++] = file;
-    }
+    *slot = (char *) file;
 
   return 0;
 }

Re: [RFA libiberty, gdb] Add hashtab support to filename_ncmp.c and use it in gdb.

[Tom Tromey]

>>>>> "Doug" == Doug Evans <dje@google.com> writes:

Doug> filename_seen in gdb does a linear search, this patch changes it
Doug> to use a hash table.

Doug> Ok to check in?

The gdb parts look good to me.

Doug> I couldn't think of a good reason to put filename_hash,filename_eq
Doug> in gdb, and I like placing them close to where hashtab.c and
Doug> filename_cmp are defined.  I also couldn't think of a sufficient
Doug> reason to put them in a file by themselves.

FWIW, I agree.  I'd like to see this patch go in.

Tom