* Re: PATCH: Use a hash table for 26X linker speedup
@ 2005-09-29 16:46 Steven Bosscher
2005-09-30 7:31 ` Alan Modra
0 siblings, 1 reply; 11+ messages in thread
From: Steven Bosscher @ 2005-09-29 16:46 UTC (permalink / raw)
To: binutils; +Cc: amodra, hjl
Hi,
Can anyone tell what happened to this linker speedup patch?
http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
Gr.
Steven
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-29 16:46 PATCH: Use a hash table for 26X linker speedup Steven Bosscher
@ 2005-09-30 7:31 ` Alan Modra
2005-09-30 15:47 ` Nick Clifton
0 siblings, 1 reply; 11+ messages in thread
From: Alan Modra @ 2005-09-30 7:31 UTC (permalink / raw)
To: Steven Bosscher; +Cc: binutils, hjl
On Thu, Sep 29, 2005 at 04:23:05PM +0200, Steven Bosscher wrote:
> Can anyone tell what happened to this linker speedup patch?
> http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
I looked at rearranging the orphan code so that this wouldn't be
necessary, and found I needed to pull apart half the linker. So I left
that job for a rainy day. Since I haven't provided a more elegant
solution, I suppose HJ's patch ought to go in.
--
Alan Modra
IBM OzLabs - Linux Technology Centre
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-30 7:31 ` Alan Modra
@ 2005-09-30 15:47 ` Nick Clifton
2005-10-01 1:45 ` Paul Brook
0 siblings, 1 reply; 11+ messages in thread
From: Nick Clifton @ 2005-09-30 15:47 UTC (permalink / raw)
To: Alan Modra; +Cc: Steven Bosscher, binutils, hjl
Hi H.J.
Just to make this explicit:
> Alan Modra wrote:
>>Can anyone tell what happened to this linker speedup patch?
>>http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
>
> I looked at rearranging the orphan code so that this wouldn't be
> necessary, and found I needed to pull apart half the linker. So I left
> that job for a rainy day. Since I haven't provided a more elegant
> solution, I suppose HJ's patch ought to go in.
ld/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* 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.
* ldlang.h (lang_finish): New.
* ldmain.c (main): Call lang_finish.
ld/testsuite/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* ld-elf/sec64k.exp: Enabled for all ELF targets.
Approved - please apply.
Cheers
Nick
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH: Use a hash table for 26X linker speedup
2005-09-30 15:47 ` Nick Clifton
@ 2005-10-01 1:45 ` Paul Brook
2005-10-04 7:23 ` Nick Clifton
0 siblings, 1 reply; 11+ messages in thread
From: Paul Brook @ 2005-10-01 1:45 UTC (permalink / raw)
To: binutils; +Cc: Nick Clifton, Alan Modra, hjl
[-- Attachment #1: Type: text/plain, Size: 826 bytes --]
> ld/testsuite/
> 2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
>
> * ld-elf/sec64k.exp: Enabled for all ELF targets.
On an arm-none-eabi cross this test takes about 8 minutes to run on my
machine. This is about 25 times longer than the whole of the rest of the
binutils+gas+gdb testsuites put together.
Tests run on a 2GHz amd64, ie. not a slow machine.
A native i386 linker completes the test in a more reasonable time (~20
seconds), so this looks like an arm specific problem.
We should probably figure out what causing this slowness. Until that happens,
the patch below disable the test on arm targets.
Ok?
I'll file a bug in bugzilla to remind me/us that there's something slow in the
arm linker.
Paul
2005-10-01 Paul Brook <paul@codesourcery.com>
* ld-elf/sec64k.exp: Skip test on arm targets (too slow).
[-- Attachment #2: patch.arm_sec64k --]
[-- Type: text/x-diff, Size: 685 bytes --]
Index: ld/testsuite/ld-elf/sec64k.exp
===================================================================
RCS file: /var/cvsroot/src-cvs/src/ld/testsuite/ld-elf/sec64k.exp,v
retrieving revision 1.7
diff -u -p -r1.7 sec64k.exp
--- ld/testsuite/ld-elf/sec64k.exp 30 Sep 2005 17:45:54 -0000 1.7
+++ ld/testsuite/ld-elf/sec64k.exp 1 Oct 2005 01:38:20 -0000
@@ -24,6 +24,11 @@ if ![is_elf_format] {
return
}
+# For some reason this is painfully slow on arm targets, so skip it.
+if { [istarget arm*-*-*] } {
+ 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.
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-01 1:45 ` Paul Brook
@ 2005-10-04 7:23 ` Nick Clifton
2005-10-19 0:59 ` Paul Brook
0 siblings, 1 reply; 11+ messages in thread
From: Nick Clifton @ 2005-10-04 7:23 UTC (permalink / raw)
To: Paul Brook; +Cc: binutils, Alan Modra, hjl
Hi Paul,
>> * ld-elf/sec64k.exp: Enabled for all ELF targets.
> On an arm-none-eabi cross this test takes about 8 minutes to run on my
> machine. This is about 25 times longer than the whole of the rest of the
> binutils+gas+gdb testsuites put together.
> We should probably figure out what causing this slowness. Until that happens,
> the patch below disable the test on arm targets.
> Ok?
Better I think to find out the cause of the slow down. I did this - it is
the get_arm_elf_section_data() function in elf32-arm.c, which is repeatedly
scanning over a list of ~64K entries trying to match up section
pointers. Since I wrote this function I felt obliged to try to fix it
and I am committing the patch below which does improve things. It is
not the best fix (which would be to use a hash function), but it does
help by noticing that the typical usage is to add sections to the list
in forwards order and then scan for them in backwards order.
Cheers
Nick
bfd/ChangeLog
2005-10-04 Nick Clifton <nickc@redhat.com>
* elf32-arm.c (get_arm_elf_section_data): Cache the last pointer
matched so that the typical case of scanning for the previous
section to last one can be handled quickly.
Index: bfd/elf32-arm.c
===================================================================
RCS file: /cvs/src/src/bfd/elf32-arm.c,v
retrieving revision 1.55
diff -c -3 -p -r1.55 elf32-arm.c
*** bfd/elf32-arm.c 9 Sep 2005 13:10:01 -0000 1.55
--- bfd/elf32-arm.c 4 Oct 2005 07:18:12 -0000
*************** static _arm_elf_section_data *
*** 6563,6572 ****
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! return elf32_arm_section_data (sec);
return NULL;
}
--- 6563,6594 ----
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
+ static struct section_list * last_entry = NULL;
+ /* This is a short cut for the typical case where the sections are added
+ to the sections_with_arm_elf_section_data list in forward order and
+ then looked up here in backwards order. This makes a real difference
+ to the ld-srec/sec64k.exp linker test. */
+ if (last_entry != NULL)
+ {
+ if (last_entry->sec == sec)
+ return elf32_arm_section_data (sec);
+
+ if (last_entry->prev != NULL
+ && last_entry->prev->sec == sec)
+ {
+ last_entry = last_entry->prev;
+ return elf32_arm_section_data (sec);
+ }
+ }
+
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! {
! last_entry = entry;
! return elf32_arm_section_data (sec);
! }
!
return NULL;
}
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-04 7:23 ` Nick Clifton
@ 2005-10-19 0:59 ` Paul Brook
2005-10-19 15:39 ` Nick Clifton
0 siblings, 1 reply; 11+ messages in thread
From: Paul Brook @ 2005-10-19 0:59 UTC (permalink / raw)
To: binutils; +Cc: Nick Clifton
[-- Attachment #1: Type: text/plain, Size: 702 bytes --]
> bfd/ChangeLog
> 2005-10-04 Nick Clifton <nickc@redhat.com>
>
> * elf32-arm.c (get_arm_elf_section_data): Cache the last pointer
> matched so that the typical case of scanning for the previous
> section to last one can be handled quickly.
It's still quite slow with this patch.
unrecord_section_with_arm_elf_section_data has the same problem.
The attached patch uses the cache for this as well, and avoids leaving
last_entry pointing a a free'd object.
Tested with cross to arm-none-eabi.
Ok?
Paul
2005-10-19 Paul Brook <paul@codesourcery.com>
* elf32-arm.c (find_arm_elf_section_entry): New function.
(get_arm_elf_section_data,
unrecord_section_with_arm_elf_section_data): Use it.
[-- Attachment #2: patch.64ksec_speedup --]
[-- Type: text/x-diff, Size: 2868 bytes --]
Index: bfd/elf32-arm.c
===================================================================
RCS file: /var/cvsroot/src-cvs/src/bfd/elf32-arm.c,v
retrieving revision 1.58
diff -u -p -r1.58 elf32-arm.c
--- bfd/elf32-arm.c 8 Oct 2005 17:07:15 -0000 1.58
+++ bfd/elf32-arm.c 19 Oct 2005 00:16:11 -0000
@@ -7311,8 +7311,8 @@ record_section_with_arm_elf_section_data
sections_with_arm_elf_section_data = entry;
}
-static _arm_elf_section_data *
-get_arm_elf_section_data (asection * sec)
+static struct section_list *
+find_arm_elf_section_entry (asection * sec)
{
struct section_list * entry;
static struct section_list * last_entry = NULL;
@@ -7321,27 +7321,37 @@ get_arm_elf_section_data (asection * sec
to the sections_with_arm_elf_section_data list in forward order and
then looked up here in backwards order. This makes a real difference
to the ld-srec/sec64k.exp linker test. */
+ entry = sections_with_arm_elf_section_data;
if (last_entry != NULL)
{
if (last_entry->sec == sec)
- return elf32_arm_section_data (sec);
-
- if (last_entry->prev != NULL
- && last_entry->prev->sec == sec)
- {
- last_entry = last_entry->prev;
- return elf32_arm_section_data (sec);
- }
+ entry = last_entry;
+ else if (last_entry->next != NULL
+ && last_entry->next->sec == sec)
+ entry = last_entry->next;
}
-
- for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
+
+ for (; entry; entry = entry->next)
if (entry->sec == sec)
- {
- last_entry = entry;
- return elf32_arm_section_data (sec);
- }
+ break;
+
+ if (entry)
+ last_entry = entry->prev;
+
+ return entry;
+}
+
+static _arm_elf_section_data *
+get_arm_elf_section_data (asection * sec)
+{
+ struct section_list * entry;
+
+ entry = find_arm_elf_section_entry (sec);
- return NULL;
+ if (entry)
+ return elf32_arm_section_data (entry->sec);
+ else
+ return NULL;
}
static void
@@ -7349,18 +7359,18 @@ unrecord_section_with_arm_elf_section_da
{
struct section_list * entry;
- for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
- if (entry->sec == sec)
- {
- if (entry->prev != NULL)
- entry->prev->next = entry->next;
- if (entry->next != NULL)
- entry->next->prev = entry->prev;
- if (entry == sections_with_arm_elf_section_data)
- sections_with_arm_elf_section_data = entry->next;
- free (entry);
- break;
- }
+ entry = find_arm_elf_section_entry (sec);
+
+ if (entry)
+ {
+ if (entry->prev != NULL)
+ entry->prev->next = entry->next;
+ if (entry->next != NULL)
+ entry->next->prev = entry->prev;
+ if (entry == sections_with_arm_elf_section_data)
+ sections_with_arm_elf_section_data = entry->next;
+ free (entry);
+ }
}
/* Called for each symbol. Builds a section map based on mapping symbols.
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-10-19 0:59 ` Paul Brook
@ 2005-10-19 15:39 ` Nick Clifton
0 siblings, 0 replies; 11+ messages in thread
From: Nick Clifton @ 2005-10-19 15:39 UTC (permalink / raw)
To: Paul Brook; +Cc: binutils
Hi Paul,
> It's still quite slow with this patch.
> unrecord_section_with_arm_elf_section_data has the same problem.
Good point.
> The attached patch uses the cache for this as well, and avoids leaving
> last_entry pointing a free'd object.
Also a very good point.
I have applied your patch together with an extra comment describing why
we set last_found to entry->prev, since I felt that it was not entirely
obvious.
Cheers
Nick
> 2005-10-19 Paul Brook <paul@codesourcery.com>
>
> * elf32-arm.c (find_arm_elf_section_entry): New function.
> (get_arm_elf_section_data,
> unrecord_section_with_arm_elf_section_data): Use it.
^ permalink raw reply [flat|nested] 11+ messages in thread
* PATCH: Use a double section list to speed up linker by 30%
@ 2005-05-01 16:57 H. J. Lu
2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu
0 siblings, 1 reply; 11+ messages in thread
From: H. J. Lu @ 2005-05-01 16:57 UTC (permalink / raw)
To: binutils
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_section_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_section_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.
I know some people have concerns over memory usage. But I will take a
faster linker with a bigger memory footprint than a slower linker any
day. I am planning to include it in the Linux binutils if it isn't in
the FSF binutils.
H.J.
----
bfd/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* bfd.c (bfd): Remove section_tail and add section_last.
(bfd_preserve): Likewise.
(bfd_preserve_save): Likewise.
(bfd_preserve_restore): Likewise.
* opncls.c (_bfd_new_bfd): Likewise.
* linker.c (bfd_new_link_order): Reuse link_order_input.
(bfd_new_input_link_order): New.
(_bfd_default_link_order): Ignore bfd_input_link_order.
* section.c (bfd_section): Add prev.
(bfd_section_double_list_remove): New.
(bfd_section_list_remove): Updated.
(bfd_section_double_list_append): New.
(bfd_section_double_list_insert_after): New.
(bfd_section_list_insert): Updated.
(bfd_section_double_list_insert_before): New.
(bfd_section_removed_from_list): Updated.
(STD_SECTION): Initialize prev.
(bfd_section_init): Updated.
(bfd_section_list_clear): Updated.
* coffcode.h (coff_compute_section_file_positions): Updated.
* xcofflink.c (_bfd_xcoff_bfd_final_link): Updated.
* bfd-in2.h: Regenerated.
gas/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* write.c (write_object_file): Use bfd_section_double_list_remove
to remove sections.
ld/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section):
Use bfd_section_double_list_remove to remove sections.
* ldlang.c (lang_insert_orphan): Likewise.
(strip_excluded_or_unused_output_sections): Likewise.
(lang_check_section_addresses): Only check the previous section
for overlap.
--- binutils/bfd/bfd.c.dbl 2005-01-19 09:06:06.000000000 -0800
+++ binutils/bfd/bfd.c 2005-05-01 08:09:56.000000000 -0700
@@ -111,8 +111,8 @@ CODE_FRAGMENT
. {* Pointer to linked list of sections. *}
. struct bfd_section *sections;
.
-. {* The place where we add to the section list. *}
-. struct bfd_section **section_tail;
+. {* The last section on the section list. *}
+. struct bfd_section *section_last;
.
. {* The number of sections. *}
. unsigned int section_count;
@@ -1390,7 +1390,7 @@ CODE_FRAGMENT
. flagword flags;
. const struct bfd_arch_info *arch_info;
. struct bfd_section *sections;
-. struct bfd_section **section_tail;
+. struct bfd_section *section_last;
. unsigned int section_count;
. struct bfd_hash_table section_htab;
.};
@@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
preserve->arch_info = abfd->arch_info;
preserve->flags = abfd->flags;
preserve->sections = abfd->sections;
- preserve->section_tail = abfd->section_tail;
+ preserve->section_last = abfd->section_last;
preserve->section_count = abfd->section_count;
preserve->section_htab = abfd->section_htab;
@@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
abfd->arch_info = &bfd_default_arch_struct;
abfd->flags &= BFD_IN_MEMORY;
abfd->sections = NULL;
- abfd->section_tail = &abfd->sections;
+ abfd->section_last = NULL;
abfd->section_count = 0;
return TRUE;
@@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct
abfd->flags = preserve->flags;
abfd->section_htab = preserve->section_htab;
abfd->sections = preserve->sections;
- abfd->section_tail = preserve->section_tail;
+ abfd->section_last = preserve->section_last;
abfd->section_count = preserve->section_count;
/* bfd_release frees all memory more recently bfd_alloc'd than
--- binutils/bfd/coffcode.h.dbl 2005-04-21 10:09:46.000000000 -0700
+++ binutils/bfd/coffcode.h 2005-05-01 08:09:56.000000000 -0700
@@ -3033,11 +3033,12 @@ coff_compute_section_file_positions (bfd
/* Rethread the linked list into sorted order; at the same time,
assign target_index values. */
target_index = 1;
- abfd->sections = section_list[0];
+ abfd->sections = NULL;
+ abfd->section_last = NULL;
for (i = 0; i < count; i++)
{
current = section_list[i];
- current->next = section_list[i + 1];
+ bfd_section_double_list_append (abfd, current);
/* Later, if the section has zero size, we'll be throwing it
away, so we don't want to number it now. Note that having
@@ -3056,7 +3057,6 @@ coff_compute_section_file_positions (bfd
else
current->target_index = target_index++;
}
- abfd->section_tail = ¤t->next;
free (section_list);
}
--- binutils/bfd/opncls.c.dbl 2005-03-13 21:36:48.000000000 -0800
+++ binutils/bfd/opncls.c 2005-05-01 08:09:56.000000000 -0700
@@ -77,7 +77,7 @@ _bfd_new_bfd (void)
return NULL;
}
nbfd->sections = NULL;
- nbfd->section_tail = &nbfd->sections;
+ nbfd->section_last = NULL;
nbfd->format = bfd_unknown;
nbfd->my_archive = NULL;
nbfd->origin = 0;
--- binutils/bfd/section.c.dbl 2005-04-30 15:00:46.000000000 -0700
+++ binutils/bfd/section.c 2005-05-01 08:09:56.000000000 -0700
@@ -164,6 +164,9 @@ CODE_FRAGMENT
. {* The next section in the list belonging to the BFD, or NULL. *}
. struct bfd_section *next;
.
+. {* The previous section in the list belonging to the BFD, or NULL. *}
+. struct bfd_section *prev;
+.
. {* The field flags contains attributes of the section. Some
. flags are read in from the object file, and some are
. synthesized from other information. *}
@@ -548,31 +551,87 @@ CODE_FRAGMENT
.{* Macros to handle insertion and deletion of a bfd's sections. These
. only handle the list pointers, ie. do not adjust section_count,
. target_index etc. *}
+.#define bfd_section_double_list_remove(ABFD, S) \
+. do \
+. { \
+. asection *_s = S; \
+. asection *_next = _s->next; \
+. asection *_prev = _s->prev; \
+. if (_prev) \
+. _prev->next = _next; \
+. else \
+. (ABFD)->sections = _next; \
+. if (_next) \
+. { \
+. _next->prev = _prev; \
+. _s->next = NULL; \
+. } \
+. else \
+. (ABFD)->section_last = _prev; \
+. } \
+. while (0)
.#define bfd_section_list_remove(ABFD, PS) \
+. bfd_section_double_list_remove ((ABFD), *(PS))
+.#define bfd_section_double_list_append(ABFD, S) \
+. do \
+. { \
+. asection *_s = S; \
+. bfd *_abfd = ABFD; \
+. _s->next = NULL; \
+. if (_abfd->section_last) \
+. { \
+. _s->prev = _abfd->section_last; \
+. _abfd->section_last->next = _s; \
+. } \
+. else \
+. _abfd->sections = _s; \
+. _abfd->section_last = _s; \
+. } \
+. while (0)
+.#define bfd_section_double_list_insert_after(ABFD, A, S) \
. do \
. { \
-. asection **_ps = PS; \
-. asection *_s = *_ps; \
-. *_ps = _s->next; \
-. if (_s->next == NULL) \
-. (ABFD)->section_tail = _ps; \
+. asection *_a = A; \
+. asection *_s = S; \
+. if (_a) \
+. { \
+. asection *_next = _a->next; \
+. _s->next = _next; \
+. _s->prev = _a; \
+. _a->next = _s; \
+. if (_next) \
+. _s->next->prev = _s; \
+. else \
+. (ABFD)->section_last = _s; \
+. } \
. else \
-. _s->next = NULL; \
+. bfd_section_double_list_append ((ABFD), (S)); \
. } \
. while (0)
-.#define bfd_section_list_insert(ABFD, PS, S) \
+.#define bfd_section_double_list_insert_before(ABFD, B, S) \
. do \
. { \
-. asection **_ps = PS; \
+. asection *_b = B; \
. asection *_s = S; \
-. _s->next = *_ps; \
-. *_ps = _s; \
-. if (_s->next == NULL) \
-. (ABFD)->section_tail = &_s->next; \
+. if (_b) \
+. { \
+. asection *_prev = _b->prev; \
+. _s->prev = _prev; \
+. _s->next = _b; \
+. _b->prev = _s; \
+. if (_prev) \
+. _prev->next = _s; \
+. else \
+. (ABFD)->sections = _s; \
+. } \
+. else \
+. bfd_section_double_list_append ((ABFD), (S)); \
. } \
. while (0)
-.#define bfd_section_removed_from_list(ABFD, S) \
-. ((S)->next == NULL && &(S)->next != (ABFD)->section_tail)
+.#define bfd_section_list_insert(ABFD, PS, S) \
+. bfd_section_double_list_insert_before ((ABFD), *(PS), (S))
+.#define bfd_section_removed_from_list(ABFD, S) \
+. ((S)->next == NULL && (S) != (ABFD)->section_last)
.
*/
@@ -604,8 +663,8 @@ static const asymbol global_syms[] =
#define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX) \
const asymbol * const SYM = (asymbol *) &global_syms[IDX]; \
asection SEC = \
- /* name, id, index, next, flags, user_set_vma, */ \
- { NAME, IDX, 0, NULL, FLAGS, 0, \
+ /* name, id, index, next, prev, flags, user_set_vma, */ \
+ { NAME, IDX, 0, NULL, NULL, FLAGS, 0, \
\
/* linker_mark, linker_has_input, gc_mark, segment_mark, */ \
0, 0, 1, 0, \
@@ -719,8 +778,7 @@ bfd_section_init (bfd *abfd, asection *n
section_id++;
abfd->section_count++;
- *abfd->section_tail = newsect;
- abfd->section_tail = &newsect->next;
+ bfd_section_double_list_append (abfd, newsect);
return newsect;
}
@@ -750,7 +808,7 @@ void
bfd_section_list_clear (bfd *abfd)
{
abfd->sections = NULL;
- abfd->section_tail = &abfd->sections;
+ abfd->section_last = NULL;
abfd->section_count = 0;
memset (abfd->section_htab.table, 0,
abfd->section_htab.size * sizeof (struct bfd_hash_entry *));
--- binutils/bfd/xcofflink.c.dbl 2005-04-11 08:54:46.000000000 -0700
+++ binutils/bfd/xcofflink.c 2005-05-01 08:09:56.000000000 -0700
@@ -5460,13 +5460,11 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st
that needs padding. This requires unlinking and
relinking the bfd's section list. */
- st = abfd->section_tail;
n = bfd_make_section_anyway (abfd, ".pad");
n->flags = SEC_HAS_CONTENTS;
n->alignment_power = 0;
- BFD_ASSERT (*st == n);
- bfd_section_list_remove (abfd, st);
+ bfd_section_double_list_remove (abfd, n);
bfd_section_list_insert (abfd, op, n);
op = &n->next;
--- binutils/gas/write.c.dbl 2005-04-27 08:28:38.000000000 -0700
+++ binutils/gas/write.c 2005-05-01 08:09:56.000000000 -0700
@@ -1471,20 +1471,11 @@ write_object_file (void)
#ifdef BFD_ASSEMBLER
/* Remove the sections created by gas for its own purposes. */
{
- asection **seclist;
int i;
- seclist = &stdoutput->sections;
- while (*seclist)
- {
- if (*seclist == reg_section || *seclist == expr_section)
- {
- bfd_section_list_remove (stdoutput, seclist);
- stdoutput->section_count--;
- }
- else
- seclist = &(*seclist)->next;
- }
+ bfd_section_double_list_remove (stdoutput, reg_section);
+ bfd_section_double_list_remove (stdoutput, expr_section);
+ stdoutput->section_count -= 2;
i = 0;
bfd_map_over_sections (stdoutput, renumber_sections, &i);
}
--- binutils/ld/emultempl/elf32.em.dbl 2005-04-30 15:00:46.000000000 -0700
+++ binutils/ld/emultempl/elf32.em 2005-05-01 08:09:56.000000000 -0700
@@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section
if (os == abs_output_section || os->constraint == -1)
continue;
s = os->bfd_section;
- if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0)
+ if (s != NULL
+ && s->size == 0
+ && (s->flags & SEC_KEEP) == 0
+ && !bfd_section_removed_from_list (output_bfd, s))
{
- asection **p;
-
- for (p = &output_bfd->sections; *p; p = &(*p)->next)
- if (*p == s)
- {
- bfd_section_list_remove (output_bfd, p);
- output_bfd->section_count--;
- break;
- }
+ bfd_section_double_list_remove (output_bfd, s);
+ output_bfd->section_count--;
}
}
}
--- binutils/ld/ldlang.c.dbl 2005-04-30 15:19:33.000000000 -0700
+++ binutils/ld/ldlang.c 2005-05-01 08:58:21.000000000 -0700
@@ -1203,7 +1203,6 @@ lang_insert_orphan (lang_input_statement
etree_type *load_base;
lang_output_section_statement_type *os;
lang_output_section_statement_type **os_tail;
- asection **bfd_tail;
/* Start building a list of statements for this section.
First save the current statement pointer. */
@@ -1257,7 +1256,6 @@ lang_insert_orphan (lang_input_statement
os_tail = ((lang_output_section_statement_type **)
lang_output_section_statement.tail);
- bfd_tail = output_bfd->section_tail;
os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL,
load_base, 0);
@@ -1316,8 +1314,8 @@ lang_insert_orphan (lang_input_statement
place->section = &output_bfd->sections;
/* Unlink the section. */
- ASSERT (*bfd_tail == snew);
- bfd_section_list_remove (output_bfd, bfd_tail);
+ ASSERT (output_bfd->section_last == snew);
+ bfd_section_double_list_remove (output_bfd, snew);
/* Now tack it back on in the right place. */
bfd_section_list_insert (output_bfd, place->section, snew);
@@ -3051,8 +3049,6 @@ strip_excluded_or_unused_output_sections
&& s->linker_has_input == 0
&& (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0)))
{
- asection **p;
-
/* We don't set bfd_section to NULL since bfd_section of
the used output section may still be used. */
if (unused)
@@ -3060,13 +3056,11 @@ strip_excluded_or_unused_output_sections
else
os->bfd_section = NULL;
- for (p = &output_bfd->sections; *p; p = &(*p)->next)
- if (*p == s)
- {
- bfd_section_list_remove (output_bfd, p);
- output_bfd->section_count--;
- break;
- }
+ if (!bfd_section_removed_from_list (output_bfd, s))
+ {
+ bfd_section_double_list_remove (output_bfd, s);
+ output_bfd->section_count--;
+ }
}
}
}
@@ -3722,7 +3716,7 @@ lang_check_section_addresses (void)
/* Once we reach section 's' stop our seach. This prevents two
warning messages from being produced, one for 'section A overlaps
section B' and one for 'section B overlaps section A'. */
- for (os = output_bfd->sections; os != s; os = os->next)
+ for (os = s->prev; os != NULL; os = os->prev)
{
bfd_vma s_start;
bfd_vma s_end;
@@ -3742,15 +3736,14 @@ lang_check_section_addresses (void)
os_end = os_start + TO_ADDR (os->size) - 1;
/* Look for an overlap. */
- if ((s_end < os_start) || (s_start > os_end))
- continue;
-
- einfo (
-_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
- s->name, s_start, s_end, os->name, os_start, os_end);
-
- /* Once we have found one overlap for this section,
- stop looking for others. */
+ if (s_end >= os_start && s_start <= os_end)
+
+ einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
+ s->name, s_start, s_end, os->name, os_start, os_end);
+
+ /* We only need to check the previous section for overlap.
+ Once we have found one overlap for this section, stop
+ looking for others. */
break;
}
}
^ permalink raw reply [flat|nested] 11+ messages in thread* PATCH: Use a hash table for 26X linker speedup
2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu
@ 2005-05-01 19:09 ` H. J. Lu
2005-05-21 11:05 ` Christian Joensson
0 siblings, 1 reply; 11+ messages in thread
From: H. J. Lu @ 2005-05-01 19:09 UTC (permalink / raw)
To: binutils
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_section_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_section_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.
>
This is the patch. I got
sh 1 13.39s user 1.28s system 95% cpu 15.431 total
vs.
sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total
That is a 26X speed up. I enabled 64k section test for all ELF targets.
H.J.
----
ld/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* 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.
* ldlang.h (lang_finish): New.
* ldmain.c (main): Call lang_finish.
ld/testsuite/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* ld-elf/sec64k.exp: Enabled for all ELF targets.
--- 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);
}
+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
+ = bfd_hash_allocate (table,
+ sizeof (struct output_statement_hash_entry));
+ ret->entry = 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. */
void
@@ -872,6 +911,8 @@ lang_init (void)
stat_ptr = &statement_list;
+ output_statement_table_init ();
+
lang_list_init (stat_ptr);
lang_list_init (&input_file_chain);
@@ -898,6 +939,12 @@ lang_init (void)
lang_statement_iteration = 0;
}
+void
+lang_finish (void)
+{
+ output_statement_table_free ();
+}
+
/*----------------------------------------------------------------------
A region is an area of memory declared with the
MEMORY { name:org=exp, len=exp ... }
@@ -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;
- for (lookup = &lang_output_section_statement.head->output_section_statement;
- lookup != NULL;
- lookup = lookup->next)
+ entry = ((struct output_statement_hash_entry *)
+ bfd_hash_lookup (&output_statement_table, name, FALSE,
+ FALSE));
+ if (entry == NULL || (lookup = entry->entry) == NULL)
+ return NULL;
+
+ hash = entry->root.hash;
+ do
{
- if (strcmp (name, lookup->name) == 0
- && lookup->constraint != -1
+ if (lookup->constraint != -1
&& (constraint == 0 || constraint == lookup->constraint))
return lookup;
+ entry = (struct output_statement_hash_entry *) entry->root.next;
+ lookup = entry ? entry->entry : NULL;
}
+ while (entry != NULL
+ && entry->root.hash == hash
+ && strcmp (name, lookup->name) == 0);
+
return NULL;
}
@@ -1010,6 +1069,8 @@ lang_output_section_statement_lookup_1 (
lookup = lang_output_section_find_1 (name, constraint);
if (lookup == NULL)
{
+ struct output_statement_hash_entry *entry;
+
lookup = new_stat (lang_output_section_statement, stat_ptr);
lookup->region = NULL;
lookup->lma_region = NULL;
@@ -1034,6 +1095,15 @@ lang_output_section_statement_lookup_1 (
lookup->update_dot_tree = NULL;
lookup->phdrs = NULL;
+ entry = ((struct output_statement_hash_entry *)
+ bfd_hash_lookup (&output_statement_table, name, TRUE,
+ FALSE));
+ if (entry == NULL)
+ einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"),
+ name);
+
+ entry->entry = 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)
}
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. */
ldemul_finish ();
- lang_finish ();
+ lang_end ();
}
/* 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;
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 != NULL)
check_nocrossrefs ();
+ lang_finish ();
+
/* Even if we're producing relocatable output, some non-fatal errors should
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 -0800
+++ ld/testsuite/ld-elf/sec64k.exp 2005-05-01 11:50:34.000000000 -0700
@@ -24,12 +24,6 @@ if ![is_elf_format] {
return
}
-# 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.
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu
@ 2005-05-21 11:05 ` Christian Joensson
2005-05-27 16:42 ` H. J. Lu
0 siblings, 1 reply; 11+ messages in thread
From: Christian Joensson @ 2005-05-21 11:05 UTC (permalink / raw)
To: H. J. Lu; +Cc: binutils
Whatever happened with this?
/ChJ
On 5/1/05, H. J. Lu <hjl@lucon.org> 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_section_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_section_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.
> >
>
> This is the patch. I got
>
> sh 1 13.39s user 1.28s system 95% cpu 15.431 total
>
> vs.
>
> sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total
>
> That is a 26X speed up. I enabled 64k section test for all ELF targets.
>
>
> H.J.
> ----
> ld/
>
> 2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
>
> * 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.
>
> * ldlang.h (lang_finish): New.
>
> * ldmain.c (main): Call lang_finish.
>
> ld/testsuite/
>
> 2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
>
> * ld-elf/sec64k.exp: Enabled for all ELF targets.
>
> --- 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);
> }
>
> +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
> + = bfd_hash_allocate (table,
> + sizeof (struct output_statement_hash_entry));
> + ret->entry = 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. */
>
> void
> @@ -872,6 +911,8 @@ lang_init (void)
>
> stat_ptr = &statement_list;
>
> + output_statement_table_init ();
> +
> lang_list_init (stat_ptr);
>
> lang_list_init (&input_file_chain);
> @@ -898,6 +939,12 @@ lang_init (void)
> lang_statement_iteration = 0;
> }
>
> +void
> +lang_finish (void)
> +{
> + output_statement_table_free ();
> +}
> +
> /*----------------------------------------------------------------------
> A region is an area of memory declared with the
> MEMORY { name:org=exp, len=exp ... }
> @@ -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;
>
> - for (lookup = &lang_output_section_statement.head->output_section_statement;
> - lookup != NULL;
> - lookup = lookup->next)
> + entry = ((struct output_statement_hash_entry *)
> + bfd_hash_lookup (&output_statement_table, name, FALSE,
> + FALSE));
> + if (entry == NULL || (lookup = entry->entry) == NULL)
> + return NULL;
> +
> + hash = entry->root.hash;
> + do
> {
> - if (strcmp (name, lookup->name) == 0
> - && lookup->constraint != -1
> + if (lookup->constraint != -1
> && (constraint == 0 || constraint == lookup->constraint))
> return lookup;
> + entry = (struct output_statement_hash_entry *) entry->root.next;
> + lookup = entry ? entry->entry : NULL;
> }
> + while (entry != NULL
> + && entry->root.hash == hash
> + && strcmp (name, lookup->name) == 0);
> +
> return NULL;
> }
>
> @@ -1010,6 +1069,8 @@ lang_output_section_statement_lookup_1 (
> lookup = lang_output_section_find_1 (name, constraint);
> if (lookup == NULL)
> {
> + struct output_statement_hash_entry *entry;
> +
> lookup = new_stat (lang_output_section_statement, stat_ptr);
> lookup->region = NULL;
> lookup->lma_region = NULL;
> @@ -1034,6 +1095,15 @@ lang_output_section_statement_lookup_1 (
> lookup->update_dot_tree = NULL;
> lookup->phdrs = NULL;
>
> + entry = ((struct output_statement_hash_entry *)
> + bfd_hash_lookup (&output_statement_table, name, TRUE,
> + FALSE));
> + if (entry == NULL)
> + einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"),
> + name);
> +
> + entry->entry = 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)
> }
>
> 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. */
>
> ldemul_finish ();
> - lang_finish ();
> + lang_end ();
> }
>
> /* 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;
>
> 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 != NULL)
> check_nocrossrefs ();
>
> + lang_finish ();
> +
> /* Even if we're producing relocatable output, some non-fatal errors should
> 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 -0800
> +++ ld/testsuite/ld-elf/sec64k.exp 2005-05-01 11:50:34.000000000 -0700
> @@ -24,12 +24,6 @@ if ![is_elf_format] {
> return
> }
>
> -# 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.
>
--
Cheers,
/ChJ
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-05-21 11:05 ` Christian Joensson
@ 2005-05-27 16:42 ` H. J. Lu
2005-05-29 11:16 ` Alan Modra
0 siblings, 1 reply; 11+ messages in thread
From: H. J. Lu @ 2005-05-27 16:42 UTC (permalink / raw)
To: Christian Joensson; +Cc: binutils
On Sat, May 21, 2005 at 08:40:55AM +0200, Christian Joensson wrote:
> Whatever happened with this?
>
> /ChJ
>
> On 5/1/05, H. J. Lu <hjl@lucon.org> 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_section_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_section_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.
> > >
> >
> > This is the patch. I got
> >
> > sh 1 13.39s user 1.28s system 95% cpu 15.431 total
> >
> > vs.
> >
> > sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total
> >
> > That is a 26X speed up. I enabled 64k section test for all ELF targets.
> >
Here is the updated patch. I have been using this for a while. Is there
any objection?
H.J.
-----
ld/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* 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.
* ldlang.h (lang_finish): New.
* ldmain.c (main): Call lang_finish.
ld/testsuite/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* ld-elf/sec64k.exp: Enabled for all ELF targets.
--- ld/ldlang.c.hash 2005-05-11 08:12:08.000000000 -0700
+++ ld/ldlang.c 2005-05-11 09:14:33.000000000 -0700
@@ -864,6 +864,45 @@ lang_add_input_file (const char *name,
return new_afile (name, file_type, target, TRUE);
}
+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
+ = bfd_hash_allocate (table,
+ sizeof (struct output_statement_hash_entry));
+ ret->entry = 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. */
void
@@ -873,6 +912,8 @@ lang_init (void)
stat_ptr = &statement_list;
+ output_statement_table_init ();
+
lang_list_init (stat_ptr);
lang_list_init (&input_file_chain);
@@ -899,6 +940,12 @@ lang_init (void)
lang_statement_iteration = 0;
}
+void
+lang_finish (void)
+{
+ output_statement_table_free ();
+}
+
/*----------------------------------------------------------------------
A region is an area of memory declared with the
MEMORY { name:org=exp, len=exp ... }
@@ -984,18 +1031,30 @@ 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;
- for (lookup = &lang_output_section_statement.head->output_section_statement;
- lookup != NULL;
- lookup = lookup->next)
+ entry = ((struct output_statement_hash_entry *)
+ bfd_hash_lookup (&output_statement_table, name, FALSE,
+ FALSE));
+ if (entry == NULL || (lookup = entry->entry) == NULL)
+ return NULL;
+
+ hash = entry->root.hash;
+ do
{
- if (strcmp (name, lookup->name) == 0
- && lookup->constraint != -1
+ if (lookup->constraint != -1
&& (constraint == 0
|| (constraint == lookup->constraint
&& constraint != SPECIAL)))
return lookup;
+ entry = (struct output_statement_hash_entry *) entry->root.next;
+ lookup = entry ? entry->entry : NULL;
}
+ while (entry != NULL
+ && entry->root.hash == hash
+ && strcmp (name, lookup->name) == 0);
+
return NULL;
}
@@ -1013,6 +1072,8 @@ lang_output_section_statement_lookup_1 (
lookup = lang_output_section_find_1 (name, constraint);
if (lookup == NULL)
{
+ struct output_statement_hash_entry *entry;
+
lookup = new_stat (lang_output_section_statement, stat_ptr);
lookup->region = NULL;
lookup->lma_region = NULL;
@@ -1036,6 +1097,15 @@ lang_output_section_statement_lookup_1 (
lookup->update_dot_tree = NULL;
lookup->phdrs = NULL;
+ entry = ((struct output_statement_hash_entry *)
+ bfd_hash_lookup (&output_statement_table, name, TRUE,
+ FALSE));
+ if (entry == NULL)
+ einfo (_("%P%F: bfd_hash_lookup failed creating section `%s'\n"),
+ name);
+
+ entry->entry = lookup;
+
lang_statement_append (&lang_output_section_statement,
(lang_statement_union_type *) lookup,
(lang_statement_union_type **) &lookup->next);
@@ -4546,7 +4616,7 @@ lang_set_startof (void)
}
static void
-lang_finish (void)
+lang_end (void)
{
struct bfd_link_hash_entry *h;
bfd_boolean warn;
@@ -5332,7 +5402,7 @@ lang_process (void)
/* Final stuffs. */
lang_mark_used_section ();
ldemul_finish ();
- lang_finish ();
+ lang_end ();
}
/* EXPORTED TO YACC */
--- ld/ldlang.h.hash 2005-05-04 08:52:34.000000000 -0700
+++ ld/ldlang.h 2005-05-11 08:13:47.000000000 -0700
@@ -448,6 +448,8 @@ extern int lang_statement_iteration;
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-05-11 08:12:08.000000000 -0700
+++ ld/ldmain.c 2005-05-11 08:13:47.000000000 -0700
@@ -474,6 +474,8 @@ main (int argc, char **argv)
if (nocrossref_list != NULL)
check_nocrossrefs ();
+ lang_finish ();
+
/* Even if we're producing relocatable output, some non-fatal errors should
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 -0800
+++ ld/testsuite/ld-elf/sec64k.exp 2005-05-11 08:13:47.000000000 -0700
@@ -24,12 +24,6 @@ if ![is_elf_format] {
return
}
-# 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.
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: PATCH: Use a hash table for 26X linker speedup
2005-05-27 16:42 ` H. J. Lu
@ 2005-05-29 11:16 ` Alan Modra
0 siblings, 0 replies; 11+ messages in thread
From: Alan Modra @ 2005-05-29 11:16 UTC (permalink / raw)
To: H. J. Lu; +Cc: Christian Joensson, binutils
On Fri, May 27, 2005 at 09:41:02AM -0700, H. J. Lu wrote:
> > > > 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.
>
> Here is the updated patch. I have been using this for a while. Is there
> any objection?
I think I made this comment before: It seems wasteful to have two hash
tables working with virtually the same set of data. We have a section
hash table holding output section names, and you're adding another hash
table to hold output_section_statement names. I realize the two aren't
identical, but all orphans will be in both tables (and it is our orphan
section handling that makes the output_section_statement list so long).
I'd prefer if you don't commit this patch, at least until I've had time
to look at changing orphan section handling.
--
Alan Modra
IBM OzLabs - Linux Technology Centre
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2005-10-19 15:39 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-09-29 16:46 PATCH: Use a hash table for 26X linker speedup Steven Bosscher
2005-09-30 7:31 ` Alan Modra
2005-09-30 15:47 ` Nick Clifton
2005-10-01 1:45 ` Paul Brook
2005-10-04 7:23 ` Nick Clifton
2005-10-19 0:59 ` Paul Brook
2005-10-19 15:39 ` Nick Clifton
-- strict thread matches above, loose matches on Subject: below --
2005-05-01 16:57 PATCH: Use a double section list to speed up linker by 30% H. J. Lu
2005-05-01 19:09 ` PATCH: Use a hash table for 26X linker speedup H. J. Lu
2005-05-21 11:05 ` Christian Joensson
2005-05-27 16:42 ` H. J. Lu
2005-05-29 11:16 ` Alan Modra
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).