After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 348825 - (fcfontsort) pango should optimize away calls to FcFontSort as much as possible
(fcfontsort)
pango should optimize away calls to FcFontSort as much as possible
Status: RESOLVED OBSOLETE
Product: pango
Classification: Platform
Component: general
1.12.x
Other All
: Normal normal
: ---
Assigned To: pango-maint
pango-maint
Depends on:
Blocks:
 
 
Reported: 2006-07-26 18:21 UTC by L. David Baron
Modified: 2018-05-22 12:20 UTC
See Also:
GNOME target: ---
GNOME version: 2.13/2.14


Attachments
Benchmark the fontset cache use (1.80 KB, text/x-csrc)
2006-08-02 06:40 UTC, Mark Steele
Details

Description L. David Baron 2006-07-26 18:21:58 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:
Comment 1 Behdad Esfahbod 2006-07-26 20:41:30 UTC
Yes, this is a known issue that we want to fix.
Comment 2 Owen Taylor 2006-07-26 21:12:52 UTC
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.
Comment 3 L. David Baron 2006-07-26 21:23:58 UTC
It could be that pango is caching the results on an object that the current Mozilla code is throwing away after each call.
Comment 4 Matthias Clasen 2006-07-26 22:06:44 UTC
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...
Comment 5 Owen Taylor 2006-07-26 22:17:59 UTC
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. 
Comment 6 L. David Baron 2006-07-26 22:49:31 UTC
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.
Comment 7 Behdad Esfahbod 2006-07-27 04:48:02 UTC
> 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.
Comment 8 Mark Steele 2006-08-02 00:45:14 UTC
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.
Comment 9 Behdad Esfahbod 2006-08-02 03:37:23 UTC
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.
Comment 10 Behdad Esfahbod 2006-08-02 03:39:09 UTC
(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
Comment 11 Mark Steele 2006-08-02 06:40:45 UTC
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.
Comment 12 Behdad Esfahbod 2006-08-17 18:35:38 UTC
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.

Comment 13 Behdad Esfahbod 2006-08-17 19:48:12 UTC
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...
Comment 14 GNOME Infrastructure Team 2018-05-22 12:20:37 UTC
-- 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.