[webkit-changes] [WebKit/WebKit] 18d37d: [JSC] Add megamorphic cache

Yusuke Suzuki noreply at github.com
Mon Apr 10 23:13:22 PDT 2023 

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 18d37d9fc2a08b00884449570d8d1011f0df2e95
      https://github.com/WebKit/WebKit/commit/18d37d9fc2a08b00884449570d8d1011f0df2e95
  Author: Yusuke Suzuki <ysuzuki at apple.com>
  Date:   2023-04-10 (Mon, 10 Apr 2023)

  Changed paths:
    A JSTests/microbenchmarks/megamorphic-miss.js
    A JSTests/microbenchmarks/megamorphic-own-load.js
    A JSTests/microbenchmarks/megamorphic-prototype-load.js
    M Source/JavaScriptCore/CMakeLists.txt
    M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
    M Source/JavaScriptCore/Sources.txt
    M Source/JavaScriptCore/bytecode/AccessCase.cpp
    M Source/JavaScriptCore/bytecode/AccessCase.h
    M Source/JavaScriptCore/bytecode/CheckPrivateBrandStatus.cpp
    M Source/JavaScriptCore/bytecode/DeleteByStatus.cpp
    M Source/JavaScriptCore/bytecode/GetByStatus.cpp
    M Source/JavaScriptCore/bytecode/InByStatus.h
    M Source/JavaScriptCore/bytecode/InlineCacheCompiler.cpp
    M Source/JavaScriptCore/bytecode/InlineCacheCompiler.h
    M Source/JavaScriptCore/bytecode/InstanceOfStatus.h
    M Source/JavaScriptCore/bytecode/PutByStatus.cpp
    M Source/JavaScriptCore/bytecode/Repatch.cpp
    M Source/JavaScriptCore/bytecode/Repatch.h
    M Source/JavaScriptCore/bytecode/SetPrivateBrandStatus.cpp
    M Source/JavaScriptCore/bytecode/StructureStubInfo.cpp
    M Source/JavaScriptCore/bytecode/StructureStubInfo.h
    M Source/JavaScriptCore/bytecode/StubInfoSummary.cpp
    M Source/JavaScriptCore/bytecode/StubInfoSummary.h
    M Source/JavaScriptCore/dfg/DFGOperations.cpp
    M Source/JavaScriptCore/heap/Heap.cpp
    M Source/JavaScriptCore/jit/JITOperations.cpp
    M Source/JavaScriptCore/jit/JITOperations.h
    M Source/JavaScriptCore/llint/LLIntSlowPaths.cpp
    M Source/JavaScriptCore/runtime/CommonSlowPaths.cpp
    M Source/JavaScriptCore/runtime/HasOwnPropertyCache.h
    M Source/JavaScriptCore/runtime/JSGlobalObject.cpp
    M Source/JavaScriptCore/runtime/JSObject.cpp
    M Source/JavaScriptCore/runtime/JSObject.h
    M Source/JavaScriptCore/runtime/JSObjectInlines.h
    A Source/JavaScriptCore/runtime/MegamorphicCache.cpp
    A Source/JavaScriptCore/runtime/MegamorphicCache.h
    M Source/JavaScriptCore/runtime/ObjectPrototype.cpp
    M Source/JavaScriptCore/runtime/Structure.cpp
    M Source/JavaScriptCore/runtime/Structure.h
    M Source/JavaScriptCore/runtime/StructureCache.cpp
    M Source/JavaScriptCore/runtime/StructureInlines.h
    M Source/JavaScriptCore/runtime/StructureTransitionTable.h
    M Source/JavaScriptCore/runtime/VM.cpp
    M Source/JavaScriptCore/runtime/VM.h
    M Source/WebCore/bindings/js/JSDOMAsyncIterator.h
    M Source/WebCore/bindings/js/JSDOMBuiltinConstructor.h
    M Source/WebCore/bindings/js/JSDOMConstructor.h
    M Source/WebCore/bindings/js/JSDOMConstructorNotCallable.h
    M Source/WebCore/bindings/js/JSDOMConstructorNotConstructable.h
    M Source/WebCore/bindings/js/JSDOMIterator.h
    M Source/WebCore/bindings/js/JSWindowProxy.cpp
    M Source/WebCore/bindings/scripts/CodeGeneratorJS.pm
    M Source/WebCore/bindings/scripts/test/JS/JSExposedStar.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSExposedToWorkerAndWindow.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestAsyncIterable.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestAsyncKeyValueIterable.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestCEReactions.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestCEReactionsStringifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestCallTracer.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestClassWithJSBuiltinConstructor.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestConditionalIncludes.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestConditionallyReadWrite.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDOMJIT.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDefaultToJSON.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDefaultToJSONFilteredByExposed.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDefaultToJSONIndirectInheritance.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDefaultToJSONInherit.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDefaultToJSONInheritFinal.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDelegateToSharedSyntheticAttribute.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestDomainSecurity.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestEnabledBySetting.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestEnabledForContext.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestEventConstructor.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestEventTarget.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestException.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestGenerateAddOpaqueRoot.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestGenerateIsReachable.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestIndexedSetterNoIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestIndexedSetterThrowingException.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestIndexedSetterWithIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestInterface.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestInterfaceLeadingUnderscore.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestIterable.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestJSBuiltinConstructor.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestLegacyFactoryFunction.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestLegacyNoInterfaceObject.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestLegacyOverrideBuiltIns.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestMapLike.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestMapLikeWithOverriddenOperations.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedAndIndexedSetterNoIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedAndIndexedSetterThrowingException.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedAndIndexedSetterWithIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedDeleterNoIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedDeleterThrowingException.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedDeleterWithIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedDeleterWithIndexedGetter.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedGetterCallWith.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedGetterNoIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedGetterWithIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterNoIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterThrowingException.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithIdentifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithIndexedGetter.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithIndexedGetterAndSetter.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithLegacyOverrideBuiltIns.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithLegacyUnforgeableProperties.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNamedSetterWithLegacyUnforgeablePropertiesAndLegacyOverrideBuiltIns.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestNode.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestObj.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestOperationConditional.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestOverloadedConstructors.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestOverloadedConstructorsWithSequence.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestPluginInterface.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestPromiseRejectionEvent.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestReadOnlyMapLike.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestReadOnlySetLike.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestReportExtraMemoryCost.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestSerializedScriptValueInterface.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestSetLike.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestSetLikeWithOverriddenOperations.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifier.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierAnonymousOperation.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierNamedOperation.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierOperationImplementedAs.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierOperationNamedToString.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierReadOnlyAttribute.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestStringifierReadWriteAttribute.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestTaggedWrapper.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSTestTypedefs.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSWorkerGlobalScope.cpp
    M Source/WebCore/bindings/scripts/test/JS/JSWorkletGlobalScope.cpp
    M Source/WebCore/workers/WorkerOrWorkletScriptController.cpp

  Log Message:
  -----------
  [JSC] Add megamorphic cache
