Changeset 275410 in webkit for trunk/Source/JavaScriptCore/builtins/BuiltinNames.cpp

Timestamp:

Apr 2, 2021, 1:33:32 AM (4 years ago)

Author:

[email protected]

Message:

[WTF] Introduce RobinHoodHashTable
​https://bugs.webkit.org/show_bug.cgi?id=223895

Reviewed by Fil Pizlo.

Source/JavaScriptCore:

• builtins/BuiltinNames.cpp:

(JSC::lookUpPrivateNameImpl):
(JSC::lookUpWellKnownSymbolImpl):

• builtins/BuiltinNames.h:
• bytecode/BytecodeIntrinsicRegistry.h:
• runtime/Identifier.h:
• runtime/IntlCollator.cpp:

(JSC::IntlCollator::initializeCollator):
(JSC::IntlCollator::checkICULocaleInvariants):

• runtime/IntlCollator.h:
• runtime/IntlDateTimeFormat.cpp:

(JSC::IntlDateTimeFormat::initializeDateTimeFormat):

• runtime/IntlDateTimeFormatConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlDisplayNames.cpp:

(JSC::IntlDisplayNames::initializeDisplayNames):

• runtime/IntlDisplayNamesConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlListFormat.cpp:

(JSC::IntlListFormat::initializeListFormat):

• runtime/IntlListFormatConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlNumberFormat.cpp:

(JSC::IntlNumberFormat::initializeNumberFormat):

• runtime/IntlNumberFormatConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlObject.cpp:

(JSC::addScriptlessLocaleIfNeeded):
(JSC::intlAvailableLocales):
(JSC::intlCollatorAvailableLocales):
(JSC::intlSegmenterAvailableLocales):
(JSC::bestAvailableLocale):
(JSC::lookupMatcher):
(JSC::bestFitMatcher):
(JSC::resolveLocale):
(JSC::lookupSupportedLocales):
(JSC::bestFitSupportedLocales):
(JSC::supportedLocales):

• runtime/IntlObject.h:

(JSC::intlDateTimeFormatAvailableLocales):
(JSC::intlDisplayNamesAvailableLocales):
(JSC::intlNumberFormatAvailableLocales):
(JSC::intlPluralRulesAvailableLocales):
(JSC::intlRelativeTimeFormatAvailableLocales):
(JSC::intlListFormatAvailableLocales):

• runtime/IntlPluralRules.cpp:

(JSC::IntlPluralRules::initializePluralRules):

• runtime/IntlPluralRulesConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlRelativeTimeFormat.cpp:

(JSC::IntlRelativeTimeFormat::initializeRelativeTimeFormat):

• runtime/IntlRelativeTimeFormatConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/IntlSegmenter.cpp:

(JSC::IntlSegmenter::initializeSegmenter):

• runtime/IntlSegmenterConstructor.cpp:

(JSC::JSC_DEFINE_HOST_FUNCTION):

• runtime/RegExpCache.h:
• runtime/RegExpKey.h:

Source/WebCore:

• Modules/mediacapabilities/MediaCapabilities.cpp:

(WebCore::bucketMIMETypes):

• accessibility/AccessibilityObject.cpp:

(WebCore::AccessibilityObject::popupValue const):

• dom/Element.cpp:

(WebCore::canAttachAuthorShadowRoot):

• dom/QualifiedName.h:
• dom/make_names.pl:

(printNamesHeaderFile):
(printFactoryCppFile):
(printWrapperFactoryCppFile):

• editing/FormatBlockCommand.cpp:

(WebCore::isElementForFormatBlock):

• editing/RemoveFormatCommand.cpp:

(WebCore::isElementForRemoveFormatCommand):

• editing/ReplaceSelectionCommand.cpp:

(WebCore::isProhibitedParagraphChild):

• html/Autofill.cpp:

(WebCore::fieldNameMap):

• html/HTMLDocument.cpp:

