This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
[PATCH] Optimize ldlang_add_file for large input quantities
- From: Noah Misch <noah at cs dot caltech dot edu>
- To: binutils at sourceware dot org
- Date: Sat, 26 May 2007 08:47:16 -0700
- Subject: [PATCH] Optimize ldlang_add_file for large input quantities
I collected a profile of GNU ld while it linked a local application. In this
invocation, ldlang_add_file used 21.7% of the linker run time. The application
in question generates many thousands of input BFDs, each rather small; as such,
the linker spends a relatively large amount of time repeatedly finding the
input_bfds tail. This patch makes ld store that tail, clearing this bottleneck.
The following fanciful link illustrates the difference:
echo 'static int foo = 5;' >foo.c
gcc -c foo.c
i=10000
while test $i -gt 0; do
ln -s foo.o f-$i.o
i=$(($i - 1))
done
echo 'int main() {return 0;}' >main.c
gcc -c main.c
time gcc f-*.o main.o
CVS ld, without patch:
15.61user 1.86system 0:17.47elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+91982minor)pagefaults 0swaps
with patch:
3.84user 1.47system 0:05.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+91983minor)pagefaults 0swaps
The test suite shows no regressions on i686-pc-linux-gnu.
2007-05-26 Noah Misch <noah@cs.caltech.edu>
include/
* bfdlink.h (struct bfd_link_info): Add input_bfds_tail.
ld/
* ldlang.c (ldlang_add_file): Use input_bfds_tail.
diff -urp -X /home/nm/src/cvs/dontdiff src-clean/include/bfdlink.h src-many_input/include/bfdlink.h
--- src-clean/include/bfdlink.h 2007-04-30 10:06:40.000000000 -0400
+++ src-many_input/include/bfdlink.h 2007-05-26 09:42:58.000000000 -0400
@@ -396,6 +396,9 @@ struct bfd_link_info
together via the link_next field. */
bfd *input_bfds;
+ /* Tail of the above list of input BFDs. */
+ bfd *input_bfds_tail;
+
/* If a symbol should be created for each input BFD, this is section
where those symbols should be placed. It must be a section in
the output BFD. It may be NULL, in which case no such symbols
diff -urp -X /home/nm/src/cvs/dontdiff src-clean/ld/ldlang.c src-many_input/ld/ldlang.c
--- src-clean/ld/ldlang.c 2007-05-01 21:22:40.000000000 -0400
+++ src-many_input/ld/ldlang.c 2007-05-26 10:39:39.000000000 -0400
@@ -5435,8 +5435,6 @@ lang_for_each_file (void (*func) (lang_i
void
ldlang_add_file (lang_input_statement_type *entry)
{
- bfd **pp;
-
lang_statement_append (&file_chain,
(lang_statement_union_type *) entry,
&entry->next);
@@ -5445,9 +5443,11 @@ ldlang_add_file (lang_input_statement_ty
a link. */
ASSERT (entry->the_bfd->link_next == NULL);
ASSERT (entry->the_bfd != output_bfd);
- for (pp = &link_info.input_bfds; *pp != NULL; pp = &(*pp)->link_next)
- ;
- *pp = entry->the_bfd;
+ if (link_info.input_bfds == NULL)
+ link_info.input_bfds = entry->the_bfd;
+ else
+ link_info.input_bfds_tail->link_next = entry->the_bfd;
+ link_info.input_bfds_tail = entry->the_bfd;
entry->the_bfd->usrdata = entry;
bfd_set_gp_size (entry->the_bfd, g_switch_value);