GNOME Bugzilla – Bug 348825
pango should optimize away calls to FcFontSort as much as possible
Last modified: 2018-05-22 12:20:37 UTC
Please describe the problem: A performance problem that affects Mozilla's use of pango is that pango unconditionally calls FcFontSort when choosing what font to use. I believe this call is O(N log N) in the number of fonts on the system. What pango does with the result of this call is presumably looking for glyphs in the fonts starting with the first font return -- so in many cases it only needs the very first font in the list returned, which can be retrieved in O(N) time with FcFontMatch. Mozilla's existing (pre-pango) direct use of Xft has an optimization that first calls FcFontMatch to get the first-choice font, and then only calls FcFontSort if it needs to look past the first-choice, which in many cases is a relatively rare event. For more details, see: https://bugzilla.mozilla.org/show_bug.cgi?id=334064 - this describes the performance problems caused by this issue. Note that these problems will be worked around significantly for the Western case by adding ASCII fast paths in Mozilla. https://bugzilla.mozilla.org/show_bug.cgi?id=223813 - the bug where Mozilla made similar optimizations Steps to reproduce: Actual results: Expected results: Does this happen every time? Other information:
Yes, this is a known issue that we want to fix.
Note that Pango does a lot of work to cache the results of these calls, so this only really should affect pages with a lot of fonts or (IIRC, I forget the state of the code) a lot of font sizes. The work is never per-character or per-string. I'm a little skeptical however of doing the work twice in the "uncommon" case. A lot of the slowness of FcFontSort looked fixable last time I took a peek.
It could be that pango is caching the results on an object that the current Mozilla code is throwing away after each call.
IIRC Keith Packard described a clever way to make FcFontSort much cheaper, but that was at the Fluendo party, and I seem to have forgotten all the details...
Well, there are basically two possibilities: - The reported timing with 70% in FcFontSort is flawed (say, the person profiled startingup Mozilla and rendering a small amount of text, though their observationof slowness was with pages with lots and lots of text) - There is something very wrong about how Firefox is using Pango and Cairo. (It's hard to defeat the caching, but certainly take a look through your sources for pango_cairo_font_map_new(); every newly created fontmap is a separate cache domain. You almost always want get_default(), though the custom encoding stuff that was added to Pango for Gecko might nmake a *single* call to _new() desirable. Even there I'd probably just hack the default font map unless it was observed to actively cause problems.) Well, there is a third possibility actually ... if you have very many fonts active at once you can exceed some of the font cache sizes in Pango and performance will go to pot. (Blizzard and I once saw this with firefox rendering a page of complete junk.. there were enough valid UTF-8 sequences in the junk that Pango was switching between 30 or 40 fonts) The actual cut-of here is 16 fonts. #define FONTSET_CACHE_SIZE 16 in pango-fcfontmap.c So if you have a web page that has, say a table where each row uses 17 fonts, that's going to render quite slowly.
The profile was taken of activity dominated by painting, and with a bit of layout (and this was actually the case in the profile). What counts as a font for the purposes of that cache? A family? Or that + style + weight? Or that + size? There are no calls to pango_cairo_font_map_new(); we're only using pango_cairo_font_map_get_default(). The pages in question may well have used more than 16 fonts, but not in repetitive iterations.
> What counts as a font for the purposes of that cache? A family? Or that + > style + weight? Or that + size? All of them. The main problem seems to be the size. In the cairo-dock making it render at float sizes made FcFontSort take 50% time and defeat all the caches. > IIRC Keith Packard described a clever way to make FcFontSort much cheaper, > but that was at the Fluendo party, and I seem to have forgotten all the > details... His idea was to do FcFontSort for sans and then instead of doing FcFontSort for patterns, do FcFontMatch and append the list from sans. This works in most of the cases but may fail in some aliasing cases. But now that I think about it, it doesn't help that much as the main bottleneck seems to be different sizes here and we cannot blindly share reuse FcFontSort results from one size for another size or we'll lose all the size-specific configuration (like turning off hinting). I think even this idea can be implemented in fontconfig in a more robust and faster way.
Mozilla's use of pango is hitting the third possibility Owen listed. The case of a single page with 17 fonts is too simplistic. The font code is used for browser UI, so at least two of these entries are taken before any page is rendered (including bold for the highlighted tab). Assuming these two aren't used in pages, this leaves 14 entries to use across all permutations of font families, sizes, and styles in ALL browser tabs. With more than one browser window or tab, these get filled quite quickly, giving the case where FcFontSort is *always* hit rather than the hash. In a test before this was filed I found that increasing this cache to an abnormally large size (say, 256) eliminated the FcFontSort hit and drastically lowered page-load times in pango Mozilla builds.
Something I've been thinking about for quite some time is caches that evacuate using a timer instead of size contraints. This case may be a very valid case to use a hybrid LFU cache whose size varies between 16 and 256 and only shortened on inactivity. Or something like that. I'll try these ideas if you give us a benchmark.
(07:47:10 PM) Behdad Esfahbod: mark: all fontconfig needs to do is, when applying configs, remember what size comparisons it did, and find out the size range that the result wouldn't change. (07:47:26 PM) Behdad Esfahbod: and then either communicate it to the user (pango), or use that to cache sort results itself
Created attachment 70057 [details] Benchmark the fontset cache use Set SIZES and STYLES to adjust. Try: SIZES 9, STYLES 2, or SIZES 17, STYLES 1.
After some measurements of how many fontsets firefox uses, I'm increasing 16 to 64. That will be in 1.14.1. I'm working on a dynamic cache size that can grow even further. Here are some stats I gathered: Planet GNOME 20 Google Personal Home 13 about: 7 my default tabs: 80 Planet GNOME Slashdot Footnotes Dilbert Recent Changes Browsing Orkut 25 Login to Flickr 18 GNOME Bugzilla bug 14 my weblog 23 a Request Tracker page 34 2006-08-17 Behdad Esfahbod <behdad@gnome.org> Part of Bug 348825 – pango should optimize away calls to FcFontSort as much as possible * pango/pangofc-fontmap.c: Increase FONTSET_CACHE_SIZE from 16 to 64.
Matthias dropped this brilliant idea: to add API to fontconfig to return ranges of fontsize that FcFontSort results will be the same. That can be generated by going over the configuration and mark whenever a fontsize comparison or operation is performed...
-- 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/53.