(WebCore::HTMLDocument::isCaseSensitiveAttribute):

• html/HTMLObjectElement.cpp:

(WebCore::preventsParentObjectFromExposure):

• html/parser/HTMLTreeBuilder.cpp:

(WebCore::createCaseMap):
(WebCore::adjustSVGTagNameCase):
(WebCore::adjustAttributes):
(WebCore::createForeignAttributesMap):
(WebCore::adjustForeignAttributes):
(WebCore::addNamesWithPrefix): Deleted.

• page/DebugPageOverlays.cpp:

(WebCore::touchEventRegionColors):
(WebCore::NonFastScrollableRegionOverlay::drawRect):

• page/PerformanceUserTiming.cpp:

(WebCore::restrictedMarkNamesToNavigationTimingFunctionMap):

• platform/cocoa/MIMETypeRegistryCocoa.mm:

(WebCore::extensionsForMIMETypeMap):

• platform/graphics/FontCascade.cpp:

(WebCore::useBackslashAsYenSignForFamily):
(WebCore::FontCascade::hasValidAverageCharWidth const):

• platform/graphics/avfoundation/CDMFairPlayStreaming.cpp:

(WebCore::validInitDataTypes):

• platform/graphics/cg/UTIRegistry.cpp:

(WebCore::defaultSupportedImageTypes):

• platform/graphics/cg/UTIRegistry.h:
• platform/graphics/cocoa/HEVCUtilitiesCocoa.mm:

(WebCore::codecTypeForDoViCodecString):

• platform/graphics/cocoa/SourceBufferParserWebM.cpp:

(WebCore::SourceBufferParserWebM::supportedVideoCodecs):
(WebCore::SourceBufferParserWebM::supportedAudioCodecs):

• platform/graphics/cocoa/SourceBufferParserWebM.h:
• rendering/svg/SVGResources.cpp:

(WebCore::clipperFilterMaskerTags):
(WebCore::markerTags):
(WebCore::fillAndStrokeTags):
(WebCore::chainableResourceTags):

• style/StyleAdjuster.cpp:

(WebCore::Style::hasEffectiveDisplayNoneForDisplayContents):

• svg/SVGAnimationElement.cpp:

(WebCore::SVGAnimationElement::isSupportedAttribute):

• svg/SVGElement.cpp:

(WebCore::createAttributeNameToCSSPropertyIDMap):
(WebCore::SVGElement::animatableAttributeForName):
(WebCore::SVGElement::cssPropertyIdForSVGAttributeName):

• svg/SVGTests.cpp:

(WebCore::SVGTests::addSupportedAttributes):

• svg/SVGTests.h:
• svg/SVGUseElement.cpp:

(WebCore::createAllowedElementSet):
(WebCore::isDisallowedElement):

• svg/animation/SVGSMILElement.cpp:

(WebCore::SVGSMILElement::isSupportedAttribute):

• xml/XPathFunctions.cpp:

(WebCore::XPath::createFunctionMap):

• xml/XPathParser.cpp:

(WebCore::XPath::createAxisNamesMap):

Source/WebKit:

• NetworkProcess/Classifier/ResourceLoadStatisticsDatabaseStore.cpp:

(WebKit::ObservedDomainsTableSchemaV1Alternate):
(WebKit::expectedUnattributedColumns):
(WebKit::expectedAttributedColumns):
(WebKit::createTableQueries):

• Platform/IPC/ArgumentCoders.h:
• Shared/Cocoa/DefaultWebBrowserChecks.mm:

(WebKit::getAppBoundDomainsTesting):

• Shared/WebPreferencesStore.cpp:

(WebKit::WebPreferencesStore::decode):

• Shared/WebPreferencesStore.h:
• UIProcess/Cocoa/WebProcessProxyCocoa.mm:

(WebKit::WebProcessProxy::platformPathsWithAssumedReadAccess):

• UIProcess/WebProcessProxy.cpp:

