1 // Copyright 2019 Google LLC.
2 #include "modules/skparagraph/include/ParagraphCache.h"
3 #include "modules/skparagraph/src/ParagraphImpl.h"
4
5 namespace skia {
6 namespace textlayout {
7
8 class ParagraphCacheKey {
9 public:
ParagraphCacheKey(const ParagraphImpl * paragraph)10 ParagraphCacheKey(const ParagraphImpl* paragraph)
11 : fText(paragraph->fText.c_str(), paragraph->fText.size())
12 , fFontSwitches(paragraph->switches())
13 , fTextStyles(paragraph->fTextStyles)
14 , fParagraphStyle(paragraph->paragraphStyle()) { }
15
16 SkString fText;
17 SkTArray<FontDescr> fFontSwitches;
18 SkTArray<Block, true> fTextStyles;
19 ParagraphStyle fParagraphStyle;
20 };
21
22 class ParagraphCacheValue {
23 public:
ParagraphCacheValue(const ParagraphImpl * paragraph)24 ParagraphCacheValue(const ParagraphImpl* paragraph)
25 : fKey(ParagraphCacheKey(paragraph))
26 , fInternalState(paragraph->state())
27 , fRuns(paragraph->fRuns)
28 , fClusters(paragraph->fClusters) { }
29
30 // Input == key
31 ParagraphCacheKey fKey;
32
33 // Shaped results:
34 InternalState fInternalState;
35 SkTArray<Run> fRuns;
36 SkTArray<Cluster, true> fClusters;
37 SkTArray<RunShifts, true> fRunShifts;
38 };
39
40
mix(uint32_t hash,uint32_t data) const41 uint32_t ParagraphCache::KeyHash::mix(uint32_t hash, uint32_t data) const {
42 hash += data;
43 hash += (hash << 10);
44 hash ^= (hash >> 6);
45 return hash;
46 }
operator ()(const ParagraphCacheKey & key) const47 uint32_t ParagraphCache::KeyHash::operator()(const ParagraphCacheKey& key) const {
48 uint32_t hash = 0;
49 for (auto& fd : key.fFontSwitches) {
50 hash = mix(hash, SkGoodHash()(fd.fStart));
51 hash = mix(hash, SkGoodHash()(fd.fFont.getSize()));
52
53 if (fd.fFont.getTypeface() != nullptr) {
54 SkString name;
55 fd.fFont.getTypeface()->getFamilyName(&name);
56 hash = mix(hash, SkGoodHash()(name));
57 hash = mix(hash, SkGoodHash()(fd.fFont.getTypeface()->fontStyle()));
58 }
59 }
60 for (auto& ts : key.fTextStyles) {
61 hash = mix(hash, SkGoodHash()(ts.fStyle.getLetterSpacing()));
62 hash = mix(hash, SkGoodHash()(ts.fStyle.getWordSpacing()));
63 hash = mix(hash, SkGoodHash()(ts.fRange));
64 }
65 hash = mix(hash, SkGoodHash()(key.fText));
66 return hash;
67 }
68
operator ==(const ParagraphCacheKey & a,const ParagraphCacheKey & b)69 bool operator==(const ParagraphCacheKey& a, const ParagraphCacheKey& b) {
70 if (a.fText.size() != b.fText.size()) {
71 return false;
72 }
73 if (a.fFontSwitches.count() != b.fFontSwitches.count()) {
74 return false;
75 }
76 if (a.fText != b.fText) {
77 return false;
78 }
79 if (a.fTextStyles.size() != b.fTextStyles.size()) {
80 return false;
81 }
82
83 if (a.fParagraphStyle.getMaxLines() != b.fParagraphStyle.getMaxLines()) {
84 // This is too strong, but at least we will not lose lines
85 return false;
86 }
87
88 for (size_t i = 0; i < a.fFontSwitches.size(); ++i) {
89 auto& fda = a.fFontSwitches[i];
90 auto& fdb = b.fFontSwitches[i];
91 if (fda.fStart != fdb.fStart) {
92 return false;
93 }
94 if (fda.fFont != fdb.fFont) {
95 return false;
96 }
97 }
98
99 for (size_t i = 0; i < a.fTextStyles.size(); ++i) {
100 auto& tsa = a.fTextStyles[i];
101 auto& tsb = b.fTextStyles[i];
102 if (tsa.fStyle.getLetterSpacing() != tsb.fStyle.getLetterSpacing()) {
103 return false;
104 }
105 if (tsa.fStyle.getWordSpacing() != tsb.fStyle.getWordSpacing()) {
106 return false;
107 }
108 if (tsa.fRange.width() != tsb.fRange.width()) {
109 return false;
110 }
111 if (tsa.fRange.start != tsb.fRange.start) {
112 return false;
113 }
114 }
115
116 return true;
117 }
118
119 struct ParagraphCache::Entry {
120
Entryskia::textlayout::ParagraphCache::Entry121 Entry(ParagraphCacheValue* value) : fValue(value) {}
122 ParagraphCacheValue* fValue;
123 };
124
ParagraphCache()125 ParagraphCache::ParagraphCache()
126 : fChecker([](ParagraphImpl* impl, const char*, bool){ })
127 , fLRUCacheMap(kMaxEntries)
128 , fCacheIsOn(true)
129 #ifdef PARAGRAPH_CACHE_STATS
130 , fTotalRequests(0)
131 , fCacheMisses(0)
132 , fHashMisses(0)
133 #endif
134 { }
135
~ParagraphCache()136 ParagraphCache::~ParagraphCache() { }
137
updateFrom(const ParagraphImpl * paragraph,Entry * entry)138 void ParagraphCache::updateFrom(const ParagraphImpl* paragraph, Entry* entry) {
139
140 entry->fValue->fInternalState = paragraph->state();
141 entry->fValue->fRunShifts = paragraph->fRunShifts;
142 for (size_t i = 0; i < paragraph->fRuns.size(); ++i) {
143 auto& run = paragraph->fRuns[i];
144 if (run.fSpaced) {
145 entry->fValue->fRuns[i] = run;
146 }
147 }
148 }
149
updateTo(ParagraphImpl * paragraph,const Entry * entry)150 void ParagraphCache::updateTo(ParagraphImpl* paragraph, const Entry* entry) {
151 paragraph->fRuns.reset();
152 paragraph->fRuns = entry->fValue->fRuns;
153 for (auto& run : paragraph->fRuns) {
154 run.setMaster(paragraph);
155 }
156
157 paragraph->fClusters.reset();
158 paragraph->fClusters = entry->fValue->fClusters;
159 for (auto& cluster : paragraph->fClusters) {
160 cluster.setMaster(paragraph);
161 }
162
163 paragraph->fRunShifts.reset();
164 for (auto& runShift : entry->fValue->fRunShifts) {
165 paragraph->fRunShifts.push_back(runShift);
166 }
167
168 paragraph->fState = entry->fValue->fInternalState;
169 }
170
printStatistics()171 void ParagraphCache::printStatistics() {
172 SkDebugf("--- Paragraph Cache ---\n");
173 SkDebugf("Total requests: %d\n", fTotalRequests);
174 SkDebugf("Cache misses: %d\n", fCacheMisses);
175 SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ? 100.f * fCacheMisses / fTotalRequests : 0.f);
176 int cacheHits = fTotalRequests - fCacheMisses;
177 SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
178 SkDebugf("---------------------\n");
179 }
180
abandon()181 void ParagraphCache::abandon() {
182 SkAutoMutexExclusive lock(fParagraphMutex);
183 fLRUCacheMap.foreach([](std::unique_ptr<Entry>* e) {
184 });
185
186 this->reset();
187 }
188
reset()189 void ParagraphCache::reset() {
190 SkAutoMutexExclusive lock(fParagraphMutex);
191 #ifdef PARAGRAPH_CACHE_STATS
192 fTotalRequests = 0;
193 fCacheMisses = 0;
194 fHashMisses = 0;
195 #endif
196 fLRUCacheMap.reset();
197 }
198
findParagraph(ParagraphImpl * paragraph)199 bool ParagraphCache::findParagraph(ParagraphImpl* paragraph) {
200 if (!fCacheIsOn) {
201 return false;
202 }
203 #ifdef PARAGRAPH_CACHE_STATS
204 ++fTotalRequests;
205 #endif
206 SkAutoMutexExclusive lock(fParagraphMutex);
207 ParagraphCacheKey key(paragraph);
208 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
209 if (!entry) {
210 // We have a cache miss
211 #ifdef PARAGRAPH_CACHE_STATS
212 ++fCacheMisses;
213 #endif
214 fChecker(paragraph, "missingParagraph", true);
215 return false;
216 }
217 updateTo(paragraph, entry->get());
218 fChecker(paragraph, "foundParagraph", true);
219 return true;
220 }
221
updateParagraph(ParagraphImpl * paragraph)222 bool ParagraphCache::updateParagraph(ParagraphImpl* paragraph) {
223 if (!fCacheIsOn) {
224 return false;
225 }
226 #ifdef PARAGRAPH_CACHE_STATS
227 ++fTotalRequests;
228 #endif
229 SkAutoMutexExclusive lock(fParagraphMutex);
230 ParagraphCacheKey key(paragraph);
231 std::unique_ptr<Entry>* entry = fLRUCacheMap.find(key);
232 if (!entry) {
233 ParagraphCacheValue* value = new ParagraphCacheValue(paragraph);
234 fLRUCacheMap.insert(key, std::unique_ptr<Entry>(new Entry(value)));
235 fChecker(paragraph, "addedParagraph", true);
236 return true;
237 } else {
238 updateFrom(paragraph, entry->get());
239 fChecker(paragraph, "updatedParagraph", true);
240 return false;
241 }
242 }
243 }
244 }
245