710727 - share character map between fonts with identical coverage

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Jonathan Kew [:jfkthame]]

Currently, we read the 'cmap' of each font on the system (or loaded via @font-face) and record its character coverage in a gfxSparseBitSet within the font entry. On a typical Mac or Windows system with a few hundred fonts, including several large CJK fonts (and remembering that there are often 4 faces per family, each with its individual character map), this may amount to a couple of megabytes of data.

We can significantly reduce the RAM footprint (by somewhat over 50%, in an initial test on a fairly font-rich Mac) by recognizing when multiple faces have the same character coverage, and letting the font entries point to a single shared gfxSparseBitSet instead of holding separate copies.

This will also allow us to add a per-family character map (for more efficient font fallback searches) without significantly increasing RAM usage.

I'm intending to do some instrumentation to determine how much runtime RAM footprint could be saved by sharing identical maps, both for desktop and mobile systems.

Comment 1

[Jonathan Kew [:jfkthame]]

Attachment: patch, share character maps between font entries with identical coverage

Comment 2

[Jonathan Kew [:jfkthame]]

Some examples of the approximate memory savings here:

Win7 machine, fairly standard font configuration (only a handful of added fonts) - saved 900K out of an original 1.2MB of character-map data.

MacOSX machine (10.7) with a standard font configuration - saved 520K out of an original 1.1MB.

MacOSX machine (10.6) with lots of custom fonts added - saved 1MB out of an original 1.8MB.

On my HTC Desire HD phone (standard config, no added fonts), this only saves about 9K out of an original 32K used for the character-map data; this is expected, as the phone only offers a handful of fonts. The savings will increase as the number of installed font families and faces increases - which I expect will happen especially on tablets.

Comment 3

[John Daggett (:jtd)]

The reason all cmaps are stored is that they are used as part of system font fallback, where the code currently scans all cmaps for all font families.  But that process will change as part of the work for bug 705594, one of the goals there is to minimize the number of cmaps read in the first place.  I think consolidating the cmaps for a family makes sense but I'd prefer to do this after system font fallback has been reworked.

Comment 4

[John Daggett (:jtd)]

If we're more conservative about loading cmaps, then the memory use will drop dramtically, which makes this optimization less of a priority.

Comment 5

[Jonathan Kew [:jfkthame]]

OTOH, I don't see any reason to hold this back - it shouldn't cause any major disruption to other cmap-loading changes, it just requires that whenever we've loaded a cmap - whether eagerly or lazily - we hand the resulting bitset over to gfxCharMapMgr, and then proceed to use the pointer it returns instead of the original.

I'd like to make this change before re-working the font memory reporter patches, as it will have a substantial effect on those - so it makes sense to implement the sharing first to reduce the amount of work/churn in the reporting code.

Comment 6

[John Daggett (:jtd)]

Comment on attachment 583101 [details] [diff] [review]
patch, share character maps between font entries with identical coverage

Rather than use static's, special objects that need to be cleaned at
shutdown, and custom ref counting I think it would be more
straightforward to simply make a ref counted subclass of
gfxSparseBitSet and use nsRefPtr everywhere.  That's a known pattern
in Gecko code and easier for others to read and quickly understand
plus it hooks in with existing leak checking code.

+    static nsTHashtable<HashEntry> sCharacterMaps;
+    static gfxSparseBitSet        *sEmptyCharacterMap;

Use nsRefPtrHashtable and nsRefPtr, add make the gfxCharMapMgr a
member of gfxPlatformFontList.

GDIFontEntry::ReadCMAP:

+    // attempt this once, if errors occur leave a blank cmap
+    if (mCharacterMap) {
+        return NS_OK;
+    }
+
+    mCharacterMap = new gfxSparseBitSet;
+
  .
  .
  .
+    gfxSparseBitSet *charMap =
+        gfxFontUtils::ReadCMAP(cmap, buffer.Length(),
+                               mUVSOffset,
+                               unicodeFont, symbolFont);
     mSymbolFont = symbolFont;
-    mHasCmapTable = NS_SUCCEEDED(rv);
+    if (charMap) {
+        mHasCmapTable = true;
+        delete mCharacterMap;
+        mCharacterMap = gfxCharMapMgr::ShareCharMap(charMap);
+    }
 
GDIFontEntry::TestCharacterMap:

+    if (hasGlyph) {
+        // it's OK to cast away the const-ness of mCharacterMap here
+        // and modify it, because in the case where there wasn't a cmap table
+        // we don't share the map with other font entries
+        gfxSparseBitSet *charMap = const_cast<gfxSparseBitSet*>(mCharacterMap);
+        charMap->set(aCh);
+        return true;
     }

There's no real reason to share the "cmap" in this case and it just
makes the code confusing and ugly (e.g. const_cast).  You're also
altering the hash key within the hashtable.

Just use a distinct instance of a refcounted sparse bitset and set a
flag in the gfxFontEntry so that the memory size can be accounted for
when you finish the memory reporter patches.

Comment 7

[Jonathan Kew [:jfkthame]]

