This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH v2] Optimize reading ELF objects with many group sections


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.

Signed-off-by: Jens Widell <jl@opera.com>
---
Changes from previous version:
 - added changelog entry
 - added comment in elf-bfd.h
 - use modulo operator for index calculation

Tests run with default build on 64-bit Linux, with CFLAGS=-m32 and
with "./configure --enable-64-bit-bfd --enable-targets=all".

 bfd/ChangeLog |  5 +++++
 bfd/elf-bfd.h |  4 ++++
 bfd/elf.c     | 12 +++++++++---
 3 files changed, 18 insertions(+), 3 deletions(-)

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 7803ef8..44a22c1 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,8 @@
+2018-01-08  Jens Widell  <jl@opera.com>
+
+	* elf.c (setup_group): Optimize search for group by remembering
+	last found group and restarting search at that index.
+
 2018-01-03  John Baldwin  <jhb@FreeBSD.org>
 
 	* elf.c (elfcore_grok_freebsd_note): Handle
diff --git a/bfd/elf-bfd.h b/bfd/elf-bfd.h
index 9c9b0c7..3136b22 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 9f44ff9..2088e4b 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,9 @@ 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.7.4


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]