[patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Paul Pluzhnikov]

Greetings,

This is the patch to eliminate repeated iteration over the same objfile
looking for Objective-C methods, as Tom suggested here:
  http://sourceware.org/ml/gdb-patches/2009-04/msg00551.html

Here is the 'diff -w', which is much easier to read due to changed
indentation:


Index: objc-lang.c
===================================================================
RCS file: /cvs/src/src/gdb/objc-lang.c,v
retrieving revision 1.77
diff -u -p -u -w -r1.77 objc-lang.c
--- objc-lang.c	20 Mar 2009 23:04:33 -0000	1.77
+++ objc-lang.c	1 May 2009 21:50:18 -0000
@@ -76,6 +76,8 @@ struct objc_method {
   CORE_ADDR imp;
 };
 
+static const struct objfile_data *objc_objfile_data;
+
 /* Lookup a structure type named "struct NAME", visible in lexical
    block BLOCK.  If NOERR is nonzero, return zero if NAME is not
    suitably defined.  */
@@ -1154,7 +1156,18 @@ find_methods (struct symtab *symtab, cha
   if (symtab)
     block = BLOCKVECTOR_BLOCK (BLOCKVECTOR (symtab), STATIC_BLOCK);
 
-  ALL_MSYMBOLS (objfile, msymbol)
+  ALL_OBJFILES (objfile)
+    {
+      unsigned int *objc_csym;
+      unsigned int objfile_csym = 0;  /* Counts ObjC symbols in this
+					 objfile.  */
+
+      objc_csym = objfile_data (objfile, objc_objfile_data);
+      if (objc_csym != NULL && *objc_csym == 0)
+	/* There are no ObjC symbols in this objfile.  */
+	continue;
+
+      ALL_OBJFILE_MSYMBOLS (objfile, msymbol)
     {
       QUIT;
 
@@ -1187,6 +1200,8 @@ find_methods (struct symtab *symtab, cha
       if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
 	continue;
       
+	  objfile_csym++;
+
       if ((type != '\0') && (ntype != type))
 	continue;
 
@@ -1237,6 +1252,13 @@ find_methods (struct symtab *symtab, cha
 	  csym++;
 	}
     }
+      if (objc_csym == NULL)
+	{
+	  objc_csym = xmalloc (sizeof (*objc_csym));
+	  *objc_csym = objfile_csym;
+	  set_objfile_data (objfile, objc_objfile_data, objc_csym);
+	}
+    }
 
   if (nsym != NULL)
     *nsym = csym;
@@ -1792,3 +1814,9 @@ resolve_msgsend_super_stret (CORE_ADDR p
     return 1;
   return 0;
 }
+
+void
+_initialize_objc_lang (void)
+{
+  objc_objfile_data = register_objfile_data ();
+}

This patch reduces runtime on a test case using 1636 shared libs without
any Objective-C in them from 1105 to 450 seconds.

Tested on Linux/x86_64 with no regressions.

--
Paul Pluzhnikov


2009-05-01  Paul Pluzhnikov  <ppluzhnikov@google.com>

	* objc-lang.c (objc_objfile_data): New variable.
	(find_methods): Skip objfiles without Obj-C methods.
	(_initialize_objc_lang): New function.


Index: objc-lang.c
===================================================================
RCS file: /cvs/src/src/gdb/objc-lang.c,v
retrieving revision 1.77
diff -u -p -u -r1.77 objc-lang.c
--- objc-lang.c	20 Mar 2009 23:04:33 -0000	1.77
+++ objc-lang.c	1 May 2009 21:50:10 -0000
@@ -76,6 +76,8 @@ struct objc_method {
   CORE_ADDR imp;
 };
 
+static const struct objfile_data *objc_objfile_data;
+
 /* Lookup a structure type named "struct NAME", visible in lexical
    block BLOCK.  If NOERR is nonzero, return zero if NAME is not
    suitably defined.  */
@@ -1154,87 +1156,107 @@ find_methods (struct symtab *symtab, cha
   if (symtab)
     block = BLOCKVECTOR_BLOCK (BLOCKVECTOR (symtab), STATIC_BLOCK);
 
-  ALL_MSYMBOLS (objfile, msymbol)
+  ALL_OBJFILES (objfile)
     {
-      QUIT;
-
-      if ((MSYMBOL_TYPE (msymbol) != mst_text)
-	  && (MSYMBOL_TYPE (msymbol) != mst_file_text))
-	/* Not a function or method.  */
+      unsigned int *objc_csym;
+      unsigned int objfile_csym = 0;  /* Counts ObjC symbols in this
+					 objfile.  */
+
+      objc_csym = objfile_data (objfile, objc_objfile_data);
+      if (objc_csym != NULL && *objc_csym == 0)
+	/* There are no ObjC symbols in this objfile.  */
 	continue;
 
-      if (symtab)
-	if ((SYMBOL_VALUE_ADDRESS (msymbol) <  BLOCK_START (block)) ||
-	    (SYMBOL_VALUE_ADDRESS (msymbol) >= BLOCK_END (block)))
-	  /* Not in the specified symtab.  */
-	  continue;
+      ALL_OBJFILE_MSYMBOLS (objfile, msymbol)
+	{
+	  QUIT;
+
+	  if ((MSYMBOL_TYPE (msymbol) != mst_text)
+	      && (MSYMBOL_TYPE (msymbol) != mst_file_text))
+	    /* Not a function or method.  */
+	    continue;
 
-      symname = SYMBOL_NATURAL_NAME (msymbol);
-      if (symname == NULL)
-	continue;
+	  if (symtab)
+	    if ((SYMBOL_VALUE_ADDRESS (msymbol) <  BLOCK_START (block)) ||
+		(SYMBOL_VALUE_ADDRESS (msymbol) >= BLOCK_END (block)))
+	      /* Not in the specified symtab.  */
+	      continue;
 
-      if ((symname[0] != '-' && symname[0] != '+') || (symname[1] != '['))
-	/* Not a method name.  */
-	continue;
+	  symname = SYMBOL_NATURAL_NAME (msymbol);
+	  if (symname == NULL)
+	    continue;
+
+	  if ((symname[0] != '-' && symname[0] != '+') || (symname[1] != '['))
+	    /* Not a method name.  */
+	    continue;
       
-      while ((strlen (symname) + 1) >= tmplen)
-	{
-	  tmplen = (tmplen == 0) ? 1024 : tmplen * 2;
-	  tmp = xrealloc (tmp, tmplen);
-	}
-      strcpy (tmp, symname);
+	  while ((strlen (symname) + 1) >= tmplen)
+	    {
+	      tmplen = (tmplen == 0) ? 1024 : tmplen * 2;
+	      tmp = xrealloc (tmp, tmplen);
+	    }
+	  strcpy (tmp, symname);
 
-      if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
-	continue;
+	  if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
+	    continue;
       
-      if ((type != '\0') && (ntype != type))
-	continue;
+	  objfile_csym++;
 
-      if ((class != NULL) 
-	  && ((nclass == NULL) || (strcmp (class, nclass) != 0)))
-	continue;
+	  if ((type != '\0') && (ntype != type))
+	    continue;
 
-      if ((category != NULL) && 
-	  ((ncategory == NULL) || (strcmp (category, ncategory) != 0)))
-	continue;
+	  if ((class != NULL) 
+	      && ((nclass == NULL) || (strcmp (class, nclass) != 0)))
+	    continue;
 
-      if ((selector != NULL) && 
-	  ((nselector == NULL) || (strcmp (selector, nselector) != 0)))
-	continue;
+	  if ((category != NULL) && 
+	      ((ncategory == NULL) || (strcmp (category, ncategory) != 0)))
+	    continue;
+
+	  if ((selector != NULL) && 
+	      ((nselector == NULL) || (strcmp (selector, nselector) != 0)))
+	    continue;
 
-      sym = find_pc_function (SYMBOL_VALUE_ADDRESS (msymbol));
-      if (sym != NULL)
-        {
-          const char *newsymname = SYMBOL_NATURAL_NAME (sym);
+	  sym = find_pc_function (SYMBOL_VALUE_ADDRESS (msymbol));
+	  if (sym != NULL)
+	    {
+	      const char *newsymname = SYMBOL_NATURAL_NAME (sym);
 	  
-          if (strcmp (symname, newsymname) == 0)
-            {
-              /* Found a high-level method sym: swap it into the
-                 lower part of sym_arr (below num_debuggable).  */
-              if (syms != NULL)
-                {
-                  syms[csym] = syms[cdebug];
-                  syms[cdebug] = sym;
-                }
-              csym++;
-              cdebug++;
-            }
-          else
-            {
-              warning (
+	      if (strcmp (symname, newsymname) == 0)
+		{
+		  /* Found a high-level method sym: swap it into the
+		     lower part of sym_arr (below num_debuggable).  */
+		  if (syms != NULL)
+		    {
+		      syms[csym] = syms[cdebug];
+		      syms[cdebug] = sym;
+		    }
+		  csym++;
+		  cdebug++;
+		}
+	      else
+		{
+		  warning (
 "debugging symbol \"%s\" does not match minimal symbol (\"%s\"); ignoring",
-                       newsymname, symname);
-              if (syms != NULL)
-                syms[csym] = (struct symbol *) msymbol;
-              csym++;
-            }
-        }
-      else 
+                           newsymname, symname);
+		  if (syms != NULL)
+		    syms[csym] = (struct symbol *) msymbol;
+		  csym++;
+		}
+	    }
+	  else
+	    {
+	      /* Found a non-debuggable method symbol.  */
+	      if (syms != NULL)
+		syms[csym] = (struct symbol *) msymbol;
+	      csym++;
+	    }
+	}
+      if (objc_csym == NULL)
 	{
-	  /* Found a non-debuggable method symbol.  */
-	  if (syms != NULL)
-	    syms[csym] = (struct symbol *) msymbol;
-	  csym++;
+	  objc_csym = xmalloc (sizeof (*objc_csym));
+	  *objc_csym = objfile_csym;
+	  set_objfile_data (objfile, objc_objfile_data, objc_csym);
 	}
     }
 
@@ -1792,3 +1814,9 @@ resolve_msgsend_super_stret (CORE_ADDR p
     return 1;
   return 0;
 }
+
+void
+_initialize_objc_lang (void)
+{
+  objc_objfile_data = register_objfile_data ();
+}

Re: [patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Joel Brobecker]

> 2009-05-01  Paul Pluzhnikov  <ppluzhnikov@google.com>
> 
> 	* objc-lang.c (objc_objfile_data): New variable.
> 	(find_methods): Skip objfiles without Obj-C methods.
> 	(_initialize_objc_lang): New function.

Looks good to me. If I may, would you mind adding a comment explaining
*why* you count the number of symbols? I think it can help understanding
the added code a little bit faster...

    /* If we haven't done so for this objfile yet, count the number
       of objc methods that this objfile defines and save it as a private
       objfile data.  That way, if have already determined that this
       objfile provides no objc methods, we can skip it entirely.  */

I wonder how well support for ObjC works. It looks like this file hasn't
really be worked on for a long time... Did you have an objc compiler in
your path when you did the testing, by any chance?

-- 
Joel

Re: [patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Tom Tromey]

>>>>> "Paul" == Paul Pluzhnikov <ppluzhnikov@google.com> writes:

Paul> +	{
Paul> +	  objc_csym = xmalloc (sizeof (*objc_csym));
Paul> +	  *objc_csym = objfile_csym;
Paul> +	  set_objfile_data (objfile, objc_objfile_data, objc_csym);
Paul> +	}

[...]

Paul> +void
Paul> +_initialize_objc_lang (void)
Paul> +{
Paul> +  objc_objfile_data = register_objfile_data ();
Paul> +}

I think this should probably call register_objfile_data_with_cleanup,
so that the per-objfile data can be freed when the objfile is
destroyed.

Tom

Re: [patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Paul Pluzhnikov]

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

On Mon, May 18, 2009 at 2:27 PM, Tom Tromey <tromey@redhat.com> wrote:

> Paul> + {
> Paul> +   objc_csym = xmalloc (sizeof (*objc_csym));
> Paul> +   *objc_csym = objfile_csym;
> Paul> +   set_objfile_data (objfile, objc_objfile_data, objc_csym);
> Paul> + }
>
> [...]
>
> Paul> +void
> Paul> +_initialize_objc_lang (void)
> Paul> +{
> Paul> +  objc_objfile_data = register_objfile_data ();
> Paul> +}
>
> I think this should probably call register_objfile_data_with_cleanup,
> so that the per-objfile data can be freed when the objfile is
> destroyed.

I believe you are correct; I misread the objfile_free_data() code.

But isn't a better fix to just obstack_alloc the data instead of
xmalloc()ing it? Proposed patch attached. Tested on Linux/x86_64, no
regressions.

Thanks,
-- 
Paul Pluzhnikov

2009-05-18  Paul Pluzhnikov  <ppluzhnikov@google.com>

	    * objc-lang.c (find_methods): Plug a small memory leak.

[-- Attachment #2: objc-memleak.txt --]
[-- Type: text/plain, Size: 514 bytes --]

Index: src/gdb/objc-lang.c
===================================================================
--- src.orig/gdb/objc-lang.c	2009-05-18 15:01:25.000000000 -0700
+++ src/gdb/objc-lang.c	2009-05-18 14:53:58.000000000 -0700
@@ -1259,7 +1259,8 @@
 	}
       if (objc_csym == NULL)
 	{
-	  objc_csym = xmalloc (sizeof (*objc_csym));
+	  objc_csym = obstack_alloc (&objfile->objfile_obstack,
+				     sizeof (*objc_csym));
 	  *objc_csym = objfile_csym;
 	  set_objfile_data (objfile, objc_objfile_data, objc_csym);
 	}

Re: [patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Tom Tromey]

>>>>> "Paul" == Paul Pluzhnikov <ppluzhnikov@google.com> writes:

Paul> But isn't a better fix to just obstack_alloc the data instead of
Paul> xmalloc()ing it? Proposed patch attached. Tested on Linux/x86_64, no
Paul> regressions.

Yeah.  I was not completely sure about the rules regarding use of the
objfile obstack.  But, I think this should be safe.  This is ok.

Tom

Re: [patch] Eliminate quadratic slow-down on number of soilibs (part 2).

[Paul Pluzhnikov]

On Mon, May 18, 2009 at 3:48 PM, Tom Tromey <tromey@redhat.com> wrote:

> Yeah.  I was not completely sure about the rules regarding use of the
> objfile obstack.  But, I think this should be safe.  This is ok.

Other parts that use set_objfile_data use obstack_alloc() this way, so I
assume that's fine. I've checked it in.

Thanks,
-- 
Paul Pluzhnikov