Subject: Re: speed results
From: Martin Sevior (msevior@mccubbin.ph.unimelb.edu.au)
Date: Sat Apr 14 2001 - 18:04:56 CDT
On Sat, 14 Apr 2001, [iso-8859-1] Joaquín Cuenca Abela wrote:
> Martin Sevior wrote:
> >
> > HI Joaquin,
> > This is really cool! Please commit the script. If for no other
> > reason than to have an first example of perl scripting of Abi. Looks like
> > I'll be learning Perl afterall.
> >
> > Regarding source of the speed slow down. There are two methods that I
> > know of that both grow at order n which are called for every keypress.
> >
> > 1. The getBounds() method in the pieceTable code as mentioned by Pat Lam.
> > 2. The updateLayout() method in fl_DocLayout also grows as order n since
> > it continually checks the whole document in the background.
> >
> > Since these are independent operations we get a slowdown of order
> > n^(2) from these methods alone.
>
> if both these methods are O(n), we end with a slowdown of O(n) (O(n) +
> O(n) = O(2n) ~= O(n))
> (and that is what we're seeing in the graphs)
>
> > As a quick check of my theory try inserting a header in your doc and
> > re-running the test. With a header in place the code should not call
> > getBounds on every word but uses a different algorthim of o(0).
>
> O(1), I suppose...
>
> > If I'm right the speed decrease should drop to order (1.5) from your order
> > 2.5.
>
> I will test it... anyway I don't know what scares me the most, a O(n)
> operation to insert a word, or a backend that improves dramatically its
> speed if you have a header in it...
With a header in place getEdittableBounds() searches for the end of the
Edittable region by skipping through the SectionLayout claases until it
bumps up against a HdrFtrSection. Then it Finds the last block then then
last run in the block and returns the docPosition of the run. That's the
end of Edittable region. On the other hand getBounds() skips through all
the Frags in the document until it runs out of then. Then find the
position of the last one.
Cheers
Martin
This archive was generated by hypermail 2b25 : Sat Apr 14 2001 - 18:05:08 CDT