Date: Mon Jan 29 2004

Authour: Johnny Lee

Email: typo_pl@hotmail.com

Summary

I took a look at Abiword bug 5880 and my profiled run of Abiword on this test case produced similar results to the profiled output attached to the bug report.

After much time trying to understand what the code was doing, I devised a solution which reduced the runtime for this operation to <2% of the original runtime!

Diffs can be found here: http://www.geocities.com/typopl/bug5880diff.txt

This table shows the time to change the language of all the text in a document from English to Greek using Abiword and using Abiword with my proposed patch.

The time is the average of three runs. The document I used is the document attached to the bug report for bug 5880.

App	Operation time (ms)
Abiword 2.1.0	8500
... + Patch 1	120

Links:

1. Bugzilla bug entry: Bugzilla Bug 5880 - very slow in setting language on entire document
2. Start of discussion thread: Are we ready for 2.0.3?
3. Abiword Piece Table Description: Piece Table Description
4. Email thread describing my patch: [PATCH] Fix bug 5880 - very slow in setting language on entire document

Setup

Windows 2000 SP4. MS VC6 with SP5.

Abiword source code, abiword-2.1.0.tar.gz

Problem

Bug 5880 describes an operation in Abiword that takes too long - changing the language of all the text in a document.

The following table shows a profile of Abiword changing the language for a large text selection.

One call to FV_View::setCharFormat proceeds to 512 calls to pt_PieceTable::_fmtChangeSpanWithNotify resulting in a similar number of calls to FV_View::getCharFormat which causes millions of calls to PP_AttrProp::getProperty and PP_AttrProp::getAttribute.

Code Investigation

When a user changes the language of a text selection, Abiword calls FV_View::setCharFormat which calls PD_Document::changeSpanFmt which calls the PieceTable code to do the actual work.

For each text fragment in the selection, the PieceTable code calls pt_PieceTable::_fmtChangeSpanWithNotify which does the actual attribute/property change and then tells the Document to notify the document listeners of the format change.

One of the objects listening is the View for the Document. When the View sees a character format change, it updates its character format change state for the current text selection, i.e. the common attributes/properties for the entire text selection.

There's a comment in the relevant code (see Line 1331 of abi\src\text\fmt\xp\fv_View.cpp) which describes how time-consuming this operation can be:

		/*
		  The following brute-force solution works, but is atrociously
		  expensive, so we should avoid using it whenever feasible.

		  TODO: devise special case logic for (at minimum) char motion
		*/

The character-format-change-state-update code does the following:

1. Put in a list all the attributes and properties for the first text fragment in the selection
2. Iterate over the remaining text fragments in the text selection, comparing the attributes and properties of the first fragment with the attributes and properties of the other text fragments in the selection. Any attribute or property which have different values between text fragments is removed from the first list. When finished all that remains in the list are attributes and properties that exist in all text fragments in the selection and have the same value in all text fragments.
3. Compare the list of common attributes and properties with the View's last list of character format changes. If the lists are different, then the new list becomes the current list of character format changes.

For the test case, the text selection covers the entire document, so each text fragment (essentially each line in the test document) causes the code to recalculate the character format since each text fragment's language is modified individually.

512 text fragments result in 512 calculations of the common character format.

That's where all the time is going.

Proposed Solution

• change the notification mechanism so that document listeners can defer propagating change notifications. In the case of a text selection that consists of several text fragments, updating the common character format for the entire text selection may be incorrect until the final text fragment in the selection has been modified.
• after the format modification operation has completed, call the document listeners to tell them that they can handle the change notifications now. Only the document listener for the View is modified to handle deferred changes.

Here's the result of profiling the new version of Abiword changing the language for the entire document: