From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22643 invoked by alias); 18 Mar 2005 14:13:02 -0000 Mailing-List: contact binutils-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sources.redhat.com Received: (qmail 22273 invoked from network); 18 Mar 2005 14:12:51 -0000 Received: from unknown (HELO sccrmhc12.comcast.net) (204.127.202.56) by sourceware.org with SMTP; 18 Mar 2005 14:12:51 -0000 Received: from lucon.org ([24.6.212.230]) by comcast.net (sccrmhc12) with ESMTP id <2005031814125101200e87j3e>; Fri, 18 Mar 2005 14:12:51 +0000 Received: by lucon.org (Postfix, from userid 1000) id 982C597B72; Fri, 18 Mar 2005 06:12:50 -0800 (PST) Date: Fri, 18 Mar 2005 16:24:00 -0000 From: "H. J. Lu" To: Nick Clifton , binutils@sources.redhat.com Subject: Re: Slow lang_insert_orphan Message-ID: <20050318141250.GB27170@lucon.org> References: <20050317180506.GA7918@lucon.org> <423AA6DF.4080405@redhat.com> <20050318131431.GA21148@bubble.modra.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050318131431.GA21148@bubble.modra.org> User-Agent: Mutt/1.4.1i X-SW-Source: 2005-03/txt/msg00526.txt.bz2 On Fri, Mar 18, 2005 at 11:44:31PM +1030, Alan Modra wrote: > On Fri, Mar 18, 2005 at 10:01:03AM +0000, Nick Clifton wrote: > > Hi H. J. > > > > >When we have many orphaned sections, lang_insert_orphan spends lots > > >of time in > > > > > >/* Unlink the section. */ > > >for (pps = &output_bfd->sections; *pps != snew; pps = &(*pps)->next) > > > continue; > > > > > >It is the case of 64K section ld test. Use a doubly linked list > > >for section may help. But it will add a pointer to bfd_section. Should > > >I give a try? > > > > I am reluctant to increase the size of the bfd_section structure. Maybe > > lang_insert_orphans() could be made smarter with a different algorithm > > ? Possibly it could keep a local bitmap or list of sections to unlink > > and then only unlink them all right at the end ? > > Yes, I think you could try other approaches first. For instance > I think it would be better to ask ourselves whether this list really > needs to be ordered. Before I wrote this code, orphan sections appeared > at the end of the section list. As the comment says, shuffling the > section list was only cosmetic, but now I see some code has crept into > lang_size_section, for DATA_SEGMENT_ALIGN, that depends on correct > section ordering. The lang_size_section code could easily be rewritten > to traverse the lang_output_section_statement list instead. > > If we do care about the ordering, then perhaps delay sorting the > bfd_section list according to the output section statement list until > after all orphans have been added. Hmm, probably the best thing would > be to save output_bfd->section_tail before adding the orphan. Then you > know how to unlink the orphan without looking through the list. (I > think the orphan code predated the section hash table and section_tail.) > It isn't just lang_insert_orphan: # find -name *.* | xargs grep bfd_section_list_remove ./bfd/bfd-in2.h:#define bfd_section_list_remove(ABFD, PS) \ ./bfd/coffcode.h: bfd_section_list_remove (abfd, ps); ./bfd/elf32-i370.c: bfd_section_list_remove (s->output_section->owner, spp); ./bfd/elf64-mmix.c: bfd_section_list_remove (abfd, secpp); ./bfd/section.c:.#define bfd_section_list_remove(ABFD, PS) \ ./bfd/sunos.c: bfd_section_list_remove (abfd, ps); ./bfd/xcofflink.c: bfd_section_list_remove (abfd, st); ./bfd/elfxx-mips.c: bfd_section_list_remove (abfd, secpp); ./gas/config/obj-ecoff.c: bfd_section_list_remove (stdoutput, sec); ./gas/config/tc-mmix.c: bfd_section_list_remove (stdoutput, secpp); ./gas/config/tc-xtensa.c: /* Handle brain-dead bfd_section_list_remove macro, which ./gas/config/tc-xtensa.c: bfd_section_list_remove (stdoutput, ps_next_ptr); ./gas/write.c: bfd_section_list_remove (stdoutput, seclist); ./ld/ldlang.c: bfd_section_list_remove (output_bfd, pps); ./ld/ldlang.c: bfd_section_list_remove (output_bfd, p); ./ld/emultempl/elf32.em: bfd_section_list_remove (output_bfd, p); We are lucky so far that bfd_section_list_remove is only called a few times in most places and most of files don't have that many sections. H.J.