Avoiding extra work
When working on justification support in Pango
, I found a loop that could use some optimization.
The loop in question is to decide how much of a piece of text (called item. For normal text it typically is the rest of the paragraph) we can fit into the current line. The implementation was removing one character at a time from the end until we find a break spot and the width of remaining chars fits the available width.
Think about it. If the entire item fits the available width the loop is not reached at all, but otherwise, unless the paragraph fits in exactly two lines, we are doing a lot of extra work. Say the paragraph takes 10 lines. Then for the first line we have to remove 9 lines worth of text before finding the right break point. For next line we have to remove 8 lines... and so on. It's quadratic in the number of lines, so to speak.
What I did
was to start inserting chars from the beginning of the item until no more fits.
For a really long paragraph (pango/pango-view/test-long-paragraph.txt) the number of times the loop contents are run came down from ~1,000,000 to about 13,000. Not bad.
This was all in my quest to make gedit run faster when viewing a REALLY LONG paragraph. I was under the impression that some silly quadratic algorithms in Pango are responsible for the slow speed, but apparently I'm wrong
. In short, Gtk+ recreates the Pango layout on EVERY CURSOR MOVEMENT OR CURSOR BLINKING. This is mostly a result of having a very extensible and powerful text object in Gtk+ that supports multiple marks, some of them may be cursors. I've already attached a patch to improve it for cursor blinking, but that's not very interesting. I want to be able to put my finger on the left or right arrow and don't see a gedit that is frozen as a result. Way to go...
Labels: gtk+, pango, performance