GNOME Bugzilla – Bug 702389
Layouting performance on very long lines containing many tabs is suboptimal
Last modified: 2018-05-22 13:09:51 UTC
Consider a code editor which displays lines with wrapping disabled. Pango's layouting performance on very long lines that contain lots of tabs is suboptimal. This can be explained by the fact that tabs force the line to be broken into many runs. Because line wrapping is disabled, these runs are all put into a single PangoLayoutLine. Due to the large amount of runs some of the algorithms within Pango's layouting code exhibit suboptimal performance. This has been tested with a string solely consisting out of tabs and normal spaces. Groups of spaces and tabs are stored in separate runs. I have identified three areas within the layouting code where performance can be improved without too much work. I will attach three patches corresponding to these areas. The patches seem to behave well, but please NOTE that I have not done extensive testing with scripts other than English ...
Created attachment 246945 [details] [review] [PATCH 1/3] Bypass line reordering if all runs have analysis level zero For all lines, an expensive reordering algorithm is run in pango_layout_line_reorder() that reconstructs a singly linked list. In case we know that the line only contains runs with equal analysis level, this line reconstruction is not necessary. Since the length of the line needs to be determined, we can determine whether all items have the same analysis level at the same time and decide to take a shortcut based on this. FIXME: There is the potential to further generalize this patch. I would like the know whether a patch like this would be acceptable for inclusion and whether I am not missing something (e.g. possibly there is a reason why reconstruction is always necessary?).
Created attachment 246947 [details] [review] [PATCH 2/3] Cache line width during construction of the line Every call to shape_tab() to shape a tab, will call line_width(). For a line with many tabs, this inefficient function is called frequently, each time recomputing the width of the line up till now. Even though the comment in the function mentions that keeping the current width of the line up to date everywhere is hard, this patch introduces a "cached_line_width". The cached_line_width basically corresponds to the current return value of line_width() if it would be called, avoiding performing an expensive iteration of the full line repeatedly.
Created attachment 246949 [details] [review] 3/3 Redo shape_tab and get_tab_pos to have better performance for long lines Next to calling line_width(), shape_tab() repeatedly calls get_tab_pos() from a for loop. For strings with a large width, get_tab_pos() will be called frequently. The main problem is that searching for tab position begins from the start of the line, regardless of the current width of the line. This patch carefully re-engineers get_tab_pos() and shape_tab() to start looking for a suitable tab position based on the current_width of the line, so close to the target tab position. As a result, many function calls to get_tab_pos() and indirectly to pango_tab_array_*() are avoided.
I agree with your analysis, but prefer to find a solution that wouldn't complicate the codebase unnecessarily. Let me find some time to take a deeper look into this. PangoLayout is due for a rewrite soon anyway, but I don't think I'll get to do that this year or even the next :(. If you clean up your patches to your own satisfaction, feel free to push them out. Re the bidi stuff, you're right, all-even and all-odd should bypass reordering.
Thanks for having a loop. I will update patch 1) with the all-even/all-odd modification soon. Also, I just found a typo crept in patch 3 during rebasing (last_post instead of last_pos); sorry for that.
Created attachment 248203 [details] [review] Update 1/3 : ypass line reordering if all runs have the same direction Update patch to not check for all zero, but for all even or all odd.
Created attachment 248204 [details] [review] Update 3/3 : Redo shape_tab and get_tab_pos to have better performance for long lines Update patch to fix a typo.
Behdad, (In reply to comment #4) > I agree with your analysis, but prefer to find a solution that wouldn't > complicate the codebase unnecessarily. Let me find some time to take a deeper > look into this On a second thought, I would say that only patch 2 complicates the codebase, because it changes from computing line_width at a single location to multiple locations. But I don't see how this can be done any cleaner without hampering performance. Patches 1 and 3 don't really complicate the code base in my opinion. Will you find time to briefly take a deeper look any time soon? Otherwise I push the patches for more testing to master in the next week or so? (I don't know what the current release schedule is, but some more testing of the code first would be good)
(In reply to comment #6) > Created an attachment (id=248203) [details] [review] > Update 1/3 : ypass line reordering if all runs have the same direction > > Update patch to not check for all zero, but for all even or all odd. LGTM. Feel free to push out. If I was to write this I would have just calculated the "bitwise and" and "bitwise or" of all the levels to avoid conditionals.
Created attachment 249138 [details] [review] Update 1/3 : Bypass line reordering if all runs have the same direction Ah, that's clever, I like bitwise tricks. Updated the patch. This is what I intend to push in the coming week.
LGTM.
Thanks! Committed patch 1/3.
Donno what the status here is but let's close for now...
Only Patch 1 of 3 was pushed. I didn't push patches 2 and 3 as you felt they would unnecessarily complicate the code base. These patches were needed in the product where we were seeing these performance issues however.
Ok, I'll try to see if I can review them. I have a vague memory that I thought they shouldn't be necessary...
Leaving for Matthias...
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/pango/issues/220.