Re: [patch] Eliminate quadratic slow-down on number of solibs (part 2).

[Paul Pluzhnikov <ppluzhnikov@google.com>]

On Thu, May 14, 2009 at 1:14 AM, Joel Brobecker <brobecker@adacore.com> wrote:

>> 3. The "don't reset all breakpoints over and over when adding
>>    multiple solibs" patch here:

> I completely misunderstood this change you proposed! I see now what
> you are doing. This wouldn't help on systems such as Windows where
> DLLs are "discovered" through special events while waiting for inferior
> events.  So shared libraries are never loaded at once, neither during
> startup or attaching.

Right. So Windows behaves as a program that dlopen()s all of
its DLLs in sequence.

> But on GNU/Linux, however, you're right, there
> is something to do in that case.
>
> I'd like to think about it, for a while... I wonder if we could use
> an observer to notify clients that symbols have been loaded, rather
> than calling breakpoint_re_set directly.

This (I think) would effectively achieve the same result as patch#2,
calling breakpoint_re_set only for individual solib.

[BTW, is it ok to commit patch#2 ?]

The problem is that breakpoint_re_set does a bunch of unnecessary
work, even when it knows which solib it should be dealing with.
In particular, for each breakpoint, it re-parses its addr_string,
selects correct address (possibly skipping function prolog, etc.).

When 'break main' is in effect, this one breakpoint's addr_string
is parsed N times, main is looked up N times, main's prolog is
skipped N times, etc. etc. This isn't quadratic, but accounts for
~15% of startup time, and adds up to minutes or large N.

I see that my comment about patch#3 transforming O(N*N) into O(N)
is correct only if patches #1 and #2 aren't applied. If they are
applied, then (I believe) patch#3 transforms O(N*M) into O(M), where
N is the number of solibs added "at once" and M is the number of
current breakpoints.

Thanks,
-- 
Paul Pluzhnikov