Closed Bug 229403 Opened 21 years ago Closed 21 years ago

Simple cache to speed up nsFontMetricsXft

Categories

(Core Graveyard :: GFX: Gtk, enhancement)

Product:
Core Graveyard
Component:
GFX: Gtk
Platform:
x86
Linux
Type:
enhancement
Priority:
Not set
Severity:
normal

Tracking

(Not tracked)

Status:
RESOLVED FIXED

People

(Reporter: jim_nance, Assigned: blizzard)

Details

(Keywords: perf)

Attachments

(1 file, 5 obsolete files)

Patch with the suggested improvements incorporated
27.76 KB, patch
jshin1987
: review+
rbs
: superreview+
Details | Diff | Splinter Review 
User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6b) Gecko/20031210
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6b) Gecko/20031210

The method nsFontMetricsXft::EnumerateGlyphs() calls FindFont() for every
character in the string that it is passed.  It is possible to eleminate over 98%
of these calls by maintaining a simple cache of character to font mappings.

Reproducible: Always

Steps to Reproduce:
1.
2.
3.
Attached patch Patch to implement the cache (obsolete) — — Splinter Review 
This patch implements a character to font cache, which greatly reduces the
number of calls the FindFont which must be made.
Keywords: perf
.
+    enum {TAG_CACHE_SIZE=131};
+    FcChar32             mTagArray[TAG_CACHE_SIZE];
+    nsFontXft           *mCacheArray[TAG_CACHE_SIZE];

That's pretty much the ASCII set (127) -- which, generally, is covered by the
first loaded font. Hence, it seems to me that the real culprit is rather that
font->HasChar() [i.e., FcCharSetHasChar()] is slow.

GfxWin's ResolveForwards() [the equivalent of EnumerateGlyphs] uses a fast bit
array (the so-called compressed character map -- CCMAP) to avoid such further
system calls. See also nsFontXftUnicode::HasChar() and nsFontXftCustom::HasChar().

Do you achieve a speed-up with your patch? Since blizzard, jshin, & co., don't
presumably want to mess with FcCharSetHasChar(), I would think your idea offers
a reasonnable trade-off to the problem.
I'm also curious to know the performance enhancement you have achieved with the
patch. BTW, I thought 
FcCharSetHasChar() has something similar to CCMap (even if so, there's a
function call overhead, but ...). Keith, how does it work? 
FWIW, there is some ccMap stuff in the code:

PRBool
nsFontXftCustom::HasChar(PRUint32 aChar)
{
    return (mFontInfo->mCCMap &&
            CCMAP_HAS_CHAR_EXT(mFontInfo->mCCMap, aChar));
}

The Unicode version makes a call down into FcCharSetHasChar(), so I cant tell
how that works.  It might be interesting to rip the mCCMap stuff out of
nsXftFontInfo and see how it performs with the cache ahead of it.  It may be
that with the cach ahead of it, the overhead of maintaining the map is greater
than the benifit it gives.

I do not have any good way to measure the speed difference.  I started playing
with this piece of code because I wanted to learn it.  There was not a speed
problem that I was trying to solve.  The case that I think it will be
significantly faster for is when there are multiple fonts and the characters do
not all match the first one.  FindFont is doing a linear search through the font
list, testing each one.

Yes, a cache size of 131 covers the entire ASCII range, which is why I chose
that size (prime (I hope) and greater than 127).  I tried it with a size of 64
and was still getting hit rates in the 90% range.  With 131 I get hits rates
between 98% and 99%.  I assume that if I tried a page which used a non-western
character set that I might get a lower hit rate.
This contains the changes which were in the original patch as well as some code
refactoring.  There were several methods that called EnumerateGlyphs.  Each of
these took either a char* or PRUnichar* string and converted into the FcChar32*
string needed by EnumerateGlyphs.  I changed the code so that there are two
versions of EnumerateGlyphs, one that takes a char* string and one that takes a
PRUnichar* string.  Each of these does the required conversion and calles a new
method EnumerateXftGlyphs() with the converted strings.  There is less code
this way, and it allows for future optimizations to the string conversion
process.
> It might be interesting to rip the mCCMap stuff out of
> nsXftFontInfo and see how it performs with the cache ahead of it.

