77942 - font cache implementation inefficient

Status: RESOLVED FIXED

(Core :: XUL, defect, P4)

Description

[Chris Waterson]

Noticed this while profiling long pages (cf. bug 56854). We spend a significant
amount of time looking up font information in the font cache; e.g., in that
bug's test case, we called nsFontCache::GetMetricsFor() 156K times. Need to do
more profile-driven analysis; logging this as a task to do so.

hyatt, I know you're interested in this: please feel free to take this bug if
you'd like.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I once noticed we create multiple nsFontCache objects, which means the
information they cache needs to be recomputed.  (We probably need one per
device, but we probably create more than that.)

Is most of the time within nsFontCache::GetMetricsFor in the calls when the
information isn't already cached?

Comment 2

[rbs]

There is a recorded bugzilla bug about this, but it is not high in the agenda 
and is marked future: bug 38993 - speed up font cache.
I am going to mark that bug a duplicate of this one. Here is the description
from that bug:

- description from [e-mail] (Erik van der Poel) -
Troy and I discussed some performance enhancements for the font cache in the
device context. It would probably be a good idea to change nsFont from a struct
to a class, making the members private, and having the setter functions compute
the hash value that is later used to fetch font metrics from the cache.

Comment 3

[rbs]

*** Bug 38993 has been marked as a duplicate of this bug. ***

Comment 4

[Chris Waterson]

dbaron: from profile in bug 56854...

      As for font, nsFontCache::GetMetricsFor() accounts for 16% of
      the inline reflow time (115msec, 2% overall). The font cache
      look to be implemented pretty inefficiently.

      - 156K calls to GetMetricsFor() fan-out to 430K calls to
        nsFont::Equals(). This accounts for 26% of the time. Hash?

      - Addref'ing and release'ing the language group atom accounts
        for about 30% of the time. Do we need to addref & release
        atoms here to compare?

      - Only 15% of the time is spent actually going to the OS to get
        font information.

Comment 5

[rbs]

<interlude> "Only 15% of the time is spent actually going to the OS to get font 
information". Problem solved - the cache is doing great :-) </interlude>

Comment 6

[Erik van der Poel]

Moving the language atom getter into the following if statement might avoid
the addref/release in many cases. I guess you could even change the getter so
that it doesn't addref, but this is not normal XPCOM practice(?).

Also, we have one nsFontCache per nsIDeviceContext, and we have one
nsIDeviceContext per DC (on Windows) (I think), so it seems to me that we may
have chosen to put the nsFontCache in the wrong object. I guess we need
multiple DCs, but we don't really need multiple nsFontCaches, do we?

Note that on Unix, the underlying font engine uses a single font cache, so we
are not calling the OS too many times for each nsFont (though we do create
more HFONTs than we need to on Windows).

On Windows, it may be possible to use a single font cache for both the screen
and printing, but this may not be possible on other platforms.

Comment 7

[Chris Waterson]

Reprofiling the test case from bug 56854 with a current build, and dug into this 
a bit.

- on that test case, we have about a 10x fanout from calls to
  nsFontCache::GetMetricsFor() to nsFontMetricsWin::GetLangGroup() et al. So,
  I'd say that means that at least on _this_ page, we've got no more than
  twenty fonts in the cache. (I'm assuming we hit in the cache on average n/2
  times.)

- The bulk of the time (45%) is spent addref'ing and release'ing the
  lang-group atom.

So, here's a simple patch that:

1. Promotes the last font that we ``hit'' to the front of the cache. This
   reduces the fanout from 10x to about 1.5x.

2. Check if the atoms are equal only once we've determined that the fonts
   themselves are equal.

With this patch, nsFontCache::GetMetricsFor() falls off the radar completely.

Comment 8

[Chris Waterson]

Attachment: promote font hits in the cache; avoid unnecessary atom refcnt churn

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Cool.  r=dbaron (although it looks like it wants my nsVoidArray::MoveElement
patch hidden within the patch on bug 74920).

Comment 10

[Chris Waterson]

I could definitely use nsVoidArray::MoveElement() in this case. If you can get 
those checked in any time soon, I'll rework this patch use it! (Adding 
dependency...)

Comment 11

[David Hyatt]

sr=hyatt

Comment 12

[rbs]

Nit: knowing how this VoidArray stuff works, would'nt you want to proceed
from the "end"?  i.e., look backwards from the last element. In case something 
is found in the middle, you remove it and re-append it? -- but I guess that 
would probably be equivalent in time to what you does, except in less code
(and would then not be dependent upon MoveElement()).

Comment 13

[Chris Waterson]

rbs: the code purposefully avoids triggering any of the nsVoidArray code that 
would ``slide'' entries around. nsVoidArray::ReplaceElementAt() is really the 
poor man's implementation of:

  void*& operator[](PRInt32 aIndex);

If nsVoidArray has _that_, I'd have written it as...

  for (PRInt32 i = cnt; cnt > 0; --cnt)
    mFontMetrics[i] = mFontMetrics[i - 1];

Does that make sense?

Comment 14

[rbs]

Yep, it makes sense (abstracting the typo on the running index). And yes, 
MoveElement() which I just looked at would do the job here.

Comment 15

[Chris Waterson]

Fix checked in. hyatt: if you do any short-page profiling, I'd be interested to
know if this makes a difference there. (I'm suspicious it won't, because IIRC,
you were seeing problems with it caching the _same_ font multiple times under
different names?) Anyway, let me know...

Comment 16

[Chris Waterson]

Really marking fixed.

Comment 17

[rbs]

I happened to pass by this spot in the font cache since I am wading again
into fonts:
  for (...) {
    const nsFont* font;
    metrics->GetFont(font);
    if (aFont.Equals(*font)) {
      ...etc
    }
  }

These are very innefficient copies just to test for equality! Since the cache is 
so heavily used, if you come by there again, do well to remember this wish of 
mine: a nsIFontMetrics::FontIs(): metrics->FontIs(font, true|false);

Comment 18

[rbs]

Err... There is no copy in that code-path...

Comment 19

[Randell Jesup [:jesup] (needinfo me)]

This is related to bug 97299 (store font names in lower case).  Note that
MoveElement() is now in nsVoidArray and is also used here now.  Yes, I know this
is marked as fixed.