Change the GlyphCache to use a hash table instead of doing its own ad-hoc
hashing. This change appears to be performance neutral.
BUG=skia:
Review URL: https://codereview.chromium.org/1216983003
diff --git a/src/core/SkGlyph.h b/src/core/SkGlyph.h
index abca215..4699859 100644
--- a/src/core/SkGlyph.h
+++ b/src/core/SkGlyph.h
@@ -8,6 +8,7 @@
#ifndef SkGlyph_DEFINED
#define SkGlyph_DEFINED
+#include "SkChecksum.h"
#include "SkTypes.h"
#include "SkFixed.h"
#include "SkMask.h"
@@ -114,6 +115,16 @@
void toMask(SkMask* mask) const;
+ class HashTraits {
+ public:
+ static uint32_t GetKey(const SkGlyph& glyph) {
+ return glyph.fID;
+ }
+ static uint32_t Hash(uint32_t glyphId) {
+ return SkChecksum::CheapMix(glyphId);
+ }
+ };
+
private:
// TODO(herb) remove friend statement after SkGlyphCache cleanup.
friend class SkGlyphCache;
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index ae268d5..9b0199f 100755
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -9,10 +9,7 @@
#include "SkGlyphCache_Globals.h"
#include "SkGraphics.h"
#include "SkLazyPtr.h"
-#include "SkMutex.h"
-#include "SkPaint.h"
#include "SkPath.h"
-#include "SkTLS.h"
#include "SkTemplates.h"
#include "SkTypeface.h"
@@ -35,118 +32,52 @@
///////////////////////////////////////////////////////////////////////////////
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- #define RecordHashSuccess() fHashHitCount += 1
- #define RecordHashCollisionIf(pred) do { if (pred) fHashMissCount += 1; } while (0)
-#else
- #define RecordHashSuccess() (void)0
- #define RecordHashCollisionIf(pred) (void)0
-#endif
-#define RecordHashCollision() RecordHashCollisionIf(true)
-
-///////////////////////////////////////////////////////////////////////////////
-
// so we don't grow our arrays a lot
#define kMinGlyphCount 16
#define kMinGlyphImageSize (16*2)
#define kMinAllocAmount ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount)
SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkScalerContext* ctx)
- : fScalerContext(ctx), fGlyphAlloc(kMinAllocAmount) {
+ : fDesc(desc->copy())
+ , fScalerContext(ctx)
+ , fGlyphAlloc(kMinAllocAmount) {
SkASSERT(typeface);
SkASSERT(desc);
SkASSERT(ctx);
fPrev = fNext = NULL;
- fDesc = desc->copy();
fScalerContext->getFontMetrics(&fFontMetrics);
- // Create the sentinel SkGlyph.
- SkGlyph* sentinel = fGlyphArray.insert(0);
- sentinel->initGlyphFromCombinedID(SkGlyph::kImpossibleID);
-
- // Initialize all index to zero which points to the sentinel SkGlyph.
- memset(fGlyphHash, 0x00, sizeof(fGlyphHash));
-
fMemoryUsed = sizeof(*this);
- fGlyphArray.setReserve(kMinGlyphCount);
-
fAuxProcList = NULL;
-
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- fHashHitCount = fHashMissCount = 0;
-#endif
}
SkGlyphCache::~SkGlyphCache() {
-#if 0
- {
- size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*);
- size_t glyphAlloc = fGlyphAlloc.totalCapacity();
- size_t glyphHashUsed = 0;
- size_t uniHashUsed = 0;
- for (int i = 0; i < kHashCount; ++i) {
- glyphHashUsed += fGlyphHash[i] ? sizeof(fGlyphHash[0]) : 0;
- uniHashUsed += fCharToGlyphHash[i].fID != 0xFFFFFFFF ? sizeof(fCharToGlyphHash[0]) : 0;
+ fGlyphMap.foreach(
+ [](SkGlyph* g) {
+ SkDELETE(g->fPath);
}
- size_t glyphUsed = fGlyphArray.count() * sizeof(SkGlyph);
- size_t imageUsed = 0;
- for (int i = 0; i < fGlyphArray.count(); ++i) {
- const SkGlyph& g = *fGlyphArray[i];
- if (g.fImage) {
- imageUsed += g.fHeight * g.rowBytes();
- }
- }
-
- SkDebugf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n",
- ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(CharGlyphRec) * kHashCount, uniHashUsed);
-
- }
-#endif
- SkGlyph* gptr = fGlyphArray.begin();
- SkGlyph* stop = fGlyphArray.end();
- while (gptr < stop) {
- SkPath* path = gptr->fPath;
- if (path) {
- SkDELETE(path);
- }
- gptr += 1;
- }
+ );
SkDescriptor::Free(fDesc);
SkDELETE(fScalerContext);
this->invokeAndRemoveAuxProcs();
}
-SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
- if (NULL == fCharToGlyphHash.get()) {
+SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(PackedUnicharID packedUnicharID) {
+ if (NULL == fPackedUnicharIDToPackedGlyphID.get()) {
// Allocate the array.
- fCharToGlyphHash.reset(kHashCount);
- // Initialize entries of fCharToGlyphHash to index the sentinel glyph and
- // an fID value that will not match any id.
+ fPackedUnicharIDToPackedGlyphID.reset(kHashCount);
+ // Initialize array to map character and position with the impossible glyph ID. This
+ // represents no mapping.
for (int i = 0; i <kHashCount; ++i) {
- fCharToGlyphHash[i].fID = SkGlyph::kImpossibleID;
- fCharToGlyphHash[i].fGlyphIndex = 0;
+ fPackedUnicharIDToPackedGlyphID[i].fPackedUnicharID = SkGlyph::kImpossibleID;
+ fPackedUnicharIDToPackedGlyphID[i].fPackedGlyphID = 0;
}
}
- return &fCharToGlyphHash[ID2HashIndex(id)];
-}
-
-void SkGlyphCache::adjustCaches(int insertion_index) {
- for (int i = 0; i < kHashCount; ++i) {
- if (fGlyphHash[i] >= SkToU16(insertion_index)) {
- fGlyphHash[i] += 1;
- }
- }
- if (fCharToGlyphHash.get() != NULL) {
- for (int i = 0; i < kHashCount; ++i) {
- if (fCharToGlyphHash[i].fGlyphIndex >= SkToU16(insertion_index)) {
- fCharToGlyphHash[i].fGlyphIndex += 1;
- }
- }
- }
+ return &fPackedUnicharIDToPackedGlyphID[SkChecksum::CheapMix(packedUnicharID) & kHashMask];
}
///////////////////////////////////////////////////////////////////////////////
@@ -159,11 +90,11 @@
uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
VALIDATE();
- uint32_t id = SkGlyph::MakeID(charCode);
- const CharGlyphRec& rec = *this->getCharGlyphRec(id);
+ PackedUnicharID packedUnicharID = SkGlyph::MakeID(charCode);
+ const CharGlyphRec& rec = *this->getCharGlyphRec(packedUnicharID);
- if (rec.fID == id) {
- return fGlyphArray[rec.fGlyphIndex].getGlyphID();
+ if (rec.fPackedUnicharID == packedUnicharID) {
+ return SkGlyph::ID2Code(rec.fPackedGlyphID);
} else {
return fScalerContext->charToGlyphID(charCode);
}
@@ -186,8 +117,8 @@
const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
VALIDATE();
- uint32_t id = SkGlyph::MakeID(glyphID);
- return *this->lookupByCombinedID(id, kJustAdvance_MetricsType);
+ PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID);
+ return *this->lookupByPackedGlyphID(packedGlyphID, kJustAdvance_MetricsType);
}
///////////////////////////////////////////////////////////////////////////////
@@ -197,58 +128,44 @@
return *this->lookupByChar(charCode, kFull_MetricsType);
}
-const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
- SkFixed x, SkFixed y) {
+const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) {
VALIDATE();
return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
}
const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
VALIDATE();
- uint32_t id = SkGlyph::MakeID(glyphID);
- return *this->lookupByCombinedID(id, kFull_MetricsType);
+ PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID);
+ return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
}
const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
VALIDATE();
- uint32_t id = SkGlyph::MakeID(glyphID, x, y);
- return *this->lookupByCombinedID(id, kFull_MetricsType);
+ PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID, x, y);
+ return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
}
SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
- uint32_t id = SkGlyph::MakeID(charCode, x, y);
+ PackedUnicharID id = SkGlyph::MakeID(charCode, x, y);
CharGlyphRec* rec = this->getCharGlyphRec(id);
- SkGlyph* glyph;
- if (rec->fID != id) {
- RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID);
+ if (rec->fPackedUnicharID != id) {
// this ID is based on the UniChar
- rec->fID = id;
+ rec->fPackedUnicharID = id;
// this ID is based on the glyph index
- id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
- rec->fGlyphIndex = this->lookupMetrics(id, type);
- glyph = &fGlyphArray[rec->fGlyphIndex];
+ PackedGlyphID combinedID = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
+ rec->fPackedGlyphID = combinedID;
+ return this->lookupByPackedGlyphID(combinedID, type);
} else {
- RecordHashSuccess();
- glyph = &fGlyphArray[rec->fGlyphIndex];
- if (type == kFull_MetricsType && glyph->isJustAdvance()) {
- fScalerContext->getMetrics(glyph);
- }
+ return this->lookupByPackedGlyphID(rec->fPackedGlyphID, type);
}
- return glyph;
}
-SkGlyph* SkGlyphCache::lookupByCombinedID(uint32_t id, MetricsType type) {
- uint32_t hash_index = ID2HashIndex(id);
- uint16_t glyph_index = fGlyphHash[hash_index];
- SkGlyph* glyph = &fGlyphArray[glyph_index];
+SkGlyph* SkGlyphCache::lookupByPackedGlyphID(PackedGlyphID packedGlyphID, MetricsType type) {
+ SkGlyph* glyph = fGlyphMap.find(packedGlyphID);
- if (glyph->fID != id) {
- RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID);
- glyph_index = this->lookupMetrics(id, type);
- fGlyphHash[hash_index] = glyph_index;
- glyph = &fGlyphArray[glyph_index];
+ if (NULL == glyph) {
+ glyph = this->allocateNewGlyph(packedGlyphID, type);
} else {
- RecordHashSuccess();
if (type == kFull_MetricsType && glyph->isJustAdvance()) {
fScalerContext->getMetrics(glyph);
}
@@ -256,55 +173,25 @@
return glyph;
}
-uint16_t SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
- SkASSERT(id != SkGlyph::kImpossibleID);
- // Count is always greater than 0 because of the sentinel.
- // The fGlyphArray cache is in descending order, so that the sentinel with a value of ~0 is
- // always at index 0.
- SkGlyph* gptr = fGlyphArray.begin();
- int lo = 0;
- int hi = fGlyphArray.count() - 1;
- while (lo < hi) {
- int mid = (hi + lo) >> 1;
- if (gptr[mid].fID > id) {
- lo = mid + 1;
- } else {
- hi = mid;
- }
- }
-
- uint16_t glyph_index = hi;
- SkGlyph* glyph = &gptr[glyph_index];
- if (glyph->fID == id) {
- if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
- fScalerContext->getMetrics(glyph);
- }
- SkASSERT(glyph->fID != SkGlyph::kImpossibleID);
- return glyph_index;
- }
-
- // check if we need to bump hi before falling though to the allocator
- if (glyph->fID > id) {
- glyph_index += 1;
- }
-
- // Not found, but hi contains the index of the insertion point of the new glyph.
+SkGlyph* SkGlyphCache::allocateNewGlyph(PackedGlyphID packedGlyphID, MetricsType mtype) {
fMemoryUsed += sizeof(SkGlyph);
- this->adjustCaches(glyph_index);
-
- glyph = fGlyphArray.insert(glyph_index);
- glyph->initGlyphFromCombinedID(id);
-
- if (kJustAdvance_MetricsType == mtype) {
- fScalerContext->getAdvance(glyph);
- } else {
- SkASSERT(kFull_MetricsType == mtype);
- fScalerContext->getMetrics(glyph);
+ SkGlyph* glyphPtr;
+ {
+ SkGlyph glyph;
+ glyph.initGlyphFromCombinedID(packedGlyphID);
+ glyphPtr = fGlyphMap.set(glyph);
}
- SkASSERT(glyph->fID != SkGlyph::kImpossibleID);
- return glyph_index;
+ if (kJustAdvance_MetricsType == mtype) {
+ fScalerContext->getAdvance(glyphPtr);
+ } else {
+ SkASSERT(kFull_MetricsType == mtype);
+ fScalerContext->getMetrics(glyphPtr);
+ }
+
+ SkASSERT(glyphPtr->fID != SkGlyph::kImpossibleID);
+ return glyphPtr;
}
const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
@@ -354,11 +241,7 @@
matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
- fGlyphArray.count());
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- const int sum = SkTMax(fHashHitCount + fHashMissCount, 1); // avoid divide-by-zero
- msg.appendf(" hash:%2d\n", 100 * fHashHitCount / sum);
-#endif
+ fGlyphMap.count());
SkDebugf("%s\n", msg.c_str());
}
@@ -529,21 +412,9 @@
SkDebugf("SkGlyphCache strikes:%d memory:%d\n",
globals.getCacheCountUsed(), (int)globals.getTotalMemoryUsed());
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- int hitCount = 0;
- int missCount = 0;
-#endif
-
for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- hitCount += cache->fHashHitCount;
- missCount += cache->fHashMissCount;
-#endif
cache->dump();
}
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- SkDebugf("Hash hit percent:%2d\n", 100 * hitCount / (hitCount + missCount));
-#endif
}
///////////////////////////////////////////////////////////////////////////////
diff --git a/src/core/SkGlyphCache.h b/src/core/SkGlyphCache.h
index f3a946c..1c985bf 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -8,10 +8,10 @@
#define SkGlyphCache_DEFINED
#include "SkBitmap.h"
-#include "SkChecksum.h"
#include "SkChunkAlloc.h"
#include "SkDescriptor.h"
#include "SkGlyph.h"
+#include "SkTHash.h"
#include "SkScalerContext.h"
#include "SkTemplates.h"
#include "SkTDArray.h"
@@ -20,10 +20,6 @@
class SkGlyphCache_Globals;
-// Enable this locally to add stats for hash-table hit rates. It also extends the dump() output
-// to show those stats.
-//#define SK_GLYPHCACHE_TRACK_HASH_STATS
-
/** \class SkGlyphCache
This class represents a strike: a specific combination of typeface, size, matrix, etc., and
@@ -181,9 +177,12 @@
kHashMask = kHashCount - 1
};
+ typedef uint32_t PackedGlyphID; // glyph-index + subpixel-pos
+ typedef uint32_t PackedUnicharID; // unichar + subpixel-pos
+
struct CharGlyphRec {
- uint32_t fID; // unichar + subpixel
- uint16_t fGlyphIndex;
+ PackedUnicharID fPackedUnicharID;
+ PackedGlyphID fPackedGlyphID;
};
struct AuxProcRec {
@@ -199,56 +198,42 @@
// Return the SkGlyph* associated with MakeID. The id parameter is the
// combined glyph/x/y id generated by MakeID. If it is just a glyph id
// then x and y are assumed to be zero.
- SkGlyph* lookupByCombinedID(uint32_t id, MetricsType type);
+ SkGlyph* lookupByPackedGlyphID(PackedGlyphID packedGlyphID, MetricsType type);
// Return a SkGlyph* associated with unicode id and position x and y.
SkGlyph* lookupByChar(SkUnichar id, MetricsType type, SkFixed x = 0, SkFixed y = 0);
- // Return the index of id in the fGlyphArray. If it does not exist,
- // create a new one using MetricsType.
- uint16_t lookupMetrics(uint32_t id, MetricsType type);
+ // Return a new SkGlyph for the glyph ID and subpixel position id. Limit the amount
+ // of work
+ // using type.
+ SkGlyph* allocateNewGlyph(PackedGlyphID packedGlyphID, MetricsType type);
+
static bool DetachProc(const SkGlyphCache*, void*) { return true; }
// The id arg is a combined id generated by MakeID.
- CharGlyphRec* getCharGlyphRec(uint32_t id);
- void adjustCaches(int insertion_index);
-
- static inline unsigned ID2HashIndex(uint32_t h) {
- return SkChecksum::CheapMix(h) & kHashMask;
- }
+ CharGlyphRec* getCharGlyphRec(PackedUnicharID id);
void invokeAndRemoveAuxProcs();
inline static SkGlyphCache* FindTail(SkGlyphCache* head);
- SkGlyphCache* fNext, *fPrev;
- SkDescriptor* fDesc;
- SkScalerContext* fScalerContext;
- SkPaint::FontMetrics fFontMetrics;
+ SkGlyphCache* fNext;
+ SkGlyphCache* fPrev;
+ SkDescriptor* const fDesc;
+ SkScalerContext* const fScalerContext;
+ SkPaint::FontMetrics fFontMetrics;
- // A quick lookup to avoid the binary search looking for glyphs in fGlyphArray.
- uint16_t fGlyphHash[kHashCount];
+ // Map from a combined GlyphID and sub-pixel position to a SkGlyph.
+ SkTHashTable<SkGlyph, PackedGlyphID, SkGlyph::HashTraits> fGlyphMap;
- // Contains the SkGlyphs that are used by fGlyphHash and fCharToGlyphHash. The ~0 element is
- // reserved for a sentinel SkGlyph that reduces the logic to check for collisions in the hash
- // arrays. The ~0 element has an fID of SkGlyph::kImpossibleID which never matches any
- // combined id generated for a char or a glyph.
- SkTDArray<SkGlyph> fGlyphArray;
- SkChunkAlloc fGlyphAlloc;
+ SkChunkAlloc fGlyphAlloc;
- // no reason to use the same kHashCount as fGlyphHash, but we do for now
- // Dynamically allocated when chars are encountered.
- SkAutoTArray<CharGlyphRec> fCharToGlyphHash;
+ SkAutoTArray<CharGlyphRec> fPackedUnicharIDToPackedGlyphID;
// used to track (approx) how much ram is tied-up in this cache
- size_t fMemoryUsed;
+ size_t fMemoryUsed;
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
- int fHashHitCount;
- int fHashMissCount;
-#endif
-
- AuxProcRec* fAuxProcList;
+ AuxProcRec* fAuxProcList;
};
class SkAutoGlyphCacheBase {
