[PATCH] Improve qsort_cmp performance by memoizing objfile data

[Vijay Klein <vijaygk2 at illinois dot edu>]

RATIONALE: The rationale behind this patch is that, currently, the
qsort_cmp function can fall into a default case where it linearly
traverses all the objfiles. Obviously a comparison function running in
linear time causes the sorting function to run in greater than
quadratic time. Thus, memoizing the id (position in the global linked
list) of a given objfile, and updating all the indices only when the
order is explicitly changed, greatly reduces the time for sorting
objfiles and provides a great performance improvement when debugging
programs that link many shared libraries.
Callgrind also revealed that the line that invoked the macro
"obj_section_offset" took an enormous amount of time, due to the
repeated calls to "gdb_bfd_section_index", which can easily be
memoized as the added index field in struct obj_section.

TESTING: Since this change does not add any new functionality, rather
enhancing previous functionality, I did not think adding new tests
were necessary. Regardless, I have run the testsuite locally and
confirmed that the same tests pass after the change as before.

CHANGELOG:

gdb/ChangeLog:

2019-08-16  Vijay Klein  <vijaygk2@illinois.edu>

* gdb/objfiles.c (add_to_objfile_sections_full): Initialize index
field in obj_section.
(objfile::objfile): Initialize id field in objfile.
(update_objfile_ids): New function to relabel objfiles with correct id.
(put_objfile_before): Call update_objfile_ids.
(qsort_cmp): Use index instead of linear traversal in final case.
* gdb/objfiles.h (struct obj_section): Add index field.
(obj_section_offset): Use memoized index.
(struct objfile): Add id field.
(update_objfile_ids): Declare function.


FSF Copyright Assignment: To be completely honest, I'm not entirely
sure what is required here. I designed and wrote the entire change, if
that is relevant. On the contribution checklist, it said the reviewer
would send me the proper form, so all help is appreciated!

From 0d2e989309f8f6fbedfddb8c78c7f108ae92a4ee Mon Sep 17 00:00:00 2001
From: Vijay Klein <vklein@nvidia.com>
Date: Fri, 16 Aug 2019 16:37:58 -0700
Subject: [PATCH] Performace improvement in qsort_cmp

---
 gdb/objfiles.c | 50 ++++++++++++++++++++++++++++++++++++++++++--------
 gdb/objfiles.h | 10 +++++++++-
 2 files changed, 51 insertions(+), 9 deletions(-)

diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index 7cbcbbd01b..e0ec3cc9ee 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -266,6 +266,7 @@ add_to_objfile_sections_full (struct bfd *abfd, struct bfd_section *asect,
 			      struct objfile *objfile, int force)
 {
   struct obj_section *section;
+  int index;
 
   if (!force)
     {
@@ -276,10 +277,12 @@ add_to_objfile_sections_full (struct bfd *abfd, struct bfd_section *asect,
 	return;
     }
 
-  section = &objfile->sections[gdb_bfd_section_index (abfd, asect)];
+  index = gdb_bfd_section_index (abfd, asect);
+  section = &objfile->sections[index];
   section->objfile = objfile;
   section->the_bfd_section = asect;
   section->ovly_mapped = 0;
+  section->index = index;
 }
 
 static void
@@ -375,7 +378,10 @@ objfile::objfile (bfd *abfd, const char *name, objfile_flags flags_)
   /* Add this file onto the tail of the linked list of other such files.  */
 
   if (object_files == NULL)
-    object_files = this;
+    {
+      object_files = this;
+      this->id = 0;
+    }
   else
     {
       struct objfile *last_one;
@@ -384,6 +390,7 @@ objfile::objfile (bfd *abfd, const char *name, objfile_flags flags_)
 	   last_one->next;
 	   last_one = last_one->next);
       last_one->next = this;
+      this->id = last_one->id + 1;
     }
 
   /* Rebuild section map next time we need it.  */
@@ -473,6 +480,33 @@ separate_debug_iterator::operator++ ()
   return *this;
 }
 
+/* Must be called whenever the order of the linked list is edited, to ensure
+   the comparison function has up to date info. Freeing an objfile does not
+   require this function, as the order is maintained, but a function like
+   `put_objfile_before` should certainly call this.  */
+void
+update_objfile_ids (void)
+{
+  if (!object_files)
+    return;
+  else
+    {
+      struct objfile *prev;
+      struct objfile *curr;
+  
+      prev = object_files;
+      prev->id = 0;
+      curr = prev->next;
+
+      while (curr)
+        {
+          curr->id = prev->id + 1;
+          prev = curr;
+          curr = curr->next;
+        }
+    }
+}
+
 /* Put one object file before a specified on in the global list.
    This can be used to make sure an object file is destroyed before
    another when using objfiles_safe to free all objfiles.  */
@@ -489,10 +523,11 @@ put_objfile_before (struct objfile *objfile, struct objfile *before_this)
 	{
 	  objfile->next = *objp;
 	  *objp = objfile;
+	  update_objfile_ids();
 	  return;
 	}
     }
-  
+  update_objfile_ids();
   internal_error (__FILE__, __LINE__,
 		  _("put_objfile_before: before objfile not in list"));
 }
@@ -1076,11 +1111,10 @@ qsort_cmp (const void *a, const void *b)
 	{
 	  /* Sort on sequence number of the objfile in the chain.  */
 
-	  for (objfile *objfile : current_program_space->objfiles ())
-	    if (objfile == objfile1)
-	      return -1;
-	    else if (objfile == objfile2)
-	      return 1;
+	  if (objfile1->id < objfile2->id)
+	    return -1;
+	  if (objfile1->id > objfile2->id)
+	    return 1;
 
 	  /* We should have found one of the objfiles before getting here.  */
 	  gdb_assert_not_reached ("objfile not found");
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index 239aba2c2a..2312fa7f55 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -135,11 +135,14 @@ struct obj_section
 
   /* True if this "overlay section" is mapped into an "overlay region".  */
   int ovly_mapped;
+  
+  /* Memoized BFD section index returned from gdb_bfd_section_index  */
+  int index;
 };
 
 /* Relocation offset applied to S.  */
 #define obj_section_offset(s)						\
-  (((s)->objfile->section_offsets)->offsets[gdb_bfd_section_index ((s)->objfile->obfd, (s)->the_bfd_section)])
+  (((s)->objfile->section_offsets)->offsets[(s)->index])
 
 /* The memory address of section S (vma + offset).  */
 #define obj_section_addr(s)				      		\
@@ -623,6 +626,9 @@ struct objfile
      store these here rather than in struct block.  Static links must be
      allocated on the objfile's obstack.  */
   htab_up static_links;
+
+  /* A unique sequence identifier for the global linked list */
+  int id;
 };
 
 /* Declarations for functions defined in objfiles.c */
@@ -635,6 +641,8 @@ extern CORE_ADDR entry_point_address (void);
 
 extern void build_objfile_section_table (struct objfile *);
 
+extern void update_objfile_ids(void);
+
 extern void put_objfile_before (struct objfile *, struct objfile *);
 
 extern void add_separate_debug_objfile (struct objfile *, struct objfile *);
-- 
2.17.1