https://bugs.webkit.org/show_bug.cgi?id=255060
rdar://problem/107683366

Reviewed by Justin Michaud.

This patch adds megamorphic load cache finally, which exists in SpiderMonkey and V8. Our plan is adding megamorphic store cache next.

1. We move mayBePrototype bit from object cell to Structure. This allows us to disable IC setup for prototype objects by observing Structure.
   (And this is extremely rare). And every time we do some modification of the object, we can check `mayBePrototype()` and we can invalidate
   megamorphic cache integrity (VM::invalidateStructureChainIntegrity). This bit & transition happens automatically when an object gets used as a prototype.
   But we mark all DOM prototypes and constructors a priori since they become prototype objects.
2. We integrate megamorphic load cache, which is 2-level hash table with 2 different hash functions. Primary table has 2048 entries and secondaryHash
   table has 512 entries, which is derived number from V8's megamorphic cache implementation. Our megamorphic cache's entry is StructureID + UniquedStringImpl.
   And the result is holder object and offset. Holder is null if property is missed. And holder is special marker (0x2) if it is own property.
   Every time objects used for prototype gets changed, whole megamorphic cache gets invalidated by incrementing epoch. This is surprisingly rare since
   we do not modify objects used for prototype after creating instances (And once the page gets stable state, we do not modify prototype objects).
   We use 2-level cache with 2 completely different hash functions to make it work well for various StructureID + UniquedStringImpl* pair.
3. We increment epoch of megamorphic cache when GC happens. So we do not keep entries valid over GC.

This change roughly offers 2-3x performance improvement for megamorphic access.

                                           ToT                     Patched

    megamorphic-own-load             99.3922+-1.9842     ^     41.2465+-0.0893        ^ definitely 2.4097x faster
    megamorphic-load                 14.8899+-0.0635     ^      5.0489+-0.0328        ^ definitely 2.9491x faster
    megamorphic-prototype-load      136.9894+-0.6358     ^     38.1426+-0.0790        ^ definitely 3.5915x faster
    megamorphic-miss                 98.3712+-1.6652     ^     31.9041+-0.0640        ^ definitely 3.0833x faster

