[webkit-changes] [WebKit/WebKit] ff19fc: [JSC] Introduce wyhash to StringImpl

Tue Aug 15 15:32:52 PDT 2023

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: ff19fc587702c99f818714c97f079c6ae60498bc
      https://github.com/WebKit/WebKit/commit/ff19fc587702c99f818714c97f079c6ae60498bc
  Author: Yijia Huang <yijia_huang at apple.com>
  Date:   2023-08-15 (Tue, 15 Aug 2023)

  Changed paths:
    M Source/JavaScriptCore/create_hash_table
    M Source/JavaScriptCore/runtime/JSCBytecodeCacheVersion.cpp.in
    M Source/JavaScriptCore/runtime/JSCell.cpp
    M Source/JavaScriptCore/runtime/TemplateObjectDescriptor.h
    M Source/JavaScriptCore/tools/JSDollarVM.cpp
    M Source/JavaScriptCore/tools/VMInspector.cpp
    M Source/JavaScriptCore/yarr/hasher.py
    M Source/WTF/WTF.xcodeproj/project.pbxproj
    M Source/WTF/wtf/CMakeLists.txt
    M Source/WTF/wtf/Hasher.h
    M Source/WTF/wtf/text/CString.cpp
    M Source/WTF/wtf/text/StringHash.h
    M Source/WTF/wtf/text/StringHasher.h
    A Source/WTF/wtf/text/StringHasherInlines.h
    M Source/WTF/wtf/text/StringImpl.h
    A Source/WTF/wtf/text/SuperFastHash.h
    A Source/WTF/wtf/text/WYHash.h
    M Source/WTF/wtf/unicode/UTF8Conversion.cpp
    M Source/WebCore/bindings/scripts/Hasher.pm
    M Source/WebCore/bindings/scripts/test/JS/JSTestGlobalObject.cpp
    M Source/WebCore/contentextensions/DFAMinimizer.cpp
    M Source/WebCore/contentextensions/HashableActionList.h
    M Source/WebCore/platform/SharedStringHash.cpp
    M Source/WebCore/platform/graphics/WidthCache.h
    M Tools/TestWebKitAPI/CMakeLists.txt
    M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
    M Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp
    A Tools/TestWebKitAPI/Tests/WTF/SuperFastHash.cpp
    A Tools/TestWebKitAPI/Tests/WTF/WYHash.cpp

  Log Message:
  -----------
  [JSC] Introduce wyhash to StringImpl
https://bugs.webkit.org/show_bug.cgi?id=260147
rdar://113860312

Reviewed by Yusuke Suzuki.

StringImpl::hashSlowCase() is one of the hottest functions when running
JetStream2. However, the existing hash function is slow for large
string since it's based on incremental hashing of each character.
This patch introduces wyhash[1] (hashing data in bulks) to StringImpl
with OSS approval (ID OSS-16203), since wyhash provides the best hash
score without quality issues according to SMhasher[2].

In this patch:
1. Rename previous StringHasher.h to SuperFastHash.h.
2. Use SuperFastHash for small strings and wyhash for large strings
in order to gain best performances on JetStream2.

[1] https://github.com/wangyi-fudan/wyhash
[2] https://github.com/rurban/smhasher

