Paragraph cache: caching the shaped results only.
That makes layout phase 10 times faster (since the shaping takes 90% of it).
LRU cache is attached to the FontCollection object and has the same life time.
Currently it has hardcoded limit on the entry numbers (128).
One the number reached, the least recently used element is removed from the cache
to free the space for a new one.
Change-Id: I597e334422614e33715d7a9ed13acf7b1f9cd0e4
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/230755
Commit-Queue: Julia Lavrova <jlavrova@google.com>
Reviewed-by: Derek Sollenberger <djsollen@google.com>
Reviewed-by: Julia Lavrova <jlavrova@google.com>
diff --git a/modules/skparagraph/src/ParagraphCache.cpp b/modules/skparagraph/src/ParagraphCache.cpp
index bd216b2..465b9bc 100644
--- a/modules/skparagraph/src/ParagraphCache.cpp
+++ b/modules/skparagraph/src/ParagraphCache.cpp
@@ -1,104 +1,69 @@
// Copyright 2019 Google LLC.
-#include "modules/skparagraph/src/ParagraphCache.h"
+#include "modules/skparagraph/include/ParagraphCache.h"
#include "modules/skparagraph/src/ParagraphImpl.h"
namespace skia {
namespace textlayout {
-// Just the flutter input for now
-// TODO: We don't really need to copy anything...
-ParagraphCacheKey::ParagraphCacheKey(ParagraphImpl* paragraph)
- : fText(paragraph->fText)
+class ParagraphCacheKey {
+public:
+ ParagraphCacheKey(const ParagraphImpl* paragraph)
+ : fText(paragraph->fText.c_str(), paragraph->fText.size())
, fFontSwitches(paragraph->switches())
, fTextStyles(paragraph->fTextStyles)
, fParagraphStyle(paragraph->paragraphStyle()) { }
-// TODO: copying clusters and runs for now (there are minor things changed on formatting)
-ParagraphCacheValue::ParagraphCacheValue(ParagraphImpl* paragraph)
+ SkString fText;
+ SkTArray<FontDescr> fFontSwitches;
+ SkTArray<Block, true> fTextStyles;
+ ParagraphStyle fParagraphStyle;
+};
+
+class ParagraphCacheValue {
+public:
+ ParagraphCacheValue(const ParagraphImpl* paragraph)
: fKey(ParagraphCacheKey(paragraph))
, fInternalState(paragraph->state())
, fRuns(paragraph->fRuns)
- , fClusters(paragraph->fClusters)
- , fMeasurement(paragraph->measurement())
- , fPicture(paragraph->fPicture) { }
+ , fClusters(paragraph->fClusters) { }
-bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
+ // Input == key
+ ParagraphCacheKey fKey;
- SkAutoMutexExclusive lock(fParagraphMutex);
- if (this->count() == 0) {
- return false;
- }
+ // Shaped results:
+ InternalState fInternalState;
+ SkTArray<Run> fRuns;
+ SkTArray<Cluster, true> fClusters;
+ SkTArray<RunShifts, true> fRunShifts;
+};
- ParagraphCacheKey key(paragraph);
- auto found = this->find(key);
- if (found == nullptr) {
- fChecker(paragraph, "findParagraph", false);
- return false;
- }
- paragraph->fRuns.reset();
- paragraph->fRuns = found->fRuns;
- for (auto& run : paragraph->fRuns) {
- run.setMaster(paragraph);
- }
- paragraph->fClusters.reset();
- paragraph->fClusters = found->fClusters;
- for (auto& cluster : paragraph->fClusters) {
- cluster.setMaster(paragraph);
- }
-
- paragraph->fLines.reset();
- for (auto& line : found->fLines) {
- paragraph->fLines.push_back(line);
- paragraph->fLines.back().setMaster(paragraph);
- }
-
- paragraph->fState = found->fInternalState;
- paragraph->setMeasurement(found->fMeasurement);
-
- paragraph->fOldWidth = found->fMeasurement.fWidth;
- paragraph->fOldHeight = found->fMeasurement.fHeight;
-
- paragraph->fPicture = found->fPicture;
-
- fChecker(paragraph, "findParagraph", true);
- return true;
+uint32_t ParagraphCache::KeyHash::mix(uint32_t hash, uint32_t data) const {
+ hash += data;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ return hash;
}
+uint32_t ParagraphCache::KeyHash::operator()(const ParagraphCacheKey& key) const {
+ uint32_t hash = 0;
+ for (auto& fd : key.fFontSwitches) {
+ hash = mix(hash, SkGoodHash()(fd.fStart));
+ hash = mix(hash, SkGoodHash()(fd.fFont.getSize()));
-void ParagraphCache::addParagraph(ParagraphImpl* paragraph) {
-
- SkAutoMutexExclusive lock(fParagraphMutex);
- auto value = new ParagraphCacheValue(paragraph);
- this->add(value);
- fChecker(paragraph, "addParagraph1", true);
-}
-
-void ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
-
- SkAutoMutexExclusive lock(fParagraphMutex);
- ParagraphCacheKey key(paragraph);
- auto found = this->find(key);
- if (found != nullptr) {
- found->fInternalState = paragraph->fState;
- found->fMeasurement = paragraph->measurement();
- found->fLines = paragraph->fLines;
- for (size_t i = 0; i < paragraph->fRuns.size(); ++i) {
- auto& run = paragraph->fRuns[i];
- if (run.fSpaced) {
- found->fRuns[i] = run;
- }
+ if (fd.fFont.getTypeface() != nullptr) {
+ SkString name;
+ fd.fFont.getTypeface()->getFamilyName(&name);
+ hash = mix(hash, SkGoodHash()(name));
+ hash = mix(hash, SkGoodHash()(fd.fFont.getTypeface()->fontStyle()));
}
- found->fPicture = paragraph->fPicture;
- fChecker(paragraph, "updateParagraph", true);
- } else {
- auto value = new ParagraphCacheValue(paragraph);
- this->add(value);
- fChecker(paragraph, "addParagraph2", true);
}
-}
-
-const ParagraphCacheKey& LookupTrait::GetKey(const ParagraphCacheValue& paragraph) {
- return paragraph.fKey;
+ for (auto& ts : key.fTextStyles) {
+ hash = mix(hash, SkGoodHash()(ts.fStyle.getLetterSpacing()));
+ hash = mix(hash, SkGoodHash()(ts.fStyle.getWordSpacing()));
+ hash = mix(hash, SkGoodHash()(ts.fRange));
+ }
+ hash = mix(hash, SkGoodHash()(key.fText));
+ return hash;
}
bool operator==(const ParagraphCacheKey& a, const ParagraphCacheKey& b) {
@@ -116,7 +81,7 @@
}
if (a.fParagraphStyle.getMaxLines() != b.fParagraphStyle.getMaxLines()) {
- // TODO: this is too strong, but at least we will not lose lines
+ // This is too strong, but at least we will not lose lines
return false;
}
@@ -151,55 +116,129 @@
return true;
}
-uint32_t LookupTrait::mix(uint32_t hash, uint32_t data) {
- hash += data;
- hash += (hash << 10);
- hash ^= (hash >> 6);
- return hash;
-}
+struct ParagraphCache::Entry {
-uint32_t LookupTrait::Hash(const ParagraphCacheKey& key) {
- uint32_t hash = 0;
- for (auto& fd : key.fFontSwitches) {
- hash = mix(hash, SkGoodHash()(fd.fStart));
- hash = mix(hash, SkGoodHash()(fd.fFont.getSize()));
+ Entry(ParagraphCacheValue* value) : fValue(value) {}
+ ParagraphCacheValue* fValue;
+};
- if (fd.fFont.getTypeface() != nullptr) {
- SkString name;
- fd.fFont.getTypeface()->getFamilyName(&name);
- hash = mix(hash, SkGoodHash()(name));
- hash = mix(hash, SkGoodHash()(fd.fFont.getTypeface()->fontStyle()));
+ParagraphCache::ParagraphCache()
+ : fChecker([](ParagraphImpl* impl, const char*, bool){ })
+ , fLRUCacheMap(kMaxEntries)
+ , fCacheIsOn(true)
+#ifdef PARAGRAPH_CACHE_STATS
+ , fTotalRequests(0)
+ , fCacheMisses(0)
+ , fHashMisses(0)
+#endif
+{ }
+
+ParagraphCache::~ParagraphCache() { }
+
+void ParagraphCache::updateFrom(const ParagraphImpl* paragraph, Entry* entry) {
+
+ entry->fValue->fInternalState = paragraph->state();
+ entry->fValue->fRunShifts = paragraph->fRunShifts;
+ for (size_t i = 0; i < paragraph->fRuns.size(); ++i) {
+ auto& run = paragraph->fRuns[i];
+ if (run.fSpaced) {
+ entry->fValue->fRuns[i] = run;
}
}
- for (auto& ts : key.fTextStyles) {
- hash = mix(hash, SkGoodHash()(ts.fStyle.getLetterSpacing()));
- hash = mix(hash, SkGoodHash()(ts.fStyle.getWordSpacing()));
- }
- hash = mix(hash, SkGoodHash()(key.fText));
- return hash;
}
-void ParagraphCache::printCache(const char* title) {
+void ParagraphCache::updateTo(ParagraphImpl* paragraph, const Entry* entry) {
+ paragraph->fRuns.reset();
+ paragraph->fRuns = entry->fValue->fRuns;
+ for (auto& run : paragraph->fRuns) {
+ run.setMaster(paragraph);
+ }
- SkDebugf("\n\n%s\n", title);
- SkTDynamicHash<ParagraphCacheValue, ParagraphCacheKey, LookupTrait>::Iter iter(this);
- while (!iter.done()) {
- ParagraphCacheValue* v = &*iter;
- const ParagraphCacheKey& k = LookupTrait::GetKey(*v);
- SkDebugf("key: '%s' runs(%d) clusters(%d)\n", k.fText.c_str(), v->fRuns.size(), v->fClusters.size());
- ++iter;
+ paragraph->fClusters.reset();
+ paragraph->fClusters = entry->fValue->fClusters;
+ for (auto& cluster : paragraph->fClusters) {
+ cluster.setMaster(paragraph);
+ }
+
+ paragraph->fRunShifts.reset();
+ for (auto& runShift : entry->fValue->fRunShifts) {
+ paragraph->fRunShifts.push_back(runShift);
+ }
+
+ paragraph->fState = entry->fValue->fInternalState;
+}
+
+void ParagraphCache::printStatistics() {
+ SkDebugf("--- Paragraph Cache ---\n");
+ SkDebugf("Total requests: %d\n", fTotalRequests);
+ SkDebugf("Cache misses: %d\n", fCacheMisses);
+ SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ? 100.f * fCacheMisses / fTotalRequests : 0.f);
+ int cacheHits = fTotalRequests - fCacheMisses;
+ SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
+ SkDebugf("---------------------\n");
+}
+
+void ParagraphCache::abandon() {
+ SkAutoMutexExclusive lock(fParagraphMutex);
+ fLRUCacheMap.foreach([](std::unique_ptr<Entry>* e) {
+ });
+
+ this->reset();
+}
+
+void ParagraphCache::reset() {
+ SkAutoMutexExclusive lock(fParagraphMutex);
+#ifdef PARAGRAPH_CACHE_STATS
+ fTotalRequests = 0;
+ fCacheMisses = 0;
+ fHashMisses = 0;
+#endif
+ fLRUCacheMap.reset();
+}
+
+bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
+ if (!fCacheIsOn) {
+ return false;
+ }
+#ifdef PARAGRAPH_CACHE_STATS
+ ++fTotalRequests;
+#endif
+ SkAutoMutexExclusive lock(fParagraphMutex);
+ ParagraphCacheKey key(paragraph);
+ std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
+ if (!entry) {
+ // We have a cache miss
+#ifdef PARAGRAPH_CACHE_STATS
+ ++fCacheMisses;
+#endif
+ fChecker(paragraph, "missingParagraph", true);
+ return false;
+ }
+ updateTo(paragraph, entry->get());
+ fChecker(paragraph, "foundParagraph", true);
+ return true;
+}
+
+bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
+ if (!fCacheIsOn) {
+ return false;
+ }
+#ifdef PARAGRAPH_CACHE_STATS
+ ++fTotalRequests;
+#endif
+ SkAutoMutexExclusive lock(fParagraphMutex);
+ ParagraphCacheKey key(paragraph);
+ std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
+ if (!entry) {
+ ParagraphCacheValue* value = new ParagraphCacheValue(paragraph);
+ fLRUCacheMap.insert(key, std::unique_ptr<Entry>(new Entry(value)));
+ fChecker(paragraph, "addedParagraph", true);
+ return true;
+ } else {
+ updateFrom(paragraph, entry->get());
+ fChecker(paragraph, "updatedParagraph", true);
+ return false;
}
}
-
-void ParagraphCache::printKeyValue(const char* title, ParagraphImpl* paragraph, bool found) {
- /*
- SkDebugf("%s '%s' ", title, paragraph->text().data());
- for (auto& fd : paragraph->switches()) {
- SkDebugf("%d ", fd.fFont.getTypeface() != nullptr ? fd.fFont.getTypeface()->uniqueID(): 0);
- };
- SkDebugf("\n");
- */
-}
-
}
}