[JSC] Implement optimized WeakMap and WeakSet
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 13 Dec 2017 02:49:00 +0000 (02:49 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 13 Dec 2017 02:49:00 +0000 (02:49 +0000)
commit7f37bf2ef9cf95c112c8dc35c403c5ae9fc43025
tree338e38bbbacdd95a3cf60538264f39e5da17d6f5
parent762287df4ef810683a735318422c077c72e90c90
[JSC] Implement optimized WeakMap and WeakSet
https://bugs.webkit.org/show_bug.cgi?id=179929

Reviewed by Saam Barati.

JSTests:

* microbenchmarks/weak-map-key.js:
* microbenchmarks/weak-set-key.js: Copied from JSTests/microbenchmarks/weak-map-key.js.
(assert):
(objectKey):
(let.start.Date.now):
* stress/basic-weakmap.js: Added.
(shouldBe):
(test):
* stress/basic-weakset.js: Added.
(shouldBe):
(test.set new):
* stress/weakmap-cse-set-break.js: Added.
(shouldBe):
(test):
* stress/weakmap-cse.js: Added.
(shouldBe):
(test):
* stress/weakmap-gc.js: Added.
(test):
* stress/weakset-cse-add-break.js: Added.
(shouldBe):
(test.set new):
* stress/weakset-cse.js: Added.
(shouldBe):
(test.set new):
* stress/weakset-gc.js: Added.
(test.set add):
(test.set new):
(test):

Source/JavaScriptCore:

This patch introduces WeakMapImpl to optimize WeakMap and WeakSet.
This is similar to HashMapImpl. But,

1. WeakMapImpl's bucket is not allocated in GC heap since WeakMap
do not need to have iterators.

2. WeakMapImpl's buffer is allocated in JSValue Gigacage instead
of auxiliary buffer. This is because we would like to allocate buffer
when finalizing GC. At that time, WeakMapImpl prunes dead entries and
shrink it if necessary. However, allocating from the GC heap during
finalization is not allowed.

In particular, (2) is important since it ensures any WeakMap operations
do not cause GC. Since GC may collect dead keys in WeakMap, rehash WeakMap,
and reallocate/change WeakMap's buffer, ensuring that any WeakMap operations
do not cause GC makes our implementation simple. To ensure this, we place
DisallowGC for each WeakMap's interface.

In DFG, we introduce WeakMapGet and ExtractValueFromWeakMapGet nodes.
WeakMapGet looks up entry in WeakMapImpl and returns value. If it is
WeakMap, it returns value. And it returns key if it is WeakSet. If it
does not find a corresponding entry, it returns JSEmpty.
ExtractValueFromWeakMapGet converts JSEmpty to JSUndefined.

This patch improves WeakMap and WeakSet operations.

                             baseline                  patched

    weak-set-key        240.6932+-10.4923    ^    148.7606+-6.1784        ^ definitely 1.6180x faster
    weak-map-key        174.3176+-8.2680     ^    151.7053+-6.8723        ^ definitely 1.1491x faster

* JavaScriptCore.xcodeproj/project.pbxproj:
* Sources.txt:
* dfg/DFGAbstractHeap.h:
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsicCall):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGNode.h:
(JSC::DFG::Node::hasHeapPrediction):
* dfg/DFGNodeType.h:
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileExtractValueFromWeakMapGet):
(JSC::DFG::SpeculativeJIT::compileWeakMapGet):
* dfg/DFGSpeculativeJIT.h:
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLAbstractHeapRepository.h:
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileExtractValueFromWeakMapGet):
(JSC::FTL::DFG::LowerDFGToB3::compileWeakMapGet):
* inspector/JSInjectedScriptHost.cpp:
(Inspector::JSInjectedScriptHost::weakMapEntries):
(Inspector::JSInjectedScriptHost::weakSetEntries):
Existing code is incorrect. They can run GC and break WeakMap's iterator.
We introduce takeSnapshot function to WeakMapImpl, which retrieves live
entries without causing any GC.