* Source/JavaScriptCore/create_hash_table:
* Source/JavaScriptCore/runtime/JSCBytecodeCacheVersion.cpp.in:
* Source/JavaScriptCore/runtime/JSCell.cpp:
(JSC::reportZappedCellAndCrash):
* Source/JavaScriptCore/runtime/TemplateObjectDescriptor.h:
(JSC::TemplateObjectDescriptor::calculateHash):
* Source/JavaScriptCore/tools/JSDollarVM.cpp:
* Source/JavaScriptCore/tools/VMInspector.cpp:
(JSC::VMInspector::dumpSubspaceHashes):
* Source/JavaScriptCore/yarr/hasher.py:
(stringHash):
(finalizeAndMaskTop8Bits):
(superFastHash):
(wyhash):
(wyhash.add64):
(wyhash.multi64):
(wyhash.wymum):
(wyhash.wymix):
(wyhash.convert32BitTo64Bit):
(wyhash.convert16BitTo32Bit):
(wyhash.c2i):
(wyhash.wyr8):
(wyhash.wyr4):
(wyhash.wyr2):
(ceilingToPowerOf2):
(createHashTable):
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/Hasher.h:
* Source/WTF/wtf/text/CString.cpp:
(WTF::CString::hash const):
* Source/WTF/wtf/text/StringHash.h:
(WTF::ASCIICaseInsensitiveHash::hash):
* Source/WTF/wtf/text/StringHasher.h:
(WTF::StringHasher::StringHasher):
(WTF::StringHasher::finalize):
(WTF::StringHasher::finalizeAndMaskTop8Bits):
(WTF::StringHasher::addCharactersAssumingAligned): Deleted.
(WTF::StringHasher::addCharacter): Deleted.
(WTF::StringHasher::addCharacters): Deleted.
(WTF::StringHasher::hashWithTop8BitsMasked const): Deleted.
(WTF::StringHasher::hash const): Deleted.
(WTF::StringHasher::computeHashAndMaskTop8Bits): Deleted.
(WTF::StringHasher::computeHash): Deleted.
(WTF::StringHasher::computeLiteralHash): Deleted.
(WTF::StringHasher::computeLiteralHashAndMaskTop8Bits): Deleted.
(WTF::StringHasher::calculateWithRemainingLastCharacter): Deleted.
(WTF::StringHasher::calculateWithTwoCharacters): Deleted.
(WTF::StringHasher::computeHashImpl): Deleted.
(WTF::StringHasher::processPendingCharacter const): Deleted.
* Source/WTF/wtf/text/StringHasherInlines.h: Added.
(WTF::StringHasher::computeHashAndMaskTop8Bits):
(WTF::StringHasher::computeLiteralHashAndMaskTop8Bits):
(WTF::StringHasher::addCharacter):
(WTF::StringHasher::hashWithTop8BitsMasked):
* Source/WTF/wtf/text/StringImpl.h:
* Source/WTF/wtf/text/SuperFastHash.h: Copied from Source/WTF/wtf/text/StringHasher.h.
(WTF::SuperFastHash::addCharactersAssumingAligned):
(WTF::SuperFastHash::addCharacter):
(WTF::SuperFastHash::addCharacters):
(WTF::SuperFastHash::hashWithTop8BitsMasked const):
(WTF::SuperFastHash::hash const):
(WTF::SuperFastHash::computeHashAndMaskTop8Bits):
(WTF::SuperFastHash::computeHash):
(WTF::SuperFastHash::computeLiteralHash):
(WTF::SuperFastHash::computeLiteralHashAndMaskTop8Bits):
(WTF::SuperFastHash::calculateWithRemainingLastCharacter):
(WTF::SuperFastHash::calculateWithTwoCharacters):
(WTF::SuperFastHash::computeHashImpl):
(WTF::SuperFastHash::processPendingCharacter const):
* Source/WTF/wtf/text/WYHash.h: Added.
(WTF::WYHash::computeHashAndMaskTop8Bits):
(WTF::WYHash::wyrot):
(WTF::WYHash::wymum):
(WTF::WYHash::wymix):
(WTF::WYHash::Reader16Bit::hasDefaultConverter):
(WTF::WYHash::Reader16Bit::convert):
(WTF::WYHash::Reader16Bit::wyr3):
(WTF::WYHash::Reader16Bit::wyr4WithConvert):
(WTF::WYHash::Reader16Bit::wyr4):
(WTF::WYHash::Reader16Bit::wyr8WithConvert):
(WTF::WYHash::Reader16Bit::wyr8):
(WTF::WYHash::Reader8Bit::hasDefaultConverter):
(WTF::WYHash::Reader8Bit::convert):
(WTF::WYHash::Reader8Bit::wyr3):
(WTF::WYHash::Reader8Bit::wyr4WithConvert):
(WTF::WYHash::Reader8Bit::wyr4):
(WTF::WYHash::Reader8Bit::wyr8WithConvert):
(WTF::WYHash::Reader8Bit::wyr8):
(WTF::WYHash::initSeed):
(WTF::WYHash::consume24Characters):
(WTF::WYHash::handleEndCase):
(WTF::WYHash::handleGreaterThan8CharactersCase):
(WTF::WYHash::hash):
(WTF::WYHash::computeHashImpl):
* Source/WTF/wtf/unicode/UTF8Conversion.cpp:
(WTF::Unicode::calculateStringHashAndLengthFromUTF8MaskingTop8Bits):
* Source/WebCore/bindings/scripts/Hasher.pm:
(finalizeAndMaskTop8Bits):
(superFastHash):
(uint64_add):
(uint64_multi):
(GenerateHashValue): Deleted.
* Source/WebCore/contentextensions/DFAMinimizer.cpp:
* Source/WebCore/contentextensions/HashableActionList.h:
(WebCore::ContentExtensions::HashableActionList::HashableActionList):
* Source/WebCore/platform/SharedStringHash.cpp:
(WebCore::computeSharedStringHashInline):
* Source/WebCore/platform/graphics/WidthCache.h:
(WebCore::WidthCache::SmallStringKey::SmallStringKey):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp:
(TestWebKitAPI::TEST):
* Tools/TestWebKitAPI/Tests/WTF/SuperFastHash.cpp: Copied from Tools/TestWebKitAPI/Tests/WTF/StringHasher.cpp.
(TestWebKitAPI::TEST):
* Tools/TestWebKitAPI/Tests/WTF/WYHash.cpp: Added.
(TestWebKitAPI::TEST):

Canonical link: https://commits.webkit.org/266929@main