Tue Apr 8 18:33:00 GMT 2003
> Date: Tue, 8 Apr 2003 20:10:20 +0200
> From: Zdenek Dvorak <email@example.com>
> Cc: firstname.lastname@example.org
> Content-Disposition: inline
> User-Agent: Mutt/1.3.28i
> X-OriginalArrivalTime: 08 Apr 2003 18:09:57.0093 (UTC) FILETIME=[0FF17950:01C2FDFA]
> > Zdenek Dvorak <email@example.com> writes:
> > > Hello,
> > >
> > > > I believe purge_addressof costs us almost nothing
> > > >
> > > > Not at all true, since it can iterate over all insns, so if you have a
> > > > mechanism that calls it a fixed percentage of the time, it's actually
> > > > *quadratic*.
> > >
> > > can you explain this in greater detail? It is one pass over insns, so it
> > > should be linear, no?
> > If you take a linear operation (that is, O(n)), and then you perform
> > it K*n times for some fixed constant K, then the program is O(n*n),
> > which is quadratic.
> Why do you think purge_adressof does linear work per insn?
I don't. I don't think anyone does. Richard was saying that if
purge_addressof is linear in the number of insns, and you then call it
a number of times that's proportional to the number of insns, that
makes it quadratic.
- Geoffrey Keating <firstname.lastname@example.org>
More information about the Gcc-patches