This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Convert frame_stash to a hash table


One of the things I have noticed with frame filters is a significant
penalty when printing backtraces.  This is because the frame filters
invalidate the frame_stash.  The reason for this is as follows.

Python frames do not store the GDB frame, nor should they.  If they
did, every time the frame cache is invalidated the Python object would
be pointing to the memory freed by the invalidated frame.  What Python
frames do store is the frame_id.  This is permanent, and allows Python
to fetch the frame on demand.

This on-demand nature is facilitated by a macro in the Python code:

FRAPY_REQUIRE_VALID

which fetches the frame with

frame_find_by_id.

All Python frame functions call this macro, and thus, all Python frame
functions end up using frame_find_by_id before each operation.  That's
fine until you consider that Python frames almost act like a random
access method of fetching frames, and the existing frame_stash being a
single entry stash cannot cope with this.

On single or occasional frame access this is fine and not noticeable.
But on large numbers of sustained frame accesses, like in backtrace,
this performance penalty of searching the frame cache (because the
frame_stash has been invalidated) mounts up and causes a significant
penalty.  Here are some tests from the existing code in GDB:

Test case is 20,000 frames printed in a backtrace.

Before patch, no frame filters.

real	0m3.081s
user	0m1.745s
sys	0m0.435s

Before patch, with frame filters.

real	4m16.094s
user	3m42.718s
sys	0m30.561s

As you can see there is a considerable performance penalty.  With the
patch that converts frame_stash to a hash table, these are the
numbers:

After patch, no frame filters

real	0m3.089s
user	0m1.765s
sys	0m0.414s

After patch, with frame filters

real	0m3.867s
user	0m3.296s
sys	0m0.414s

As you can see, the performance penalty is removed.  The "no frame
filters" timings after the patch do appear to be slightly larger, but,
using "time" is not very deterministic on such small numbers.  I
largely think we can ignore the difference with "no frame filters"
before and after the patch.  However "with frame filters" shows a
massive improvement.

Here are some gprof images that show the profiling statistics of "with
frame filters" before and after the patch:

Before patch:

http://picobot.org/withoutpatch_filters.png

After patch:

http://picobot.org/withpatch_filters.png

(These are large images)

The numbers in the brackets in each box are the important ones to look
at.  Without the patch, GDB spends a large amount of time in
get_prev_frame, which indicates constant hitting of the frame cache.

I think this patch improves the frame_stash "with filters" without 
affecting "no filters" performance.

Tested on x8664 with no regressions.

What do you think?

Cheers,

Phil


2013-05-16  Phil Muldoon  <pmuldoon@redhat.com>

	* frame.c (frame_stash): Convert to htab.
	(frame_addr_hash): New function.
	(frame_addr_hash_eq): New function.
	(frame_stash_create): Convert function to create
	a hash table.
	(frame_stash_add): Convert function to add an entry to a hash
	table.
	(frame_stash_find): Convert function to search the hash table.
	(frame_stash_invalidate): Convert function to empty the hash
	table.
	(get_frame_id): Only add to stash if a frame_id is created.
	(_initialize_frame): Call frame_stash_create.


--
	
Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
diff -u -r1.317 frame.c
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	16 May 2013 12:57:05 -0000
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,101 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  if (! f_id.stack_addr_p && ! f_id.code_addr_p && ! f_id.special_addr)
+    gdb_assert ("Cannot calculate hash for frame_id.");
+
+  if (f_id.stack_addr_p == 1)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p == 1)
+    hash =  iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p == 1)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
 
-/* Add the following FRAME to the frame stash.  */
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
+
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
 
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
 static void
-frame_stash_add (struct frame_info *frame)
+frame_stash_create (void)
 {
-  frame_stash = frame;
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
+static void
+frame_stash_add (struct frame_info *frame)
+{
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      if (*slot != frame)
+	*slot = frame;
+    }
+}
 
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
-
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +409,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2514,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\
--

	


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]