Subject: Re: speed results
From: Joaquín Cuenca Abela (cuenca@celium.net)
Date: Sat Apr 14 2001 - 13:05:25 CDT
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...
> If this works I'll put code in place in getEdittableBounds() to use
> something like this algorithm for docs without headers too.
>
> For updateLayout() we need to find a way to just scan blocks in pages on
> screen only.
>
> I have some ideas for this too.
>
> It's great to have this sort of metric to test algorithims against.
>
> The random formatting changes are a great idea. If Abi passes those the
> next test are random insertions of line breaks, paragraph breaks, tabs,
> column breaks and page breaks.
yes, currently my tests involves random words with random formatter
changes (the probabilities are choosen to mimic a typical user session
(maybe the number of format changes are still a bit too high).
I will add a bit of line breaks (done), paragraph breaks (done), tabs
(todo), column breaks (todo) and page breaks (todo). But I want to
split the script in
1) a torture test, which ultimate goal is segfault abi
2) a "typical-user-like" test, which goal is only to mesure the
performance.
> Then toss in some undos/redos. If you really want to break Abi put in some
> section breaks with column changes then undo/redo them.
>
> Also try multi-level lists with more than one view of the document. Put in
> some random deletes/ cuts/pastes and undo/redo stuff.
Yeah, I want to add too, a bit of cursor motion (right now it always
append the word at the end of the document).
> Ask Jesper for even more specific torture tests :-)
:-) I will ask bugzilla too
Cheers,
-- Joaquín Cuenca Abela cuenca@celium.net
This archive was generated by hypermail 2b25 : Sat Apr 14 2001 - 13:05:40 CDT