msevior (msevior) wrote,

Another successful GSoC at AbiWord

Following on from James Denton's project last year which got us MultiPage View (available in our upcoming 2.8 release) I had the good fortune to mentor Aditya Manthramurthy this year. Together with legendary AbiWord Hacker Joaquin Cuenca Abela, we fixed two of the four issues that slow down AbiWord's performance for large documents.

The first fixed was our table layout algorithm. Aditya identified and fixed the cause of our layout speed increasing as N^2, where N is the number of cells. Here is a graph showing the performance of the table-layout branch.



We also had time at the end to improve the performance of AbiWord's core PieceTable by implementing Joaquin's awesome Log(N) data structure. AbiWord's current PieceTable is a doubly linked list of objects called "fragments". In addition it has a vector of the fragments ordered in their location in the document and a little cache containing the last Fragment. We perform binary searches on the PieceTable so that we can look up random positions at a rate proportional to log(N) where N is the number of fragments in the document. However upon every insert or delete we need to rebuild the vector of Fragments to reflect the changed location of the fragments downstream of the change. This means that an insert or delete happens at a rate proportional to the number of fragments, N. Consequently operations like inserting a table, which require 4 fragment inserts for each cell, slow down at a rate proportional N*N*N*N = N^4!

Joaquin invented a PieceTable based on a Red/Black tree structure which allows searchs, inserts and deletes to all happen at a rate proportional to Log(N). (See the link above) and we finally found the time to actually implement it in AbiWord. See the dramatic improvement for large table inserts below.




Since we're polishing off 2.8 now, you can expect these and many other improvements in AbiWord-2.10 :-)
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 7 comments