[xft] avoid sorting list of font matches



Core Graveyard
GFX: Gtk
15 years ago
9 years ago


(Reporter: Brian Ryner (not reading), Assigned: Brian Ryner (not reading))



Firefox Tracking Flags

(Not tracked)



(1 attachment, 1 obsolete attachment)



15 years ago
We currently call FcFontSort() to retrieve a list of fonts sorted by closeness 
to our pattern.  This is at least O(N lg N) for N fonts installed on the 
system, and in practice is a lot slower than that in current versions of 

Since in the common case, the first font returned will have all of the 
characters we'll be asked to draw, we can optimize by just calling FcFontMatch
() to retrieve the best match font in O(N) time.  This will always be the same 
as the first font in the list returned by FcFontSort().  If we need to draw a 
character that's not present in that font, _then_ we can call FcFontSort() to 
get the rest of the fonts.

Comment 1

15 years ago
Created attachment 134278 [details] [diff] [review]

This does what I described above.


15 years ago
Attachment #134278 - Flags: superreview?(dbaron)
Attachment #134278 - Flags: review?(blizzard)
Comment on attachment 134278 [details] [diff] [review]

> void
>+nsFontMetricsXft::DoMatch(PRBool aMatchAll)
> {
>     FcFontSet *set = nsnull;
>     // now that we have a pattern we can match
>-    FcCharSet *charset;
>+    FcCharSet *charset = nsnull;
>     FcResult   result;
>-    set = FcFontSort(0, mPattern, FcTrue, &charset, &result);
>+    if (aMatchAll) {
>+        set = FcFontSort(0, mPattern, FcTrue, &charset, &result);

Rather than initializing |charset| to null, move it into this if, along with
the destroy code that uses it.

With that, and some testing of web pages that use fallback chars (e.g.,
sprinkle 䀀 and 怀 into a web page somewhere), sr=dbaron.
Comment on attachment 134278 [details] [diff] [review]

>+    if (mLoadedFonts.Count() != 0) {

Oh, and if |mLoadedFonts.Count()| is 0, you've probably run out of memory and
can return null.  I *think*.


15 years ago
Attachment #134278 - Flags: superreview?(dbaron)
Attachment #134278 - Flags: review?(blizzard)

Comment 5

15 years ago
Created attachment 134599 [details] [diff] [review]
patch #2

I addressed dbaron's comments, and I also found a somewhat serious problem with
the fallback support.  Namely, FindFont() was only being used for mWesternFont,
but we need to also use it in EnumerateGlyphs() for things to work correctly.

In addition,

- I applied the optimization of changing FcFontSort to FcFontMatch in
SetupMiniFont().  It's particularly relevant there since we were only looking
at the first font in the returned set.

- I optimized DoMatch() a bit by not passing a charset parameter to FcFontSort.
 We destroy it immediately; FcFontSort will do the same if you just pass NULL
for the charset.


15 years ago
Attachment #134278 - Attachment is obsolete: true

Comment 6

15 years ago
Comment on attachment 134599 [details] [diff] [review]
patch #2

dbaron, I know you marked sr= on the first patch, but this has some changes
beyond what you asked for so I'm requesting it again.
Attachment #134599 - Flags: superreview?(dbaron)
Attachment #134599 - Flags: review?(blizzard)
Is there any reason that we're touching the loop in EnumerateGlyphs?  That makes
my spider sense tingle.  We were avoiding the if() for performance reasons,
possibly bogus reasons.  Does it speed up the code making the change?

Comment 8

15 years ago
We have to call FindFont() so it can handle loading the remainder of the fonts
if the character doesn't exist in the first font.  So touching this loop is
necessary for the patch to operate correctly.

As far as I can tell, the "optimization" in the original code is to not have to
check  |if (currFont)| again after HasChar() returns true.  So with this patch,
at the instruction level, there may be one extra comparison, since FindFont()
checks HasChar() and returns the font if the character is there, and then we
check the result to see that it's non-null.  Of course, the compiler might be
able to optimize that if it chooses to inline FindFont().

Note that I did a small amount of micro-optimizing here by making the test for
currFont check for the null case first -- that's because, as I understand it,
x86 cpu's predict "no" for branches if you don't tell them otherwise.  So it
would work out better to make the |if| be for the uncommon case.  That may be
just over-optimizing on my part... I'm willing to switch the order if you think
it makes the code cleaner (we could also use gcc's __builtin_expect() for the
same effect with the success case first).
Comment on attachment 134599 [details] [diff] [review]
patch #2

>+            rv = aCallback(&c, 1, nsnull,  aCallbackData);

Watch the weird spacing.
Attachment #134599 - Flags: superreview?(dbaron) → superreview+
Attachment #134599 - Flags: review?(blizzard) → review+

Comment 10

15 years ago
Checked in.  redwood shows a Tp improvement of a little over 40% from this.
Last Resolved: 15 years ago
Resolution: --- → FIXED

Comment 11

15 years ago
wow, I really miscalculated that.  The speedup is closer to 4.8%.
Yeah, we were kind of wondering. :)
Product: Core → Core Graveyard
You need to log in before you can comment on or make changes to this bug.