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

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

[Paul Pluzhnikov]

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

On Tue, May 12, 2009 at 2:10 AM, Joel Brobecker <brobecker@adacore.com> wrote:

> 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've slightly reworded and added this. Thanks.

> 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?

Yes, I tested with objc-enabled gcc. Here are results from current
CVS Head:

$ grep '\.objc' gdb.sum
Running ../../../gdb/testsuite/gdb.objc/basicclass.exp ...
PASS: gdb.objc/basicclass.exp: successfully compiled objc with posix
threads test case
PASS: gdb.objc/basicclass.exp: deduced language is Objective-C, before
full symbols
PASS: gdb.objc/basicclass.exp: deduced language is Objective-C, after
full symbols
PASS: gdb.objc/basicclass.exp: breakpoint method
PASS: gdb.objc/basicclass.exp: breakpoint method with colon
PASS: gdb.objc/basicclass.exp: breakpoint class method with colon
PASS: gdb.objc/basicclass.exp: continue until method breakpoint
PASS: gdb.objc/basicclass.exp: resetting breakpoints when rerunning
PASS: gdb.objc/basicclass.exp: continue until method breakpoint
PASS: gdb.objc/basicclass.exp: print an ivar of self
PASS: gdb.objc/basicclass.exp: print self
PASS: gdb.objc/basicclass.exp: print contents of self
PASS: gdb.objc/basicclass.exp: breakpoint in category method
PASS: gdb.objc/basicclass.exp: continue until category method
PASS: gdb.objc/basicclass.exp: Call an Objective-C method with no arguments
PASS: gdb.objc/basicclass.exp: Call an Objective-C method with one argument
PASS: gdb.objc/basicclass.exp: Use of the print-object command
PASS: gdb.objc/basicclass.exp: Use of the po (print-object) command
Running ../../../gdb/testsuite/gdb.objc/nondebug.exp ...
PASS: gdb.objc/nondebug.exp: successfully compiled objc with posix
threads test case
KFAIL: gdb.objc/nondebug.exp: break on non-debuggable method (PRMS: gdb/1236)
Running ../../../gdb/testsuite/gdb.objc/objcdecode.exp ...
PASS: gdb.objc/objcdecode.exp: successfully compiled objc with posix
threads test case
PASS: gdb.objc/objcdecode.exp: break on multiply defined method
FAIL: gdb.objc/objcdecode.exp: continue after break on multiply
defined symbol (GDB internal error)

No changes after the patch.

Here is 'diff -w' again:

diff --git a/gdb/objc-lang.c b/gdb/objc-lang.c
index 9b8d801..aa55baf 100644
--- a/gdb/objc-lang.c
+++ b/gdb/objc-lang.c
@@ -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,23 @@ find_methods (struct symtab *symtab, char type,
   if (symtab)
     block = BLOCKVECTOR_BLOCK (BLOCKVECTOR (symtab), STATIC_BLOCK);

-  ALL_MSYMBOLS (objfile, msymbol)
+  ALL_OBJFILES (objfile)
+    {
+      unsigned int *objc_csym;
+
+      /* The objfile_csym variable counts the number of ObjC methods
+	 that this objfile defines.  We save that count as a private
+	 objfile data.	If we have already determined that this objfile
+	 provides no ObjC methods, we can skip it entirely.  */
+
+      unsigned int objfile_csym = 0;
+
+      objc_csym = objfile_data (objfile, objc_objfile_data);
+      if (objc_csym != NULL && *objc_csym == 0)
+	/* There are no ObjC symbols in this objfile.  Skip it entirely.  */
+	continue;
+
+      ALL_OBJFILE_MSYMBOLS (objfile, msymbol)
     {
       QUIT;

@@ -1187,6 +1205,8 @@ find_methods (struct symtab *symtab, char type,
       if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
 	continue;

+	  objfile_csym++;
+
       if ((type != '\0') && (ntype != type))
 	continue;

@@ -1237,6 +1257,16 @@ find_methods (struct symtab *symtab, char type,
 	  csym++;
 	}
     }
+      if (objc_csym == NULL)
+	{
+	  objc_csym = xmalloc (sizeof (*objc_csym));
+	  *objc_csym = objfile_csym;
+	  set_objfile_data (objfile, objc_objfile_data, objc_csym);
+	}
+      else
+	/* Count of ObjC methods in this objfile should be constant.  */
+	gdb_assert (*objc_csym == objfile_csym);
+    }

   if (nsym != NULL)
     *nsym = csym;
@@ -1792,3 +1822,9 @@ resolve_msgsend_super_stret (CORE_ADDR pc,
CORE_ADDR *new_pc)
     return 1;
   return 0;
 }
+
+void
+_initialize_objc_lang (void)
+{
+  objc_objfile_data = register_objfile_data ();
+}


OK to commit?

Thanks,
-- 
Paul Pluzhnikov

2009-05-12  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.

[-- Attachment #2: gdb-objc-20090512.txt --]
[-- Type: text/plain, Size: 6086 bytes --]

diff --git a/gdb/objc-lang.c b/gdb/objc-lang.c
index 9b8d801..aa55baf 100644
--- a/gdb/objc-lang.c
+++ b/gdb/objc-lang.c
@@ -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,88 +1156,116 @@ find_methods (struct symtab *symtab, char type,
   if (symtab)
     block = BLOCKVECTOR_BLOCK (BLOCKVECTOR (symtab), STATIC_BLOCK);
 
-  ALL_MSYMBOLS (objfile, msymbol)
+  ALL_OBJFILES (objfile)
     {
-      QUIT;
+      unsigned int *objc_csym;
 
-      if ((MSYMBOL_TYPE (msymbol) != mst_text)
-	  && (MSYMBOL_TYPE (msymbol) != mst_file_text))
-	/* Not a function or method.  */
-	continue;
+      /* The objfile_csym variable counts the number of ObjC methods
+	 that this objfile defines.  We save that count as a private
+	 objfile data.	If we have already determined that this objfile
+	 provides no ObjC methods, we can skip it entirely.  */
 
-      if (symtab)
-	if ((SYMBOL_VALUE_ADDRESS (msymbol) <  BLOCK_START (block)) ||
-	    (SYMBOL_VALUE_ADDRESS (msymbol) >= BLOCK_END (block)))
-	  /* Not in the specified symtab.  */
-	  continue;
+      unsigned int objfile_csym = 0;
 
-      symname = SYMBOL_NATURAL_NAME (msymbol);
-      if (symname == NULL)
+      objc_csym = objfile_data (objfile, objc_objfile_data);
+      if (objc_csym != NULL && *objc_csym == 0)
+	/* There are no ObjC symbols in this objfile.  Skip it entirely.  */
 	continue;
 
-      if ((symname[0] != '-' && symname[0] != '+') || (symname[1] != '['))
-	/* Not a method name.  */
-	continue;
-      
-      while ((strlen (symname) + 1) >= tmplen)
+      ALL_OBJFILE_MSYMBOLS (objfile, msymbol)
 	{
-	  tmplen = (tmplen == 0) ? 1024 : tmplen * 2;
-	  tmp = xrealloc (tmp, tmplen);
-	}
-      strcpy (tmp, symname);
+	  QUIT;
 
-      if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
-	continue;
+	  if ((MSYMBOL_TYPE (msymbol) != mst_text)
+	      && (MSYMBOL_TYPE (msymbol) != mst_file_text))
+	    /* Not a function or method.  */
+	    continue;
+
+	  if (symtab)
+	    if ((SYMBOL_VALUE_ADDRESS (msymbol) <  BLOCK_START (block)) ||
+		(SYMBOL_VALUE_ADDRESS (msymbol) >= BLOCK_END (block)))
+	      /* Not in the specified symtab.  */
+	      continue;
+
+	  symname = SYMBOL_NATURAL_NAME (msymbol);
+	  if (symname == NULL)
+	    continue;
+
+	  if ((symname[0] != '-' && symname[0] != '+') || (symname[1] != '['))
+	    /* Not a method name.  */
+	    continue;
       
-      if ((type != '\0') && (ntype != type))
-	continue;
+	  while ((strlen (symname) + 1) >= tmplen)
+	    {
+	      tmplen = (tmplen == 0) ? 1024 : tmplen * 2;
+	      tmp = xrealloc (tmp, tmplen);
+	    }
+	  strcpy (tmp, symname);
 
-      if ((class != NULL) 
-	  && ((nclass == NULL) || (strcmp (class, nclass) != 0)))
-	continue;
+	  if (parse_method (tmp, &ntype, &nclass, &ncategory, &nselector) == NULL)
+	    continue;
+      
+	  objfile_csym++;
 
-      if ((category != NULL) && 
-	  ((ncategory == NULL) || (strcmp (category, ncategory) != 0)))
-	continue;
+	  if ((type != '\0') && (ntype != type))
+	    continue;
 
-      if ((selector != NULL) && 
-	  ((nselector == NULL) || (strcmp (selector, nselector) != 0)))
-	continue;
+	  if ((class != NULL) 
+	      && ((nclass == NULL) || (strcmp (class, nclass) != 0)))
+	    continue;
+
+	  if ((category != NULL) && 
+	      ((ncategory == NULL) || (strcmp (category, ncategory) != 0)))
+	    continue;
 
-      sym = find_pc_function (SYMBOL_VALUE_ADDRESS (msymbol));
-      if (sym != NULL)
-        {
-          const char *newsymname = SYMBOL_NATURAL_NAME (sym);
+	  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);
 	  
-          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);
 	}
+      else
+	/* Count of ObjC methods in this objfile should be constant.  */
+	gdb_assert (*objc_csym == objfile_csym);
     }
 
   if (nsym != NULL)
@@ -1792,3 +1822,9 @@ resolve_msgsend_super_stret (CORE_ADDR pc, CORE_ADDR *new_pc)
     return 1;
   return 0;
 }