* JSTests/microbenchmarks/megamorphic-miss.js: Added.
(f):
* JSTests/microbenchmarks/megamorphic-own-load.js: Added.
(f):
* JSTests/microbenchmarks/megamorphic-prototype-load.js: Added.
(f):
* Source/JavaScriptCore/CMakeLists.txt:
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/Sources.txt:
* Source/JavaScriptCore/bytecode/AccessCase.cpp:
(JSC::AccessCase::create):
(JSC::AccessCase::guardedByStructureCheckSkippingConstantIdentifierCheck const):
(JSC::AccessCase::requiresIdentifierNameMatch const):
(JSC::AccessCase::requiresInt32PropertyCheck const):
(JSC::AccessCase::needsScratchFPR const):
(JSC::AccessCase::forEachDependentCell const):
(JSC::AccessCase::doesCalls const):
(JSC::AccessCase::canReplace const):
(JSC::AccessCase::runWithDowncast):
(JSC::AccessCase::canBeShared):
* Source/JavaScriptCore/bytecode/AccessCase.h:
* Source/JavaScriptCore/bytecode/CheckPrivateBrandStatus.cpp:
(JSC::CheckPrivateBrandStatus::CheckPrivateBrandStatus):
* Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:
(JSC::DeleteByStatus::DeleteByStatus):
* Source/JavaScriptCore/bytecode/GetByStatus.cpp:
(JSC::GetByStatus::GetByStatus):
* Source/JavaScriptCore/bytecode/InByStatus.h:
* Source/JavaScriptCore/bytecode/InlineCacheCompiler.cpp:
(JSC::InlineCacheCompiler::generateWithGuard):
(JSC::InlineCacheCompiler::generateImpl):
(JSC::InlineCacheCompiler::regenerate):
(WTF::printInternal):
* Source/JavaScriptCore/bytecode/InlineCacheCompiler.h:
(JSC::AccessGenerationResult::AccessGenerationResult):
(JSC::AccessGenerationResult::generatedMegamorphicCode const):
(JSC::AccessGenerationResult::generatedSomeCode const):
* Source/JavaScriptCore/bytecode/InstanceOfStatus.h:
* Source/JavaScriptCore/bytecode/PutByStatus.cpp:
(JSC::PutByStatus::PutByStatus):
(JSC::PutByStatus::computeFor):
* Source/JavaScriptCore/bytecode/Repatch.cpp:
(JSC::tryCacheGetBy):
(JSC::repatchGetBy):
(JSC::repatchGetBySlowPathCall):
(JSC::tryCachePutBy):
(JSC::tryCacheDeleteBy):
* Source/JavaScriptCore/bytecode/Repatch.h:
* Source/JavaScriptCore/bytecode/SetPrivateBrandStatus.cpp:
(JSC::SetPrivateBrandStatus::SetPrivateBrandStatus):
* Source/JavaScriptCore/bytecode/StructureStubInfo.cpp:
(JSC::StructureStubInfo::summary const):
* Source/JavaScriptCore/bytecode/StructureStubInfo.h:
(JSC::StructureStubInfo::considerCachingGeneric):
(JSC::StructureStubInfo::considerCachingBy):
(JSC::StructureStubInfo::considerCachingMegamorphic):
(JSC::StructureStubInfo::considerCachingImpl):
(JSC::StructureStubInfo::considerCaching): Deleted.
* Source/JavaScriptCore/bytecode/StubInfoSummary.cpp:
(WTF::printInternal):
* Source/JavaScriptCore/bytecode/StubInfoSummary.h:
(JSC::isInlineable):
(JSC::slowVersion):
* Source/JavaScriptCore/dfg/DFGOperations.cpp:
(JSC::DFG::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/heap/Heap.cpp:
(JSC::Heap::finalize):
* Source/JavaScriptCore/jit/JITOperations.cpp:
(JSC::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/jit/JITOperations.h:
* Source/JavaScriptCore/llint/LLIntSlowPaths.cpp:
(JSC::LLInt::LLINT_SLOW_PATH_DECL):
* Source/JavaScriptCore/runtime/CommonSlowPaths.cpp:
(JSC::JSC_DEFINE_COMMON_SLOW_PATH):
* Source/JavaScriptCore/runtime/HasOwnPropertyCache.h:
(JSC::VM::ensureHasOwnPropertyCache):
* Source/JavaScriptCore/runtime/JSGlobalObject.cpp:
(JSC::JSGlobalObject::init):
* Source/JavaScriptCore/runtime/JSObject.cpp:
(JSC::JSObject::setPrototypeDirect):
(JSC::JSObject::deleteProperty):
* Source/JavaScriptCore/runtime/JSObject.h:
* Source/JavaScriptCore/runtime/JSObjectInlines.h:
(JSC::JSObject::prepareToPutDirectWithoutTransition):
(JSC::JSObject::putDirectInternal):
(JSC::JSObject::mayBePrototype const):
(JSC::JSObject::didBecomePrototype):
* Source/JavaScriptCore/runtime/MegamorphicCache.cpp: Copied from Source/JavaScriptCore/bytecode/StubInfoSummary.cpp.
(JSC::MegamorphicCache::age):
(JSC::MegamorphicCache::clearEntries):
* Source/JavaScriptCore/runtime/MegamorphicCache.h: Added.
(JSC::MegamorphicCache::Entry::offsetOfUid):
(JSC::MegamorphicCache::Entry::offsetOfStructureID):
(JSC::MegamorphicCache::Entry::offsetOfEpoch):
(JSC::MegamorphicCache::Entry::offsetOfOffset):
(JSC::MegamorphicCache::Entry::offsetOfHolder):
(JSC::MegamorphicCache::Entry::initAsMiss):
(JSC::MegamorphicCache::Entry::initAsHit):
(JSC::MegamorphicCache::offsetOfPrimaryEntries):
(JSC::MegamorphicCache::offsetOfSecondaryEntries):
(JSC::MegamorphicCache::offsetOfEpoch):
(JSC::MegamorphicCache::primaryHash):
(JSC::MegamorphicCache::secondaryHash):
(JSC::MegamorphicCache::initAsMiss):
(JSC::MegamorphicCache::initAsHit):
(JSC::MegamorphicCache::epoch const):
(JSC::MegamorphicCache::bumpEpoch):
* Source/JavaScriptCore/runtime/ObjectPrototype.cpp:
(JSC::objectPrototypeHasOwnProperty):
* Source/JavaScriptCore/runtime/Structure.cpp:
(JSC::Structure::Structure):
(JSC::Structure::becomePrototypeTransition):
(JSC::Structure::nonPropertyTransitionSlow):
* Source/JavaScriptCore/runtime/Structure.h:
* Source/JavaScriptCore/runtime/StructureCache.cpp:
(JSC::StructureCache::createEmptyStructure):
* Source/JavaScriptCore/runtime/StructureInlines.h:
(JSC::Structure::create):
(JSC::Structure::nonPropertyTransition):
* Source/JavaScriptCore/runtime/StructureTransitionTable.h:
* Source/JavaScriptCore/runtime/VM.cpp:
(JSC::VM::VM):
(JSC::VM::ensureMegamorphicCacheSlow):
(JSC::VM::invalidateStructureChainIntegrity):
* Source/JavaScriptCore/runtime/VM.h:
(JSC::VM::megamorphicCache):
(JSC::VM::ensureMegamorphicCache):
* Source/WebCore/bindings/js/JSDOMAsyncIterator.h:
(WebCore::JSDOMAsyncIteratorBase::createPrototype):
* Source/WebCore/bindings/js/JSDOMBuiltinConstructor.h:
(WebCore::JSDOMBuiltinConstructor<JSClass>::createStructure):
* Source/WebCore/bindings/js/JSDOMConstructor.h:
(WebCore::JSDOMConstructor<JSClass>::createStructure):
* Source/WebCore/bindings/js/JSDOMConstructorNotCallable.h:
(WebCore::JSDOMConstructorNotCallable<JSClass>::createStructure):
* Source/WebCore/bindings/js/JSDOMConstructorNotConstructable.h:
(WebCore::JSDOMConstructorNotConstructable<JSClass>::createStructure):
* Source/WebCore/bindings/js/JSDOMIterator.h:
(WebCore::JSDOMIteratorBase::createPrototype):
* Source/WebCore/bindings/js/JSWindowProxy.cpp:
(WebCore::JSWindowProxy::setWindow):
* Source/WebCore/bindings/scripts/CodeGeneratorJS.pm:
(GenerateImplementation):
* Source/WebCore/workers/WorkerOrWorkletScriptController.cpp:
(WebCore::WorkerOrWorkletScriptController::initScriptWithSubclass):

Canonical link: https://commits.webkit.org/262808@main

More information about the webkit-changes mailing list