Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: b451fca37277a0b56042695981ba0efda1795d80
https://github.com/WebKit/WebKit/commit/b451fca37277a0b56042695981ba0efda1795d80
Author: Yijia Huang <yijia_hu...@apple.com>
Date: 2024-07-08 (Mon, 08 Jul 2024)
Changed paths:
A JSTests/microbenchmarks/js-map-get-int-no-dfg-no-inline.js
A JSTests/microbenchmarks/js-map-get-int.js
A JSTests/microbenchmarks/js-map-get-string-no-dfg-no-inline.js
A JSTests/microbenchmarks/js-map-get-string.js
A JSTests/microbenchmarks/js-map-set-int-no-dfg-no-inline.js
A JSTests/microbenchmarks/js-map-set-int.js
A JSTests/microbenchmarks/js-map-set-string-no-dfg-no-inline.js
A JSTests/microbenchmarks/js-map-set-string.js
A JSTests/stress/map-iterators-next-2.js
A JSTests/stress/set-iterators-next-2.js
M Source/JavaScriptCore/CMakeLists.txt
M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
M Source/JavaScriptCore/Sources.txt
M Source/JavaScriptCore/builtins/BuiltinNames.h
M Source/JavaScriptCore/builtins/MapIteratorPrototype.js
M Source/JavaScriptCore/builtins/MapPrototype.js
M Source/JavaScriptCore/builtins/SetIteratorPrototype.js
M Source/JavaScriptCore/builtins/SetPrototype.js
M Source/JavaScriptCore/bytecode/BytecodeIntrinsicRegistry.cpp
M Source/JavaScriptCore/bytecode/BytecodeIntrinsicRegistry.h
M Source/JavaScriptCore/bytecode/LinkTimeConstant.h
M Source/JavaScriptCore/bytecode/SpeculatedType.cpp
M Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
M Source/JavaScriptCore/dfg/DFGAbstractHeap.h
M Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
M Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
M Source/JavaScriptCore/dfg/DFGClobberize.h
M Source/JavaScriptCore/dfg/DFGDoesGC.cpp
M Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
M Source/JavaScriptCore/dfg/DFGHeapLocation.cpp
M Source/JavaScriptCore/dfg/DFGHeapLocation.h
M Source/JavaScriptCore/dfg/DFGNode.h
M Source/JavaScriptCore/dfg/DFGNodeType.h
M Source/JavaScriptCore/dfg/DFGOperations.cpp
M Source/JavaScriptCore/dfg/DFGOperations.h
M Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
M Source/JavaScriptCore/dfg/DFGSafeToExecute.h
M Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
M Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
M Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
M Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
M Source/JavaScriptCore/dfg/DFGUseKind.cpp
M Source/JavaScriptCore/dfg/DFGUseKind.h
M Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h
M Source/JavaScriptCore/ftl/FTLCapabilities.cpp
M Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
M Source/JavaScriptCore/heap/Heap.h
M Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp
A Source/JavaScriptCore/runtime/HashMapHelper.h
R Source/JavaScriptCore/runtime/HashMapImpl.cpp
R Source/JavaScriptCore/runtime/HashMapImpl.h
R Source/JavaScriptCore/runtime/HashMapImplInlines.h
M Source/JavaScriptCore/runtime/Intrinsic.h
M Source/JavaScriptCore/runtime/JSCJSValue.h
M Source/JavaScriptCore/runtime/JSGlobalObject.cpp
M Source/JavaScriptCore/runtime/JSGlobalObjectInlines.h
M Source/JavaScriptCore/runtime/JSImmutableButterfly.h
M Source/JavaScriptCore/runtime/JSMap.h
M Source/JavaScriptCore/runtime/JSMapInlines.h
M Source/JavaScriptCore/runtime/JSMapIterator.cpp
M Source/JavaScriptCore/runtime/JSMapIterator.h
M Source/JavaScriptCore/runtime/JSSet.h
M Source/JavaScriptCore/runtime/JSSetInlines.h
M Source/JavaScriptCore/runtime/JSSetIterator.cpp
M Source/JavaScriptCore/runtime/JSSetIterator.h
M Source/JavaScriptCore/runtime/MapConstructor.cpp
M Source/JavaScriptCore/runtime/MapConstructor.h
M Source/JavaScriptCore/runtime/MapPrototype.cpp
A Source/JavaScriptCore/runtime/OrderedHashTable.cpp
A Source/JavaScriptCore/runtime/OrderedHashTable.h
A Source/JavaScriptCore/runtime/OrderedHashTableHelper.h
M Source/JavaScriptCore/runtime/SetConstructor.cpp
M Source/JavaScriptCore/runtime/SetConstructor.h
M Source/JavaScriptCore/runtime/SetPrototype.cpp
M Source/JavaScriptCore/runtime/VM.cpp
M Source/JavaScriptCore/runtime/VM.h
M Source/JavaScriptCore/runtime/WeakMapImpl.h
M Source/JavaScriptCore/runtime/WeakMapImplInlines.h
M Source/JavaScriptCore/runtime/WeakSetPrototype.cpp
M Source/WebCore/bindings/js/JSDOMMapLike.cpp
M Source/WebCore/bindings/js/SerializedScriptValue.cpp
Log Message:
-----------
[JSC] Refine JSMap and JSSet with CloseTable
https://bugs.webkit.org/show_bug.cgi?id=274415
rdar://120931591
Reviewed by Yusuke Suzuki.
This patch enhances the implementation of JSMap and JSSet by replacing
the existing storage mechanism (HashMapImpl<HashMapBucket<Data>>) with
an OrderedHashTable. The new OrderedHashTable flattens the CloseTable[1]
structure into a single array, optimizing memory usage and improving
cache locality.
Microbenchmark results with 20 iterations:
without with
js-map-set-int 0.5624+-0.0070 ^
0.4446+-0.0069 ^ definitely 1.2651x faster
js-map-get-string-no-dfg-no-inline 5.3237+-0.0117 ^
5.1858+-0.0176 ^ definitely 1.0266x faster
js-map-get-int 1.3820+-0.0118 ^
1.2287+-0.0127 ^ definitely 1.1247x faster
js-map-set-int-no-dfg-no-inline 0.6037+-0.0069 ^
0.4741+-0.0073 ^ definitely 1.2734x faster
js-map-get-string 1.7580+-0.0118 ^
1.6399+-0.0158 ^ definitely 1.0721x faster
js-map-set-string-no-dfg-no-inline 0.8514+-0.0087 ^
0.7264+-0.0080 ^ definitely 1.1722x faster
js-map-get-int-no-dfg-no-inline 3.3643+-0.0109 ^
3.2791+-0.0116 ^ definitely 1.0260x faster
js-map-set-string 0.8092+-0.0092 ^
0.6811+-0.0091 ^ definitely 1.1881x faster
<geometric> 1.3356+-0.0070 ^
1.1714+-0.0075 ^ definitely 1.1402x faster
[1] https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
* JSTests/microbenchmarks/js-map-get-int-no-dfg-no-inline.js: Added.
(testSet):
(testGet):
* JSTests/microbenchmarks/js-map-get-int.js: Added.
(testSet):
(testGet):
* JSTests/microbenchmarks/js-map-get-string-no-dfg-no-inline.js: Added.
(testSet):
(testGet):
* JSTests/microbenchmarks/js-map-get-string.js: Added.
(testSet):
(testGet):
* JSTests/microbenchmarks/js-map-set-int-no-dfg-no-inline.js: Added.
(testSet):
* JSTests/microbenchmarks/js-map-set-int.js: Added.
(testSet):
* JSTests/microbenchmarks/js-map-set-string-no-dfg-no-inline.js: Added.
(testSet):
* JSTests/microbenchmarks/js-map-set-string.js: Added.
(testSet):
* JSTests/stress/map-iterators-next-2.js: Added.
(assert):
* JSTests/stress/set-iterators-next-2.js: Added.
(assert):
* Source/JavaScriptCore/CMakeLists.txt:
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/Sources.txt:
* Source/JavaScriptCore/builtins/BuiltinNames.h:
* Source/JavaScriptCore/builtins/MapIteratorPrototype.js:
(next):
(linkTimeConstant.mapIteratorNext): Deleted.
* Source/JavaScriptCore/builtins/MapPrototype.js:
(forEach):
* Source/JavaScriptCore/builtins/SetIteratorPrototype.js:
(next):
(linkTimeConstant.setIteratorNext): Deleted.
* Source/JavaScriptCore/builtins/SetPrototype.js:
(forEach):
(isSubsetOf):
* Source/JavaScriptCore/bytecode/BytecodeIntrinsicRegistry.cpp:
(JSC::BytecodeIntrinsicRegistry::BytecodeIntrinsicRegistry):
(JSC::BytecodeIntrinsicRegistry::orderedHashTableSentinelValue):
(JSC::BytecodeIntrinsicRegistry::sentinelMapBucketValue): Deleted.
(JSC::BytecodeIntrinsicRegistry::sentinelSetBucketValue): Deleted.
* Source/JavaScriptCore/bytecode/BytecodeIntrinsicRegistry.h:
* Source/JavaScriptCore/bytecode/LinkTimeConstant.h:
* Source/JavaScriptCore/bytecode/SpeculatedType.cpp:
(JSC::speculationFromClassInfoInheritance):
* Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:
(JSC::mapIteratorInternalFieldIndex):
(JSC::setIteratorInternalFieldIndex):
* Source/JavaScriptCore/dfg/DFGAbstractHeap.h:
* Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsicCall):
* Source/JavaScriptCore/dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* Source/JavaScriptCore/dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* Source/JavaScriptCore/dfg/DFGHeapLocation.cpp:
(WTF::printInternal):
* Source/JavaScriptCore/dfg/DFGHeapLocation.h:
* Source/JavaScriptCore/dfg/DFGNode.h:
(JSC::DFG::Node::hasHeapPrediction):
(JSC::DFG::Node::hasBucketOwnerType):
* Source/JavaScriptCore/dfg/DFGNodeType.h:
* Source/JavaScriptCore/dfg/DFGOperations.cpp:
(JSC::DFG::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/dfg/DFGOperations.h:
* Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:
* Source/JavaScriptCore/dfg/DFGSafeToExecute.h:
(JSC::DFG::SafeToExecuteEdge::operator()):
(JSC::DFG::safeToExecute):
* Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:
* Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h:
* Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compileGetMapIndexImpl):
(JSC::DFG::SpeculativeJIT::compileMapKeyIndex):
(JSC::DFG::SpeculativeJIT::compileMapValue):
(JSC::DFG::SpeculativeJIT::compile):
* Source/JavaScriptCore/dfg/DFGUseKind.cpp:
(WTF::printInternal):
* Source/JavaScriptCore/dfg/DFGUseKind.h:
(JSC::DFG::typeFilterFor):
(JSC::DFG::isCell):
* Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h:
* Source/JavaScriptCore/ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileCompareStrictEq):
* Source/JavaScriptCore/heap/Heap.h:
* Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp:
(Inspector::cloneMapIteratorObject):
(Inspector::cloneSetIteratorObject):
(Inspector::JSInjectedScriptHost::iteratorEntries):
* Source/JavaScriptCore/runtime/HashMapHelper.h: Added.
(JSC::areKeysEqual):
(JSC::normalizeMapKey):
(JSC::wangsInt64Hash):
(JSC::jsMapHash):
(JSC::jsMapHashImpl):
(JSC::jsMapHashForAlreadyHashedValue):
(JSC::concurrentJSMapHash):
(JSC::shouldShrink):
(JSC::shouldRehash):
(JSC::nextCapacity):
* Source/JavaScriptCore/runtime/HashMapImpl.cpp: Removed.
* Source/JavaScriptCore/runtime/HashMapImpl.h: Removed.
* Source/JavaScriptCore/runtime/HashMapImplInlines.h: Removed.
* Source/JavaScriptCore/runtime/Intrinsic.h:
* Source/JavaScriptCore/runtime/JSCJSValue.h:
(JSC::OrderedHashTableTraits::set):
(JSC::OrderedHashTableTraits::increment):
(JSC::OrderedHashTableTraits::decrement):
* Source/JavaScriptCore/runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* Source/JavaScriptCore/runtime/JSGlobalObjectInlines.h:
(JSC::createTuple):
* Source/JavaScriptCore/runtime/JSImmutableButterfly.h:
* Source/JavaScriptCore/runtime/JSMap.h:
* Source/JavaScriptCore/runtime/JSMapInlines.h:
* Source/JavaScriptCore/runtime/JSMapIterator.cpp:
(JSC::JSMapIterator::finishCreation):
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::JSMapIterator::createPair): Deleted.
* Source/JavaScriptCore/runtime/JSMapIterator.h:
* Source/JavaScriptCore/runtime/JSSet.h:
* Source/JavaScriptCore/runtime/JSSetInlines.h:
* Source/JavaScriptCore/runtime/JSSetIterator.cpp:
(JSC::JSSetIterator::finishCreation):
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::JSSetIterator::createPair): Deleted.
* Source/JavaScriptCore/runtime/JSSetIterator.h:
* Source/JavaScriptCore/runtime/MapConstructor.cpp:
(JSC::JSC_DEFINE_HOST_FUNCTION):
* Source/JavaScriptCore/runtime/MapConstructor.h:
* Source/JavaScriptCore/runtime/MapPrototype.cpp:
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::createMapIteratorObject):
* Source/JavaScriptCore/runtime/OrderedHashTable.cpp: Copied from
Source/JavaScriptCore/runtime/JSMapInlines.h.
(JSC::OrderedHashTable<Traits>::visitChildrenImpl):
* Source/JavaScriptCore/runtime/OrderedHashTable.h: Added.
(JSC::OrderedHashTable::OrderedHashTable):
(JSC::OrderedHashTable::offsetOfButterfly):
(JSC::OrderedHashTable::finishCreation):
(JSC::OrderedHashTable::getKeyIndex):
(JSC::OrderedHashTable::has):
(JSC::OrderedHashTable::add):
(JSC::OrderedHashTable::addNormalized):
(JSC::OrderedHashTable::remove):
(JSC::OrderedHashTable::removeNormalized):
(JSC::OrderedHashTable::size):
(JSC::OrderedHashTable::clear):
(JSC::OrderedHashTable::materializeIfNeeded):
(JSC::OrderedHashTable::storageOrSentinel):
(JSC::OrderedHashTable::storageRef):
(JSC::OrderedHashMap::OrderedHashMap):
(JSC::OrderedHashMap::getImpl):
(JSC::OrderedHashMap::get):
(JSC::OrderedHashMap::createSentinel):
(JSC::OrderedHashMap::createDeletedValue):
(JSC::OrderedHashSet::OrderedHashSet):
* Source/JavaScriptCore/runtime/OrderedHashTableHelper.h: Added.
(JSC::OrderedHashTableHelper::toNumber):
(JSC::OrderedHashTableHelper::asNumber):
(JSC::OrderedHashTableHelper::toJSValue):
(JSC::OrderedHashTableHelper::isDeleted):
(JSC::OrderedHashTableHelper::isValidTableIndex):
(JSC::OrderedHashTableHelper::invalidTableIndex):
(JSC::OrderedHashTableHelper::get):
(JSC::OrderedHashTableHelper::slot):
(JSC::OrderedHashTableHelper::set):
(JSC::OrderedHashTableHelper::setWithWriteBarrier):
(JSC::OrderedHashTableHelper::aliveEntryCountIndex):
(JSC::OrderedHashTableHelper::deletedEntryCountIndex):
(JSC::OrderedHashTableHelper::capacityIndex):
(JSC::OrderedHashTableHelper::iterationEntryIndex):
(JSC::OrderedHashTableHelper::aliveEntryCount):
(JSC::OrderedHashTableHelper::deletedEntryCount):
(JSC::OrderedHashTableHelper::usedCapacity):
(JSC::OrderedHashTableHelper::capacity):
(JSC::OrderedHashTableHelper::iterationEntry):
(JSC::OrderedHashTableHelper::incrementAliveEntryCount):
(JSC::OrderedHashTableHelper::decrementAliveEntryCount):
(JSC::OrderedHashTableHelper::incrementDeletedEntryCount):
(JSC::OrderedHashTableHelper::bucketCount):
(JSC::OrderedHashTableHelper::hashTableStartIndex):
(JSC::OrderedHashTableHelper::hashTableEndIndex):
(JSC::OrderedHashTableHelper::bucketIndex):
(JSC::OrderedHashTableHelper::dataTableSize):
(JSC::OrderedHashTableHelper::dataTableStartIndex):
(JSC::OrderedHashTableHelper::dataTableEndIndex):
(JSC::OrderedHashTableHelper::entryDataStartIndex):
(JSC::OrderedHashTableHelper::setKeyOrValueData):
(JSC::OrderedHashTableHelper::deleteData):
(JSC::OrderedHashTableHelper::addToChain):
(JSC::OrderedHashTableHelper::tableSize):
(JSC::OrderedHashTableHelper::tableSizeSlow):
(JSC::OrderedHashTableHelper::isObsolete):
(JSC::OrderedHashTableHelper::nextTable):
(JSC::OrderedHashTableHelper::setNextTable):
(JSC::OrderedHashTableHelper::deletedEntriesStartIndex):
(JSC::OrderedHashTableHelper::isCleared):
(JSC::OrderedHashTableHelper::setClearedTableSentinel):
(JSC::OrderedHashTableHelper::tryCreate):
(JSC::OrderedHashTableHelper::copyImpl):
(JSC::OrderedHashTableHelper::copy):
(JSC::OrderedHashTableHelper::rehash):
(JSC::OrderedHashTableHelper::clear):
(JSC::OrderedHashTableHelper::find):
(JSC::OrderedHashTableHelper::expandIfNeeded):
(JSC::OrderedHashTableHelper::addImpl):
(JSC::OrderedHashTableHelper::add):
(JSC::OrderedHashTableHelper::addNormalized):
(JSC::OrderedHashTableHelper::shrinkIfNeed):
(JSC::OrderedHashTableHelper::removeImpl):
(JSC::OrderedHashTableHelper::remove):
(JSC::OrderedHashTableHelper::removeNormalized):
(JSC::OrderedHashTableHelper::transit):
(JSC::OrderedHashTableHelper::transitAndNext):
(JSC::OrderedHashTableHelper::getKey):
(JSC::OrderedHashTableHelper::getValue):
(JSC::OrderedHashTableHelper::nextAndUpdateIterationEntry):
(JSC::OrderedHashTableHelper::getIterationEntry):
(JSC::OrderedHashTableHelper::getIterationEntryKey):
(JSC::OrderedHashTableHelper::getIterationEntryValue):
* Source/JavaScriptCore/runtime/SetConstructor.cpp:
(JSC::JSC_DEFINE_HOST_FUNCTION):
* Source/JavaScriptCore/runtime/SetConstructor.h:
* Source/JavaScriptCore/runtime/SetPrototype.cpp:
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::createSetIteratorObject):
* Source/JavaScriptCore/runtime/VM.cpp:
(JSC::VM::VM):
(JSC::VM::orderedHashTableDeletedValueSlow):
(JSC::VM::orderedHashTableSentinelSlow):
(JSC::VM::visitAggregateImpl):
(JSC::VM::sentinelSetBucketSlow): Deleted.
(JSC::VM::sentinelMapBucketSlow): Deleted.
* Source/JavaScriptCore/runtime/VM.h:
(JSC::VM::orderedHashTableDeletedValue):
(JSC::VM::orderedHashTableSentinel):
(JSC::VM::sentinelSetBucket): Deleted.
(JSC::VM::sentinelMapBucket): Deleted.
* Source/JavaScriptCore/runtime/WeakMapImpl.h:
* Source/JavaScriptCore/runtime/WeakMapImplInlines.h:
* Source/JavaScriptCore/runtime/WeakSetPrototype.cpp:
* Source/WebCore/bindings/js/JSDOMMapLike.cpp:
* Source/WebCore/bindings/js/SerializedScriptValue.cpp:
(WebCore::CloneSerializer::serialize):
Canonical link: https://commits.webkit.org/280734@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
