Description of problem:
Linking our shared C++ library got much slower after an update to FC5. I am not
sure about FC4, but I can tell that there is a difference, like night and day,
compared to FC3. Even given the large symbol count both in the library and its
dependencies, it definitely didn't take minutes as it does now. On a 2.8 P4 with
3GB of RAM, it now takes 5 minutes. Runtimes in the order of minutes have been
seen with a 3.0GHz dual Xeon (3GB of RAM) and a 2.0GHz dual Opteron 246 (4GB of
RAM). Under FC3, the same library used to link in 30-60 seconds at most. I can
collect more accurate numbers if it helps, but the above should give an idea.

Version-Release number of selected component (if applicable):
binutils-2.16.91.0.6-5

How reproducible:
Always

Additional info:
I captured oprofile data with callgraph=3.

This is the short -l output of symbols with 5 or more samples:

CPU: P4 / Xeon, speed 2793.52 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped)
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
1094     27.1128  ld                       walk_wild_section_specs3_wild2
904      22.4040  anon (tgid:15116 range:0x970000-0x971000) (no symbols)
874      21.6605  ld                       walk_wild_section_general
596      14.7708  ld                       match_simple_wild
158       3.9157  ld                       walk_wild_section_specs1_wild1
138       3.4201  ld                       walk_wild_section_specs2_wild1
79        1.9579  ld                       lang_size_sections_1
54        1.3383  ld                       lang_process
43        1.0657  ld                       walk_wild_section_specs4_wild2
22        0.5452  ld                       lang_add_section
15        0.3717  ld                       lang_do_assignments_1
8         0.1983  ld                       walk_wild_file
6         0.1487  ld                       walk_wild
5         0.1239  ld                       walk_wild_section
5         0.1239  ld                       yylex

This is the callgraph output of the top four symbols (all those above 5% of
total sample count):

CPU: P4 / Xeon, speed 2793.52 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped)
with a unit mask of 0x01 (mandatory) count 100000
samples  %        image name               symbol name
-------------------------------------------------------------------------------
  1519     100.000  ld                       walk_wild_section
1094     27.1128  ld                       walk_wild_section_specs3_wild2
  1094     71.3633  ld                       walk_wild_section_specs3_wild2 [self]
  417      27.2016  ld                       match_simple_wild
  14        0.9132  ld                       find_section
  8         0.5219  ld                       walk_wild_consider_section
-------------------------------------------------------------------------------
904      22.4040  anon (tgid:15116 range:0x970000-0x971000) (no symbols)
  904      100.000  anon (tgid:15116 range:0x970000-0x971000) (no symbols) [self]
-------------------------------------------------------------------------------
  2009     100.000  ld                       walk_wild_section
874      21.6605  ld                       walk_wild_section_general
  874      99.3182  ld                       walk_wild_section_general [self]
  6         0.6818  ld                       walk_wild_consider_section
-------------------------------------------------------------------------------
  21        3.5176  ld                       walk_wild_section_specs4_wild2
  23        3.8526  ld                       walk_wild_section
  52        8.7102  ld                       walk_wild_section_specs2_wild1
  84       14.0704  ld                       walk_wild_section_specs1_wild1
  417      69.8492  ld                       walk_wild_section_specs3_wild2
596      14.7708  ld                       match_simple_wild
  596      100.000  ld                       match_simple_wild [self]

I guess the problem has something to do with symbol lookups, but I have no clue
where to start looking for more hints. Did something in this area change? The
only other factor I can think of is that the library itself depends on a number
of other libraries and some of those are the same binaries we used under FC3.
Maybe the newer ld triggers some pathological behaviour when linking against
older libraries? I have no more ideas. Please advise.