Fwd: First report from Ersin

---------- Forwarded message ----------
From: Ersin Akinci <ersin.akinci@gmail.com>
Date: Tue, Jun 1, 2010 at 3:15 PM
Subject: Fwd: First report from Ersin
To: Martin Sevior <msevior@gmail.com>

---------- Forwarded message ----------
From: Ersin Akinci <ersin.akinci@gmail.com>
Date: Sat, May 29, 2010 at 3:06 AM
Subject: First report from Ersin
To: abiword-dev <abiword-dev@abisource.com>

Hi all,

I'm writing to share my progress on my GSoC 2010 with the community.
This is my first report, so please feel free to let me know if this
isn't quite what was expected or if I can improve next time.  All
comments and criticisms are welcome!

I've spent the past two weeks largely exploring the code base,
especially Joaquin's excellent new red black tree structure, which I
have yet to fully comprehend.  My aim has been to identify bottlenecks
that would prevent the implementation of my project proposal, which
calls for complex non-linear page flows with documents tested up to
1000 pages.  I have a pretty solid grasp on how input works from the
keyboard and how the piece table functions operate together to create
the linked list, but I'm still unclear about the tree itself,
especially the theory behind how each node manages to be unique with
only left branch length and fragment length information.

Part of the problem has been my inexperience with debugging in gdb.  I
had been placing breakpoints in various functions related to the tree
structure to understand how it works, but these were constantly called
by notifier functions for what seemed to be thousands of iterations
that I couldn't get past and which prevented me from properly
backtracing.  This occupied several days of effort, until yesterday
when Martin pointed out that you can press Ctrl+C to arbitrarily break
anywhere (thanks, Martin!)

As it turns out, the major inefficiencies in inserting characters (and
possibly in loading documents) aren't coming from the tree structure,
but rather from the formatting functions, especially
FV_View::getPageScreenOffsets.  I've been observing the behavior of
this function, and it seems like it is ultimately being called by
FL_DocLayout::_redrawUpdate (after several intermediary calls) to set
the x and y offsets of the current page that's being edited.  There
are a few problems with this.  First, getPageScreenOffsets's algorithm
is really inefficient: if you're editing the last page in a 3000 page
document, it will traverse the layouts for each page starting from 0
and use the sum of the y offsets to calculate page 3000's yoffset.
Second, this function seems to be called a number of times for each
page refresh.  A cache/pointer of some sort would probably help, as
might perhaps migrating the particular structures that it traverses (I
think it is the block layouts) from whatever form they currently have
(linked list?) to the new tree structure (NB, this is wild
speculation; as I said, I'm still figuring out the piece table, and I
forget if block layouts are contained in it already or not).  But
perhaps the fundamental problem is that the screen refresh is being
calculated on a gigantic virtual coordinate plane, whereas the code
should be changed so that the x and y offsets are calculated from the
screen.  I hope that my next steps will be little more than a
refresher, as I've already dealt with the logical/physical layers of
the rendering engine before.  As always with programming, however,
I've learned to expect these things to take much more time than usual.

Personally, I was a little disappointed at my progress these past two
weeks.  I had to move between towns, which distracted me for a while,
but I still want to get more done in the coming round.  I have a very
positive feeling about my current tack, and my optimistic half says
that I will be able to commit a patch to my branch to fix
getPageScreenOffsets within a week.  After that, hopefully performance
will have improved enough that I can move on with implementing my
proposal.  There are a few other performance-related areas that I'd
like to look into, however, especially the notifiers.

Best,
Ersin

--
What Digital Revolution? -- www.whatdigitalrevolution.com
Thinking critically about digital worlds.
--
What Digital Revolution? -- www.whatdigitalrevolution.com
Thinking critically about digital worlds.