Re: Notes on Pango Xft backend

[Owen Taylor <otaylor redhat com>]

Keith Packard <keithp keithp com> writes:

> > Operation A) is far too slow to implement into its entirety for each
> > small segment of text, so the bulk of the operation is cached -
> > a "infinite sized" map from PangoFontDescription to a list of patterns
> > is kept. (So, basically, everything but actually creating the PangoXftFont
> > objects and adding them to the fontset is cached.))
> 
> There's a new call you might like -- FcFontSetSort takes a pattern and 
> returns the *whole* set of available fonts in sorted order, along with the 
> union of all of their coverages.  It's not significantly slower than 
> matching a single font.  

Hmmm, well;; with ~460 fonts the timing is:

 FcFontSetMatch: ~2 ms
 FcFontSetSort:  ~10 ms

But in this case particular case (matching the "Sans" alias), I'd have called 
FcFontSetMatch 8 times, so FcFontSetSort does end up ahead by 
a small margin. 

As you might expect all the excess time is in doing the coverage computations.

[...]

> > A second cache is kept of PangoXftFont; when creating a PangoXftFont
> > for a pattern, instead of always creating it from scratch, we instead 
> > check to see if there is already an outstanding font for the pattern,
> > and, if so, return it. We also keep a small number of fonts around
> > after the last refcount is dropped (MAX_FREED_FONTS, currently 16.)
> 
> You don't have to do this; Xft caches at this level as well.  It doesn't 
> keep previously opened fonts around, but it could if you think that would 
> be useful.

The reason that Pango does it is that Pango does not keep font objects
around persistantly; it looks them up from PangoFontDescription 
as needed; so you could get bad thrashing effects without keeping
some up.

But a frontend 'description => font' cache might do a good enough job
at keeping fonts open without making Xft do it.

> >  * The PangoFontDescription => [list of patterns] map really can
> >    grow without bond, because each size is stored independently
> >    (and Pango allows very fine-grained sizes.) So, an app that
> >    allowed arbitrary zooming could easily end with a huge amount
> >    of cached lists of patterns.
> 
> If you use FcFontSetSort, you can keep only the pattern around and 
> regenerate it as needed.  That operation is (relatively) quick.

You mean the FcFontSetSort operation is relatively quick? Guess it's
a matter of perspective ... it is currently around 10 ms; my target
for the PangoFontDescription => PangoFontSet operation would be 10 us.
(Best case its once per paragraph; with a 10,000 paragraphs second
target; any one operation shouldn't be more than 1/10th of that.)

So, even with any conceivable optimization, I think some sort of
cache in front of FcFontSetSort will be needed.
 
> >   (So, first Pango does an hash lookup to make sure that 
> >   the no PangoXftFont is already open; if none is, then Xft will
> >   do a linear lookup to the same effect.)
> 
> If you find it necessary to avoid the linear search, it's obvious that Xft 
> needs to use a hash as well.  I avoided the complexity because I couldn't 
> see it in my performance data (which is obviously limited at this point).

Programming with GLib, its very natural to use hash tables; GLib
makes them as simple to use. So I haven't actually tried it with
a linear search. 

The equality operation that Pango is doing is pretty expensive
compared to what Xft does, so O(n) might do OK here; it depends
on enough other architural things that its hard to predict for
me at the moment.
 
> Using Xft's cache instead of Pango's avoids the duplication of effort and 
> allows faster operations as Xft can use the internal structures.  I assume
> that the pattern equality tests have been of some use here already; I did 
> convert the internal pattern representation to sort the pattern elements 
> which avoided a quadratic comparison operation.

FcPatternEqual got rid of a bad hack in Pango but seems to be
significantly slower than the bad hack was. (I think the main
difference being that the bad hack only cared about a subset of all
the pattern fields.)

> >   [ One problem with dropping the pattern => PangoXftFont cache, is 
> >     that you will end up creating many PangoXftFont objects for the
> >     same font at the same size, even though Xft will only create
> >     one XftFont object. ]
> 
> We could allow you to store the PangoXftFont object from the XftFont; that 
> way successive open operations could look for that and return it if it 
> existed, saving the memory.
> 
> >  * Xft could export the idea of the "core" of a pattern ... an opaque
> >    structure holding:
> > 
> >     file/minspace/char_width/size/spacing/rgba/antialias/load_flags/render/matrix
> 
> 
> 
> >   a) XftFont is fairly large. (It stores the complete pattern, for one thing)
> 
> Note that the Unicode coverage is not duplicated; that structure is ref 
> counted to avoid copying it.  Your idea of further sub-caching leaves of 
> that structure would serve to really reduce storage of these objects.
> 
> I could attempt to reduce the pattern size further by sharing strings 
> across different patterns and perhaps finding a small representation for 
> the lists of values that are present today; embedding the initial value 
> within the object header would save quite a bit of malloc overhead in this 
> case.

My guess is that the biggest memory chunk for values is the strings for all
the keys; using a shared set of strings for these would be a definite
space win. (Also, allows a big further speedup in FcPatternEqual by
reducing string compares.)

> >   b) When you open an XftFont, it immediately opens the FT_Face
> >      for the font. We'd really like to avoid having to ever open the FT_Face
> >      for fonts that are in our patterns but not used.
> 
> I don't know why you're opening the font then; everything you need to know 
> about the font is available from the pattern, including the Unicode 
> coverage.  The only thing not available are the glyph metrics; I assume 
> you don't need those until you draw the glyphs.

Perhaps my presentation here was a little confusing. 

 * Currently, we just get the pattern, and only open the font as  
   necessary.

 * But patterns are a) big; b) slow to compare and hash, so we
   might want to look for an alternative.
 
 * Is an XftFont a reasonable alternative to keeping around the
   pattern? no, because it is *bigger* than the pattern and 
   also forces an open of the font file.

[...] 

> Hmm. The return value from FcFontSetSort references the patterns of the 
> original fonts; taking that value and opening a font requires a call to 
> FcFontRenderPrepare; that makes the storage of this list *very* small,
> it's just an array of pointers, and a fairly short list at that.  Let's 
> see if we can't make this operation work for Pango, that seems like it 
> will solve the pattern storage and matching performance problems.

Hmm, that is good news on the storage size point of view. 

I think I'll still need to do one of:

 a) Limit the number of "PangoFontDescription => font set" 
    lookups I store.

or:

 b) Have some way of limiting the number of separate sizes that I 
    store.

What did you think of the idea of having FcConfigSubstitute return
a range of sizes for which the subsitution applies? Does that
assume too much about the subsitution proces?

Regards,
                                        Owen