Re: Second report from Ersin

HI Ersin,

Thanks very much for this report. It's great to hear about all your
progress. Feel free to make small commits as needed to your branch. It
helps to see what you're working and is is fare as well.

With regards to re-using Joaquin's Red-back data structure, it is not
clear you win much over a vector of pointers to the page classes. The
vector allows extremely rapid searches (O(1) and O(Log(N) )and inserts
and deletes of pages are rather rare. I suspect it is not worth the
extra complexity to implement the red-black structure over the current
vector.

Cheers!

Martin

On Sun, Jun 13, 2010 at 6:51 AM, Ersin Akinci <ersin.akinci@gmail.com> wrote:
>
> Cheers everyone,
>
> I hope everyone's well!  I'm writing to apprise you of my progress on
> my GSoC project over the past two weeks.
>
> I've been working on optimizing the rendering algorithms in the
> FV_View classes, which have been considerably slowing down text input
> in very large documents (currently working with a 3000+ page text file
> of Casanova's autobiography).  As I mentioned in my previous report,
> FV_View::getPageScreenOffsets seemed to be the likely culprit, as it
> was iterating through each page starting from the first and ending
> with the current page in order to calculate a page's offsets on the
> screen, which in turn was continuously being called by
> FL_DocLayout::_redrawUpdate in order to determine which pages were on
> screen and had to be redrawn.  It turns out that this work was
> basically duplicated in FV_View::_draw, which does the actual work of
> drawing onto the screen, and I fixed it so that getPageScreenOffsets
> didn't need to be called to determine what pages are on screen.
> instead, the algorithm in _draw that does the same work sets a boolean
> variable (m_bOnScreen) for each page, and when the time comes to call
> getPageScreenOffsets for the purposes of figuring out what's on the
> page, AbiWord just checks the variable.  (NB, getPageScreenOffsets is
> still inefficient and still being called from time to time.)
>
> This has helped tremendously, but on my top of the line rig it still
> takes about 1-2 seconds to press spacebar at the end of a 3000 page
> plain text file, which is unacceptable.  The main problem now is that
> the algorithm in _draw essentially uses the same inefficient logic in
> getPageScreenOffsets: iterate through each page starting with the
> first and ending with the last until you get to the last, and
> determine which need to be drawn.  All to press spacebar!  To be more
> precise, it takes the first page of the current document section
> layout, but in text files since there's only one section that means
> going through all 3000+ pages in my test document.
>
> What I've been doing now is to rewrite _draw and various bits of the
> rendering engine so that any time AbiWord does something that would
> change the pages displayed on the screen, the called function updates
> a data structure that contains all the pages that should be on the
> screen, and then _draw simply renders those.  I haven't gotten around
> to implementing the structure, but I think that I'll end up using
> Joaquin's wonderful new red black tree, thus creating a second
> "pages-on-screen piece table".  Right now, I'm in the middle of
> identifying exactly where to put in calls to a new function that will
> determine that a particular page is on screen and in which functions
> to do so.  It will be complicated and messy, but I haven't thought of
> a better way to do it.  My strategy has been to focus on identifying
> the obvious functions first (e.g., scrolling, zooming, print preview,
> autoscroll when a new page is created), after which I will insert test
> code, then real code, and finally then remove the inefficient loop
> from _draw and test for corner cases where I still need to put in a
> call or two.
>
> I'm not thrilled about the solution I've found, but I can't think of
> anything better.  At the very least, I think it will be efficient, if
> not particularly elegant.  I'm open to suggestions and comments!
>
> Best,
> Ersin
>
> --
> Ersin Y. Akinci -- ersinakinci.com
>
> What Digital Revolution? -- www.whatdigitalrevolution.com
> Thinking critically about digital worlds.
>
Received on Sun Jun 13 15:52:04 2010