[PATCH] Improve qsort_cmp performance by memoizing objfile data

classic Classic list List threaded Threaded
2 messages 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!

qsort_cmp_perf_improvement.patch (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Improve qsort_cmp performance by memoizing objfile data

Tom Tromey-2
>>>>> "Vijay" == Vijay Klein <[hidden email]> 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