This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
[PATCH] Improve qsort_cmp performance by memoizing objfile data
- From: Vijay Klein <vijaygk2 at illinois dot edu>
- To: gdb-patches at sourceware dot org
- Date: Fri, 16 Aug 2019 18:01:42 -0700
- Subject: [PATCH] Improve qsort_cmp performance by memoizing objfile data
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!