[PATCH] Improve qsort_cmp performance by memoizing objfile data

Vijay Klein vijaygk2@illinois.edu
Sat Aug 17 01:08:00 GMT 2019


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!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qsort_cmp_perf_improvement.patch
Type: text/x-patch
Size: 4879 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/gdb-patches/attachments/20190817/4e416947/attachment.bin>


More information about the Gdb-patches mailing list