Ignore:
Timestamp:
Oct 28, 2020, 12:25:14 PM (5 years ago)
Author:
[email protected]
Message:

Better cache our serialization of the outer TDZ environment when creating FunctionExecutables during bytecode generation
​https://bugs.webkit.org/show_bug.cgi?id=199866
<rdar://problem/53333108>

Reviewed by Tadeu Zagallo.

JSTests:

  • microbenchmarks/let-const-tdz-environment-parsing-and-hash-consing-speed.js: Added.

Source/JavaScriptCore:

This patch removes performance pathologies regarding programs with
many variables under TDZ (let/const). We had an algorithm for caching
the results of gathering all variables under TDZ, but that algorithm
wasn't nearly aggressive enough in its caching. This lead us to worst
case quadratic runtime, which could happens in practice for large functions.

There are a few fixes here:

  • Instead of flattening the entire TDZ stack, and caching that result,

we now cache each stack entry individually. So as you push/pop to the
TDZ environment stack, we no longer invalidate everything. Instead, we
will just need to cache the newly pushed entry. We also no longer invalidate
the cache for lifting a TDZ check. The compromise here is we may emit
more runtime TDZ checks for closure variables. This is better than N2
bytecode compile time perf, since a well predicted branch for a TDZ
check is essentially free.

  • We no longer transform the CompactTDZEnvironment (formerly CompactVariableEnvironment)

from a Vector into a HashSet each time we generate code for an inner function. Instead,
CompactTDZEnvironment can be in two modes: compact and inflated. It starts life off in
compact mode (a vector), and will turn into an inflated mode if it's ever needed. Once
inflated, it'll stay this way until it's destructed. This improves our algorithm from being
O(EnvSize * NumFunctions) to O(EnvSize) at the cost of using more space in a HashTable versus a
Vector. In the future, we could consider just binary searching through this Vector, and never using
a hash table.

  • bytecode/UnlinkedFunctionExecutable.cpp:

(JSC::generateUnlinkedFunctionCodeBlock):
(JSC::UnlinkedFunctionExecutable::UnlinkedFunctionExecutable):

  • bytecode/UnlinkedFunctionExecutable.h:
  • bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::BytecodeGenerator):
(JSC::BytecodeGenerator::popLexicalScopeInternal):
(JSC::BytecodeGenerator::needsTDZCheck):
(JSC::BytecodeGenerator::liftTDZCheckIfPossible):
(JSC::BytecodeGenerator::pushTDZVariables):
(JSC::BytecodeGenerator::getVariablesUnderTDZ):
(JSC::BytecodeGenerator::preserveTDZStack):
(JSC::BytecodeGenerator::restoreTDZStack):
(JSC::BytecodeGenerator::emitNewInstanceFieldInitializerFunction):

  • bytecompiler/BytecodeGenerator.h:

(JSC::BytecodeGenerator::generate):
(JSC::BytecodeGenerator::makeFunction):

  • debugger/DebuggerCallFrame.cpp:

(JSC::DebuggerCallFrame::evaluateWithScopeExtension):

  • interpreter/Interpreter.cpp:

(JSC::eval):

  • parser/Parser.h:

(JSC::Parser<LexerType>::parse):
(JSC::parse):

  • parser/VariableEnvironment.cpp:

(JSC::CompactTDZEnvironment::sortCompact):
(JSC::CompactTDZEnvironment::CompactTDZEnvironment):
(JSC::CompactTDZEnvironment::operator== const):
(JSC::CompactTDZEnvironment::toTDZEnvironmentSlow const):
(JSC::CompactTDZEnvironmentMap::get):
(JSC::CompactTDZEnvironmentMap::Handle::~Handle):
(JSC::CompactTDZEnvironmentMap::Handle::Handle):
(JSC::CompactVariableEnvironment::CompactVariableEnvironment): Deleted.
(JSC::CompactVariableEnvironment::operator== const): Deleted.
(JSC::CompactVariableEnvironment::toVariableEnvironment const): Deleted.
(JSC::CompactVariableMap::get): Deleted.
(JSC::CompactVariableMap::Handle::~Handle): Deleted.
(JSC::CompactVariableMap::Handle::Handle): Deleted.

  • parser/VariableEnvironment.h:

