Changeset 209179 in webkit
- Timestamp:
- Dec 1, 2016 1:24:21 AM (7 years ago)
- Location:
- trunk
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WTF/ChangeLog
r209173 r209179 1 2016-12-01 Yusuke Suzuki <utatane.tea@gmail.com> 2 3 Introduce StringImpl::StaticStringImpl with constexpr constructor 4 https://bugs.webkit.org/show_bug.cgi?id=165093 5 6 Reviewed by Darin Adler. 7 8 This patch adds new class, StringImpl::StaticStringImpl. 9 By using this class, we can easily create static StringImpls. 10 This class has constexpr constructor. You can initialize instances 11 of this class as global static variables without invoking global 12 constructors. 13 14 We already have similar system, StaticASCIILiteral. But using it 15 requires some special perl script since we need to calculate 16 hash value. On the other hand, we can use StaticStringImpl without 17 any script supports since we implement constexpr hash function. 18 In the future, we will replace all the use of StaticASCIILiteral 19 with this StaticStringImpl. 20 21 We define empty / null strings as StaticStringImpl. And we make 22 StringImpl::empty() & StringImpl::null() inline functions. 23 24 * wtf/Hasher.h: 25 (WTF::StringHasher::hashWithTop8BitsMasked): 26 (WTF::StringHasher::hash): 27 (WTF::StringHasher::finalize): 28 (WTF::StringHasher::finalizeAndMaskTop8Bits): 29 (WTF::StringHasher::computeLiteralHash): 30 (WTF::StringHasher::computeLiteralHashAndMaskTop8Bits): 31 (WTF::StringHasher::avalancheBits3): 32 (WTF::StringHasher::avalancheBits2): 33 (WTF::StringHasher::avalancheBits1): 34 (WTF::StringHasher::avalancheBits0): 35 (WTF::StringHasher::avalancheBits): 36 (WTF::StringHasher::avoidZero): 37 (WTF::StringHasher::processPendingCharacter): 38 (WTF::StringHasher::calculateWithRemainingLastCharacter1): 39 (WTF::StringHasher::calculateWithRemainingLastCharacter0): 40 (WTF::StringHasher::calculateWithRemainingLastCharacter): 41 (WTF::StringHasher::calculate1): 42 (WTF::StringHasher::calculate0): 43 (WTF::StringHasher::calculate): 44 (WTF::StringHasher::computeLiteralHashImpl): 45 * wtf/text/StringImpl.cpp: 46 * wtf/text/StringImpl.h: 47 (WTF::StringImpl::StaticStringImpl::StaticStringImpl): 48 (WTF::StringImpl::null): 49 (WTF::StringImpl::empty): 50 * wtf/text/StringStatics.cpp: 51 (WTF::StringImpl::null): Deleted. 52 (WTF::StringImpl::empty): Deleted. 53 1 54 2016-11-30 Darin Adler <darin@apple.com> 2 55 -
trunk/Source/WTF/wtf/Hasher.h
r208958 r209179 37 37 38 38 // Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash value of zero. 39 static const unsigned stringHashingStartValue = 0x9E3779B9U;39 static constexpr const unsigned stringHashingStartValue = 0x9E3779B9U; 40 40 41 41 class StringHasher { 42 42 public: 43 static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags. 43 static constexpr const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags. 44 static constexpr const unsigned maskHash = (1U << (sizeof(unsigned) * 8 - flagCount)) - 1; 44 45 45 46 StringHasher() … … 163 164 unsigned hashWithTop8BitsMasked() const 164 165 { 165 unsigned result = avalancheBits(); 166 166 return finalizeAndMaskTop8Bits(processPendingCharacter()); 167 } 168 169 unsigned hash() const 170 { 171 return finalize(processPendingCharacter()); 172 } 173 174 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 175 { 176 StringHasher hasher; 177 hasher.addCharactersAssumingAligned<T, Converter>(data, length); 178 return hasher.hashWithTop8BitsMasked(); 179 } 180 181 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data) 182 { 183 StringHasher hasher; 184 hasher.addCharactersAssumingAligned<T, Converter>(data); 185 return hasher.hashWithTop8BitsMasked(); 186 } 187 188 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 189 { 190 return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length); 191 } 192 193 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data) 194 { 195 return computeHashAndMaskTop8Bits<T, defaultConverter>(data); 196 } 197 198 template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length) 199 { 200 StringHasher hasher; 201 hasher.addCharactersAssumingAligned<T, Converter>(data, length); 202 return hasher.hash(); 203 } 204 205 template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data) 206 { 207 StringHasher hasher; 208 hasher.addCharactersAssumingAligned<T, Converter>(data); 209 return hasher.hash(); 210 } 211 212 template<typename T> static unsigned computeHash(const T* data, unsigned length) 213 { 214 return computeHash<T, defaultConverter>(data, length); 215 } 216 217 template<typename T> static unsigned computeHash(const T* data) 218 { 219 return computeHash<T, defaultConverter>(data); 220 } 221 222 static unsigned hashMemory(const void* data, unsigned length) 223 { 224 size_t lengthInUChar = length / sizeof(UChar); 225 StringHasher hasher; 226 hasher.addCharactersAssumingAligned(static_cast<const UChar*>(data), lengthInUChar); 227 228 for (size_t i = 0; i < length % sizeof(UChar); ++i) 229 hasher.addCharacter(static_cast<const char*>(data)[lengthInUChar * sizeof(UChar) + i]); 230 231 return hasher.hash(); 232 } 233 234 template<size_t length> static unsigned hashMemory(const void* data) 235 { 236 return hashMemory(data, length); 237 } 238 239 static constexpr unsigned finalize(unsigned hash) 240 { 241 return avoidZero(avalancheBits(hash)); 242 } 243 244 static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash) 245 { 167 246 // Reserving space from the high bits for flags preserves most of the hash's 168 247 // value, since hash lookup typically masks out the high bits anyway. 169 result &= (1U << (sizeof(result) * 8 - flagCount)) - 1; 170 171 // This avoids ever returning a hash code of 0, since that is used to 172 // signal "hash not computed yet". Setting the high bit maintains 173 // reasonable fidelity to a hash code of 0 because it is likely to yield 174 // exactly 0 when hash lookup masks out the high bits. 175 if (!result) 176 result = 0x80000000 >> flagCount; 177 178 return result; 179 } 180 181 unsigned hash() const 182 { 183 unsigned result = avalancheBits(); 184 185 // This avoids ever returning a hash code of 0, since that is used to 186 // signal "hash not computed yet". Setting the high bit maintains 187 // reasonable fidelity to a hash code of 0 because it is likely to yield 188 // exactly 0 when hash lookup masks out the high bits. 189 if (!result) 190 result = 0x80000000; 191 192 return result; 193 } 194 195 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 196 { 197 StringHasher hasher; 198 hasher.addCharactersAssumingAligned<T, Converter>(data, length); 199 return hasher.hashWithTop8BitsMasked(); 200 } 201 202 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data) 203 { 204 StringHasher hasher; 205 hasher.addCharactersAssumingAligned<T, Converter>(data); 206 return hasher.hashWithTop8BitsMasked(); 207 } 208 209 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 210 { 211 return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length); 212 } 213 214 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data) 215 { 216 return computeHashAndMaskTop8Bits<T, defaultConverter>(data); 217 } 218 219 template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length) 220 { 221 StringHasher hasher; 222 hasher.addCharactersAssumingAligned<T, Converter>(data, length); 223 return hasher.hash(); 224 } 225 226 template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data) 227 { 228 StringHasher hasher; 229 hasher.addCharactersAssumingAligned<T, Converter>(data); 230 return hasher.hash(); 231 } 232 233 template<typename T> static unsigned computeHash(const T* data, unsigned length) 234 { 235 return computeHash<T, defaultConverter>(data, length); 236 } 237 238 template<typename T> static unsigned computeHash(const T* data) 239 { 240 return computeHash<T, defaultConverter>(data); 241 } 242 243 static unsigned hashMemory(const void* data, unsigned length) 244 { 245 size_t lengthInUChar = length / sizeof(UChar); 246 StringHasher hasher; 247 hasher.addCharactersAssumingAligned(static_cast<const UChar*>(data), lengthInUChar); 248 249 for (size_t i = 0; i < length % sizeof(UChar); ++i) 250 hasher.addCharacter(static_cast<const char*>(data)[lengthInUChar * sizeof(UChar) + i]); 251 252 return hasher.hash(); 253 } 254 255 template<size_t length> static unsigned hashMemory(const void* data) 256 { 257 return hashMemory(data, length); 248 return avoidZero(avalancheBits(hash) & StringHasher::maskHash); 249 } 250 251 template<typename T, unsigned charactersCount> 252 static constexpr unsigned computeLiteralHash(const T (&characters)[charactersCount]) 253 { 254 return StringHasher::finalize(computeLiteralHashImpl(stringHashingStartValue, 0, characters, charactersCount - 1)); 255 } 256 257 template<typename T, unsigned charactersCount> 258 static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[charactersCount]) 259 { 260 return StringHasher::finalizeAndMaskTop8Bits(computeLiteralHashImpl(stringHashingStartValue, 0, characters, charactersCount - 1)); 258 261 } 259 262 … … 269 272 } 270 273 271 unsigned avalancheBits() const 274 ALWAYS_INLINE static constexpr unsigned avalancheBits3(unsigned hash) 275 { 276 return hash ^ (hash << 10); 277 } 278 279 ALWAYS_INLINE static constexpr unsigned avalancheBits2(unsigned hash) 280 { 281 return avalancheBits3(hash + (hash >> 15)); 282 } 283 284 ALWAYS_INLINE static constexpr unsigned avalancheBits1(unsigned hash) 285 { 286 return avalancheBits2(hash ^ (hash << 2)); 287 } 288 289 ALWAYS_INLINE static constexpr unsigned avalancheBits0(unsigned hash) 290 { 291 return avalancheBits1(hash + (hash >> 5)); 292 } 293 294 ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash) 295 { 296 return avalancheBits0(hash ^ (hash << 3)); 297 } 298 299 // This avoids ever returning a hash code of 0, since that is used to 300 // signal "hash not computed yet". Setting the high bit maintains 301 // reasonable fidelity to a hash code of 0 because it is likely to yield 302 // exactly 0 when hash lookup masks out the high bits. 303 ALWAYS_INLINE static constexpr unsigned avoidZero(unsigned hash) 304 { 305 return hash ? hash : (0x80000000 >> StringHasher::flagCount); 306 } 307 308 unsigned processPendingCharacter() const 272 309 { 273 310 unsigned result = m_hash; … … 279 316 result += result >> 17; 280 317 } 281 282 // Force "avalanching" of final 31 bits.283 result ^= result << 3;284 result += result >> 5;285 result ^= result << 2;286 result += result >> 15;287 result ^= result << 10;288 289 318 return result; 319 } 320 321 322 // FIXME: This code limits itself to the older, more limited C++11 constexpr capabilities, using 323 // recursion instead of looping, for example. Would be nice to rewrite this in a simpler way 324 // once we no longer need to support compilers like GCC 4.9 that do not yet support it. 325 static constexpr unsigned calculateWithRemainingLastCharacter1(unsigned hash) 326 { 327 return hash + (hash >> 17); 328 } 329 330 static constexpr unsigned calculateWithRemainingLastCharacter0(unsigned hash) 331 { 332 return calculateWithRemainingLastCharacter1((hash << 11) ^ hash); 333 } 334 335 static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character) 336 { 337 return calculateWithRemainingLastCharacter0(hash + character); 338 } 339 340 static constexpr unsigned calculate1(unsigned hash) 341 { 342 return hash + (hash >> 11); 343 } 344 345 static constexpr unsigned calculate0(unsigned hash, unsigned secondCharacter) 346 { 347 return calculate1((hash << 16) ^ ((secondCharacter << 11) ^ hash)); 348 } 349 350 static constexpr unsigned calculate(unsigned hash, unsigned firstCharacter, unsigned secondCharacter) 351 { 352 return calculate0(hash + firstCharacter, secondCharacter); 353 } 354 355 static constexpr unsigned computeLiteralHashImpl(unsigned hash, unsigned index, const char* characters, unsigned length) 356 { 357 return (index == length) 358 ? hash : ((index + 1) == length) 359 ? calculateWithRemainingLastCharacter(hash, characters[index]) 360 : computeLiteralHashImpl(calculate(hash, characters[index], characters[index + 1]), index + 2, characters, length); 290 361 } 291 362 -
trunk/Source/WTF/wtf/text/StringImpl.cpp
r206804 r209179 102 102 #endif 103 103 104 StringImpl::StaticStringImpl StringImpl::s_atomicNullString("", StringImpl::StringAtomic); 105 StringImpl::StaticStringImpl StringImpl::s_atomicEmptyString("", StringImpl::StringAtomic); 104 106 105 107 StringImpl::~StringImpl() -
trunk/Source/WTF/wtf/text/StringImpl.h
r206804 r209179 150 150 // The bottom 6 bits in the hash are flags. 151 151 public: 152 static const unsigned s_flagCount = 6;152 static constexpr const unsigned s_flagCount = 6; 153 153 private: 154 static const unsigned s_flagMask = (1u << s_flagCount) - 1;155 COMPILE_ASSERT(s_flagCount <= StringHasher::flagCount, StringHasher_reserves_enough_bits_for_StringImpl_flags);156 static const unsigned s_flagStringKindCount = 4;157 158 static const unsigned s_hashFlagStringKindIsAtomic = 1u << (s_flagStringKindCount);159 static const unsigned s_hashFlagStringKindIsSymbol = 1u << (s_flagStringKindCount + 1);160 static const unsigned s_hashMaskStringKind = s_hashFlagStringKindIsAtomic | s_hashFlagStringKindIsSymbol;161 static const unsigned s_hashFlag8BitBuffer = 1u << 3;162 static const unsigned s_hashFlagDidReportCost = 1u << 2;163 static const unsigned s_hashMaskBufferOwnership = (1u << 0) | (1u << 1);154 static constexpr const unsigned s_flagMask = (1u << s_flagCount) - 1; 155 static_assert(s_flagCount <= StringHasher::flagCount, "StringHasher reserves enough bits for StringImpl flags"); 156 static constexpr const unsigned s_flagStringKindCount = 4; 157 158 static constexpr const unsigned s_hashFlagStringKindIsAtomic = 1u << (s_flagStringKindCount); 159 static constexpr const unsigned s_hashFlagStringKindIsSymbol = 1u << (s_flagStringKindCount + 1); 160 static constexpr const unsigned s_hashMaskStringKind = s_hashFlagStringKindIsAtomic | s_hashFlagStringKindIsSymbol; 161 static constexpr const unsigned s_hashFlag8BitBuffer = 1u << 3; 162 static constexpr const unsigned s_hashFlagDidReportCost = 1u << 2; 163 static constexpr const unsigned s_hashMaskBufferOwnership = (1u << 0) | (1u << 1); 164 164 165 165 enum StringKind { … … 168 168 StringSymbol = s_hashFlagStringKindIsSymbol, // symbol, non-atomic 169 169 }; 170 171 // Used to construct static strings, which have an special refCount that can never hit zero.172 // This means that the static string will never be destroyed, which is important because173 // static strings will be shared across threads & ref-counted in a non-threadsafe manner.174 friend class NeverDestroyed<StringImpl>;175 enum ConstructEmptyStringTag { ConstructEmptyString };176 StringImpl(ConstructEmptyStringTag)177 : m_refCount(s_refCountFlagIsStaticString)178 , m_length(0)179 , m_data8(reinterpret_cast<const LChar*>(&m_length))180 , m_hashAndFlags(s_hashFlag8BitBuffer | StringAtomic | BufferOwned)181 {182 // Ensure that the hash is computed so that AtomicStringHash can call existingHash()183 // with impunity. The empty string is special because it is never entered into184 // AtomicString's HashKey, but still needs to compare correctly.185 STRING_STATS_ADD_8BIT_STRING(m_length);186 187 hash();188 }189 170 190 171 // FIXME: there has to be a less hacky way to do this. … … 607 588 } 608 589 609 WTF_EXPORT_PRIVATE static StringImpl* empty(); 590 class StaticStringImpl { 591 public: 592 // Used to construct static strings, which have an special refCount that can never hit zero. 593 // This means that the static string will never be destroyed, which is important because 594 // static strings will be shared across threads & ref-counted in a non-threadsafe manner. 595 template<unsigned charactersCount> 596 constexpr StaticStringImpl(const char (&characters)[charactersCount], StringKind stringKind = StringNormal) 597 : m_refCount(s_refCountFlagIsStaticString) 598 , m_length(charactersCount - 1) 599 , m_data8(characters) 600 , m_hashAndFlags(s_hashFlag8BitBuffer | stringKind | BufferInternal | (StringHasher::computeLiteralHashAndMaskTop8Bits(characters) << s_flagCount)) 601 { 602 } 603 604 template<unsigned charactersCount> 605 constexpr StaticStringImpl(const char16_t (&characters)[charactersCount], StringKind stringKind = StringNormal) 606 : m_refCount(s_refCountFlagIsStaticString) 607 , m_length(charactersCount - 1) 608 , m_data16(characters) 609 , m_hashAndFlags(stringKind | BufferInternal | (StringHasher::computeLiteralHashAndMaskTop8Bits(characters) << s_flagCount)) 610 { 611 } 612 613 // These member variables must match the layout of StringImpl. 614 unsigned m_refCount; 615 unsigned m_length; 616 union { 617 const char* m_data8; 618 const char16_t* m_data16; 619 }; 620 unsigned m_hashAndFlags; 621 }; 622 623 WTF_EXPORTDATA static StaticStringImpl s_atomicNullString; 624 WTF_EXPORTDATA static StaticStringImpl s_atomicEmptyString; 625 ALWAYS_INLINE static StringImpl* null() { return reinterpret_cast<StringImpl*>(&s_atomicNullString); } 626 ALWAYS_INLINE static StringImpl* empty() { return reinterpret_cast<StringImpl*>(&s_atomicEmptyString); } 610 627 611 628 // FIXME: Does this really belong in StringImpl? … … 867 884 WTF_EXPORT_PRIVATE NEVER_INLINE unsigned hashSlowCase() const; 868 885 WTF_EXPORT_PRIVATE static unsigned nextHashForSymbol(); 869 WTF_EXPORT_PRIVATE static StringImpl* null();870 886 871 887 // The bottom bit in the ref count indicates a static (immortal) string. … … 878 894 879 895 public: 896 // FIXME: It should be replaced with StaticStringImpl. 897 // https://bugs.webkit.org/show_bug.cgi?id=165134 880 898 struct StaticASCIILiteral { 881 899 // These member variables must match the layout of StringImpl. … … 900 918 901 919 private: 902 // These member variables must match the layout of StaticASCIILiteral .920 // These member variables must match the layout of StaticASCIILiteral and StaticStringImpl. 903 921 unsigned m_refCount; 904 922 unsigned m_length; … … 911 929 912 930 static_assert(sizeof(StringImpl) == sizeof(StringImpl::StaticASCIILiteral), ""); 931 static_assert(sizeof(StringImpl) == sizeof(StringImpl::StaticStringImpl), ""); 913 932 914 933 #if !ASSERT_DISABLED -
trunk/Source/WTF/wtf/text/StringStatics.cpp
r205819 r209179 41 41 42 42 namespace WTF { 43 44 StringImpl* StringImpl::null()45 {46 static NeverDestroyed<StringImpl> nullString(ConstructEmptyString);47 return &nullString.get();48 }49 50 StringImpl* StringImpl::empty()51 {52 static NeverDestroyed<StringImpl> emptyString(ConstructEmptyString);53 return &emptyString.get();54 }55 43 56 44 // In addition to the normal hash value, store specialized hash value for -
trunk/Tools/ChangeLog
r209161 r209179 1 2016-12-01 Yusuke Suzuki <utatane.tea@gmail.com> 2 3 Introduce StringImpl::StaticStringImpl with constexpr constructor 4 https://bugs.webkit.org/show_bug.cgi?id=165093 5 6 Reviewed by Darin Adler. 7 8 * TestWebKitAPI/Tests/WTF/StringImpl.cpp: 9 (TestWebKitAPI::TEST): 10 1 11 2016-11-30 Antoine Quint <graouts@apple.com> 2 12 -
trunk/Tools/TestWebKitAPI/Tests/WTF/StringImpl.cpp
r201782 r209179 26 26 #include "config.h" 27 27 28 #include <wtf/Hasher.h> 28 29 #include <wtf/text/SymbolImpl.h> 29 30 #include <wtf/text/WTFString.h> … … 575 576 } 576 577 578 TEST(WTF, StringImplConstexprHasher) 579 { 580 ASSERT_EQ(stringFromUTF8("")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("")); 581 ASSERT_EQ(stringFromUTF8("A")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("A")); 582 ASSERT_EQ(stringFromUTF8("AA")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("AA")); 583 ASSERT_EQ(stringFromUTF8("Cocoa")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("Cocoa")); 584 ASSERT_EQ(stringFromUTF8("Cappuccino")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("Cappuccino")); 585 } 586 587 TEST(WTF, StringImplEmpty) 588 { 589 ASSERT_FALSE(StringImpl::empty()->length()); 590 ASSERT_FALSE(StringImpl::null()->length()); 591 ASSERT_NE(StringImpl::null(), StringImpl::empty()); 592 } 593 577 594 } // namespace TestWebKitAPI
Note: See TracChangeset
for help on using the changeset viewer.