haikuwebkit/Source/WTF/wtf/JSValueMalloc.h

84 lines
2.8 KiB
C
Raw Permalink Normal View History

[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. Canonical link: https://commits.webkit.org/196645@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225832 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2017-12-13 02:49:00 +00:00
/*
* Copyright (C) 2017 Yusuke Suzuki <utatane.tea@gmail.com>.
*
* 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. ``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
* 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/FastMalloc.h>
namespace WTF {
WTF_EXPORT_PRIVATE void* tryJSValueMalloc(size_t);
WTF_EXPORT_PRIVATE void* jsValueMalloc(size_t);
WTF_EXPORT_PRIVATE void* jsValueRealloc(void*, size_t);
WTF_EXPORT_PRIVATE void jsValueFree(void*);
#define WTF_MAKE_JSVALUE_ALLOCATED \
public: \
void* operator new(size_t, void* p) { return p; } \
void* operator new[](size_t, void* p) { return p; } \
\
void* operator new(size_t size) \
{ \
return ::WTF::jsValueMalloc(size); \
} \
\
void operator delete(void* p) \
{ \
::WTF::jsValueFree(p); \
} \
\
void* operator new[](size_t size) \
{ \
return ::WTF::jsValueMalloc(size); \
} \
\
void operator delete[](void* p) \
{ \
::WTF::jsValueFree(p); \
} \
void* operator new(size_t, NotNullTag, void* location) \
{ \
ASSERT(location); \
return location; \
} \
private: \
2021-06-21 18:48:29 +00:00
typedef int __thisIsHereToForceASemicolonAfterThisMacro UNUSED_TYPE_ALIAS
[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. Canonical link: https://commits.webkit.org/196645@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225832 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2017-12-13 02:49:00 +00:00
struct JSValueMalloc {
static void* malloc(size_t size) { return jsValueMalloc(size); }
static void* tryMalloc(size_t size) { return tryJSValueMalloc(size); }
static void* realloc(void* p, size_t size) { return jsValueRealloc(p, size); }
static void free(void* p) { jsValueFree(p); }
};
} // namespace WTF
using WTF::JSValueMalloc;
using WTF::jsValueMalloc;
using WTF::jsValueRealloc;
using WTF::jsValueFree;
using WTF::tryJSValueMalloc;