[PATCH] Improve qsort_cmp performance by memoizing objfile data

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] Improve qsort_cmp performance by memoizing objfile data

Vijay Klein
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  <[hidden email]>

* 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!