Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(112)

Side by Side Diff: Source/platform/fonts/shaping/ShapeCache.h

Issue 1192223002: Optimize Complex Text Shaping and Caching (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Change CachingWordShaperTest as suggested Created 5 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/platform/fonts/shaping/HarfBuzzShaperTest.cpp ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2012 Apple Inc. All rights reserved. 2 * Copyright (C) 2012 Apple Inc. All rights reserved.
3 * Copyright (C) 2015 Google Inc. All rights reserved.
3 * 4 *
4 * Redistribution and use in source and binary forms, with or without 5 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions 6 * modification, are permitted provided that the following conditions
6 * are met: 7 * are met:
7 * 1. Redistributions of source code must retain the above copyright 8 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer. 9 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright 10 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the 11 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution. 12 * documentation and/or other materials provided with the distribution.
12 * 13 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */ 25 */
25 26
26 #ifndef WidthCache_h 27 #ifndef ShapeCache_h
27 #define WidthCache_h 28 #define ShapeCache_h
28 29
29 #include "platform/geometry/FloatRectOutsets.h" 30 #include "platform/fonts/shaping/HarfBuzzShaper.h"
30 #include "platform/text/TextRun.h" 31 #include "platform/text/TextRun.h"
31 #include "wtf/Forward.h" 32 #include "wtf/Forward.h"
32 #include "wtf/HashFunctions.h" 33 #include "wtf/HashFunctions.h"
33 #include "wtf/HashSet.h" 34 #include "wtf/HashSet.h"
34 #include "wtf/HashTableDeletedValueType.h" 35 #include "wtf/HashTableDeletedValueType.h"
35 #include "wtf/StringHasher.h" 36 #include "wtf/StringHasher.h"
36 37
37 namespace blink { 38 namespace blink {
38 39
39 struct WidthCacheEntry { 40 class Font;
40 WidthCacheEntry() 41 class GlyphBuffer;
42 class SimpleFontData;
43 class HarfBuzzShaper;
44
45 struct ShapeCacheEntry {
46 ShapeCacheEntry()
41 { 47 {
42 width = std::numeric_limits<float>::quiet_NaN(); 48 m_shapeResult = nullptr;
43 } 49 }
44 bool isValid() const { return !std::isnan(width); } 50 RefPtr<ShapeResult> m_shapeResult;
45 float width;
46 FloatRect glyphBounds;
47 }; 51 };
48 52
49 class WidthCache { 53 class ShapeCache {
50 private: 54 private:
51 // Used to optimize small strings as hash table keys. Avoids malloc'ing an o ut-of-line StringImpl. 55 // Used to optimize small strings as hash table keys. Avoids malloc'ing an o ut-of-line StringImpl.
52 class SmallStringKey { 56 class SmallStringKey {
53 public: 57 public:
54 static unsigned capacity() { return s_capacity; } 58 static unsigned capacity() { return s_capacity; }
55 59
56 SmallStringKey() 60 SmallStringKey()
57 : m_length(s_emptyValueLength) 61 : m_length(s_emptyValueLength), m_direction(LTR)
58 { 62 {
59 } 63 }
60 64
61 SmallStringKey(WTF::HashTableDeletedValueType) 65 SmallStringKey(WTF::HashTableDeletedValueType)
62 : m_length(s_deletedValueLength) 66 : m_length(s_deletedValueLength), m_direction(LTR)
63 { 67 {
64 } 68 }
65 69
66 template<typename CharacterType> SmallStringKey(CharacterType* character s, unsigned short length) 70 template<typename CharacterType> SmallStringKey(CharacterType* character s, unsigned short length, TextDirection direction)
67 : m_length(length) 71 : m_length(length), m_direction(direction)
68 { 72 {
69 ASSERT(length <= s_capacity); 73 ASSERT(length <= s_capacity);
70 74
71 StringHasher hasher; 75 StringHasher hasher;
72 76
73 bool remainder = length & 1; 77 bool remainder = length & 1;
74 length >>= 1; 78 length >>= 1;
75 79
76 unsigned i = 0; 80 unsigned i = 0;
77 while (length--) { 81 while (length--) {
78 m_characters[i] = characters[i]; 82 m_characters[i] = characters[i];
79 m_characters[i + 1] = characters[i + 1]; 83 m_characters[i + 1] = characters[i + 1];
80 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]); 84 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
81 i += 2; 85 i += 2;
82 } 86 }
83 87
84 if (remainder) { 88 if (remainder) {
85 m_characters[i] = characters[i]; 89 m_characters[i] = characters[i];
86 hasher.addCharacter(characters[i]); 90 hasher.addCharacter(characters[i]);
87 } 91 }
88 92
89 m_hash = hasher.hash(); 93 m_hash = hasher.hash();
90 } 94 }
91 95
92 const UChar* characters() const { return m_characters; } 96 const UChar* characters() const { return m_characters; }
93 unsigned short length() const { return m_length; } 97 unsigned short length() const { return m_length; }
98 TextDirection direction() const { return static_cast<TextDirection>(m_di rection); }
94 unsigned hash() const { return m_hash; } 99 unsigned hash() const { return m_hash; }
95 100
96 bool isHashTableDeletedValue() const { return m_length == s_deletedValue Length; } 101 bool isHashTableDeletedValue() const { return m_length == s_deletedValue Length; }
97 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLeng th; } 102 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLeng th; }
98 103
99 private: 104 private:
100 static const unsigned s_capacity = 15; 105 static const unsigned s_capacity = 15;
101 static const unsigned s_emptyValueLength = s_capacity + 1; 106 static const unsigned s_emptyValueLength = s_capacity + 1;
102 static const unsigned s_deletedValueLength = s_capacity + 2; 107 static const unsigned s_deletedValueLength = s_capacity + 2;
103 108
104 unsigned m_hash; 109 unsigned m_hash;
105 unsigned short m_length; 110 unsigned m_length : 15;
111 unsigned m_direction : 1;
106 UChar m_characters[s_capacity]; 112 UChar m_characters[s_capacity];
107 }; 113 };
108 114
109 struct SmallStringKeyHash { 115 struct SmallStringKeyHash {
110 static unsigned hash(const SmallStringKey& key) { return key.hash(); } 116 static unsigned hash(const SmallStringKey& key) { return key.hash(); }
111 static bool equal(const SmallStringKey& a, const SmallStringKey& b) { re turn a == b; } 117 static bool equal(const SmallStringKey& a, const SmallStringKey& b) { re turn a == b; }
112 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and del eted values have lengths that are not equal to any valid length. 118 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and del eted values have lengths that are not equal to any valid length.
113 }; 119 };
114 120
115 struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> { 121 struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
116 static const bool hasIsEmptyValueFunction = true; 122 static const bool hasIsEmptyValueFunction = true;
117 static bool isEmptyValue(const SmallStringKey& key) { return key.isHashT ableEmptyValue(); } 123 static bool isEmptyValue(const SmallStringKey& key) { return key.isHashT ableEmptyValue(); }
118 static const unsigned minimumTableSize = 16; 124 static const unsigned minimumTableSize = 16;
119 }; 125 };
120 126
121 friend bool operator==(const SmallStringKey&, const SmallStringKey&); 127 friend bool operator==(const SmallStringKey&, const SmallStringKey&);
122 128
123 public: 129 public:
124 WidthCache() 130 ShapeCache() { }
125 : m_interval(s_maxInterval)
126 , m_countdown(m_interval)
127 {
128 }
129 131
130 WidthCacheEntry* add(const TextRun& run, WidthCacheEntry entry) 132 ShapeCacheEntry* add(const TextRun& run, ShapeCacheEntry entry)
131 { 133 {
132 if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity()) 134 if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
133 return 0; 135 return 0;
134 136
135 if (m_countdown > 0) {
136 --m_countdown;
137 return 0;
138 }
139
140 return addSlowCase(run, entry); 137 return addSlowCase(run, entry);
141 } 138 }
142 139
143 void clear() 140 void clear()
144 { 141 {
145 m_singleCharMap.clear(); 142 m_singleCharMap.clear();
146 m_map.clear(); 143 m_shortStringMap.clear();
147 } 144 }
148 145
149 private: 146 private:
150 WidthCacheEntry* addSlowCase(const TextRun& run, WidthCacheEntry entry) 147 ShapeCacheEntry* addSlowCase(const TextRun& run, ShapeCacheEntry entry)
151 { 148 {
152 int length = run.length(); 149 int length = run.length();
153 bool isNewEntry; 150 bool isNewEntry;
154 WidthCacheEntry *value; 151 ShapeCacheEntry *value;
155 if (length == 1) { 152 if (length == 1) {
156 SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], ent ry); 153 uint32_t key = run[0];
154 // All current codepointsin UTF-32 are bewteen 0x0 and 0x10FFFF,
155 // as such use bit 32 to indicate direction.
156 if (run.direction() == RTL)
157 key |= (1u << 31);
158 SingleCharMap::AddResult addResult = m_singleCharMap.add(key, entry) ;
157 isNewEntry = addResult.isNewEntry; 159 isNewEntry = addResult.isNewEntry;
158 value = &addResult.storedValue->value; 160 value = &addResult.storedValue->value;
159 } else { 161 } else {
160 SmallStringKey smallStringKey; 162 SmallStringKey smallStringKey;
161 if (run.is8Bit()) 163 if (run.is8Bit())
162 smallStringKey = SmallStringKey(run.characters8(), length); 164 smallStringKey = SmallStringKey(run.characters8(), length, run.d irection());
163 else 165 else
164 smallStringKey = SmallStringKey(run.characters16(), length); 166 smallStringKey = SmallStringKey(run.characters16(), length, run. direction());
165 167
166 Map::AddResult addResult = m_map.add(smallStringKey, entry); 168 SmallStringMap::AddResult addResult = m_shortStringMap.add(smallStri ngKey, entry);
167 isNewEntry = addResult.isNewEntry; 169 isNewEntry = addResult.isNewEntry;
168 value = &addResult.storedValue->value; 170 value = &addResult.storedValue->value;
169 } 171 }
170 172
171 // Cache hit: ramp up by sampling the next few words. 173 // Cache hit: ramp up by sampling the next few words.
172 if (!isNewEntry) { 174 if (!isNewEntry) {
173 m_interval = s_minInterval;
174 return value; 175 return value;
175 } 176 }
176 177
177 // Cache miss: ramp down by increasing our sampling interval. 178 if (m_singleCharMap.size() + m_shortStringMap.size() < s_maxSize) {
178 if (m_interval < s_maxInterval)
179 ++m_interval;
180 m_countdown = m_interval;
181
182 if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
183 return value; 179 return value;
180 }
184 181
185 // No need to be fancy: we're just trying to avoid pathological growth. 182 // No need to be fancy: we're just trying to avoid pathological growth.
186 m_singleCharMap.clear(); 183 m_singleCharMap.clear();
187 m_map.clear(); 184 m_shortStringMap.clear();
185
188 return 0; 186 return 0;
189 } 187 }
190 188
191 typedef HashMap<SmallStringKey, WidthCacheEntry, SmallStringKeyHash, SmallSt ringKeyHashTraits> Map; 189 typedef HashMap<SmallStringKey, ShapeCacheEntry, SmallStringKeyHash, SmallSt ringKeyHashTraits> SmallStringMap;
192 typedef HashMap<uint32_t, WidthCacheEntry, DefaultHash<uint32_t>::Hash, WTF: :UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap; 190 typedef HashMap<uint32_t, ShapeCacheEntry, DefaultHash<uint32_t>::Hash, WTF: :UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap;
193 static const int s_minInterval = -3; // A cache hit pays for about 3 cache m isses.
194 static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
195 static const unsigned s_maxSize = 500000; // Just enough to guard against pa thological growth.
196 191
197 int m_interval; 192 // Hard limit to guard against pathological growth. The expected number of
198 int m_countdown; 193 // cache entries is a lot lower given the average word count for a web page
194 // is well below 1,000 and even full length books rarely have over 10,000
195 // unique words [1]. 1: http://www.mine-control.com/zack/guttenberg/
196 // 2,500 seems like a resonable number.
197 static const unsigned s_maxSize = 2500;
198
199 SingleCharMap m_singleCharMap; 199 SingleCharMap m_singleCharMap;
200 Map m_map; 200 SmallStringMap m_shortStringMap;
201 }; 201 };
202 202
203 inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::Sm allStringKey& b) 203 inline bool operator==(const ShapeCache::SmallStringKey& a, const ShapeCache::Sm allStringKey& b)
204 { 204 {
205 if (a.length() != b.length()) 205 if (a.length() != b.length() || a.direction() != b.direction())
206 return false; 206 return false;
207 return WTF::equal(a.characters(), b.characters(), a.length()); 207 return WTF::equal(a.characters(), b.characters(), a.length());
208 } 208 }
209 209
210 } // namespace blink 210 } // namespace blink
211 211
212 #endif // WidthCache_h 212 #endif // ShapeCache_h
OLDNEW
« no previous file with comments | « Source/platform/fonts/shaping/HarfBuzzShaperTest.cpp ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698