FcCharSetHasChar is not applicable to nsFontXftCustom. Notice that I gave a
reference to nsFontXftCustom::HasChar earlier to highlight the difference.
mCCMap has to be there -- for correctness.

> There was not a speed problem that I was trying to solve.

I am less enthusiastically with the patch then... (the consolidation part is
fine). The risk of too much optimisation is that they tend to be premature and
obfuscate the code.

> The case that I think it will be significantly faster for is when there are
> multiple fonts and the characters do not all match the first one.

But that's the rare case.

> FindFont is doing a linear search through the font list, testing each one.

Yes, it is supposed to work like that, so as to honour the CSS ordering of the
font-family list.

I put in some code to measure the time required to call FindFont().  It is about
600 nano-seconds on my 400 MHz laptop.  We make about 25000 calls to FindFont
when bringing up the initial window using the bash HTML manual as the initial
URL which is a pretty large page.  So I think your instinct is right.  There is
no point in adding the cache.  I am going to include a patch which has the code
consolidation but removes the cache.

If you would, take a look at the EnumerateXftGlyphs() method I wrote.  It is
based on EnumerateGlyphs, but it coalesses callbacks when FindFont() returns
NULL as well as when it finds a font.  The original EnumerateGlyphs() only
coalessed callbacks when the font was not NULL.  It actually makes the code much
simpler to do this and it should run faster as well.  I just want to make sure
this is an acceptable change to make.
Attached patch code consolidation patch (obsolete) — — Splinter Review 
This patch consolidates the string conversions so that they only happen in one
place.	Adds 60 lines, deletes 90, which isnt too bad :-)
Attachment #137965 - Attachment is obsolete: true
Attachment #137994 - Attachment is obsolete: true
Some comments:

==========================
+        if(currFont != prevFont) {
+            if (i>start) {

Looks like this is a redundant test. My reading is that, by construction, if the
first clause is true, then the second must be automatically true. No?

========================
-    if (prevFont) 
+    if (i>start) {

What if the font is null after the |for|, i.e. across the entire string?

         rv = aCallback(&aString[start], i - start, prevFont, aCallbackData);
+        NS_ENSURE_SUCCESS(rv, rv);

The |ensure| doesn't seem necessary since the next |return| takes care.
+    }
 
     return rv;

==================
Apart from these, the consolidation looks okay to me.
> +        if(currFont != prevFont) {
> +            if (i>start) {

> Looks like this is a redundant test. My reading is that, by construction, if the
> first clause is true, then the second must be automatically true. No?

 Actually, no. The loop is entered with i=start=0 and prevFont=NULL. If the
currFont (the font for the  1st char.) is not null, the first condition is met
while the second condition is not. 

> -    if (prevFont) 
> +    if (i>start) {

> What if the font is null after the |for|, i.e. across the entire string?

  Is there a problem with that case? Callback functions will be called with NULL
font, but that will be taken care of  (minifont will kick in). Am I missing
something?

Now here comes my comment :-). First of all, thansk for the nice job. Because
there can be a surprise that can escape the inspection by eyes (especially with
custom fonts and minifonts), you may want to do some extensive testing (I'll do
that, too).  Just one point:  wouldn't it be better to use 'EnumerateGlyphs' for
all three functions instead of using 'EnumerateXftGlyphs' for the main one?
There's no worry for the namespace pollution.  Another comment (not directly
related to the fix) is that it's easier to read the patch if you give more
context (using 'cvs diff -u8 -p' when making a patch is a good idea, IMHO).
> Actually, no. The loop is entered with i=start=0 and prevFont=NULL. If the

I see. Somehow, I have the feeling that these |if| can be collapsed, though.
E.g., by recasting the code with |nsFontXft *currFont = FindFont(aString[i++])|
and a |while| loop.

> Is there a problem with that case? Callback functions will be called with 
> NULL font, but that will be taken care of  (minifont will kick in). Am I
> missing something?

That's right. I realized it soon after pressing the 'submit' button, but then
had to go off.

However, something to take care of now is to loop over the substring for the
mini-font. All the callbacks presently only expect a single char, and will assert.

> all three functions instead of using 'EnumerateXftGlyphs' for the main one?

My own preference in this case is for the separation. It makes the understanding
easier.
> something to take care of now is to loop over the substring for the mini-font. 

  You're right. I've been wondering why I hadn't treated NULL-font the same way
as non-Null cases (as is done here) This was why. Jim, would you take care of
that? That would cut down the line number differential, but perhaps will be
useful for other things later (e.g. transliterator)

Ill take a look at NULL-font thing.

As for having 3 EnumerateGlyphs() rather than 2 plus an EnumerateXftGlyphs.  I
originally coded it with 3 EnumerateGlyphs.  When you do this, 2 of the
EnumerateGlyph functions are distinguished only by the type difference between
PRUnichar and FcChar32.  I was worried that someone might want to change
PRUnichar to a 32 bit type someday and that it would make these functions
ambigous, so I changed the name of the base function.
BTW, would someone post a URL or a page which will cause NULL fonts to be
generated when it is viewed?  I do not think I ever hit that case when I test.
Try both BMP and Plane 1 example pages (without installing fonts mentioned
there)  at 

  http://www.i18nguy.com/unicode/unicode-example-intro.html
(there are links to other sample pages, too)

For Plane 1 example pages, you have to apply the patch for bug 229270 because
non-BMP rendering was broken by mistaked in 1.6branch/trunk.

As for PRUnichar becoming 32bit integer type someday, I guess the chance is
rather low. Originally (in 1998), that was talked about...
> Ill take a look at NULL-font thing.

Since you are keen on consolidation the code, I wish you could bite the bullet
and do the necessary factoring that is needed for future issues:
transliteration, ignorable characters.

In essense, the null font is not needed. It can be fully replaced by a
substitute font, i.e., another class, say |nsFontXftSubstitute|, along side
|nsFontXftUnicode| and |nsFontXftCustom|. 

Then, you transfer all the operations that the mini-font is doing into that
class. And rather than returning a null font in FindFont() -- which entails
special casing all the callback functions... you just return a substitute font
-- whose member functions implement just what the mini-font is doing.

[Further down the track, these functions will be improved to do the
transliteration, etc, as done in GfxWin for example. "Transliteration" means
that the copyright character could be replaced by "(c)" if there is no glyph for
© Or EUR could be displayed if there is no glyph for the euro currency
symbol, etc. But this will come later, and the |nsFontXftSubstitute| class will
provide a basis for that.]
Added code so callbacks can handle sequences of NULL fonts.
Attachment #138028 - Attachment is obsolete: true
Ill be happy to work on the substitute font thing.
The patch looks good to me, feel free to ask r/sr if you are happy with your
testings.

[I hope you guys could push to improve & make Xft the default official build
this year...]
I took a look at implementing nsFontXftSubstitute.  Its going to involve changes
to the existing nsFontXft* classes if we dont want the changes to be ugly (and I
dont see any point in making ugly changes when we dont need to).  Therefor I
would like to get the existing patches checked in before I start doing major
surgery to the code.  I fed a gzipped some text and told mozilla it was html. 
It had a lot of undefinded glyphs :-).  It rendered identically with and without
my changes, so I think everything is working.  Im ready to ask for a r/sr.  It
has been a while since I checked anything in, so if you would let me know when I
can actually have the necessary approvals to commit this to CVS I would
appreciate it.

Also, right now when rendering a NULL font, we draw a rectangle and put the
digits of the character inside the rectangle.  We could make this look much more
like a regular font IF there was a unicode font/glyph that was a rectangle. 
Does anyone know if there is a unicode rectangle symbol?
> Im ready to ask for a r/sr. 

I can give you sr straightaway, having followed from the beginning, and knowing
that you are keen to pursue other valuable steps... I am sure others are equally
interested and will review. Start by trying jshin for the r, since he is around
now. Just ask, otherwise little will happen...

> Does anyone know if there is a unicode rectangle symbol?

Not really important. Users will have to install that font (and that could be a
problem -- as the experience of requesting users to install math fonts has
shown). nsFontXftSubstitute will have other options. GfxWin simply shows the
question mark, or the &#xNCR; entity (numeric character reference).
jshin, can I get an r from you?

I didnt realize I had the option of changing how the NULL fonts were displayed.
 Displaying a question mark would be extrodinarily easy and the &#xNCR would
only be slightly more difficult.  It is drawing the rectangle which makes things
difficult because the rectangle is not represented as an Xft font, and nsXftFont
assumes that it is dealing with fonts.
Attached patch As before plus method pointers (obsolete) — — Splinter Review 
Since I am after reviews, I thought I should attach the latest patch.  This is
like the one before but it changes EnumerateGlyphs to take a pointer to an
nsFontMetricsXft class method rather than a function pointer.  This eleminates
the need for the static callback functions which just call back into class.  In
all it gets rid of about another 50 lines of code.

I will be glad to check in either this or the prior patch, depending on the
preferences of the reviewers.
Comment on attachment 138314 [details] [diff] [review]
As before plus method pointers

A nice job. Fix the following problems and ask me for review (using edit
attachment)

> typedef struct _DrawStringData {
>-    nsFontMetricsXft      *metrics;
...
> } DrawStringData;

While you're at it, how about replacing 'typedef struct _Foo {...} Foo'
with 'struct Foo { }'?

>@@ -602,30 +571,18 @@ nsFontMetricsXft::GetTextDimensions(cons
>-    rv = EnumerateGlyphs(chars, len, StaticTextDimensionsCallback, &data);
>+    rv = EnumerateGlyphs(aString, aLength, &nsFontMetricsXft::TextDimensionsCallback, &aDimensions);

  Please, keep the line length smaller than 80.


>@@ -676,40 +633,30 @@ nsFontMetricsXft::DrawString(const char
>-    rv = EnumerateGlyphs(chars, len, StaticDrawStringCallback, &data);
>+    rv = EnumerateGlyphs(aString, aLength, &nsFontMetricsXft::DrawStringCallback, &data);

  same here and several more lines like this.


>         XftDrawGlyphFontSpec(data.draw, &data.color, data.specBuffer, data.specBufferLen);

  Hmm... Can you take care of the above line as well :-) ?

>-nsFontMetricsXft::EnumerateGlyphs(const FcChar32 *aString, PRUint32 aLen,
>+nsFontMetricsXft::EnumerateXftGlyphs(const FcChar32 *aString, PRUint32 aLen,
>                                   GlyphEnumeratorCallback aCallback,
>                                   void *aCallbackData)

  Alignment is broken here.


>+        if(currFont != prevFont) {
>+            if (i>start) {

   if (i > start) {

and some more like that.

>+                rv = (this->*aCallback)(&aString[start], i - start, prevFont,
>+                        aCallbackData);

  alignment : if it's due to a tab, make sure you remove all tabs.

>-    if (prevFont)
>-        rv = aCallback(&aString[start], i - start, prevFont, aCallbackData);
>+    if (i>start) {
>+        rv = (this->*aCallback)(&aString[start], i - start, prevFont, aCallbackData);
>+        NS_ENSURE_SUCCESS(rv, rv);
>+    }
>
>     return rv;

   As rbs pointed out, you don't need NS_ENSURE.... here

>+nsresult
>+nsFontMetricsXft::EnumerateGlyphs(const PRUnichar *aString,
>+                                  PRUint32  aLen,
>+                                  GlyphEnumeratorCallback aCallback,
>+                                  void     *aCallbackData)

  nit. be consistent with spacing here (across the file, a couple of
different styles are used, but in a single definition, it'd better be
consistent)

>+nsFontMetricsXft::EnumerateGlyphs(const char *aString,
>+                                  PRUint32  aLen,
>+                                  GlyphEnumeratorCallback aCallback,
>+                                  void     *aCallbackData)

 same as above.

>+        for(PRUint32 i=0; i<aLen; i++) {

    for (PRUint32 i = 0; i < aLen; ++i) {

 fix also   a couple of more places like the above.

>+            DrawUnknownGlyph(ch, x, y + mMiniFontYOffset, &data->color,
>+                    data->draw);

 alignment again


>-    TextDimensionsData *data = (TextDimensionsData *)aData;
>+    nsTextDimensions *dimensions = (nsTextDimensions*) aData;

      nsTextDimensions *dimensions = (nsTextDimensions *)aData;
and a few more.

>+        for(PRUint32 i=0; i<aLen; i++) {
>+            bm.width += mMiniFontWidth * (IS_NON_BMP(aString[i]) ? 3 : 2) +
>+                mMiniFontPadding * (IS_NON_BMP(aString[i]) ? 6 : 5);
>+            bm.rightBearing += bm.width; // no need to set leftBearing.
>+            bm.ascent += mMiniFontAscent;
>+            bm.descent += mMiniFontDescent;

   You shouldn't add up ascent and decent for bm. 

>-    nsresult    EnumerateGlyphs  (const FcChar32 *aString,
>+    nsresult    EnumerateXftGlyphs  (const FcChar32 *aString,
>+                                  PRUint32  aLen,
>+                                  GlyphEnumeratorCallback aCallback,
>+                                  void     *aCallbackData);

  Would you line this up with other declarations below and above it?
I believe I have fixed everything you pointed out.
Attachment #138262 - Attachment is obsolete: true
Attachment #138314 - Attachment is obsolete: true
Attachment #138439 - Flags: review?(jshin)
Attachment #138439 - Flags: superreview?(rbs)
Comment on attachment 138439 [details] [diff] [review]
Patch with the suggested improvements incorporated

r=jshin with the following nits taken care of.

blizzard, do you have anything to comment on? 


>+        XftDrawGlyphFontSpec(data.draw, &data.color, data.specBuffer,
>+                data.specBufferLen);

  alignment :-) 

>+    if (NS_FAILED(rv)) {
>+        width = 0;
>+    }

  I guess  the local (in this file) convention is not using braces if there's a
single statement in a if-block. 

>+    if (i > start) {
>+        rv = (this->*aCallback)(&aString[start], i - start, prevFont,
>+                                aCallbackData);
>+    }

  The same here.

>+        for (PRUint32 i=0; i<aLen; i++) {

   for (PRUint32 i = 0; i < aLen; ++i)

>+        for (PRUint32 i=0; i<aLen; i++) {
>+            dimensions->width += 
	  ditto

>-        data->width += mMiniFontWidth * (IS_NON_BMP(*aString) ? 3 : 2) + 
>-                       mMiniFontPadding * (IS_NON_BMP(*aString) ? 6 : 5);
>+        for (PRUint32 i=0; i<aLen; i++) {

  same spacing issue.

>+            *width += mMiniFontWidth * (IS_NON_BMP(aString[i]) ? 3 : 2) + 
>+                mMiniFontPadding * (IS_NON_BMP(aString[i]) ? 6 : 5);
>+        }

   Please, line up 'width += ....'  as before. (there's one more case like the
above.)  Make sure there's no tab (one way to check that out is to search for a
tab in an editor that colors matches string.)

>+        for (PRUint32 i=0; i<aLen; i++) {

     again, spacing.
Attachment #138439 - Flags: review?(jshin) → review+
Comment on attachment 138439 [details] [diff] [review]
Patch with the suggested improvements incorporated

sr=rbs
Attachment #138439 - Flags: superreview?(rbs) → superreview+
I checked in the patch with the additional spacing changes requested by jshin
Status: NEW → RESOLVED
Closed: 21 years ago
Resolution: --- → FIXED
I probably would have if I had had the chance to look at the patch.
Those static functions were in there for a reason.  Your callbacks specify a
method that happens to be a class memeber, not a static function.  Also, C and
C++ calling conventions can be different so generally callbacks need to be C-based.
Hi Chris, would you like me to put them back?
Product: Core → Core Graveyard
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: