Improve qsort_cmp performance by memoizing objfile data
Commit Message
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!
Comments
>>>>> "Vijay" == Vijay Klein <vijaygk2@illinois.edu> writes:
Vijay> RATIONALE: The rationale behind this patch is that, currently, the
Vijay> qsort_cmp function can fall into a default case where it linearly
Vijay> traverses all the objfiles.
Thank you for the patch.
I'm curious if you have seen this code path taken.
Vijay> FSF Copyright Assignment: To be completely honest, I'm not entirely
Vijay> sure what is required here. I designed and wrote the entire change, if
Vijay> that is relevant. On the contribution checklist, it said the reviewer
Vijay> would send me the proper form, so all help is appreciated!
I don't think I have the forms available any more. Maybe one of the
other maintainers can email you the appropriate one; or you can email
assign@gnu for the paperwork.
Vijay> + int index;
...
Vijay> - section = &objfile->sections[gdb_bfd_section_index (abfd, asect)];
Vijay> + index = gdb_bfd_section_index (abfd, asect);
Better nowadays to just write "int index = ...".
Vijay> +/* Must be called whenever the order of the linked list is edited, to ensure
Vijay> + the comparison function has up to date info. Freeing an objfile does not
Vijay> + require this function, as the order is maintained, but a function like
Vijay> + `put_objfile_before` should certainly call this. */
Vijay> +void
Vijay> +update_objfile_ids (void)
It seems to me that there isn't a deep reason to prefer exactly the
order of the objfiles in the list -- any consistent order seems fine.
So, how about just setting the objfile's "id" at creation time, and
using that?
Then this function wouldn't be needed.
Vijay> + /* Memoized BFD section index returned from gdb_bfd_section_index */
Vijay> + int index;
GNU style is to have a period (followed by 2 spaces) at the end of
comment.
Vijay> + /* A unique sequence identifier for the global linked list */
Here too.
Tom
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(-)
@@ -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");
@@ -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