(In reply to John Daggett (:jtd) (Away 23 Dec - 4 Jan) from comment #6)
> Comment on attachment 583101 [details] [diff] [review]
> patch, share character maps between font entries with identical coverage
> 
> Rather than use static's, special objects that need to be cleaned at
> shutdown, and custom ref counting I think it would be more
> straightforward to simply make a ref counted subclass of
> gfxSparseBitSet and use nsRefPtr everywhere.  That's a known pattern
> in Gecko code and easier for others to read and quickly understand
> plus it hooks in with existing leak checking code.
> 
> +    static nsTHashtable<HashEntry> sCharacterMaps;
> +    static gfxSparseBitSet        *sEmptyCharacterMap;
> 
> Use nsRefPtrHashtable and nsRefPtr, add make the gfxCharMapMgr a
> member of gfxPlatformFontList.

We don't really want an nsRefPtrHashtable here, as we're not doing a key-value mapping. We just need a hashset that records the existence of each charmap and counts how many current users it has. The "obvious" solution (IMO) would have been a nsTHashtable<nsRefPtr<gfxSparseBitSet> > (assuming we make the gfxSparseBitSet refcountable), but I'm not sure that's actually a supported usage for these classes. At least, my attempt to write it didn't work out.

> GDIFontEntry::TestCharacterMap:
> 
> +    if (hasGlyph) {
> +        // it's OK to cast away the const-ness of mCharacterMap here
> +        // and modify it, because in the case where there wasn't a cmap
> table
> +        // we don't share the map with other font entries
> +        gfxSparseBitSet *charMap =
> const_cast<gfxSparseBitSet*>(mCharacterMap);
> +        charMap->set(aCh);
> +        return true;
>      }
> 
> There's no real reason to share the "cmap" in this case and it just
> makes the code confusing and ugly (e.g. const_cast).  You're also
> altering the hash key within the hashtable.

No, in the (non-sfnt) case where there isn't an actual cmap table, mCharacterMap is not entered in the hashtable at all; gfxGDIFontEntry allocates its own blank charmap and adds characters to it as they're found, but it never shares that via gfxCharMapMgr. That's what the comment here is pointing out. And so - unlike the "normal" case of sfnt-format fonts, where we share the cmap via the hashtable and therefore must not change it dynamically - in this case it doesn't actually need to be const, and it's OK to fill it in incrementally here.

> Just use a distinct instance of a refcounted sparse bitset and set a
> flag in the gfxFontEntry so that the memory size can be accounted for
> when you finish the memory reporter patches.

It _is_ a distinct instance of a bitset. For memory reporting purposes, I was intending to add a method on gfxCharMapMgr to query whether a given bitset is known in the shared-cmap hashtable or not; font entries would account for their own charmap if this returns false.

Comment 8

[John Daggett (:jtd)]

Attachment: count of unique cmaps within font families on OSX 10.5

> We don't really want an nsRefPtrHashtable here, as we're not doing a
> key-value mapping. We just need a hashset that records the existence
> of each charmap and counts how many current users it has. The
> "obvious" solution (IMO) would have been a
> nsTHashtable<nsRefPtr<gfxSparseBitSet> > (assuming we make the
> gfxSparseBitSet refcountable), but I'm not sure that's actually a
> supported usage for these classes. At least, my attempt to write it
> didn't work out.

I think I have a better idea here.  Rather than use a global hash table,
simply use an array of nsRefPtr's associated with the gfxFontFamily.  I
looked through the fonts on OSX 10.5 and of the 209 families only 19 of
them have faces with different cmaps.  The commonality of cmaps is
typically with other fonts of the same family, not fonts from a
different family.  Most of the time a single comparison is all that will
be needed when "sharing" a cmap within the same family.  The code for
this will reduce to something much simpler than the patch here.

Comment 9

[Jonathan Kew [:jfkthame]]

(In reply to John Daggett (:jtd) (Away 23 Dec - 4 Jan) from comment #8)

> I think I have a better idea here.  Rather than use a global hash table,
> simply use an array of nsRefPtr's associated with the gfxFontFamily.  I
> looked through the fonts on OSX 10.5 and of the 209 families only 19 of
> them have faces with different cmaps.  The commonality of cmaps is
> typically with other fonts of the same family, not fonts from a
> different family.

This isn't entirely true - there are a lot of cases where different font families have identical cmap coverage, and we'll save memory by recognising this. It's not uncommon for a font foundry to have established character inventories that are implemented across a range of families; e.g. a character list that they consider sufficient to cover all European Latin-script languages, or a Latin+Cyrillic inventory, etc.

More significantly, there are some standard inventories of CJK characters (e.g. the Adobe-Japan* collections) that are likely to match across multiple CJK families, where the size of the cmap means that cross-family sharing is particularly beneficial.

Some CJK examples where a cmap can be shared across families, found among fonts on my 10.6 machine:
* Hiragino Kaku/Maru/Mincho
* STFangsong/STHeiti/STKaiti/STSong
* Kozuka Gothic/Mincho
* Gulim/Batang
* STHeitiSC/STHeitiTC
* MS-Gothic/MS-Mincho/MS-PGothic/MS-PMincho
* LiHeiPro/LiSongPro

And some non-CJK examples of cross-family sharing:
* Arial-Black/ArialNarrow/BookAntiqua/BookmanOldStyle/CenturyGothic/ComicSansMS/Garamond/MonotypeCorsiva
* AbadiMT/ArialRoundedMTBold/BernardMT/BrushScriptMT/CalistoMT/ColonnaMT/CooperBlackMS/CopperplateGothic/Haettenschweiler/MaturaMTScriptCapitals/Modern/NewsGothicMT/PerpetuaTitlingMT/Rockwell
* Bauhaus93/BritannicBold/LucidaBlackletter/LucidaBright/LucidaCalligraphy/LucidaFax/LucidaHandwriting/LucidaSans/Playbill
* Candara/Constantia/Corbel

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Sharing cmaps across families does look useful. I would love to see this land.

Comment 11

[Jonathan Kew [:jfkthame]]

Would you like to review it? Note responses to John's r- comments above; I still think the patch as it stands is a good approach.

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I can review it, but I don't want to go over John's head. It's important he OK's this approach first.

Comment 13

[Jonathan Kew [:jfkthame]]

Comment on attachment 583101 [details] [diff] [review]
patch, share character maps between font entries with identical coverage

Re-requesting review, in the light of comments 7 and 9 (responses to earlier review comments).

Comment 14

[John Daggett (:jtd)]

Attachment: cmap checksum per font family, Windows 7 JA

Data columns are size of cmap bitvector, checksum, family name.

Comment 15

[John Daggett (:jtd)]

Comment on attachment 583101 [details] [diff] [review]
patch, share character maps between font entries with identical coverage

This patch implements global sharing of cmaps rather than per-family
sharing.  Yes, there is a savings when cmaps are shared globally rather
than per-family *if* all cmaps are loaded.  But the point of bug 705594
is to avoid loading the vast majority of cmaps, that's why I marked this
bug as dependent on that one.

Data for the Windows 7 JA case:

Total space used by cmaps:     1,059K
Sharing cmaps within families:   474K
Sharing cmaps globally:          310K

Roughly 80% of the 160K difference between these two approaches are from
CJK fonts (the top 70 fonts by cmap size in the attached data file) that
contain multiple families in TrueType collections (e.g. MS Gothic and MS
PGothic). With hard-coded fallback, in many of these cases only a small
subset of all these cmaps will ever be loaded.

Sharing cmaps per-family with a simple, dumb array of nsRefPtr's is
*much* simpler to implement.  Once the changes to system fallback are
landed we can reevaluate whether it makes sense to globally share cmaps
or not.

Comment 16

[Jonathan Kew [:jfkthame]]

I don't understand why you're opposed to the global approach - it doesn't seem particularly complex to me, the gfxCharMapMgr provides a very simple API that the font entries use to make this work. And even if you avoid loading so many cmaps overall, it still provides a greater benefit than sharing only within families.

The only somewhat hairy part, ISTM, is the special case of non-sfnt fonts under GDI, where we build the 'cmap' incrementally as characters are required, rather than reading it in a single operation - which means we can't use a potentially shared map here. And that case would require special handling in a per-family approach, too; those fonts just don't fit in with the rest of our character-map handling.

Comment 17

[John Daggett (:jtd)]

(In reply to Jonathan Kew (:jfkthame) from comment #16)
> I don't understand why you're opposed to the global approach - it
> doesn't seem particularly complex to me, the gfxCharMapMgr provides a
> very simple API that the font entries use to make this work. And even
> if you avoid loading so many cmaps overall, it still provides a
> greater benefit than sharing only within families.

That "greater benefit" is relative to the number of fonts involved, the idea that there's a greater benefit when 20-30 fonts are involved is very different from the case when 200-300 fonts are involved.  I don't want to land code that
will essentially be dead weight when system font fallback is revised to read in font cmaps much more selectively.  It might end up making a difference but I think it's a better strategy to use very simple code now and revise it later if warranted in practice.

> The only somewhat hairy part, ISTM, is the special case of non-sfnt
> fonts under GDI, where we build the 'cmap' incrementally as characters
> are required, rather than reading it in a single operation - which
> means we can't use a potentially shared map here. And that case would
> require special handling in a per-family approach, too; those fonts
> just don't fit in with the rest of our character-map handling.

I don't follow why this is hard, non-SFNT fonts simply never share their character maps.

Comment 18

[Jonathan Kew [:jfkthame]]

Attachment: alternative patch, share cmap between faces within a family when character coverage is identical

Here's an alternative patch that maintains an array of character maps (gfxSparseBitSet) in each font family, and lets the family's faces point to these instead of keeping their own separate copies.

We don't actually need to refcount the maps at all in this case; they can simply be owned by the family, and deleted when it dies (at which point all of its faces are deleted as well).

Comment 19

[John Daggett (:jtd)]

(In reply to Jonathan Kew (:jfkthame) from comment #18)

> We don't actually need to refcount the maps at all in this case; they can
> simply be owned by the family, and deleted when it dies (at which point all
> of its faces are deleted as well).

As noted in bug 668813, comment 47, I think it's possible to get dangling mFamily ptr's in gfxFontEntry objects.  Either we refcount the cmaps or assure that mFamily is never dangling.

Comment 20

[Jonathan Kew [:jfkthame]]

Filed bug 721315 on the dangling pointers. However, that's not enough to make this safe, as the mCharacterMap pointer would also be invalidated by the deletion of the family. We could clear those pointers too, but then a font entry that has lived longer than its family (because we have a currently-active gfxFont) would "forget" its character coverage and cease to work properly.

I experimented with a version of this based on adding standard refcounting to the gfxSparseBitSet, and holding nsRefPtr<> references to them in the font entries (as well as an array of nsRefPtr in the family). However, this gets hairy because of the deferred deletion of font entries (via timed gfxFontCache expiration) from a secondary thread. I used the thread-safe version of refcounting, but still ran into unpredictable crashes during shutdown of the observer service.... messy.

IMO, it's conceptually simpler (and safer, considering the pitfalls of font family and entry lifetimes) to have a single "global" cache of character maps, as per the original patch here.

Comment 21

[John Daggett (:jtd)]

Comment on attachment 590874 [details] [diff] [review]
alternative patch, share cmap between faces within a family when character coverage is identical

If you refresh the patch, I'll take a look at this first thing tomorrow.

Comment 22

[Jonathan Kew [:jfkthame]]

Attachment: share cmap between faces within a family when character coverage is identical - updated

Comment 23

[John Daggett (:jtd)]

Attachment: alternate patch, share cmaps within font families

Rather than store cmaps in a common array, this patch stores the cmap in a
nsRefPtr attached to each font entry.  When a new cmap is read in the code
simply loops through the fonts for a given family to find one that matches,
using a checksum and the Equals method from the previous patch.

I ran into some problems related to downloadable fonts related to the patch
landed before that iterates over all fonts in the family.  For downloadable
fonts, the present code is testing the cmaps of proxy font entries(!) which is
silly and problematic when using a pointer that needs to be initialized.  So I
ended up disabling cmap sharing for this case but I think we actually need
to revisit the original issue.

Comment 24

[John Daggett (:jtd)]

Attachment: alternate patch, share fonts globally

This patch builds on the previous one.  Cmaps are pointed to by nsRefPtr's in the base font entry.  When a new cmap is loaded it's matched with existing cmaps in a custom hashtable attached to the font list.  The Release method code pulls the weak reference out of the hashtable when the reference count hits zero.

Comment 25

[John Daggett (:jtd)]

Results on Lion OSX:

Simple test: start browser, visit wikipedia.org

269 font families

size of all cmaps:                  3.58mb
size of cmaps shared within family: 1.75mb
size of globally shared cmaps:      1.13mb

This sort of pattern will turn up on XP but on DirectWrite and OSX, system fallback is used so cmaps are loading much more sparingly:

size of cmaps:                      0.24mb
size of cmaps shared with family:   0.19mb

Sharing the fonts globally in this case makes no difference in the amount of cmap data stored.

Comment 26

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I personally think that sharing an extra 600KB in the Wikipedia case is worth it.

Comment 27

[John Daggett (:jtd)]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #26)
> I personally think that sharing an extra 600KB in the Wikipedia case is
> worth it.

That savings is based on loading *all* cmaps (the current XP case when hitting a codepoint supported by no system font).  On Win7/OSX, there are no such savings, in the case of Wikipedia the two are almost identical.

That said, I'm okay with global sharing as long as the code is not unduly complex.  I don't think the two alternate patches are so different, they use existing Gecko patterns.  What I didn't like about the original global sharing patch was that it seemed overly complex, I found the logic in gfxCharMapMgr difficult to follow easily.  Standard ref-counted objects shared by gfxFontEntry objects with a global hash set seems simpler and easier to follow for those familiar with Gecko code.

Comment 28

[Jonathan Kew [:jfkthame]]

(In reply to John Daggett (:jtd) from comment #23)
> When a new cmap is read in the code
> simply loops through the fonts for a given family to find one that matches,
> using a checksum and the Equals method from the previous patch.

Is it really worth checksumming the character maps? I'd guess that in the vast majority of cases that we actually encounter, either (a) the charmaps are identical, in which case we'll still end up doing the full Equals() to establish this, so computing the checksum was just added overhead; or (b) they're sufficiently different that Equals() will return false quickly, without actually comparing every byte of all the blocks.

Comment 29

[John Daggett (:jtd)]

(In reply to Jonathan Kew (:jfkthame) from comment #28)

> Is it really worth checksumming the character maps? I'd guess that in the
> vast majority of cases that we actually encounter, either (a) the charmaps
> are identical, in which case we'll still end up doing the full Equals() to
> establish this, so computing the checksum was just added overhead; or (b)
> they're sufficiently different that Equals() will return false quickly,
> without actually comparing every byte of all the blocks.

In the case of per-family sharing, it helps eliminate the Equals call for cmaps that are different.  But you're right, it adds overhead that is only gained for the case that cmaps are different.  But in the global sharing case, the checksum is used as the hash, so it's needed for that.

Comment 30

[Jonathan Kew [:jfkthame]]

Comment on attachment 609526 [details] [diff] [review]
alternate patch, share cmaps within font families

Review of attachment 609526 [details] [diff] [review]:
-----------------------------------------------------------------

See below for a suggested adjustment to the style. It looks like this needs quite a bit of rebasing to apply on a current tree, however; if you could refresh the patch, I'll finish looking it over.

::: gfx/thebes/gfxDWriteFontList.cpp
@@ +362,4 @@
>          return NS_OK;
> +    }
> +
> +    nsRefPtr<gfxCharacterMap> charmap = new gfxCharacterMap();

I think it'd be better to directly set  mCharacterMap = new gfxCharacterMap()  here, so that you can do early returns using  if (NS_FAILED(rv)) { return rv; }  or similar wherever there's a possibility of failure. This avoids needing to put entire blocks inside if  (NS_SUCCEEDED(rv))  conditionals....

@@ +413,5 @@
> +        if (mFamily) {
> +            mCharacterMap = mFamily->FindSameCharacterMap(charmap);
> +        } else {
> +            mCharacterMap = charmap;
> +        }

...and then adjust this to something like

    mHasCmapTable = true;
    nsRefPtr<gfxCharacterMap> charmap = mCharacterMap;
    if (mFamily) {
        mCharacterMap = nsnull; // temporarily detach from the entry
        mCharacterMap = mFamily->FindSame....
    }

and no more messy error-checking is needed here.

A similar pattern applies to the other font-list classes; gfxMacPlatformFontList, in particular, has a big chunk inside  if (NS_SUCCEEDED(rv))  which can then shed its conditional block wrapper.

::: gfx/thebes/gfxFontUtils.h
@@ +340,5 @@
>      void Compact() {
>          mBlocks.Compact();
>      }
>  
> +    PRUint32 GetChecksum() {

I think you should drop the checksum stuff from this patch, as it's unlikely to be beneficial here and may well actually be a net loss; then introduce a Hash() function in the global-sharing patch instead. And then it'd probably make sense to use mozilla::HashBytes as the basis, rather than zlib's adler32.

Comment 31

[John Daggett (:jtd)]

Attachment: alternate patch v2, share cmaps globally

This is a merged version of the two alternate patches which shares
cmaps globally, updated to latest trunk code.

> ::: gfx/thebes/gfxDWriteFontList.cpp
> @@ +362,4 @@
> >          return NS_OK;
> > +    }
> > +
> > +    nsRefPtr<gfxCharacterMap> charmap = new gfxCharacterMap();
> 
> I think it'd be better to directly set  mCharacterMap = new
> gfxCharacterMap()  here, so that you can do early returns using  if
> (NS_FAILED(rv)) { return rv; }  or similar wherever there's a possibility of
> failure. This avoids needing to put entire blocks inside if 
> (NS_SUCCEEDED(rv))  conditionals....

I reworked this behavior in the latest patch to do less
of this "create blank cmap on error" behavior.  Other than the GDI
case, it only creates a blank cmap once.  The reason for not immediately
assigning this to mCharacterMap is that the struct may be partially filled
in when the ReadCMAP call fails (e.g. if the cmap structure is slightly
corrupt).  I think this is a lot less messy than the original patch
for sharing cmaps within a family.

> ::: gfx/thebes/gfxFontUtils.h
> @@ +340,5 @@
> >      void Compact() {
> >          mBlocks.Compact();
> >      }
> >  
> > +    PRUint32 GetChecksum() {
> 
> I think you should drop the checksum stuff from this patch, as it's unlikely
> to be beneficial here and may well actually be a net loss; then introduce a
> Hash() function in the global-sharing patch instead. And then it'd probably
> make sense to use mozilla::HashBytes as the basis, rather than zlib's
> adler32.

I switched mChecksum to mHash but I think the alder32 checksum routine
is a better match for the job here.  The mozilla::HashBytes is particularly
inefficient for long byte sequences and for objects where the hash is
calculated from a disjoint set of memory blocks, which is the case with
the sparse bitset object.  I think it might be a good idea to switch
HashBytes to use adler32 but that's probably a larger bug, since there
may be important reasons not to use zlib routines within basic xpcom
util classes.

Comment 32

[Jonathan Kew [:jfkthame]]

Comment on attachment 611381 [details] [diff] [review]
alternate patch v2, share cmaps globally

Review of attachment 611381 [details] [diff] [review]:
-----------------------------------------------------------------

Basically seems fine; a few nits, and a couple of larger questions: what about sharing the family cmap? And I think the memory reporting isn't handled correctly here (see below).

::: gfx/thebes/gfxDWriteFontList.cpp
@@ +427,5 @@
>  
> +    mHasCmapTable = NS_SUCCEEDED(rv);
> +    if (mHasCmapTable) {
> +        mCharacterMap =
> +         gfxPlatformFontList::PlatformFontList()->FindSameCharacterMap(charmap);

Here and in the other platform implementations, the irregular indent looks very odd - please fix.

(Could maybe shorten "FindSameCharacterMap" to "FindCharMap" or "ShareCharMap" or something.)

::: gfx/thebes/gfxFont.cpp
@@ +181,5 @@
>  }
>  
>  nsresult gfxFontEntry::ReadCMAP()
>  {
> +    NS_ASSERTION(false, "using default no-op implementation of ReadCMAP");

Presumably we're never supposed to hit this, but wouldn't it be safer to do mCharacterMap = new gfxCharacterMap() here, so that we leave the entry in a safe state rather than our caller proceeding to dereference a null pointer?

@@ +447,5 @@
>      aSizes->mFontListSize += mName.SizeOfExcludingThisIfUnshared(aMallocSizeOf);
> +    if (mCharacterMap) {
> +        aSizes->mCharMapsSize +=
> +            mCharacterMap->SizeOfExcludingThis(aMallocSizeOf);
> +    }

I think this is wrong - when multiple entries share a character map, its size will end up getting counted multiple times, won't it?

::: gfx/thebes/gfxFont.h
@@ +218,5 @@
> +        }
> +        return mRefCnt;
> +    }
> +
> +    PRInt32 GetRefCount() { return mRefCnt; }

Is this needed? I don't see why.

@@ +237,5 @@
> +    // if cmap is built on the fly it's never shared
> +    bool mBuildOnTheFly : 1;
> +
> +    // cmap is shared globally
> +    bool mShared : 1;

Because of alignment, I don't think there'll be any benefit to using bit-fields for these, and presumably it makes for a little extra overhead when accessing them.

@@ +243,5 @@
> +protected:
> +    void NotifyReleased();
> +
> +    nsAutoRefCnt mRefCnt;
> +};

As a precaution, gfxCharacterMap should probably have a private, unimplemented copy constructor and assignment operator.

@@ +313,5 @@
>          return mHasCmapTable;
>      }
>  
>      inline bool HasCharacter(PRUint32 ch) {
> +        if (mCharacterMap && mCharacterMap->test(ch))

While we're touching this anyway, let's add the missing braces.

@@ +664,1 @@
>          }

Given that it's common for all the faces in a family to have the same character repertoire, it might be worth reworking this so as to check for this case first (by just checking whether the faces all refer to the same map) before bothering with the full Union() operations.

@@ +723,5 @@
>      }
>  
>      nsString mName;
>      nsTArray<nsRefPtr<gfxFontEntry> >  mAvailableFonts;
> +    gfxSparseBitSet mFamilyCharacterMap;

It's pretty common for all the fonts in a family to share the same character map; and even when that's not the case, it's likely that some of them are subsets of others, so that the family map will still be identical to the more-complete entry's map.

As such, it seems a pity to maintain a separate copy for the family; in most cases this could also be a shared map.

::: gfx/thebes/gfxFontUtils.h
@@ +344,5 @@
>      void Compact() {
>          mBlocks.Compact();
>      }
>  
> +    PRUint32 GetChecksum() {

This should be a const function.

@@ +348,5 @@
> +    PRUint32 GetChecksum() {
> +        PRUint32 check = adler32(0, Z_NULL, 0);
> +        for (PRUint32 i = 0; i < mBlocks.Length(); i++) {
> +            if (mBlocks[i]) {
> +              const Block *block = mBlocks[i];

nit: standard indent is 4 spaces around here.

::: gfx/thebes/gfxGDIFontList.cpp
@@ +371,3 @@
>      }
>  
> +    if (mCharacterMap->mBuildOnTheFly) {

I think we should reverse the sense of the test here, so that the common case (where mBuildOnTheFly is false) comes first and immediately does an early return.

::: gfx/thebes/gfxPlatformFontList.cpp
@@ +213,5 @@
>      gFontListPrefObserver = new gfxFontListPrefObserver();
>      NS_ADDREF(gFontListPrefObserver);
>      Preferences::AddStrongObservers(gFontListPrefObserver, kObservedPrefs);
> +
> +    mSharedCmaps.Init(50);

Let's have a smaller initial table size (the hashtable default is 16, I think?) - in many cases where a user doesn't browse to a wide variety of sites with different styles, we won't need this many. (Especially on mobile, where there may only be a few dozen fonts altogether on the device.)

@@ +739,5 @@
> +void
> +gfxPlatformFontList::RemoveCmap(const gfxCharacterMap* aCharMap)
> +{
> +    // skip lookups during teardown
> +    if (mSharedCmaps.Count() == 0) return;

I don't think the style guide approves of the single-line form here.

::: gfx/thebes/gfxPlatformFontList.h
@@ +75,5 @@
> +
> +    bool KeyEquals(const gfxCharacterMap *aCharMap) const {
> +        // cmaps built on the fly never match
> +        if (aCharMap->mBuildOnTheFly || mCharMap->mBuildOnTheFly ||
> +            aCharMap->mHash != mCharMap->mHash)

IIUC, cmaps that are built on the fly never get recorded in the global hash, so it shouldn't be necessary to check mCharMap->mBuildOnTheFly here. (Maybe you could just assert that it must be false?)

Comment 33

[Justin Lebar (not reading bugmail)]

> The mozilla::HashBytes is particularly
> inefficient for long byte sequences and for objects where the hash is
> calculated from a disjoint set of memory blocks

The first one, perhaps.  Byte-by-byte is slow, but it's such a simple hash, you might end up being memory-bound on long sequences anyway.  The second one, I doubt.  There's basically no work to "finish" the hash, so I don't see why calling HashBytes many times would be worse than calling adler32 many times.

Anyway, HashBytes is not a particularly good hash function; using adler32 seems fine to me.  We also have spookyhash, murmurhash, and cityhash hiding in the tree, if you wanted to use one of those.   :)

So long as you don't use |hash ^= rol(bytes[i], 4)|, I'm happy!

Comment 34

[John Daggett (:jtd)]

(In reply to Justin Lebar [:jlebar] from comment #33)
> The first one, perhaps.  Byte-by-byte is slow, but it's such a simple hash,
> you might end up being memory-bound on long sequences anyway.  The second
> one, I doubt.  There's basically no work to "finish" the hash, so I don't
> see why calling HashBytes many times would be worse than calling adler32
> many times.

HashBytes calculates the hash for a sequence of bytes starting with a fixed initial value.  So for multiple blocks one would either need to manually composite the hash for a given block with the previous hash or call AddToHash repeatedly (which is exactly what HashBytes does).  The adler32 function takes an existing hash value as an input parameter and runs over a set of bytes in a simple loop.  That's why it's a better fit for this case.

Comment 35

[Justin Lebar (not reading bugmail)]

> So for multiple blocks one would either need to manually composite the hash for a given block with 
> the previous hash or call AddToHash repeatedly (which is exactly what HashBytes does).  The adler32 
> function takes an existing hash value as an input parameter and runs over a set of bytes in a simple 
> loop.  That's why it's a better fit for this case.

Well, you could do

  newHash = AddToHash(oldHash, HashBytes(buf, len))

to get the same effect.  I agree that the ergonomics of two function calls versus one are not ideal, but this isn't substantially different from |adler32(oldHash, buf, len)|.  We could of course write AddBytesToHash as a mnemonic for the code above.

I'm not sure that the ergonomic inconvenience here outweighs the ugliness of calling into zlib from unrelated code.  But like I said, I do not object to your using any non-pathetic hash function.  :)

Comment 36

[John Daggett (:jtd)]

Attachment: alternate patch v3, share cmaps globally

Updated based on review comments.

I reworked the memory reporting to include shared cmaps in the platform list total and non-shared in the font entry total.

> @@ +664,1 @@
> >          }
> 
> Given that it's common for all the faces in a family to have the
> same character repertoire, it might be worth reworking this so as to
> check for this case first (by just checking whether the faces all
> refer to the same map) before bothering with the full Union()
> operations.
> 
> @@ +723,5 @@
> >      }
> >  
> >      nsString mName;
> >      nsTArray<nsRefPtr<gfxFontEntry> >  mAvailableFonts;
> > +    gfxSparseBitSet mFamilyCharacterMap;
> 
> It's pretty common for all the fonts in a family to share the same
> character map; and even when that's not the case, it's likely that
> some of them are subsets of others, so that the family map will
> still be identical to the more-complete entry's map.

I intentionally tried to avoid changing the family cmap as much as
possible. I don't think there's a lot to be gained here and I'm
concerned that the logic behind loading all family cmaps doesn't
really make sense.  I think any modification of that logic beyond
what's here should be done on a different bug.

Comment 37

[Jonathan Kew [:jfkthame]]

Comment on attachment 612817 [details] [diff] [review]
alternate patch v3, share cmaps globally

Review of attachment 612817 [details] [diff] [review]:
-----------------------------------------------------------------

Looking good, except for the font-matching change in gfxFontGroup::FindFontForChar, which I think needs to be considered in its own right as a separate bug; otherwise, just a couple of little things I noticed.

r=me with that fixed.

::: gfx/thebes/gfxFont.cpp
@@ +3667,5 @@
>          // check other faces of the family
>          gfxFontFamily *family = font->GetFontEntry()->Family();
> +        if (family && !font->GetFontEntry()->IsUserFont() &&
> +            family->TestCharacterMap(aCh))
> +        {

I don't think this change belongs here. I realize there's an issue you're aiming to address with it (alluded to in comment 23), but this will regress existing behavior and I don't think we should simply bundle it into this patch. If we're going to do something that modifies font-matching behavior for user fonts, it should be filed as a separate bug where the specific issue can be properly addressed.

::: gfx/thebes/gfxFont.h
@@ +226,5 @@
> +    void CalcHash() { mHash = GetChecksum(); }
> +
> +    size_t SizeOfExcludingThis(nsMallocSizeOfFun aMallocSizeOf) const {
> +        return gfxSparseBitSet::SizeOfExcludingThis(aMallocSizeOf);
> +    }

Surely this is redundant?

::: gfx/thebes/gfxGDIFontList.cpp
@@ +365,5 @@
>  bool 
>  GDIFontEntry::TestCharacterMap(PRUint32 aCh)
>  {
> +    if (!mCharacterMap) {
> +        nsresult rv = ReadCMAP();

This looks like it'll produce a "variable set but not used" warning or something like that.

Comment 38

[John Daggett (:jtd)]

(In reply to Jonathan Kew (:jfkthame) from comment #37)
> @@ +3667,5 @@
> >          // check other faces of the family
> >          gfxFontFamily *family = font->GetFontEntry()->Family(); +  
> >               if (family && !font->GetFontEntry()->IsUserFont() && +
> >                     family->TestCharacterMap(aCh)) +        {
> 
> I don't think this change belongs here. I realize there's an issue
> you're aiming to address with it (alluded to in comment 23), but this
> will regress existing behavior and I don't think we should simply
> bundle it into this patch. If we're going to do something that
> modifies font-matching behavior for user fonts, it should be filed as
> a separate bug where the specific issue can be properly addressed.

The problem here is that the existing logic is "loading" and testing the
cmap of the proxy font entries for downloadable fonts.  I realized this
because when I put an assert into gfxFontEntry::ReadCMAP it immediately
fired because of the logic that's trying to load all cmaps for a given
family.  This is logged as bug 738147.

If you would feel better, I could change this to test
!fontEntry->mIsProxy, that would avoid the problem I was running into. 
Then we can figure out the solution to the family cmap problem in bug
738147.

I'm going to hold off landing this until you have time to respond.

Comment 39

[Jonathan Kew [:jfkthame]]

(In reply to John Daggett (:jtd) from comment #38)
> If you would feel better, I could change this to test
> !fontEntry->mIsProxy, that would avoid the problem I was running into. 
> Then we can figure out the solution to the family cmap problem in bug
> 738147.

I don't think that'll help, will it? The "current" font won't be a proxy by this time, or we'd never have gotten this far; but other members of its family may still be proxies, and those are the ones that'll assert when they're asked to read cmaps.

Maybe the solution - pending bug 738147 - is for the loop in ReadAllCMAPs() to simply do "if (fe->mIsProxy) continue;" rather than asserting, for now. That way proxy entries will contribute nothing to the family cmap, which should maintain the existing behavior (without breaking it for the case where all the user fonts making up the family *have* been loaded), I think.

Comment 40

[John Daggett (:jtd)]

Including changes suggested in comment 39, pushed to mozilla-inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2b364a0ca1da

Comment 41

[John Daggett (:jtd)]

Backed out due to reftest/mochitest-4 failures on Win7
https://hg.mozilla.org/integration/mozilla-inbound/rev/1721afdbf0c3

Comment 42

[John Daggett (:jtd)]

https://tbpl.mozilla.org/php/getParsedLog.php?id=10745705&tree=Mozilla-Inbound&full=1

REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/text-overflow/clipped-elements.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-face/src-list-local-full.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-face/src-list-local-full-quotes.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-face/src-list-local-fallback.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-face/src-list-local-ps.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-face/local-1.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-matching/synthetic-bold-1.html | image comparison (!=)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-matching/synthetic-bold-2.html | image comparison (!=)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-matching/defaultfont-bold.html | image comparison (!=)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-matching/impact-bold.html | image comparison (!=)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/font-matching/arialunicode-bold.html | image comparison (!=)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/selection/addrange-2.html | image comparison (==)
REFTEST TEST-UNEXPECTED-FAIL | file:///c:/talos-slave/test/build/reftest/tests/layout/reftests/text/726392-2.html | image comparison (==)

https://tbpl.mozilla.org/php/getParsedLog.php?id=10745088&tree=Mozilla-Inbound&full=1

12848 ERROR TEST-UNEXPECTED-FAIL | /tests/layout/base/tests/test_bug394057.html | changing font pref should change width of table (monospace) - got 150, expected 151

Comment 43

[(no longer active)]

https://hg.mozilla.org/mozilla-central/rev/2b364a0ca1da
https://hg.mozilla.org/mozilla-central/rev/1721afdbf0c3

Comment 44

[John Daggett (:jtd)]

The reftest failures on Win7 debug were caused by an extra nsresult declaration in gfxDWriteFontEntry::ReadCMAP which caused an uninitialized value to be used.  Once that's removed all reftests pass.

Comment 45

[John Daggett (:jtd)]

This is a memshrink:P2 bug that I think would be valuable to land for the FF14 cycle.

Comment 46

[John Daggett (:jtd)]

Pushed to mozilla-inbound
https://hg.mozilla.org/integration/mozilla-inbound/rev/8094acc0a47e

Comment 47

[(no longer active)]

https://hg.mozilla.org/mozilla-central/rev/8094acc0a47e