Fl_Text_Editor + pango + word wrap -> hangs on scroll

[Taeril]

FLTK 1.4 - latest at moment from git
Linux cmake builds: with and without pango

Test case:
Run editor from example programs and open some file (for example editor.cxx). Next select word wrapping from menu and try to scroll view.

Result:
Build without pango works without a hitch.
Build with pango hangs making program unresponsive for a while.

[Albrecht-S]

Thanks for the report. I'll look into it...

My guess is that FLTK built with pango is much slower when it comes to calculating all the widths it needs to find the word wrapping positions. This is a well-known issue.

However, I also guess that FLTK might calculate too much text (maybe the entire file?) and not only the parts needed for the current display. This is where I'd like to look into further. However, don't expect quick results since Fl_Text_Display (Fl_Text_Editor) is a giant and complicated widget.

[Albrecht-S]

If you are willing to test further, can you please answer these questions?

• do you also see this effect with smaller files?
• i.e. does the time it "hangs" depend on file size?
• does it also depend on the Fl_Text_Editor (screen) width? (unlikely IMHO)
• any other insights, maybe?

[Taeril]

• Yes, I noticed that effect also with smaller files
• It's hard to measure time so I can't tell. But other time related thing is tiny movement of mouse scroll resulted with shorted hang.
• Haven't tested width of Fl_Text_Editor
• There is that function called so many times...

diff --git a/src/drivers/Xlib/Fl_Xlib_Graphics_Driver_font_xft.cxx b/src/drivers/Xlib/Fl_Xlib_Graphics_Driver_font_xft.cxx
index ee36e1cf6..ace58845e 100644
--- a/src/drivers/Xlib/Fl_Xlib_Graphics_Driver_font_xft.cxx
+++ b/src/drivers/Xlib/Fl_Xlib_Graphics_Driver_font_xft.cxx
@@ -1352,11 +1352,20 @@ void Fl_Xlib_Graphics_Driver::do_draw(int from_right, const char *str, int n, in
 double Fl_Xlib_Graphics_Driver::width_unscaled(const char* str, int n) {
   if (!n) return 0;
   if (!fl_display || size_ == 0) return -1;
+  //fprintf(stderr, "[%d] %.*s\n", n, n, str);
+  //return 8 * n;
+  static int n1[256] = {0};
+  if (n == 1 && n1[str[0]] != 0) {
+    return (double)n1[str[0]];
+  }
   if (!playout_) context();
   int width, height;
   pango_layout_set_font_description(playout_, pfd_array[font_]);
   pango_layout_set_text(playout_, str, n);
   pango_layout_get_pixel_size(playout_, &width, &height);
+  if (n == 1) {
+    n1[str[0]] = width;
+  }
   return (double)width;
 }
 

With that commented out printf you can see that it's doing a lot of work.
Just returning 8*n "solves" problem, but it OK value only in this case.
Rest of added code uses memoization for one letter strings and that make it almost OK with noticeable refreshes when resizing window, but scrolling view was smooth enough.
But sometimes after that change text was hidden behind right scrollbar and I have no idea why. Maybe because it's wrong solution as it's not taking into account what font is used?

I have no idea if I was looking at right place even if I got some results. Maybe solution is not to call that function so many times?

[ManoloFLTK]

The Fl_Text_Display widget computes the width of each character in the buffer as drawn
when in "word wrap" mode. That computation is not done when that mode is off.
This is done in Fl_Text_Display::recalc_display() when the user moves the mouse wheel.

Under Xft, these widths are obtained by function XftTextExtents32() which presumably,
memorizes widths once computed.
Under Pango, these widths are obtained by the function Taeril mentionned,
that calls pango_layout_get_pixel_size() which apparently does not memorize
precomputed character widths.

For a 4500-line C++ text file, I got these durations of the Fl_Text_Display::recalc_display()
function: 2 sec with Pango, 0.05 sec with Xft. That's the source of the hanging effect.

* do you also see this effect with smaller files?

Not with small files

* i.e. does the time it "hangs" depend on file size?

Yes

* does it also depend on the Fl_Text_Editor (screen) width? (unlikely IMHO)

No

[Albrecht-S]

Many thanks to both of you for testing and analysis. @ManoloFLTK, do you have any ideas on how to improve this?

For a 4500-line C++ text file, I got these durations of the Fl_Text_Display::recalc_display()
function: 2 sec with Pango, 0.05 sec with Xft. That's the source of the hanging effect.

So, whatever pango does, let's assume the display height allows the display of 45 lines. If we could manage to calculate only these 45 lines this would result in 0.02 sec (1/100 of the measured time 2 sec) which would likely be fine. Scrolling could still be slow because we'd have to calculate more and more of the text in the file. This is just a thought and would have to be done in the context of Fl_Text_Display.

OTOH, do you think we could optimize the usage of pango to find a faster function to measure text? I'm sure you know the involved code better than me.

[ManoloFLTK]

It might be possible to memorize character widths after each has been computed.
That's what happens in the Windows platform. But this can cost much memory
if a large character set is used.

[Albrecht-S]

I can try to look into the "calculate less widths" issue, i.e. limit recalculation to the part that is currently displayed. If this works out we'd not need to worry about pango usage and memorizing character widths, which seems not well suited anyway since pango would layout text properly - i.e. the width of a word is not equal to the sum of the individual character widths. Hence memorizing and adding character widths would not be correct.

[ManoloFLTK]

I attach a first approach to memorize some character widths when computed under pango.
The patch also modifies the Fl_Text_Dispay widget to time calls to function Fl_Text_Display::recalc_display()

fast-pango.patch.txt

[Albrecht-S]

@ManoloFLTK Thanks for the patch. I tried it and it works ... somehow. When I looked at the patch I wondered how it could work since it would only cache single character widths and I assumed that the majority of width calculations would be entire words or full lines. Hence I added some more code for statistics output (see attached patch statistics.diff.txt which is an add-on on your patch (apply after yours) and the output in statistics.txt).

Some words to the output: both tests were done by starting the editor with the same file, then I scrolled slowly all the way down, then up again, and then a little bit down again until I saw the output given in statistics.txt. Shown Variables:

• num = number of width calculations
• hits = number of hits (width already in memory)
• miss = number of misses (width of string not found or more than 1 char)
• ncount is an array of the number of calls with n = {0, 1, ..., 10, >10}
• lcount is an array of the length of the first char in UTF-8 encoding = {0, 1, ...}

As we can see in this test all tested characters were strict ASCII (0-127) which is encoded by 1 byte in UTF-8. [Edit: this is only correct for the first test.]

width[] is an image of the array of found character widths, indexed by its Unicode value. The output would show each character literally, but in the first test the only character found/tested is the space character which you can't see.

1. The first test was done w/o word-wrap and showed only 1.88% hits of single character hits.

2. The second test was done with word-wrap enabled and shows that we're testing way more strings (37,550,000 vs. 120,000) which is suspicious by itself. As a consequence we see millions of single character matches (99.78%) which seems to be the reason why the patch has such a positive effect. You can see many more different characters in the width[] array.

Note that I tried a text file (arbitrary text from a man page). A source file would show a different character pattern in the width[] hit array.

My conclusion is that the culprit seems to be in Fl_Text_Display which measures too many strings to find the word wrap positions. I'll try to analyze that code later.

The single character (or whatever) width caching can't work well in general, particularly if we think of international (e.g. Chinese) characters.

But anyway many thanks for the patch, it gave some interesting insights. I'm open for other ideas but my gut feeling is that the culprit is really in Fl_Text_Display and we must reduce the number of width measurements to be effective in all cases.

[ManoloFLTK]

Thanks for these complementary data.
As I wrote above, function Fl_Text_Display::recalc_display() is called at each click of the mouse wheel, which, when in word wrap mode, computes the width of each character of the text buffer, one by one.
That makes a lot of one-char width calculations. That's why the patch which speeds up only
these calculations has a large effect.
That approach of speeding one-char width computations can be generalized to the whole unicode space as done for the windows platform which allocates blocks of char widths around the codepoints effectively in use in the text.
I agree it would be good to reduce the number of widths computations, but fear it's a complex task.

[ManoloFLTK]

@albrecht: do you intend to modify Fl_Text_Display to reduce the number of one-char width computations it makes?

Here are a few other ways to fix this issue, possibly temporarily, I see :

1. use the patch above which is very ad-hoc to accelerate Fl_Text_Display in wrap mode
   for unicode codepoints below 0x590 which covers essentially all latins scripts, Greek and Cyrillic.
   Fl_Text_Display would remain slow with, say, CJK text.

2. extend the patch above to cover all unicode. That is what is done for the Windows
   platform in function Fl_GDI_Graphics_Driver::width_unscaled(unsigned int c).
   I could do that rapidly because it would be simple to adapt to Pango the Windows code.

3. as in 2) above, and also compute string widths by summing one-character widths,
   as done under Windows in function Fl_GDI_Graphics_Driver::width_unscaled(const char* c, int n).
   That would make the code less ad hoc, but could be inaccurate if Pango changes
   character spacing in strings in a context-dependent way.

