Re: PATCH: Slow linker with shared C++ libraries (sorted array)

[Lars Knoll <lars at trolltech dot com>]

On Friday 27 February 2004 06:54, Andreas Jaeger wrote:
> "H. J. Lu" <hjl@lucon.org> writes:
> > On Thu, Feb 26, 2004 at 01:11:47PM -0800, H. J. Lu wrote:
> >> On Thu, Feb 26, 2004 at 11:58:05AM +0100, Lars Knoll wrote:
> >> > On Thursday 26 February 2004 07:19, H. J. Lu wrote:
> >> > > If a shared C++ library has many weak data definitions and many
> >> > > symbols, linking against such libraries can be very slow since
> >> > > elf_link_add_object_symbols has to go through all symbols for
> >> > > each referenced weak data definition to search for its aliases,
> >> > > although in most cases there is no alias. What is the best way
> >> > > to speed it up? Can we introduce a linker command not to check
> >> > > aliase for a DSO?
> >> >
> >> > Michael Matz and myself made a patch to speed up weak symbol handling
> >> > in the linker, see:
> >> >
> >> > http://sources.redhat.com/ml/binutils/2003-09/msg00175.html
> >> >
> >> > As far as I know the patch is still not in binutils, but it sounds
> >> > very much like a solution to your problem.
> >>
> >> That is the same problem. You may want to add h->type != STT_FUNC
> >> when you create the hash table. In my testcase, there is no visible
> >> speed difference between sorted array and hash table. Either way
> >> should work for me.
> >>
> >> I am enclosing the modified hash table patch here. Could someone
> >> please take a look at both?
> >
> > Here is the updated version of sorted array approach. I'd like to
> > see one of them get checked in.
>
> Can you give us some runtime number of binutils with either patch and
> without?

You can find some numbers using Qt and Qt designer (which links against libqt) 
as test library and application in the mail from september. Just added them 
for convenience once again. The speedup is huge when linking against a big 
C++ library (so linking of libqt doesn't profit, while linking of designer 
gets a factor of 5 faster):

without patch:
libqt-mt.so  real    0m2.409s user    0m2.190s sys     0m0.220s
designer     real    0m3.425s user    0m3.350s sys     0m0.080s

with patch for weak symbols:
libqt-mt.so  real    0m2.374s user    0m2.040s sys     0m0.330s
designer     real    0m0.815s user    0m0.710s sys     0m0.100s

Notice that the running time for linking N weak symbols changes from O(N^2) to 
O(NlogN), so for bigger projects the effect will be even larger.

Regards,
Lars