From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23719 invoked by alias); 21 May 2005 06:41:05 -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 23647 invoked from network); 21 May 2005 06:40:56 -0000 Received: from unknown (HELO wproxy.gmail.com) (64.233.184.195) by sourceware.org with SMTP; 21 May 2005 06:40:56 -0000 Received: by wproxy.gmail.com with SMTP id 67so1341977wri for ; Fri, 20 May 2005 23:40:55 -0700 (PDT) Received: by 10.54.47.1 with SMTP id u1mr1094600wru; Fri, 20 May 2005 23:40:55 -0700 (PDT) Received: by 10.54.56.70 with HTTP; Fri, 20 May 2005 23:40:55 -0700 (PDT) Message-ID: <5460e333050520234029eb42a8@mail.gmail.com> Date: Sat, 21 May 2005 11:05:00 -0000 From: Christian Joensson Reply-To: Christian Joensson To: "H. J. Lu" Subject: Re: PATCH: Use a hash table for 26X linker speedup Cc: binutils@sources.redhat.com In-Reply-To: <20050501190856.GA15653@lucon.org> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <20050501165707.GA13713@lucon.org> <20050501190856.GA15653@lucon.org> X-SW-Source: 2005-05/txt/msg00631.txt.bz2 Whatever happened with this? /ChJ On 5/1/05, H. J. Lu wrote: > On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote: > > Linker is very slow on input files with many sections. The 64k section > > test is only enabled for CRIS. I did a profile. 70% of linker time is > > spent in lang_check_section_addresses: > > > > Flat profile: > > > > Each sample counts as 0.01 seconds. > > % cumulative self self total > > time seconds seconds calls Ks/call Ks/call name > > 72.92 948.31 948.31 1 0.95 0.95 lang_check_section= _addresses > > 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_sectio= n_find_1 > > > > The main problem is we use a single section list. We have to scan the > > whole list for anything. In case of address overlap check, we only > > need to check the previous section. There are many other places in > > bfd, assembler and linker where a double section list will help. With > > this patch, I got 30% linker speed up in 64k section test: > > > > The old linker: > > > > sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total > > > > The new linker: > > > > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total > > > > The profile data shows: > > > > Flat profile: > > > > Each sample counts as 0.01 seconds. > > % cumulative self self total > > time seconds seconds calls s/call s/call name > > 81.20 256.42 256.42 132089 0.00 0.00 lang_output_sectio= n_find_1 > > 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup > > > > I will work on lang_output_section_find_1 next. I am planning to use > > a hash table. I hope to enable 64k section on all ELF targets. > > >=20 > This is the patch. I got >=20 > sh 1 13.39s user 1.28s system 95% cpu 15.431 total >=20 > vs. >=20 > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total >=20 > That is a 26X speed up. I enabled 64k section test for all ELF targets. >=20 >=20 > H.J. > ---- > ld/ >=20 > 2005-05-01 H.J. Lu >=20 > * ldlang.c (output_statement_hash_entry): New type. > (output_statement_table): New variable for hash table. > (output_statement_newfunc): New function. > (output_statement_table_init): Likewise. > (output_statement_table_free): Likewise. > (lang_init): Call output_statement_table_init. > (lang_finish): Renamed to ... > (lang_end): This. > (lang_process): Updated. > (lang_finish): New function. > (lang_output_section_find_1): Use hash table. > (lang_output_section_statement_lookup_1): Likewise. >=20 > * ldlang.h (lang_finish): New. >=20 > * ldmain.c (main): Call lang_finish. >=20 > ld/testsuite/ >=20 > 2005-05-01 H.J. Lu >=20 > * ld-elf/sec64k.exp: Enabled for all ELF targets. >=20 > --- ld/ldlang.c.hash 2005-05-01 09:00:10.000000000 -0700 > +++ ld/ldlang.c 2005-05-01 12:05:32.000000000 -0700 > @@ -863,6 +863,45 @@ lang_add_input_file (const char *name, > return new_afile (name, file_type, target, TRUE); > } >=20 > +struct output_statement_hash_entry > +{ > + struct bfd_hash_entry root; > + lang_output_section_statement_type *entry; > +}; > + > +/* The hash table. */ > + > +static struct bfd_hash_table output_statement_table; > + > +/* Support routines for the hash table used by lang_output_section_find_= 1, > + initialize the table, fill in an entry and remove the table. */ > + > +static struct bfd_hash_entry * > +output_statement_newfunc (struct bfd_hash_entry *entry ATTRIBUTE_UNUSED, > + struct bfd_hash_table *table, > + const char *string ATTRIBUTE_UNUSED) > +{ > + struct output_statement_hash_entry *ret > + =3D bfd_hash_allocate (table, > + sizeof (struct output_statement_hash_entry)); > + ret->entry =3D NULL; > + return (struct bfd_hash_entry *) ret; > +} > + > +static void > +output_statement_table_init (void) > +{ > + if (! bfd_hash_table_init_n (&output_statement_table, > + output_statement_newfunc, 61)) > + einfo (_("%P%F: Failed to create hash table\n")); > +} > + > +static void > +output_statement_table_free (void) > +{ > + bfd_hash_table_free (&output_statement_table); > +} > + > /* Build enough state so that the parser can build its tree. */ >=20 > void > @@ -872,6 +911,8 @@ lang_init (void) >=20 > stat_ptr =3D &statement_list; >=20 > + output_statement_table_init (); > + > lang_list_init (stat_ptr); >=20 > lang_list_init (&input_file_chain); > @@ -898,6 +939,12 @@ lang_init (void) > lang_statement_iteration =3D 0; > } >=20 > +void > +lang_finish (void) > +{ > + output_statement_table_free (); > +} > + > /*---------------------------------------------------------------------- > A region is an area of memory declared with the > MEMORY { name:org=3Dexp, len=3Dexp ... } > @@ -983,16 +1030,28 @@ static lang_output_section_statement_typ > lang_output_section_find_1 (const char *const name, int constraint) > { > lang_output_section_statement_type *lookup; > + struct output_statement_hash_entry *entry; > + unsigned long hash; >=20 > - for (lookup =3D &lang_output_section_statement.head->output_section_st= atement; > - lookup !=3D NULL; > - lookup =3D lookup->next) > + entry =3D ((struct output_statement_hash_entry *) > + bfd_hash_lookup (&output_statement_table, name, FALSE, > + FALSE)); > + if (entry =3D=3D NULL || (lookup =3D entry->entry) =3D=3D NULL) > + return NULL; > + > + hash =3D entry->root.hash; > + do > { > - if (strcmp (name, lookup->name) =3D=3D 0 > - && lookup->constraint !=3D -1 > + if (lookup->constraint !=3D -1 > && (constraint =3D=3D 0 || constraint =3D=3D lookup->constraint)) > return lookup; > + entry =3D (struct output_statement_hash_entry *) entry->root.next; > + lookup =3D entry ? entry->entry : NULL; > } > + while (entry !=3D NULL > + && entry->root.hash =3D=3D hash > + && strcmp (name, lookup->name) =3D=3D 0); > + > return NULL; > } >=20 > @@ -1010,6 +1069,8 @@ lang_output_section_statement_lookup_1 ( > lookup =3D lang_output_section_find_1 (name, constraint); > if (lookup =3D=3D NULL) > { > + struct output_statement_hash_entry *entry; > + > lookup =3D new_stat (lang_output_section_statement, stat_ptr); > lookup->region =3D NULL; > lookup->lma_region =3D NULL; > @@ -1034,6 +1095,15 @@ lang_output_section_statement_lookup_1 ( > lookup->update_dot_tree =3D NULL; > lookup->phdrs =3D NULL; >=20 > + entry =3D ((struct output_statement_hash_entry *) > + bfd_hash_lookup (&output_statement_table, name, TRUE, > + FALSE)); > + if (entry =3D=3D NULL) > + einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"), > + name); > + > + entry->entry =3D lookup; > + > lang_statement_append (&lang_output_section_statement, > (lang_statement_union_type *) lookup, > (lang_statement_union_type **) &lookup->next); > @@ -4495,7 +4565,7 @@ lang_set_startof (void) > } >=20 > static void > -lang_finish (void) > +lang_end (void) > { > struct bfd_link_hash_entry *h; > bfd_boolean warn; > @@ -5294,7 +5364,7 @@ lang_process (void) > /* Final stuffs. */ >=20 > ldemul_finish (); > - lang_finish (); > + lang_end (); > } >=20 > /* EXPORTED TO YACC */ > --- ld/ldlang.h.hash 2005-05-01 09:00:10.000000000 -0700 > +++ ld/ldlang.h 2005-05-01 11:39:36.000000000 -0700 > @@ -449,6 +449,8 @@ extern int lang_statement_iteration; >=20 > extern void lang_init > (void); > +extern void lang_finish > + (void); > extern lang_memory_region_type *lang_memory_region_lookup > (const char *const, bfd_boolean); > extern lang_memory_region_type *lang_memory_region_default > --- ld/ldmain.c.hash 2005-03-16 17:37:00.000000000 -0800 > +++ ld/ldmain.c 2005-05-01 11:40:39.000000000 -0700 > @@ -474,6 +474,8 @@ main (int argc, char **argv) > if (nocrossref_list !=3D NULL) > check_nocrossrefs (); >=20 > + lang_finish (); > + > /* Even if we're producing relocatable output, some non-fatal errors sh= ould > be reported in the exit status. (What non-fatal errors, if any, do = we > want to ignore for relocatable output?) */ > --- ld/testsuite/ld-elf/sec64k.exp.hash 2005-03-03 08:56:35.000000000 -08= 00 > +++ ld/testsuite/ld-elf/sec64k.exp 2005-05-01 11:50:34.000000000 -07= 00 > @@ -24,12 +24,6 @@ if ![is_elf_format] { > return > } >=20 > -# Per-port excludes, since this test takes an overwhelmingly long time > -# currently. > -if { ![istarget cris-*-*] } { > - return > -} > - > # Test >64k sections, with and without -r. First, create the assembly > # files. Have a relocation to another section and one within the local > # section. >=20 --=20 Cheers, /ChJ