From 564e11c9a9d9570b233b38cd995f1b4eb7c757e8 Mon Sep 17 00:00:00 2001 From: Jens Widell Date: Fri, 12 Jan 2018 13:16:17 +0000 Subject: [PATCH] Optimize the performance of the group_setup function. When processing a section that is a member of a group, the group that contains it is looked up using a linear search. The resulting O(n^2) complexity causes significant performance issues when dealing with object files with very many groups. By remembering the index of the last found group and restarting the next search from that index, the search instead becomes O(n) in common cases. * elf.c (setup_group): Optimize search for group by remembering last found group and restarting search at that index. * elf-bfd.h (struct elf_obj_tdata): Add group_search_offset field. --- bfd/ChangeLog | 6 ++++++ bfd/elf-bfd.h | 4 ++++ bfd/elf.c | 11 ++++++++--- 3 files changed, 18 insertions(+), 3 deletions(-) diff --git a/bfd/ChangeLog b/bfd/ChangeLog index 19364c0c779..cc54b535f75 100644 --- a/bfd/ChangeLog +++ b/bfd/ChangeLog @@ -1,3 +1,9 @@ +2018-01-12 Jens Widell + + * elf.c (setup_group): Optimize search for group by remembering + last found group and restarting search at that index. + * elf-bfd.h (struct elf_obj_tdata): Add group_search_offset field. + 2018-01-12 Gunther Nikl * aoutx.h (aout_link_check_ar_symbols): Remove default and handle diff --git a/bfd/elf-bfd.h b/bfd/elf-bfd.h index 9c9b0c7fac1..b580dc2769a 100644 --- a/bfd/elf-bfd.h +++ b/bfd/elf-bfd.h @@ -1909,6 +1909,10 @@ struct elf_obj_tdata Elf_Internal_Shdr **group_sect_ptr; int num_group; + /* Index into group_sect_ptr, updated by setup_group when finding a + section's group. Used to optimize subsequent group searches. */ + unsigned int group_search_offset; + unsigned int symtab_section, dynsymtab_section; unsigned int dynversym_section, dynverdef_section, dynverref_section; diff --git a/bfd/elf.c b/bfd/elf.c index 1d0eefd0536..90aef091329 100644 --- a/bfd/elf.c +++ b/bfd/elf.c @@ -737,10 +737,14 @@ setup_group (bfd *abfd, Elf_Internal_Shdr *hdr, asection *newsect) if (num_group != (unsigned) -1) { - unsigned int i; + unsigned int search_offset = elf_tdata (abfd)->group_search_offset; + unsigned int j; - for (i = 0; i < num_group; i++) + for (j = 0; j < num_group; j++) { + /* Begin search from previous found group. */ + unsigned i = (j + search_offset) % num_group; + Elf_Internal_Shdr *shdr = elf_tdata (abfd)->group_sect_ptr[i]; Elf_Internal_Group *idx; bfd_size_type n_elt; @@ -803,7 +807,8 @@ setup_group (bfd *abfd, Elf_Internal_Shdr *hdr, asection *newsect) if (shdr->bfd_section != NULL) elf_next_in_group (shdr->bfd_section) = newsect; - i = num_group - 1; + elf_tdata (abfd)->group_search_offset = i; + j = num_group - 1; break; } } -- 2.30.2