* runtime/HashMapImpl.h:
(JSC::shouldShrink):
(JSC::shouldRehashAfterAdd):
(JSC::nextCapacity):
(JSC::HashMapImpl::shouldRehashAfterAdd const):
(JSC::HashMapImpl::shouldShrink const):
(JSC::HashMapImpl::rehash):
(JSC::WeakMapHash::hash): Deleted.
(JSC::WeakMapHash::equal): Deleted.
* runtime/Intrinsic.cpp:
(JSC::intrinsicName):
* runtime/Intrinsic.h:
* runtime/JSWeakMap.cpp:
* runtime/JSWeakMap.h:
* runtime/JSWeakSet.cpp:
* runtime/JSWeakSet.h:
* runtime/VM.cpp:
* runtime/WeakGCMap.h:
(JSC::WeakGCMap::forEach): Deleted.
* runtime/WeakMapBase.cpp: Removed.
* runtime/WeakMapBase.h: Removed.
* runtime/WeakMapConstructor.cpp:
(JSC::constructWeakMap):
* runtime/WeakMapImpl.cpp: Added.
(JSC::WeakMapImpl<WeakMapBucket>::destroy):
(JSC::WeakMapImpl<WeakMapBucket>::visitChildren):
(JSC::WeakMapImpl<WeakMapBucket>::estimatedSize):
(JSC::WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>::visitWeakReferences):
(JSC::WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>::visitWeakReferences):
(JSC::WeakMapImpl<WeakMapBucket>::finalizeUnconditionally):
(JSC::WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>::takeSnapshot):
(JSC::WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>::takeSnapshot):
* runtime/WeakMapImpl.h: Added.
(JSC::jsWeakMapHash):
(JSC::nextCapacityAfterRemoveBatching):
(JSC::WeakMapBucket::setKey):
(JSC::WeakMapBucket::setValue):
(JSC::WeakMapBucket::key const):
(JSC::WeakMapBucket::value const):
(JSC::WeakMapBucket::copyFrom):
(JSC::WeakMapBucket::offsetOfKey):
(JSC::WeakMapBucket::offsetOfValue):
(JSC::WeakMapBucket::extractValue):
(JSC::WeakMapBucket::isEmpty):
(JSC::WeakMapBucket::deletedKey):
(JSC::WeakMapBucket::isDeleted):
(JSC::WeakMapBucket::makeDeleted):
(JSC::WeakMapBucket::visitAggregate):
(JSC::WeakMapBucket::clearValue):
(JSC::WeakMapBuffer::allocationSize):
(JSC::WeakMapBuffer::buffer const):
(JSC::WeakMapBuffer::create):
(JSC::WeakMapBuffer::reset):
(JSC::WeakMapImpl::WeakMapImpl):
(JSC::WeakMapImpl::finishCreation):
(JSC::WeakMapImpl::get):
(JSC::WeakMapImpl::has):
(JSC::WeakMapImpl::add):
(JSC::WeakMapImpl::remove):
(JSC::WeakMapImpl::size const):
(JSC::WeakMapImpl::offsetOfBuffer):
(JSC::WeakMapImpl::offsetOfCapacity):
(JSC::WeakMapImpl::findBucket):
(JSC::WeakMapImpl::buffer const):
(JSC::WeakMapImpl::forEach):
(JSC::WeakMapImpl::shouldRehashAfterAdd const):
(JSC::WeakMapImpl::shouldShrink const):
(JSC::WeakMapImpl::canUseBucket):
(JSC::WeakMapImpl::addInternal):
(JSC::WeakMapImpl::findBucketAlreadyHashed):
(JSC::WeakMapImpl::rehash):
(JSC::WeakMapImpl::checkConsistency const):
(JSC::WeakMapImpl::makeAndSetNewBuffer):
(JSC::WeakMapImpl::assertBufferIsEmpty const):
(JSC::WeakMapImpl::DeadKeyCleaner::target):
* runtime/WeakMapPrototype.cpp:
(JSC::WeakMapPrototype::finishCreation):
(JSC::protoFuncWeakMapGet):
(JSC::protoFuncWeakMapHas):
* runtime/WeakSetConstructor.cpp:
(JSC::constructWeakSet):
* runtime/WeakSetPrototype.cpp:
(JSC::WeakSetPrototype::finishCreation):
(JSC::protoFuncWeakSetHas):
(JSC::protoFuncWeakSetAdd):

