Re: speed results

Subject: Re: speed results
From: Martin Sevior (
Date: Sat Apr 14 2001 - 10:49:03 CDT

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.

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).

If I'm right the speed decrease should drop to order (1.5) from your order

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.

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.

Ask Jesper for even more specific torture tests :-)



This archive was generated by hypermail 2b25 : Sat Apr 14 2001 - 10:50:22 CDT