[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.
* 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!
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> +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
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
Vijay> + /* A unique sequence identifier for the global linked list */