Source/WTF:

We introduce JSValueMalloc, which is specialized malloc scheme with Gigacage::JSValue.
This is used for WeakMapImpl's buffer.

* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/JSValueMalloc.cpp: Added.
(WTF::tryJSValueMalloc):
(WTF::jsValueMalloc):
(WTF::jsValueRealloc):
(WTF::jsValueFree):
* wtf/JSValueMalloc.h: Added.
(WTF::JSValueMalloc::malloc):
(WTF::JSValueMalloc::tryMalloc):
(WTF::JSValueMalloc::realloc):
(WTF::JSValueMalloc::free):
* wtf/MallocPtr.h:
(WTF::MallocPtr::~MallocPtr):
(WTF::MallocPtr::malloc):
(WTF::MallocPtr::tryMalloc):
(WTF::MallocPtr::realloc):
We extend MallocPtr to adopt malloc scheme as its template parameter.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225832 268f45cc-cd09-0410-ab3c-d52691b4dbfc
57 files changed:
JSTests/ChangeLog
JSTests/microbenchmarks/weak-map-key.js
JSTests/microbenchmarks/weak-set-key.js [new file with mode: 0644]
JSTests/stress/basic-weakmap.js [new file with mode: 0644]
JSTests/stress/basic-weakset.js [new file with mode: 0644]
JSTests/stress/weakmap-cse-set-break.js [new file with mode: 0644]
JSTests/stress/weakmap-cse.js [new file with mode: 0644]
JSTests/stress/weakmap-gc.js [new file with mode: 0644]
JSTests/stress/weakset-cse-add-break.js [new file with mode: 0644]
JSTests/stress/weakset-cse.js [new file with mode: 0644]
JSTests/stress/weakset-gc.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Sources.txt
Source/JavaScriptCore/dfg/DFGAbstractHeap.h
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLAbstractHeapRepository.h
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/inspector/JSInjectedScriptHost.cpp
Source/JavaScriptCore/runtime/HashMapImpl.h
Source/JavaScriptCore/runtime/Intrinsic.cpp
Source/JavaScriptCore/runtime/Intrinsic.h
Source/JavaScriptCore/runtime/JSWeakMap.cpp
Source/JavaScriptCore/runtime/JSWeakMap.h
Source/JavaScriptCore/runtime/JSWeakSet.cpp
Source/JavaScriptCore/runtime/JSWeakSet.h
Source/JavaScriptCore/runtime/VM.cpp
Source/JavaScriptCore/runtime/WeakGCMap.h
Source/JavaScriptCore/runtime/WeakMapBase.cpp [deleted file]
Source/JavaScriptCore/runtime/WeakMapBase.h [deleted file]
Source/JavaScriptCore/runtime/WeakMapConstructor.cpp
Source/JavaScriptCore/runtime/WeakMapImpl.cpp [new file with mode: 0644]
Source/JavaScriptCore/runtime/WeakMapImpl.h [new file with mode: 0644]
Source/JavaScriptCore/runtime/WeakMapPrototype.cpp
Source/JavaScriptCore/runtime/WeakSetConstructor.cpp
Source/JavaScriptCore/runtime/WeakSetPrototype.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/JSValueMalloc.cpp [new file with mode: 0644]
Source/WTF/wtf/JSValueMalloc.h [new file with mode: 0644]
Source/WTF/wtf/MallocPtr.h