From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 125684 invoked by alias); 8 Jan 2018 09:54:44 -0000 Mailing-List: contact binutils-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sourceware.org Received: (qmail 125675 invoked by uid 89); 8 Jan 2018 09:54:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_LAZY_DOMAIN_SECURITY,MSGID_FROM_MTA_HEADER,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=remembering, chromium, H*r:sk:service X-HELO: smx2.opera.com Received: from smx2.opera.com (HELO smx2.opera.com) (185.26.183.153) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 08 Jan 2018 09:54:42 +0000 X-Received: from critic.ams.osa (services.fw-ams.opera.com [185.26.183.129]) by smx2.opera.com (Postfix) with ESMTP id 365431F8B; Mon, 8 Jan 2018 09:54:39 +0000 (UTC) From: Jens Widell To: binutils@sourceware.org Cc: Jens Widell Subject: [PATCH] Optimize reading ELF objects with many group sections Date: Mon, 08 Jan 2018 09:54:00 -0000 Message-Id: <1515405262-67993-1-git-send-email-jl@opera.com> Received: from nerv.fw-osl.opera.com (nerv.fw-osl.opera.com. [91.203.97.254]) by smx2.opera.com (tobijsmtp) with SMTP id 365431F8B; Mon, 8 Jan 2018 09:54:39 +0000 Received: from services.fw-ams.opera.com (services.fw-ams.opera.com [185.26.183.129]) by nerv.fw-osl.opera.com (tobijsmtp) with SMTP id 365431F8B; Mon, 8 Jan 2018 09:54:39 +0000 Received: from critic.ams.osa (services.fw-ams.opera.com [185.26.183.129]) by smx2.opera.com (Postfix) with ESMTP id 365431F8B; Mon, 8 Jan 2018 09:54:39 +0000 (UTC) X-SW-Source: 2018-01/txt/msg00060.txt.bz2 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 --- Background: This turned out to be a significant issue when building Chromium with debug fission, which means clang calls objcopy twice at the end of a compilation to extract debug information into a separate file, and unity building, which combines many source files into a single compilation unit to reduce overall build time, thus procuding some very large object files with many sections. bfd/elf-bfd.h | 1 + bfd/elf.c | 15 ++++++++++++--- 2 files changed, 13 insertions(+), 3 deletions(-) diff --git a/bfd/elf-bfd.h b/bfd/elf-bfd.h index 9c9b0c7..07879e5 100644 --- a/bfd/elf-bfd.h +++ b/bfd/elf-bfd.h @@ -1908,6 +1908,7 @@ struct elf_obj_tdata Elf_Internal_Shdr **group_sect_ptr; int num_group; + 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..d7d084e 100644 --- a/bfd/elf.c +++ b/bfd/elf.c @@ -737,10 +737,17 @@ 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; + + if (i >= num_group) + i -= num_group; + Elf_Internal_Shdr *shdr = elf_tdata (abfd)->group_sect_ptr[i]; Elf_Internal_Group *idx; bfd_size_type n_elt; @@ -803,7 +810,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