[Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Jerome Guitton]

[-- Attachment #1: Type: text/plain, Size: 1081 bytes --]


The move to bugzilla has "resurrected" this patch; I suggested it
several years ago, but it's still relevant.

The problem is explained in details in the comment (very useful when I
had to double-check that the patch was not obsolete, actually). To
summarize it: lookup_partial_symtab is particularly slow when it has
been given an absolute path. The reason is that it needs to build the
full filename for every psymtab; when building this full filename, the
corresponding file is opened/closed by find_and_open_source. As a
consequence, in the worst case, the loop ends up opening/closing
every source file of the application. Pretty bad for a big application,
in particular if the sources are located on a slow file system.

The idea of the patch is to avoid building the psymtab full filename
if the basenames are different.

Tested on linux, no regression.

OK to apply?


2009-01-14  Jerome Guitton  <guitton@adacore.com>

	* symtab.c (lookup_partial_symtab): When looking up an absolute path
	in the partial symtabs, compare the base names before checking the
	full names.


[-- Attachment #2: lookup_partial_symtab.dif --]
[-- Type: video/dv, Size: 2457 bytes --]

Re: [Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Jerome Guitton]

[-- Attachment #1: Type: text/plain, Size: 354 bytes --]


Hmm, wrong MIME type for the attachment (video/dv?). Reposting it
properly.  Sorry for the noise.

Jerome Guitton (guitton@adacore.com):

> 2009-01-14  Jerome Guitton  <guitton@adacore.com>
> 
> 	* symtab.c (lookup_partial_symtab): When looking up an absolute path
> 	in the partial symtabs, compare the base names before checking the
> 	full names.




[-- Attachment #2: lookup_partial_symtab.diff --]
[-- Type: text/x-diff, Size: 2388 bytes --]

Index: symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.200
diff -u -p -r1.200 symtab.c
--- symtab.c	3 Jan 2009 05:57:53 -0000	1.200
+++ symtab.c	14 Jan 2009 17:10:27 -0000
@@ -281,8 +281,48 @@ lookup_partial_symtab (const char *name)
       }
 
     /* If the user gave us an absolute path, try to find the file in
-       this symtab and use its absolute path.  */
-    if (full_path != NULL)
+       this symtab and use its absolute path. 
+
+       psymtab_to_fullname has a significant cost as it calls
+       find_and_open_source, which itself does some I/O operation
+       (e.g. open). In cumulative, it can take several seconds with
+       large systems (around 4000 files), if the file is accessed
+       through a slow file system (e.g. NFS). Here is a shell script
+       that you can use to generate such a large system:
+
+       echo "void main () {}" > t.c
+       gcc -c -g t.c
+       previous=""
+       for i in 0 1 2 3 ; do
+	  for j in 0 1 2 3 4 5 6 7 8 9 ; do
+	     for k in 0 1 2 3 4 5 6 7 8 9 ; do
+		for l in 0 1 2 3 4 5 6 7 8 9 ; do
+		   name="${i}${j}${k}${l}"
+		   echo "void f_$name () {}" >> f_$name.c
+		   gcc -c -g f_$name.c
+		   ld -r  f_$name.o $previous -o main_$name
+		   rm f_*.o
+		   rm $previous
+		   previous=main_$name
+		done
+	    done
+	  done
+       done
+       gcc $previous t.o -o main
+
+       Using the following GDB commands should demonstrate the problem:
+       list <working directory>/f_0000.c:1
+       list <working directory>/f_3999.c:1
+
+       To reduce the cost, the full comparison is done if and only if
+       the base names are not different. This would have a low cost,
+       as it only does string manipulations. This optimisation has no
+       impact on relatives path (e.g. the more common 'list
+       f_0000.c:1'), as in this case full_path == NULL.  */
+
+    if (full_path != NULL
+	&& FILENAME_CMP (lbasename (full_path),
+			 lbasename (pst->filename)) == 0)
       {
 	psymtab_to_fullname (pst);
 	if (pst->fullname != NULL
@@ -292,7 +332,9 @@ lookup_partial_symtab (const char *name)
 	  }
       }
 
-    if (real_path != NULL)
+    if (real_path != NULL
+	&& FILENAME_CMP (lbasename (full_path),
+			 lbasename (pst->filename)) == 0)
       {
         char *rp = NULL;
 	psymtab_to_fullname (pst);

Re: [Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Joel Brobecker]

> > 2009-01-14  Jerome Guitton  <guitton@adacore.com>
> > 
> > 	* symtab.c (lookup_partial_symtab): When looking up an absolute path
> > 	in the partial symtabs, compare the base names before checking the
> > 	full names.

We're only 3.5 months late reviewing this patch :-(... This looks OK
to me. I verified that this cannot create behavior changes due to
find_and_open_source returning a fullname with a different basename
(for instance if the source file was actually a link to another source
file): openp only canonicalizes the directory portion of the fullname.

So I think this is reasonable. Please go ahead and commit.

-- 
Joel

Re: [Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Joel Brobecker]

> +       psymtab_to_fullname has a significant cost as it calls
> +       find_and_open_source, which itself does some I/O operation
> +       (e.g. open). In cumulative, it can take several seconds with
> +       large systems (around 4000 files), if the file is accessed
> +       through a slow file system (e.g. NFS). Here is a shell script
> +       that you can use to generate such a large system:

I forgot to mention: Double-space after a period :). There's a couple
of places where you used a single space.

Cheers,
-- 
Joel

Re: [Bug symtab/8367] [RFA] performance improvement of lookup_partial_symtab

[Jerome Guitton]

Joel Brobecker (brobecker@adacore.com):

> > > 2009-01-14  Jerome Guitton  <guitton@adacore.com>
> > > 
> > > 	* symtab.c (lookup_partial_symtab): When looking up an absolute path
> > > 	in the partial symtabs, compare the base names before checking the
> > > 	full names.
> 
> We're only 3.5 months late reviewing this patch :-(... This looks OK
> to me. I verified that this cannot create behavior changes due to
> find_and_open_source returning a fullname with a different basename
> (for instance if the source file was actually a link to another source
> file): openp only canonicalizes the directory portion of the fullname.
> 
> So I think this is reasonable. Please go ahead and commit.


There has been an alternative patch for the same problem, submitted here:

http://sourceware.org/ml/gdb-patches/2009-03/msg00309.html

François' patch should handle one more problem (files can be the same
even if basenames differs). So I prefer his approach. I think there's
still some paperwork to be done before we can merge his changes into
GDB (copyright assignment), but I guess that it will happen at some
point in the future. If not, I will modify my patch to take the link
problem into account.