(WebKit::WebProcessProxy::platformPathsWithAssumedReadAccess):

• UIProcess/WebProcessProxy.h:

Source/WTF:

This patch implements RobinHoodHashTable[1]. We don't use it as a default hashtable since it has different performance v.s. memory-saving characteristics,
and this patch's goal is not tackling on making this default. Rather, the goal of this patch is introducing it to non-performance sensitive area quickly
so that we can save memory. RobinHoodHashTable more frequently computes hash value compared to HashTable, so this is not drop-in replacement for the existing
one. But still, this is useful since we know that "while there are many small HashTables and they holds much memory, there are super large HashTables and
they holds almost same amount of memory while they are a few.". This patch's goal is applying this RobinHoodHashTable to these "large, but a few" singleton tables.

RobinHoodHashTable maintains distance-from-initial-bucket (DIB) small by adjusting existing entries when inserting. When inserting, if we found that the
existing entry has less DIB than the current inserting entry's DIB, then we swap entries, and insert the existing entry to the other place. This is giving
some good DIB from rich entry to poor entry (that's why it is called RobinHood Hashing), and making average DIB lower. And this algorithm adds good invariant
that, when looking up an entry, and we found that existing entry has smaller DIB, then we can stop searching in the middle of the chain since we know that
we should swap entries when this happened when inserting. These two tricks maintain HashTable performance even under significantly high load factor: 90% load-factor
just works. 95% load-factor regress adding performance, but still it does not become catastrophic compared to normal open-addressing HashTable.

We introduce RobinHoodHashTable, and adding several kinds of tables based on load-factors.

1. MemoryCompactLookupOnlyRobinHoodHashSet / HashMap

This has 95% load-factor. This is suitable for sets and maps which is mostly-constant: constructing once, and looking up repeatedly. In WebKit, there are so
many this kind of tables e.g. singleton HashMap for various kinds of things. We can use this super high load-factor table so that we can save memory even while
we are maintains fast HashTable lookup.

2. MemoryCompactRobinHoodHashSet / HashMap

This has 90% load-factor. It just works, and we can try using it if sets and maps are significantly performance intensive.

3. FastRobinHoodHashSet / HashMap

This has 75% load-factor. This is still good compared to HashSet and HashMap since they are using 50% load-factor for large sized tables. This has very slightly performance regressed
compared to 50% load-factor large HashSet and HashMap, but if that is not performance intensive (e.g. AtomStringTable is one of the most performance intensive table), this is good.

In this patch, we replace many singleton HashSet / HashMap with RobinHoodHashTable.

[1]: ​https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

• WTF.xcodeproj/project.pbxproj:
• wtf/CMakeLists.txt:
• wtf/Forward.h:
• wtf/HashMap.h:

(WTF::Y>::swap):
(WTF::Y>::size const):
(WTF::Y>::capacity const):
(WTF::Y>::isEmpty const):
(WTF::Y>::begin):
(WTF::Y>::end):
(WTF::Y>::begin const):
(WTF::Y>::end const):
(WTF::Y>::find):
(WTF::Y>::find const):
(WTF::Y>::contains const):
(WTF::Y>::get const):
(WTF::Y>::inlineGet const):
(WTF::TableTraitsArg>::inlineSet):
(WTF::TableTraitsArg>::inlineAdd):
(WTF::TableTraitsArg>::inlineEnsure):
(WTF::TableTraitsArg>::set):
(WTF::TableTraitsArg>::add):
(WTF::TableTraitsArg>::fastAdd):
(WTF::TableTraitsArg>::ensure):
(WTF::Y>::remove):
(WTF::Y>::removeIf):
(WTF::Y>::clear):
(WTF::Y>::take):
(WTF::Y>::checkConsistency const):
(WTF::Y>::isValidKey):
(WTF::operator==):
(WTF::operator!=):
(WTF::X>::swap): Deleted.
(WTF::X>::size const): Deleted.
(WTF::X>::capacity const): Deleted.
(WTF::X>::isEmpty const): Deleted.
(WTF::X>::begin): Deleted.
(WTF::X>::end): Deleted.
(WTF::X>::begin const): Deleted.
(WTF::X>::end const): Deleted.
(WTF::X>::find): Deleted.
(WTF::X>::find const): Deleted.
(WTF::X>::contains const): Deleted.
(WTF::X>::get const): Deleted.
(WTF::X>::inlineGet const): Deleted.
(WTF::MappedTraitsArg>::inlineSet): Deleted.
(WTF::MappedTraitsArg>::inlineAdd): Deleted.
(WTF::MappedTraitsArg>::inlineEnsure): Deleted.
(WTF::MappedTraitsArg>::set): Deleted.
(WTF::MappedTraitsArg>::add): Deleted.
(WTF::MappedTraitsArg>::fastAdd): Deleted.
(WTF::MappedTraitsArg>::ensure): Deleted.
(WTF::MappedTraits>::get const): Deleted.
(WTF::MappedTraits>::inlineGet const): Deleted.
(WTF::X>::remove): Deleted.
(WTF::X>::removeIf): Deleted.
(WTF::X>::clear): Deleted.
(WTF::MappedTraits>::take): Deleted.
(WTF::X>::take): Deleted.
(WTF::X>::checkConsistency const): Deleted.
(WTF::X>::isValidKey): Deleted.

• wtf/HashSet.h:

(WTF::W>::swap):
(WTF::W>::size const):
(WTF::W>::capacity const):
(WTF::W>::isEmpty const):
(WTF::W>::begin const):
(WTF::W>::end const):
(WTF::W>::find const):
(WTF::W>::contains const):
(WTF::TableTraits>::find const):
(WTF::TableTraits>::contains const):
(WTF::TableTraits>::ensure):
(WTF::W>::add):
(WTF::W>::addVoid):
(WTF::TableTraits>::add):
(WTF::W>::remove):
(WTF::W>::removeIf):
(WTF::W>::clear):
(WTF::W>::take):
(WTF::W>::takeAny):
(WTF::TableTraits>::remove):
(WTF::TableTraits>::take):
(WTF::W>::isValidValue):
(WTF::= const):
(WTF::W>::checkConsistency const):
(WTF::V>::swap): Deleted.
(WTF::V>::size const): Deleted.
(WTF::V>::capacity const): Deleted.
(WTF::V>::isEmpty const): Deleted.
(WTF::V>::begin const): Deleted.
(WTF::V>::end const): Deleted.
(WTF::V>::find const): Deleted.
(WTF::V>::contains const): Deleted.
(WTF::Traits>::find const): Deleted.
(WTF::Traits>::contains const): Deleted.
(WTF::Traits>::ensure): Deleted.
(WTF::V>::add): Deleted.
(WTF::V>::addVoid): Deleted.
(WTF::Traits>::add): Deleted.
(WTF::V>::remove): Deleted.
(WTF::V>::removeIf): Deleted.
(WTF::V>::clear): Deleted.
(WTF::V>::take): Deleted.
(WTF::V>::takeAny): Deleted.
(WTF::Traits>::remove): Deleted.
(WTF::Traits>::take): Deleted.
(WTF::V>::isValidValue): Deleted.
(WTF::V>::checkConsistency const): Deleted.

• wtf/HashTable.h:

(WTF::addIterator):
(WTF::removeIterator):
(WTF::invalidateIterators):
(WTF::HashTable::~HashTable):
(WTF::HashTable::random):
(WTF::KeyTraits>::inlineLookup):
(WTF::KeyTraits>::lookupForWriting):
(WTF::KeyTraits>::fullLookupForWriting):
(WTF::KeyTraits>::addUniqueForInitialization):
(WTF::KeyTraits>::add):
(WTF::KeyTraits>::addPassingHashCode):
(WTF::KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck):
(WTF::KeyTraits>::removeAndInvalidate):
(WTF::KeyTraits>::clear):
(WTF::KeyTraits>::swap):
(WTF::KeyTraits>::HashTable):
(WTF::HashTable::invalidateIterators): Deleted.
(WTF::KeyTraits>::invalidateIterators): Deleted.

• wtf/RobinHoodHashMap.h: Added.
• wtf/RobinHoodHashSet.h: Added.
• wtf/RobinHoodHashTable.h: Added.

(WTF::RobinHoodHashTable::~RobinHoodHashTable):
(WTF::RobinHoodHashTable::begin):
(WTF::RobinHoodHashTable::end):
(WTF::RobinHoodHashTable::begin const):
(WTF::RobinHoodHashTable::end const):
(WTF::RobinHoodHashTable::random):
(WTF::RobinHoodHashTable::random const):
(WTF::RobinHoodHashTable::size const):
(WTF::RobinHoodHashTable::capacity const):
(WTF::RobinHoodHashTable::isEmpty const):
(WTF::RobinHoodHashTable::reserveInitialCapacity):
(WTF::RobinHoodHashTable::add):
(WTF::RobinHoodHashTable::find):
(WTF::RobinHoodHashTable::find const):
(WTF::RobinHoodHashTable::contains const):
(WTF::RobinHoodHashTable::isEmptyBucket):
(WTF::RobinHoodHashTable::isEmptyOrDeletedBucket):
(WTF::RobinHoodHashTable::lookup):
(WTF::RobinHoodHashTable::checkTableConsistency):
(WTF::RobinHoodHashTable::internalCheckTableConsistency const):
(WTF::RobinHoodHashTable::internalCheckTableConsistencyExceptSize const):
(WTF::RobinHoodHashTable::internalCheckTableConsistencyExceptSize):
(WTF::RobinHoodHashTable::internalCheckTableConsistency):
(WTF::RobinHoodHashTable::shouldExpand):
(WTF::RobinHoodHashTable::computeTableHash):
(WTF::RobinHoodHashTable::shouldExpand const):
(WTF::RobinHoodHashTable::shouldShrink const):
(WTF::RobinHoodHashTable::shrink):
(WTF::RobinHoodHashTable::deleteBucket):
(WTF::RobinHoodHashTable::desiredIndex):
(WTF::RobinHoodHashTable::probeDistance):
(WTF::RobinHoodHashTable::makeIterator):
(WTF::RobinHoodHashTable::makeConstIterator const):
(WTF::RobinHoodHashTable::makeKnownGoodIterator):
(WTF::RobinHoodHashTable::makeKnownGoodConstIterator const):
(WTF::RobinHoodHashTable::checkTableConsistencyExceptSize):
(WTF::RobinHoodHashTable::tableSize const):
(WTF::RobinHoodHashTable::tableSizeMask const):
(WTF::RobinHoodHashTable::keyCount const):
(WTF::RobinHoodHashTable::tableHash const):
(WTF::SizePolicy>::checkKey):
(WTF::SizePolicy>::lookup):
(WTF::SizePolicy>::inlineLookup):
(WTF::SizePolicy>::initializeBucket):
(WTF::SizePolicy>::add):
(WTF::SizePolicy>::maintainProbeDistanceForAdd):
(WTF::SizePolicy>::addPassingHashCode):
(WTF::SizePolicy>::reinsert):
(WTF::SizePolicy>::find):
(WTF::SizePolicy>::find const):
(WTF::SizePolicy>::contains const):
(WTF::SizePolicy>::removeAndInvalidateWithoutEntryConsistencyCheck):
(WTF::SizePolicy>::removeAndInvalidate):
(WTF::SizePolicy>::remove):
(WTF::SizePolicy>::removeWithoutEntryConsistencyCheck):
(WTF::SizePolicy>::allocateTable):
(WTF::SizePolicy>::deallocateTable):
(WTF::SizePolicy>::expand):
(WTF::SizePolicy>::computeBestTableSize):
(WTF::SizePolicy>::shrinkToBestSize):
(WTF::SizePolicy>::rehash):
(WTF::SizePolicy>::clear):
(WTF::SizePolicy>::RobinHoodHashTable):
(WTF::SizePolicy>::swap):
(WTF::=):
(WTF::SizePolicy>::checkTableConsistency const):
(WTF::SizePolicy>::checkTableConsistencyExceptSize const):

• wtf/text/AtomStringHash.h:
• wtf/text/AtomStringImpl.cpp:
• wtf/text/AtomStringTable.cpp:

(WTF::AtomStringTable::~AtomStringTable):

• wtf/text/AtomStringTable.h:

(WTF::AtomStringTable::table):

• wtf/text/StringHash.h:

Tools:

• TestWebKitAPI/CMakeLists.txt:
• TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
• TestWebKitAPI/Tests/WTF/DeletedAddressOfOperator.h:
• TestWebKitAPI/Tests/WTF/HashMap.cpp:

(TestWebKitAPI::testMovingUsingEnsure):
(TestWebKitAPI::testMovingUsingAdd):

• TestWebKitAPI/Tests/WTF/HashSet.cpp:

(TestWebKitAPI::generateTestCapacityUpToSize<0>):
(TestWebKitAPI::generateTestCapacityUpToSize):

• TestWebKitAPI/Tests/WTF/MoveOnly.h:
• TestWebKitAPI/Tests/WTF/RobinHoodHashMap.cpp: Copied from Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp.

(TestWebKitAPI::TEST):
(TestWebKitAPI::bucketForKey):
(TestWebKitAPI::ZeroHash::hash):
(TestWebKitAPI::ObjectWithRefLogger::ObjectWithRefLogger):
(TestWebKitAPI::testMovingUsingEnsure):
(TestWebKitAPI::testMovingUsingAdd):
(TestWebKitAPI::DerefObserver::ref):
(TestWebKitAPI::DerefObserver::deref):
(TestWebKitAPI::TestObjectWithCustomDestructor::TestObjectWithCustomDestructor):
(TestWebKitAPI::TestObjectWithCustomDestructor::~TestObjectWithCustomDestructor):

• TestWebKitAPI/Tests/WTF/RobinHoodHashSet.cpp: Copied from Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp.

(TestWebKitAPI::capacityForSize):
(TestWebKitAPI::testInitialCapacity):
(TestWebKitAPI::generateTestCapacityUpToSize<0>):
(TestWebKitAPI::generateTestCapacityUpToSize):
(TestWebKitAPI::TEST):
(TestWebKitAPI::DerefObserver::ref):
(TestWebKitAPI::DerefObserver::deref):

File:

• trunk/Source/JavaScriptCore/builtins/BuiltinNames.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/builtins/BuiltinNames.cpp

@@ -114 +114 @@
 
 template<typename CharacterType>
-static PrivateSymbolImpl* lookUpPrivateNameImpl(const HashSet<String>& set, const WTF::HashTranslatorCharBuffer<CharacterType>& buffer)
+static PrivateSymbolImpl* lookUpPrivateNameImpl(const BuiltinNames::PrivateNameSet& set, const WTF::HashTranslatorCharBuffer<CharacterType>& buffer)
 {
     auto iterator = set.find<CharBufferSeacher<CharacterType>>(buffer);
@@ -127 +127 @@
 
 template<typename CharacterType>
-static SymbolImpl* lookUpWellKnownSymbolImpl(const HashMap<String, SymbolImpl*>& map, const WTF::HashTranslatorCharBuffer<CharacterType>& buffer)
+static SymbolImpl* lookUpWellKnownSymbolImpl(const BuiltinNames::WellKnownSymbolMap& map, const WTF::HashTranslatorCharBuffer<CharacterType>& buffer)
 {
     auto iterator = map.find<CharBufferSeacher<CharacterType>>(buffer);