+
+void
+_initialize_objc_lang (void)
+{
+  objc_objfile_data = register_objfile_data ();
+}

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

[Joel Brobecker]

(thanks for posting the results for ObjC)

> 2009-05-12  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.

> OK to commit?

Yep :)


-- 
Joel

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

[Paul Pluzhnikov]

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

On Fri, May 1, 2009 at 3:16 PM, Paul Pluzhnikov <ppluzhnikov@google.com> wrote:

> 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

Even after the two patches above, there is still some repeated
and unnecessary setting and resetting of the breakpoints as each
solib is added :-(

Attached is an alternative patch which subsumes the other two,
and kills additional 15% of wasted CPU time.

It feels like a hack, but I don't see how to achieve the same
result in a cleaner way :-(

Timing on my 2780-solib test (just running ldd on that takes 15s):

time gdb -ex 'break main' -ex run -ex kill -ex quit request_test

=== current CVS Head ===
real    11m16.762s
user    11m5.530s
sys     0m9.697s

=== with attached patch ===
real    2m43.595s
user    2m33.350s
sys     0m9.353s

Tested on Linux/x86_64 without regressions.

Comments?
--
Paul Pluzhnikov

[-- Attachment #2: gdb-breakpoint-20090505.txt --]
[-- Type: text/plain, Size: 2309 bytes --]

? foof.12580
Index: breakpoint.c
===================================================================
RCS file: /cvs/src/src/gdb/breakpoint.c,v
retrieving revision 1.393
diff -u -p -u -r1.393 breakpoint.c
--- breakpoint.c	5 May 2009 13:24:48 -0000	1.393
+++ breakpoint.c	6 May 2009 00:46:59 -0000
@@ -72,6 +72,9 @@
 #define CATCH_PERMANENT ((void *) (uintptr_t) 0)
 #define CATCH_TEMPORARY ((void *) (uintptr_t) 1)
 
+/* If non-zero, breakpoin_re_set() is a no-op.  */
+int suppress_breakpoint_reset;
+
 /* Prototypes for local functions. */
 
 static void enable_delete_command (char *, int);
@@ -7723,6 +7726,9 @@ breakpoint_re_set (void)
   enum language save_language;
   int save_input_radix;
 
+  if (suppress_breakpoint_reset)
+    return;
+
   save_language = current_language->la_language;
   save_input_radix = input_radix;
   ALL_BREAKPOINTS_SAFE (b, temp)
Index: breakpoint.h
===================================================================
RCS file: /cvs/src/src/gdb/breakpoint.h,v
retrieving revision 1.90
diff -u -p -u -r1.90 breakpoint.h
--- breakpoint.h	31 Mar 2009 16:44:17 -0000	1.90
+++ breakpoint.h	6 May 2009 00:46:59 -0000
@@ -669,6 +669,8 @@ enum breakpoint_here
     permanent_breakpoint_here
   };
 \f
+/* If non-zero, breakpoin_re_set() is a no-op.  */
+extern int suppress_breakpoint_reset;
 
 /* Prototypes for breakpoint-related functions.  */
 
Index: solib.c
===================================================================
RCS file: /cvs/src/src/gdb/solib.c,v
retrieving revision 1.115
diff -u -p -u -r1.115 solib.c
--- solib.c	9 Mar 2009 22:38:37 -0000	1.115
+++ solib.c	6 May 2009 00:46:59 -0000
@@ -738,6 +738,9 @@ solib_add (char *pattern, int from_tty, 
     int any_matches = 0;
     int loaded_any_symbols = 0;
 
+    /* Delay resetting breakpoints until after we added all solibs.  */
+    suppress_breakpoint_reset += 1;
+
     for (gdb = so_list_head; gdb; gdb = gdb->next)
       if (! pattern || re_exec (gdb->so_name))
 	{
@@ -754,6 +757,10 @@ solib_add (char *pattern, int from_tty, 
 	    loaded_any_symbols = 1;
 	}
 
+    suppress_breakpoint_reset -= 1;
+    if (loaded_any_symbols)
+      breakpoint_re_set ();
+
     if (from_tty && pattern && ! any_matches)
       printf_unfiltered
 	("No loaded shared libraries match the pattern `%s'.\n", pattern);

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

[Joel Brobecker]

> Even after the two patches above, there is still some repeated
> and unnecessary setting and resetting of the breakpoints as each
> solib is added :-(
> 
> Attached is an alternative patch which subsumes the other two,
> and kills additional 15% of wasted CPU time.
> 
> It feels like a hack, but I don't see how to achieve the same
> result in a cleaner way :-(

I haven't had a chance to look at the other patch, but, yeah,
it does feel like a hack! :-/.

But I'm sympathetic to the issue - it's tough to have to wait
an extra 20secs when you know that you don't have any breakpoint
refering to any SO... My thoughts on this: Perhaps a setting
in the "maintenance set/show" that the user could change to deactivate
breakpoint reset.  The default is the current behavior, but if the user
knows what he's doing, he can change it. Not sure what the other
maintainers think about that. Horrible, but better than nothing.

That being said, I still think we should try to do as good a job
as we can automatically, so your first suggestion should also be
incorporated.

-- 
Joel

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

[Paul Pluzhnikov]

On Tue, May 12, 2009 at 1:25 AM, Joel Brobecker <brobecker@adacore.com> wrote:

>> It feels like a hack, but I don't see how to achieve the same
>> result in a cleaner way :-(
>
> But I'm sympathetic to the issue - it's tough to have to wait
> an extra 20secs

Or extra 2 minutes in my case :-(

> when you know that you don't have any breakpoint
> refering to any SO... My thoughts on this: Perhaps a setting
> in the "maintenance set/show" that the user could change to deactivate
> breakpoint reset.

Note that the gdb-breakpoint-20090505.txt patch did not deactivate
breakpoint reset. It merely turned an O(N*N) operation into O(N)
operation, by resetting breakpoints once, after all solib symbols
have been loaded.

Because of that, your "maintenance set ..." suggestion doesn't
make sense to me: why would you ever want O(N*N) algorithm when an
O(N) one is available?

Thanks,
-- 
Paul Pluzhnikov

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

[Joel Brobecker]

> Because of that, your "maintenance set ..." suggestion doesn't
> make sense to me: why would you ever want O(N*N) algorithm when an
> O(N) one is available?

There was a communication issue somewhere. I didn't suggest that
we should keep the O(N*N) algorithm. The command was on top of already
having the O(N) approach...

-- 
Joel

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

[Paul Pluzhnikov]

On Wed, May 13, 2009 at 2:27 AM, Joel Brobecker <brobecker@adacore.com> wrote:

>> Because of that, your "maintenance set ..." suggestion doesn't
>> make sense to me: why would you ever want O(N*N) algorithm when an
>> O(N) one is available?
>
> There was a communication issue somewhere. I didn't suggest that
> we should keep the O(N*N) algorithm. The command was on top of already
> having the O(N) approach...

Ah, sorry I misunderstood you.

To summarize, there are 4 separate changes flying around:

1. The "don't rescan all objfiles over and over looking for ObjC
   methods" patch here:
   http://sourceware.org/ml/gdb-patches/2009-05/msg00253.html

   I just committed that.

2. The "don't rescan all objfiles over and
   over looking for _ovly_debug_event" patch here:
   http://sourceware.org/ml/gdb-patches/2009-05/msg00255.html

   This patch is "ready to commit"; not sure if I need any further
   approvals for it.

3. The "don't reset all breakpoints over and over when adding
   multiple solibs" patch here:
   http://sourceware.org/ml/gdb-patches/2009-05/msg00097.html

   This patch feels like a hack, but does save significant additional
   CPU cycles (even after patches #1 and #2 above) and transforms
   breakpoint reset operation from O(N*N) into O(N) where N is the
   number of solibs added "at once" (such as at program startup). It
   is not clear how to make this less of a hack :-(

4. Joel's proposal (if I understood it correctly) to extend patch#3
   above to add external control of the suppress_breakpoint_reset
   variable via "maintenance set/show breakpoint-reset" or some such.

   This would allow advanced users to turn off breakpoint reset
   even in cases not addressed by patch#3, but they should really
   know what they are doing.

   Once could easily imagine such a scenario: a program that
   dlopen()s 1000s of solibs in sequence. You'd then turn off
   breakpoint reset for all but the very last solib. But I can't
   imagine a real program actually doing this.

Thanks,
-- 
Paul Pluzhnikov

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

[Joel Brobecker]

> 3. The "don't reset all breakpoints over and over when adding
>    multiple solibs" patch here:
>    http://sourceware.org/ml/gdb-patches/2009-05/msg00097.html
> 
>    This patch feels like a hack, but does save significant additional
>    CPU cycles (even after patches #1 and #2 above) and transforms
>    breakpoint reset operation from O(N*N) into O(N) where N is the
>    number of solibs added "at once" (such as at program startup). It
>    is not clear how to make this less of a hack :-(

I completely misunderstood this change you proposed! I see now what
you are doing. This wouldn't help on systems such as Windows where
DLLs are "discovered" through special events while waiting for inferior
events.  So shared libraries are never loaded at once, neither during
startup or attaching.  But on GNU/Linux, however, you're right, there
is something to do in that case.

I'd like to think about it, for a while... I wonder if we could use
an observer to notify clients that symbols have been loaded, rather
than calling breakpoint_re_set directly.

> 4. Joel's proposal (if I understood it correctly) to extend patch#3

This proposal was a direct consequence of my misunderstanding. It might
still have some merit on its own, but I don't think it is necessary
(I thought that your change could cause incorrect behavior).

-- 
Joel

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

[Paul Pluzhnikov]

On Thu, May 14, 2009 at 1:14 AM, Joel Brobecker <brobecker@adacore.com> wrote:

>> 3. The "don't reset all breakpoints over and over when adding
>>    multiple solibs" patch here:

> I completely misunderstood this change you proposed! I see now what
> you are doing. This wouldn't help on systems such as Windows where
> DLLs are "discovered" through special events while waiting for inferior
> events.  So shared libraries are never loaded at once, neither during
> startup or attaching.

Right. So Windows behaves as a program that dlopen()s all of
its DLLs in sequence.

> But on GNU/Linux, however, you're right, there
> is something to do in that case.
>
> I'd like to think about it, for a while... I wonder if we could use
> an observer to notify clients that symbols have been loaded, rather
> than calling breakpoint_re_set directly.

This (I think) would effectively achieve the same result as patch#2,
calling breakpoint_re_set only for individual solib.

[BTW, is it ok to commit patch#2 ?]

The problem is that breakpoint_re_set does a bunch of unnecessary
work, even when it knows which solib it should be dealing with.
In particular, for each breakpoint, it re-parses its addr_string,
selects correct address (possibly skipping function prolog, etc.).

When 'break main' is in effect, this one breakpoint's addr_string
is parsed N times, main is looked up N times, main's prolog is
skipped N times, etc. etc. This isn't quadratic, but accounts for
~15% of startup time, and adds up to minutes or large N.

I see that my comment about patch#3 transforming O(N*N) into O(N)
is correct only if patches #1 and #2 aren't applied. If they are
applied, then (I believe) patch#3 transforms O(N*M) into O(M), where
N is the number of solibs added "at once" and M is the number of
current breakpoints.

Thanks,
-- 
Paul Pluzhnikov

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

[Joel Brobecker]

I'll look at the rest of the email tomorrow morning, but in the meantime...

> [BTW, is it ok to commit patch#2 ?]

http://sourceware.org/ml/gdb-patches/2009-05/msg00265.html.
Perhaps my answer was too equivocal? In any case, I confirm that
this is OK, just remove the empty lines in your ChangeLog entry.
(no need to request approval again, this is only a CL entry after all)

Cheers,
-- 
Joel

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

[Paul Pluzhnikov]

On Thu, May 14, 2009 at 12:23 PM, Joel Brobecker <brobecker@adacore.com> wrote:

>> [BTW, is it ok to commit patch#2 ?]
>
> http://sourceware.org/ml/gdb-patches/2009-05/msg00265.html.
> Perhaps my answer was too equivocal? In any case, I confirm that
> this is OK, just remove the empty lines in your ChangeLog entry.
> (no need to request approval again, this is only a CL entry after all)

Thanks, this part is committed.
-- 
Paul Pluzhnikov

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

[Paul Pluzhnikov]

On Thu, May 21, 2009 at 8:15 AM, Joel Brobecker <brobecker@adacore.com> wrote:

> I lost track a little. Are there still some patches pending review
> in this series?

Yes, the "hacky patch":
  http://sourceware.org/ml/gdb-patches/2009-05/msg00097.html
saves additional 15% of CPU, because it avoids resetting the breakpoint
on every solib addition, when many solibs are added "at once" (this happens
at program startup/attach on UNIXen, but not on Windows).

Resetting a breakpoint involves non-trivial amount of computation:
bp->addr_string is re-parsed, symbol is looked up, sal's are evaluated, and
finally the breakpoint (on main) is reset to exactly the same location it
were before :-(

I am not happy with the "hackiness" of this patch, but don't see how to
fix this better.

Thanks,
-- 
Paul Pluzhnikov

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

[Joel Brobecker]

> I am not happy with the "hackiness" of this patch, but don't see how to
> fix this better.

Yeah, I'm also very uncomfortable with this change but I don't see
a better solution yet either. One of the issues is that I don't like
globals, because I know they're probably going to be a pain to deal with
multi-process (althought I wonder if that part can easily be dealt with
by putting it in struct inferior).

I'd really like it to be approved by more than just me before
it goes in. I can't propose anything better at the moment, so I won't
object. Can you lobby some of the other global maintainers to take
a look?

-- 
Joel

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

[Tom Tromey]

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

Paul> The problem is that breakpoint_re_set does a bunch of unnecessary
Paul> work, even when it knows which solib it should be dealing with.

What happens if we change this?

I'm wondering about something like updating only the pending
breakpoints when we read a new objfile for an existing inferior.
Would this break something?  If not, wouldn't it also fix your
situation?

Tom

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

[Tom Tromey]

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

Paul> Attached is an alternative patch which subsumes the other two,
Paul> and kills additional 15% of wasted CPU time.
Paul> It feels like a hack, but I don't see how to achieve the same
Paul> result in a cleaner way :-(

I think the idea is sound: defer some updates until after a batch of
updates has gone through.

The problem is the implementation -- adding a new global is ugly.
But, it seems to me that it would not be too hard to add a new flag
argument to the call chain here.  This would be a bit ad hoc, but so
what?

Tom

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

[Paul Pluzhnikov]

On Fri, May 29, 2009 at 6:59 PM, Tom Tromey <tromey@redhat.com> wrote:

> Paul> It feels like a hack, but I don't see how to achieve the same
> Paul> result in a cleaner way :-(
>
> I think the idea is sound: defer some updates until after a batch of
> updates has gone through.
>
> The problem is the implementation -- adding a new global is ugly.
> But, it seems to me that it would not be too hard to add a new flag
> argument to the call chain here.  This would be a bit ad hoc, but so
> what?

The problem is that the call chain is deep:

Breakpoint 1, breakpoint_re_set_objfile (objfile=0xd57fe0) at
../../src/gdb/breakpoint.c:7754
7754    {
(top) bt
#0  breakpoint_re_set_objfile (objfile=0xd57fe0)
    at ../../src/gdb/breakpoint.c:7754
#1  0x00000000004e3487 in new_symfile_objfile (objfile=0xd57fe0,
    mainline=0, verbo=0) at ../../src/gdb/symfile.c:924
#2  0x00000000004e360e in symbol_file_add_with_addrs_or_offsets (
    abfd=0xddc420, from_tty=0, addrs=0xddd700, offsets=0x0,
    num_offsets=0, mainline=0, flags=<value optimized out>)
    at ../../src/gdb/symfile.c:1084
#3  0x00000000004e3ee5 in symbol_file_add_from_bfd (abfd=0xd57fe0,
    from_tty=0, addrs=0x0, mainline=0, flags=<value optimized out>)
    at ../../src/gdb/symfile.c:1103
#4  0x00000000004e3812 in symbol_file_add_with_addrs_or_offsets (
    abfd=<value optimized out>, from_tty=0, addrs=0xa62410,
    offsets=0x0, num_offsets=0, mainline=0,
    flags=<value optimized out>) at ../../src/gdb/symfile.c:1033
#5  0x00000000004e3ee5 in symbol_file_add_from_bfd (abfd=0xd57fe0,
    from_tty=0, addrs=0x0, mainline=0, flags=<value optimized out>)
    at ../../src/gdb/symfile.c:1103
#6  0x0000000000462070 in symbol_add_stub (arg=<value optimized out>)
    at ../../src/gdb/solib.c:470
#7  0x00000000004fdf8b in catch_errors (
    func=0x461ff0 <symbol_add_stub>, func_args=0xae7a10,
    errstring=0x658e68 "Error while reading shared library
symbols:\n", mask=<value optimized out>) at
../../src/gdb/exceptions.c:510
#8  0x0000000000461dd1 in solib_read_symbols (so=0x0, from_tty=0)
    at ../../src/gdb/solib.c:496
#9  0x0000000000462623 in solib_add (pattern=0x0, from_tty=0,
    target=<value optimized out>, readsyms=1)
    at ../../src/gdb/solib.c:752

We know we should defer breakpoint_re_set in frame #9.
We want to "telegraph" that message into frame #1.
But how?

On Fri, May 29, 2009 at 7:05 PM, Tom Tromey <tromey@redhat.com> wrote:

> Paul> The problem is that breakpoint_re_set does a bunch of unnecessary
> Paul> work, even when it knows which solib it should be dealing with.
>
> What happens if we change this?
>
> I'm wondering about something like updating only the pending
> breakpoints when we read a new objfile for an existing inferior.
> Would this break something?  If not, wouldn't it also fix your
> situation?

At process startup, with the breakpoint on '_exit', you'll have:

(top) p *b
$11 = {next = 0x0, type = bp_breakpoint, enable_state = bp_enabled,
  disposition = disp_donttouch, number = 2, loc = 0x2c2f390,
  line_number = 29,
  source_file = 0x2596510 "../sysdeps/unix/sysv/linux/_exit.c",
  ...
  addr_string = 0x1ea9fc0 "_exit", language = language_cplus,
...
(top) p *b.loc
$12 = {next = 0x0, global_next = 0x0,
  loc_type = bp_loc_software_breakpoint, owner = 0x2c2f260,
  cond = 0x0, shlib_disabled = 1 '\001', enabled = 1 '\001',
...

So the b->loc.shlib_disabled makes this breakpoint "pending".

Since any library could define _exit, we need to see if the current objfile
does (it will not). Repeat for next objfile, etc. until we reach all the
way to libc. To add insult to injury, current objfile is not propagated
into decode_line_1, so it does symbol lookup in all psymtabs, making this
quadratic on number of solibs. Propagating current objfile down another
10 levels of call stack:

#0  lookup_symbol_aux_psymtabs (block_index=0,
    name=0x7fffffffcf40 "_exit", linkage_name=0x0, domain=VAR_DOMAIN)
    at ../../src/gdb/symtab.c:1525
#1  0x000000000058044a in lookup_symbol_file (
    name=0x7fffffffcf40 "_exit", linkage_name=0x0, block=0x0,
    domain=VAR_DOMAIN, anonymous_namespace=0)
    at ../../src/gdb/cp-namespace.c:450
#2  0x0000000000580581 in cp_lookup_symbol_namespace (
    namespace=0x7fffffffce70 "", name=0x7fffffffcf40 "_exit",
    linkage_name=0x0, block=0x0, domain=VAR_DOMAIN)
    at ../../src/gdb/cp-namespace.c:401
#3  0x000000000058076c in lookup_namespace_scope (
    name=0x7fffffffcf40 "_exit", linkage_name=0x0, block=0x0,
    domain=VAR_DOMAIN, scope=0x65ead0 "",
    scope_len=<value optimized out>)
    at ../../src/gdb/cp-namespace.c:357
#4  0x00000000004ddad3 in lookup_symbol_in_language (
    name=0x7fffffffcf40 "_exit", block=0x0, domain=VAR_DOMAIN,
    lang=language_cplus, is_a_field_of_this=0x0)
    at ../../src/gdb/symtab.c:1345
#5  0x0000000000558f20 in find_imps (symtab=0x0, block=0x0,
    method=0x1ea9fc0 "_exit", syms=0x0, nsym=0x7fffffffd05c,
    ndebug=0x7fffffffd058) at ../../src/gdb/objc-lang.c:1319
#6  0x00000000004e702c in decode_objc (argptr=0x7fffffffd288,
    funfirstline=1, file_symtab=0x0, canonical=0x0,
    saved_arg=<value optimized out>) at ../../src/gdb/linespec.c:1129
#7  0x00000000004e85f3 in decode_line_1 (argptr=0x7fffffffd288,
    funfirstline=1, default_symtab=0xd2a300, default_line=1347,
    canonical=0x0, not_found_ptr=0x7fffffffd29c)
    at ../../src/gdb/linespec.c:746
#8  0x00000000004b7e5c in breakpoint_re_set_one (
    bint=<value optimized out>) at ../../src/gdb/breakpoint.c:7620
#9  0x00000000004fdf8b in catch_errors (
    func=0x4b7d00 <breakpoint_re_set_one>, func_args=0x2c2f260,
    errstring=0x167bd20 "Error in re-setting breakpoint 2: ",
    mask=<value optimized out>) at ../../src/gdb/exceptions.c:510
#10 0x00000000004bad10 in breakpoint_re_set_objfile (
    objfile=0x2a2ca10) at ../../src/gdb/breakpoint.c:7767

isn't easy either :-(

-- 
Paul Pluzhnikov

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

[Tom Tromey]

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

Paul> The problem is that the call chain is deep:

Yeah, but it can be simplified.

Paul> #3  0x00000000004e3ee5 in symbol_file_add_from_bfd (abfd=0xd57fe0,
Paul>     from_tty=0, addrs=0x0, mainline=0, flags=<value optimized out>)
Paul>     at ../../src/gdb/symfile.c:1103
Paul> #4  0x00000000004e3812 in symbol_file_add_with_addrs_or_offsets (
Paul>     abfd=<value optimized out>, from_tty=0, addrs=0xa62410,
Paul>     offsets=0x0, num_offsets=0, mainline=0,
Paul>     flags=<value optimized out>) at ../../src/gdb/symfile.c:1033
Paul> #5  0x00000000004e3ee5 in symbol_file_add_from_bfd (abfd=0xd57fe0,
Paul>     from_tty=0, addrs=0x0, mainline=0, flags=<value optimized out>)
Paul>     at ../../src/gdb/symfile.c:1103

These are all just forwarding calls, basically overloads.
You could add a new overload just for this purpose.

Paul> #6  0x0000000000462070 in symbol_add_stub (arg=<value optimized out>)
Paul>     at ../../src/gdb/solib.c:470
Paul> #7  0x00000000004fdf8b in catch_errors (
Paul>     func=0x461ff0 <symbol_add_stub>, func_args=0xae7a10,
Paul>     errstring=0x658e68 "Error while reading shared library
Paul> symbols:\n", mask=<value optimized out>) at
Paul> ../../src/gdb/exceptions.c:510

These could be turned into a TRY_CATCH inside solib_read_symbols.
symbol_add_stub is only called from a single place.

Tom