[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):
Canonical link: https://commits.webkit.org/236073@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@275410 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2021-04-02 08:33:32 +00:00
|
|
|
/*
|
|
|
|
|
* Copyright (C) 2021 Apple Inc. All rights reserved.
|
|
|
|
|
*
|
|
|
|
|
* Redistribution and use in source and binary forms, with or without
|
|
|
|
|
* modification, are permitted provided that the following conditions
|
|
|
|
|
* are met:
|
|
|
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
|
|
|
* notice, this list of conditions and the following disclaimer.
|
|
|
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
|
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
|
|
|
* documentation and/or other materials provided with the distribution.
|
|
|
|
|
*
|
|
|
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
|
|
|
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
|
|
|
|
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
|
|
|
|
|
* DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
|
|
|
|
|
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
|
|
|
|
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
|
|
|
|
|
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
|
|
|
|
|
* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
|
|
|
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
#pragma once
|
|
|
|
|
|
|
|
|
|
#include <wtf/HashSet.h>
|
|
|
|
|
#include <wtf/RobinHoodHashTable.h>
|
|
|
|
|
|
|
|
|
|
namespace WTF {
|
|
|
|
|
|
|
|
|
|
// 95% load-factor.
|
|
|
|
|
template<typename ValueArg, typename HashArg = DefaultHash<ValueArg>, typename TraitsArg = HashTraits<ValueArg>>
|
|
|
|
|
using MemoryCompactLookupOnlyRobinHoodHashSet = HashSet<ValueArg, HashArg, TraitsArg, MemoryCompactLookupOnlyRobinHoodHashTableTraits>;
|
|
|
|
|
|
|
|
|
|
// 90% load-factor.
|
|
|
|
|
template<typename ValueArg, typename HashArg = DefaultHash<ValueArg>, typename TraitsArg = HashTraits<ValueArg>>
|
|
|
|
|
using MemoryCompactRobinHoodHashSet = HashSet<ValueArg, HashArg, TraitsArg, MemoryCompactRobinHoodHashTableTraits>;
|
|
|
|
|
|
|
|
|
|
// 75% load-factor.
|
|
|
|
|
template<typename ValueArg, typename HashArg = DefaultHash<ValueArg>, typename TraitsArg = HashTraits<ValueArg>>
|
|
|
|
|
using FastRobinHoodHashSet = HashSet<ValueArg, HashArg, TraitsArg, FastRobinHoodHashTableTraits>;
|
|
|
|
|
|
|
|
|
|
} // namespace WTF
|
|
|
|
|
|
|
|
|
|
using WTF::MemoryCompactLookupOnlyRobinHoodHashSet;
|
|
|
|
|
using WTF::MemoryCompactRobinHoodHashSet;
|
|
|
|
|
using WTF::FastRobinHoodHashSet;
|