(JSC::CompactTDZEnvironment::toTDZEnvironment const):
(JSC::CompactTDZEnvironmentKey::CompactTDZEnvironmentKey):
(JSC::CompactTDZEnvironmentKey::hash):
(JSC::CompactTDZEnvironmentKey::equal):
(JSC::CompactTDZEnvironmentKey::makeDeletedValue):
(JSC::CompactTDZEnvironmentKey::isHashTableDeletedValue const):
(JSC::CompactTDZEnvironmentKey::environment):
(WTF::HashTraits<JSC::CompactTDZEnvironmentKey>::emptyValue):
(WTF::HashTraits<JSC::CompactTDZEnvironmentKey>::isEmptyValue):
(WTF::HashTraits<JSC::CompactTDZEnvironmentKey>::constructDeletedValue):
(WTF::HashTraits<JSC::CompactTDZEnvironmentKey>::isDeletedValue):
(JSC::CompactTDZEnvironmentMap::Handle::environment const):
(JSC::CompactVariableEnvironment::hash const): Deleted.
(JSC::CompactVariableMapKey::CompactVariableMapKey): Deleted.
(JSC::CompactVariableMapKey::hash): Deleted.
(JSC::CompactVariableMapKey::equal): Deleted.
(JSC::CompactVariableMapKey::makeDeletedValue): Deleted.
(JSC::CompactVariableMapKey::isHashTableDeletedValue const): Deleted.
(JSC::CompactVariableMapKey::isHashTableEmptyValue const): Deleted.
(JSC::CompactVariableMapKey::environment): Deleted.
(WTF::HashTraits<JSC::CompactVariableMapKey>::emptyValue): Deleted.
(WTF::HashTraits<JSC::CompactVariableMapKey>::isEmptyValue): Deleted.
(WTF::HashTraits<JSC::CompactVariableMapKey>::constructDeletedValue): Deleted.
(WTF::HashTraits<JSC::CompactVariableMapKey>::isDeletedValue): Deleted.
(JSC::CompactVariableMap::Handle::Handle): Deleted.
(JSC::CompactVariableMap::Handle::operator=): Deleted.
(JSC::CompactVariableMap::Handle::operator bool const): Deleted.
(JSC::CompactVariableMap::Handle::environment const): Deleted.
(JSC::CompactVariableMap::Handle::swap): Deleted.

  • runtime/CachedTypes.cpp:

(JSC::Decoder::handleForTDZEnvironment const):
(JSC::Decoder::setHandleForTDZEnvironment):
(JSC::CachedCompactTDZEnvironment::encode):
(JSC::CachedCompactTDZEnvironment::decode const):
(JSC::CachedCompactTDZEnvironmentMapHandle::encode):
(JSC::CachedCompactTDZEnvironmentMapHandle::decode const):
(JSC::CachedFunctionExecutableRareData::decode const):
(JSC::Decoder::handleForEnvironment const): Deleted.
(JSC::Decoder::setHandleForEnvironment): Deleted.
(JSC::CachedCompactVariableEnvironment::encode): Deleted.
(JSC::CachedCompactVariableEnvironment::decode const): Deleted.
(JSC::CachedCompactVariableMapHandle::encode): Deleted.
(JSC::CachedCompactVariableMapHandle::decode const): Deleted.

  • runtime/CachedTypes.h:
  • runtime/CodeCache.cpp:

(JSC::generateUnlinkedCodeBlockImpl):
(JSC::generateUnlinkedCodeBlock):
(JSC::generateUnlinkedCodeBlockForDirectEval):
(JSC::recursivelyGenerateUnlinkedCodeBlockForProgram):
(JSC::recursivelyGenerateUnlinkedCodeBlockForModuleProgram):
(JSC::CodeCache::getUnlinkedGlobalCodeBlock):

  • runtime/CodeCache.h:
  • runtime/Completion.cpp:

(JSC::generateProgramBytecode):
(JSC::generateModuleBytecode):

  • runtime/DirectEvalExecutable.cpp:

(JSC::DirectEvalExecutable::create):

  • runtime/DirectEvalExecutable.h:
  • runtime/JSScope.cpp:

(JSC::JSScope::collectClosureVariablesUnderTDZ):

  • runtime/JSScope.h:
  • runtime/VM.cpp:

(JSC::VM::VM):

  • runtime/VM.h:

Source/WTF:

  • wtf/RefPtr.h:

(WTF::swap): Deleted.
This function is no longer necessary, and causes ADL (​https://en.cppreference.com/w/cpp/language/adl)
compile errors when not using DumbPtrTraits and calling sort on a vector of that type.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/parser/VariableEnvironment.h

    r264488 r269115  
    3030#include <wtf/HashSet.h>
    3131#include <wtf/IteratorRange.h>
     32#include <wtf/Variant.h>
    3233
    3334namespace JSC {
    … …  
    120121
    121122class VariableEnvironment {
     123    WTF_MAKE_FAST_ALLOCATED;
    122124private:
    123125    typedef HashMap<PackedRefPtr<UniquedStringImpl>, VariableEnvironmentEntry, IdentifierRepHash, HashTraits<RefPtr<UniquedStringImpl>>, VariableEnvironmentEntryHashTraits> Map;
    … …  
    263265};
    264266
    265 class CompactVariableEnvironment {
     267using TDZEnvironment = HashSet<RefPtr<UniquedStringImpl>, IdentifierRepHash>;
     268
     269class CompactTDZEnvironment {
    266270    WTF_MAKE_FAST_ALLOCATED;
    267     WTF_MAKE_NONCOPYABLE(CompactVariableEnvironment);
    268 
    269     friend class CachedCompactVariableEnvironment;
     271    WTF_MAKE_NONCOPYABLE(CompactTDZEnvironment);
     272
     273    friend class CachedCompactTDZEnvironment;
     274
     275    using Compact = Vector<PackedRefPtr<UniquedStringImpl>>;
     276    using Inflated = TDZEnvironment;
     277    using Variables = Variant<Compact, Inflated>;
    270278
    271279public:
    272     CompactVariableEnvironment(const VariableEnvironment&);
    273     VariableEnvironment toVariableEnvironment() const;
    274 
    275     bool operator==(const CompactVariableEnvironment&) const;
     280    CompactTDZEnvironment(const TDZEnvironment&);
     281
     282    bool operator==(const CompactTDZEnvironment&) const;
    276283    unsigned hash() const { return m_hash; }
    277284
    278 private:
    279     CompactVariableEnvironment() = default;
    280 
    281     Vector<PackedRefPtr<UniquedStringImpl>> m_variables;
    282     Vector<VariableEnvironmentEntry> m_variableMetadata;
     285    static void sortCompact(Compact&);
     286
     287    TDZEnvironment& toTDZEnvironment() const
     288    {
     289        if (WTF::holds_alternative<Inflated>(m_variables))
     290            return const_cast<TDZEnvironment&>(WTF::get<Inflated>(m_variables));
     291        return toTDZEnvironmentSlow();
     292    }
     293
     294private:
     295    CompactTDZEnvironment() = default;
     296    TDZEnvironment& toTDZEnvironmentSlow() const;
     297
     298    mutable Variables m_variables;
    283299    unsigned m_hash;
    284     bool m_isEverythingCaptured;
    285 };
    286 
    287 struct CompactVariableMapKey {
    288     CompactVariableMapKey()
     300};
     301
     302struct CompactTDZEnvironmentKey {
     303    CompactTDZEnvironmentKey()
    289304        : m_environment(nullptr)
    290305    {
    … …  
    292307    }
    293308
    294     CompactVariableMapKey(CompactVariableEnvironment& environment)
     309    CompactTDZEnvironmentKey(CompactTDZEnvironment& environment)
    295310        : m_environment(&environment)
    296311    { }
    297312
    298     static unsigned hash(const CompactVariableMapKey& key) { return key.m_environment->hash(); }
    299     static bool equal(const CompactVariableMapKey& a, const CompactVariableMapKey& b) { return *a.m_environment == *b.m_environment; }
     313    static unsigned hash(const CompactTDZEnvironmentKey& key) { return key.m_environment->hash(); }
     314    static bool equal(const CompactTDZEnvironmentKey& a, const CompactTDZEnvironmentKey& b) { return *a.m_environment == *b.m_environment; }
    300315    static constexpr bool safeToCompareToEmptyOrDeleted = false;
    301     static void makeDeletedValue(CompactVariableMapKey& key)
    302     {
    303         key.m_environment = reinterpret_cast<CompactVariableEnvironment*>(1);
     316    static void makeDeletedValue(CompactTDZEnvironmentKey& key)
     317    {
     318        key.m_environment = reinterpret_cast<CompactTDZEnvironment*>(1);
    304319    }
    305320    bool isHashTableDeletedValue() const
    306321    {
    307         return m_environment == reinterpret_cast<CompactVariableEnvironment*>(1);
     322        return m_environment == reinterpret_cast<CompactTDZEnvironment*>(1);
    308323    }
    309324    bool isHashTableEmptyValue() const
    … …  
    312327    }
    313328
    314     CompactVariableEnvironment& environment()
     329    CompactTDZEnvironment& environment()
    315330    {
    316331        RELEASE_ASSERT(!isHashTableDeletedValue());
    … …  
    320335
    321336private:
    322     CompactVariableEnvironment* m_environment;
     337    CompactTDZEnvironment* m_environment;
    323338};
    324339
    … …  
    328343
    329344template<typename T> struct DefaultHash;
    330 template<> struct DefaultHash<JSC::CompactVariableMapKey> : JSC::CompactVariableMapKey { };
    331 
    332 template<> struct HashTraits<JSC::CompactVariableMapKey> : GenericHashTraits<JSC::CompactVariableMapKey> {
     345template<> struct DefaultHash<JSC::CompactTDZEnvironmentKey> : JSC::CompactTDZEnvironmentKey { };
     346
     347template<> struct HashTraits<JSC::CompactTDZEnvironmentKey> : GenericHashTraits<JSC::CompactTDZEnvironmentKey> {
    333348    static constexpr bool emptyValueIsZero = true;
    334     static JSC::CompactVariableMapKey emptyValue() { return JSC::CompactVariableMapKey(); }
     349    static JSC::CompactTDZEnvironmentKey emptyValue() { return JSC::CompactTDZEnvironmentKey(); }
    335350
    336351    static constexpr bool hasIsEmptyValueFunction = true;
    337     static bool isEmptyValue(JSC::CompactVariableMapKey key) { return key.isHashTableEmptyValue(); }
    338 
    339     static void constructDeletedValue(JSC::CompactVariableMapKey& key) { JSC::CompactVariableMapKey::makeDeletedValue(key); }
    340     static bool isDeletedValue(JSC::CompactVariableMapKey key) { return key.isHashTableDeletedValue(); }
     352    static bool isEmptyValue(JSC::CompactTDZEnvironmentKey key) { return key.isHashTableEmptyValue(); }
     353
     354    static void constructDeletedValue(JSC::CompactTDZEnvironmentKey& key) { JSC::CompactTDZEnvironmentKey::makeDeletedValue(key); }
     355    static bool isDeletedValue(JSC::CompactTDZEnvironmentKey key) { return key.isHashTableDeletedValue(); }
    341356};
    342357
    … …  
    345360namespace JSC {
    346361
    347 class CompactVariableMap : public RefCounted<CompactVariableMap> {
     362class CompactTDZEnvironmentMap : public RefCounted<CompactTDZEnvironmentMap> {
    348363public:
    349364    class Handle {
    350         friend class CachedCompactVariableMapHandle;
     365        friend class CachedCompactTDZEnvironmentMapHandle;
    351366
    352367    public:
    353368        Handle() = default;
    354369
    355         Handle(CompactVariableEnvironment&, CompactVariableMap&);
     370        Handle(CompactTDZEnvironment&, CompactTDZEnvironmentMap&);
    356371
    357372        Handle(Handle&& other)
    … …  
    378393        explicit operator bool() const { return !!m_map; }
    379394
    380         const CompactVariableEnvironment& environment() const
     395        const CompactTDZEnvironment& environment() const
    381396        {
    382397            return *m_environment;
    … …  
    390405        }
    391406
    392         CompactVariableEnvironment* m_environment { nullptr };
    393         RefPtr<CompactVariableMap> m_map;
     407        CompactTDZEnvironment* m_environment { nullptr };
     408        RefPtr<CompactTDZEnvironmentMap> m_map;
    394409    };
    395410
    396     Handle get(const VariableEnvironment&);
     411    Handle get(const TDZEnvironment&);
    397412
    398413private:
    399414    friend class Handle;
    400     friend class CachedCompactVariableMapHandle;
    401 
    402     Handle get(CompactVariableEnvironment*, bool& isNewEntry);
    403 
    404     HashMap<CompactVariableMapKey, unsigned> m_map;
     415    friend class CachedCompactTDZEnvironmentMapHandle;
     416
     417    Handle get(CompactTDZEnvironment*, bool& isNewEntry);
     418
     419    HashMap<CompactTDZEnvironmentKey, unsigned> m_map;
    405420};
    406421
Note: See TracChangeset for help on using the changeset viewer.