One of these 3 options could be implemented soon not to delay the release of FLTK 1.4,
and the more ambitious fix based on reducing the number of widths computations
could be implemented later, when available.

Opinions?

[Albrecht-S]

@ManoloFLTK Thanks for your suggestions. I'd like to take a look at Fl_Text_Display to reduce the number of one-char width computations but this may take a while. For a temporary solution as suggested by you my thoughts are:

1. would be acceptable for a short-term solution
2. would also be fine with me
3. I would suggest not to use (3) because it feels wrong to do this when we use Pango

Before we decide (IMHO between 2 and 3) I'd like to take a look at the code to see if I can find a better solution quickly. If that doesn't work out we can still decide to use (1) or (2) as a quick solution. I'll post my findings here ASAP.

[ManoloFLTK]

Please, consider in https://github.com/ManoloFLTK/fltk.git, branch fast-pango
an implementation of solution 2 exposed above, that is, where all of unicode is considered.

Furthermore, this code modifies computations of string widths only within the Fl_Text_Display
widget and only when it's in word wrap mode. That is achieved by a new virtual member function
of class Fl_Graphics_Driver
virtual double fast_width(const char *str, int n) {return width(str, n);};
which is re-implemented only under X11+pango and which is used only
in function Fl_Text_Display::string_width(). The modified code therefore impacts (for the better) only
Fl_Text_Display widgets in word wrap mode and only under the X11+pango platform.

[ManoloFLTK]

I attach a test text file containing, at the end, text from various scripts.
prov.txt

[ManoloFLTK]

This issue affects also the test/table demo program which requires a very long time to start
when PANGO is activated.
The cause of the problem is the same: an Fl_Text_Display object recomputes many times the width
of single characters.
The cure is the same: branch fast-pango of https://github.com/ManoloFLTK/fltk.git .
With that modification, test/table starts rapidly.

[ManoloFLTK]

This should be fixed with commit 368f180 .