Attachment 339765 Details for Bug 185329 – patch

[patch] patch

a-backup.diff (text/plain), 17.05 KB, created by Saam Barati on 2018-05-07 16:35:22 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Saam Barati

Created: 2018-05-07 16:35:22 PDT

Size: 17.05 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 231460)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,75 @@
>+2018-05-07  Saam Barati  <sbarati@apple.com>
>+
>+        Make a compact version of VariableEnvironment that UnlinkedFunctionExecutable stores and hash-cons these compact environments as we make them
>+        https://bugs.webkit.org/show_bug.cgi?id=185329
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        I was made aware of a memory goof inside of JSC where we would inefficiently
>+        use space to represent and UnlinkedFunctionExecutable's parent TDZ variables.
>+        
>+        We did two things badly:
>+        1. We used a HashMap instead of a Vector to represent the environment. Having
>+        a HashMap is useful when looking things up when generating bytecode, but it's
>+        space inefficient. Because UnlinkedFunctionExecutables live a long time because
>+        of the code cache, we should have them store this information efficiently
>+        inside of a Vector.
>+        
>+        2. We didn't hash-cons these environments together. If you think about how
>+        some programs are structured, hash-consing these together is hugely profitable.
>+        Consider some code like this:
>+        ```
>+        const/let V_1 = ...;
>+        const/let V_2 = ...;
>+        ...
>+        const/let V_n = ...;
>+        
>+        function f_1() { ... };
>+        function f_2() { ... };
>+        ...
>+        function f_n() { ... };
>+        ```
>+        
>+        Each f_i would store an identical hash map for its parent TDZ variables
>+        consisting of {V_1, ..., V_n}. This was incredibly dumb. With hash-consing,
>+        each f_i just holds onto a reference to the environment.
>+        
>+        I benchmarked this change against an app that made heavy use of the
>+        above code pattern and it reduced its peak memory footprint from ~220MB
>+        to ~160MB.
>+
>+        * bytecode/UnlinkedFunctionExecutable.cpp:
>+        (JSC::generateUnlinkedFunctionCodeBlock):
>+        (JSC::UnlinkedFunctionExecutable::UnlinkedFunctionExecutable):
>+        * bytecode/UnlinkedFunctionExecutable.h:
>+        * parser/VariableEnvironment.cpp:
>+        (JSC::CompactVariableEnvironment::CompactVariableEnvironment):
>+        (JSC::CompactVariableEnvironment::operator== const):
>+        (JSC::CompactVariableEnvironment::toVariableEnvironment const):
>+        (JSC::CompactVariableMap::get):
>+        (JSC::CompactVariableMap::Handle::~Handle):
>+        * parser/VariableEnvironment.h:
>+        (JSC::VariableEnvironmentEntry::bits const):
>+        (JSC::VariableEnvironmentEntry::operator== const):
>+        (JSC::VariableEnvironment::isEverythingCaptured const):
>+        (JSC::CompactVariableEnvironment::hash const):
>+        (JSC::CompactVariableMapKey::CompactVariableMapKey):
>+        (JSC::CompactVariableMapKey::hash):
>+        (JSC::CompactVariableMapKey::equal):
>+        (JSC::CompactVariableMapKey::makeDeletedValue):
>+        (JSC::CompactVariableMapKey::isHashTableDeletedValue const):
>+        (JSC::CompactVariableMapKey::isHashTableEmptyValue const):
>+        (JSC::CompactVariableMapKey::environment):
>+        (WTF::HashTraits<JSC::CompactVariableMapKey>::constructDeletedValue):
>+        (WTF::HashTraits<JSC::CompactVariableMapKey>::isDeletedValue):
>+        (WTF::HashTraits<JSC::CompactVariableMapKey>::isEmptyValue):
>+        (JSC::CompactVariableMap::Handle::Handle):
>+        (JSC::CompactVariableMap::Handle::environment const):
>+        (JSC::VariableEnvironment::VariableEnvironment): Deleted.
>+        * runtime/VM.cpp:
>+        (JSC::VM::VM):
>+        * runtime/VM.h:
>+
> 2018-05-07  Andy VanWagoner  <andy@vanwagoner.family>
> 
>         Remove defunct email address
>Index: Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp
>===================================================================
>--- Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp	(revision 231394)
>+++ Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp	(working copy)
>@@ -68,7 +68,8 @@ static UnlinkedFunctionCodeBlock* genera
> 
>     UnlinkedFunctionCodeBlock* result = UnlinkedFunctionCodeBlock::create(&vm, FunctionCode, ExecutableInfo(function->usesEval(), function->isStrictMode(), kind == CodeForConstruct, functionKind == UnlinkedBuiltinFunction, executable->constructorKind(), scriptMode, executable->superBinding(), parseMode, executable->derivedContextType(), false, isClassContext, EvalContextType::FunctionEvalContext), debuggerMode);
> 
>-    error = BytecodeGenerator::generate(vm, function.get(), source, result, debuggerMode, executable->parentScopeTDZVariables());
>+    VariableEnvironment parentScopeTDZVariables = executable->parentScopeTDZVariables();
>+    error = BytecodeGenerator::generate(vm, function.get(), source, result, debuggerMode, &parentScopeTDZVariables);
> 
>     if (error.isValid())
>         return nullptr;
>@@ -104,6 +105,7 @@ UnlinkedFunctionExecutable::UnlinkedFunc
>     , m_inferredName(node->inferredName())
>     , m_parentSourceOverride(WTFMove(parentSourceOverride))
>     , m_classSource(node->classSource())
>+    , m_parentScopeTDZVariables(vm->m_compactVariableMap->get(parentScopeTDZVariables))
> {
>     // Make sure these bitfields are adequately wide.
>     ASSERT(m_constructAbility == static_cast<unsigned>(constructAbility));
>@@ -112,8 +114,6 @@ UnlinkedFunctionExecutable::UnlinkedFunc
>     ASSERT(m_scriptMode == static_cast<unsigned>(scriptMode));
>     ASSERT(m_superBinding == static_cast<unsigned>(node->superBinding()));
>     ASSERT(m_derivedContextType == static_cast<unsigned>(derivedContextType));
>-
>-    m_parentScopeTDZVariables.swap(parentScopeTDZVariables);
> }
> 
> void UnlinkedFunctionExecutable::destroy(JSCell* cell)
>Index: Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h
>===================================================================
>--- Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h	(revision 231394)
>+++ Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h	(working copy)
>@@ -127,7 +127,7 @@ public:
>     ConstructAbility constructAbility() const { return static_cast<ConstructAbility>(m_constructAbility); }
>     JSParserScriptMode scriptMode() const { return static_cast<JSParserScriptMode>(m_scriptMode); }
>     bool isClassConstructorFunction() const { return constructorKind() != ConstructorKind::None; }
>-    const VariableEnvironment* parentScopeTDZVariables() const { return &m_parentScopeTDZVariables; }
>+    VariableEnvironment parentScopeTDZVariables() const { return m_parentScopeTDZVariables.environment().toVariableEnvironment(); }
>     
>     bool isArrowFunction() const { return isArrowFunctionParseMode(parseMode()); }
> 
>@@ -176,7 +176,7 @@ private:
>     String m_sourceURLDirective;
>     String m_sourceMappingURLDirective;
> 
>-    VariableEnvironment m_parentScopeTDZVariables;
>+    CompactVariableMap::Handle m_parentScopeTDZVariables;
> 
> protected:
>     static void visitChildren(JSCell*, SlotVisitor&);
>Index: Source/JavaScriptCore/parser/VariableEnvironment.cpp
>===================================================================
>--- Source/JavaScriptCore/parser/VariableEnvironment.cpp	(revision 231394)
>+++ Source/JavaScriptCore/parser/VariableEnvironment.cpp	(working copy)
>@@ -96,4 +96,91 @@ void VariableEnvironment::markVariableAs
>     findResult->value.setIsExported();
> }
> 
>+CompactVariableEnvironment::CompactVariableEnvironment(const VariableEnvironment& env)
>+{
>+    m_isEverythingCaptured = env.isEverythingCaptured();
>+    Vector<std::pair<UniquedStringImpl*, VariableEnvironmentEntry>, 32> sortedEntries;
>+    sortedEntries.reserveInitialCapacity(env.size());
>+    for (auto& pair : env)
>+        sortedEntries.append({ pair.key.get(), pair.value });
>+
>+    std::sort(sortedEntries.begin(), sortedEntries.end(), [] (const auto& a, const auto& b) {
>+        return a.first < b.first;
>+    });
>+
>+    m_hash = 0;
>+    m_variables.reserveInitialCapacity(sortedEntries.size());
>+    m_variableMetadata.reserveInitialCapacity(sortedEntries.size());
>+    for (const auto& pair : sortedEntries) {
>+        m_variables.append(pair.first);
>+        m_variableMetadata.append(pair.second);
>+        m_hash ^= pair.first->hash();
>+        m_hash += pair.second.bits();
>+    }
>+
>+    if (m_isEverythingCaptured)
>+        m_hash *= 2;
>+}
>+
>+bool CompactVariableEnvironment::operator==(const CompactVariableEnvironment& other) const
>+{
>+    if (this == &other)
>+        return true;
>+    if (m_isEverythingCaptured != other.m_isEverythingCaptured)
>+        return false;
>+    if (m_variables != other.m_variables)
>+        return false;
>+    if (m_variableMetadata != other.m_variableMetadata)
>+        return false;
>+    return true;
>+}
>+
>+VariableEnvironment CompactVariableEnvironment::toVariableEnvironment() const
>+{
>+    VariableEnvironment result;
>+    ASSERT(m_variables.size() == m_variableMetadata.size());
>+    for (size_t i = 0; i < m_variables.size(); ++i) {
>+        auto addResult = result.add(m_variables[i]);
>+        ASSERT(addResult.isNewEntry);
>+        addResult.iterator->value = m_variableMetadata[i];
>+    }
>+
>+    if (m_isEverythingCaptured)
>+        result.markAllVariablesAsCaptured();
>+
>+    return result;
>+}
>+
>+CompactVariableMap::Handle CompactVariableMap::get(const VariableEnvironment& env)
>+{
>+    auto* environment = new CompactVariableEnvironment(env);
>+    CompactVariableMapKey key { *environment };
>+    auto addResult = m_map.add(key, 1);
>+    if (addResult.isNewEntry)
>+        return CompactVariableMap::Handle(*environment, *this);
>+
>+    delete environment;
>+    ++addResult.iterator->value;
>+    return CompactVariableMap::Handle(addResult.iterator->key.environment(), *this);
>+}
>+
>+CompactVariableMap::Handle::~Handle()
>+{
>+    if (!m_map) {
>+        ASSERT(!m_environment);
>+        // This happens if we were moved into a different handle.
>+        return;
>+    }
>+
>+    RELEASE_ASSERT(m_environment);
>+    auto iter = m_map->m_map.find(CompactVariableMapKey { *m_environment });
>+    RELEASE_ASSERT(iter != m_map->m_map.end());
>+    --iter->value;
>+    if (!iter->value) {
>+        ASSERT(m_environment == &iter->key.environment());
>+        m_map->m_map.remove(iter);
>+        fastFree(m_environment);
>+    }
>+}
>+
> } // namespace JSC
>Index: Source/JavaScriptCore/parser/VariableEnvironment.h
>===================================================================
>--- Source/JavaScriptCore/parser/VariableEnvironment.h	(revision 231394)
>+++ Source/JavaScriptCore/parser/VariableEnvironment.h	(working copy)
>@@ -56,6 +56,13 @@ public:
> 
>     ALWAYS_INLINE void clearIsVar() { m_bits &= ~IsVar; }
> 
>+    uint16_t bits() const { return m_bits; }
>+
>+    bool operator==(const VariableEnvironmentEntry& other) const
>+    {
>+        return m_bits == other.m_bits;
>+    }
>+
> private:
>     enum Traits : uint16_t {
>         IsCaptured = 1 << 0,
>@@ -80,14 +87,11 @@ class VariableEnvironment {
> private:
>     typedef HashMap<RefPtr<UniquedStringImpl>, VariableEnvironmentEntry, IdentifierRepHash, HashTraits<RefPtr<UniquedStringImpl>>, VariableEnvironmentEntryHashTraits> Map;
> public:
>-    VariableEnvironment()
>-    { }
>-    VariableEnvironment(VariableEnvironment&& other)
>-        : m_map(WTFMove(other.m_map))
>-        , m_isEverythingCaptured(other.m_isEverythingCaptured)
>-    { }
>+    VariableEnvironment() = default;
>+    VariableEnvironment(VariableEnvironment&& other) = default;
>     VariableEnvironment(const VariableEnvironment&) = default;
>     VariableEnvironment& operator=(const VariableEnvironment&) = default;
>+    VariableEnvironment& operator=(VariableEnvironment&&) = default;
> 
>     ALWAYS_INLINE Map::iterator begin() { return m_map.begin(); }
>     ALWAYS_INLINE Map::iterator end() { return m_map.end(); }
>@@ -109,9 +113,126 @@ public:
>     void markVariableAsImported(const RefPtr<UniquedStringImpl>& identifier);
>     void markVariableAsExported(const RefPtr<UniquedStringImpl>& identifier);
> 
>+    bool isEverythingCaptured() const { return m_isEverythingCaptured; }
>+
> private:
>     Map m_map;
>     bool m_isEverythingCaptured { false };
> };
> 
>+class CompactVariableEnvironment {
>+    WTF_MAKE_FAST_ALLOCATED;
>+    WTF_MAKE_NONCOPYABLE(CompactVariableEnvironment);
>+public:
>+    CompactVariableEnvironment(const VariableEnvironment&);
>+    VariableEnvironment toVariableEnvironment() const;
>+
>+    bool operator==(const CompactVariableEnvironment&) const;
>+    unsigned hash() const { return m_hash; }
>+
>+private:
>+    Vector<RefPtr<UniquedStringImpl>> m_variables;
>+    Vector<VariableEnvironmentEntry> m_variableMetadata;
>+    unsigned m_hash;
>+    bool m_isEverythingCaptured;
>+};
>+
>+struct CompactVariableMapKey {
>+    CompactVariableMapKey()
>+        : m_environment(nullptr)
>+    {
>+        ASSERT(isHashTableEmptyValue());
>+    }
>+
>+    CompactVariableMapKey(CompactVariableEnvironment& environment)
>+        : m_environment(&environment)
>+    { }
>+
>+    static unsigned hash(const CompactVariableMapKey& key) { return key.m_environment->hash(); }
>+    static bool equal(const CompactVariableMapKey& a, const CompactVariableMapKey& b) { return *a.m_environment == *b.m_environment; }
>+    static const bool safeToCompareToEmptyOrDeleted = false;
>+    static void makeDeletedValue(CompactVariableMapKey& key)
>+    {
>+        key.m_environment = reinterpret_cast<CompactVariableEnvironment*>(1);
>+    }
>+    bool isHashTableDeletedValue() const
>+    {
>+        return m_environment == reinterpret_cast<CompactVariableEnvironment*>(1);
>+    }
>+    bool isHashTableEmptyValue() const
>+    {
>+        return !m_environment;
>+    }
>+
>+    CompactVariableEnvironment& environment()
>+    {
>+        RELEASE_ASSERT(!isHashTableDeletedValue());
>+        RELEASE_ASSERT(!isHashTableEmptyValue());
>+        return *m_environment;
>+    }
>+
>+private:
>+    CompactVariableEnvironment* m_environment;
>+};
>+
>+} // namespace JSC
>+
>+namespace WTF {
>+
>+template<typename T> struct DefaultHash;
>+template<> struct DefaultHash<JSC::CompactVariableMapKey> {
>+    using Hash = JSC::CompactVariableMapKey;
>+};
>+
>+template<> struct HashTraits<JSC::CompactVariableMapKey> : GenericHashTraits<JSC::CompactVariableMapKey> {
>+    static const bool emptyValueIsZero = true;
>+    static JSC::CompactVariableMapKey emptyValue() { return JSC::CompactVariableMapKey(); }
>+
>+    static const bool hasIsEmptyValueFunction = true;
>+    static bool isEmptyValue(JSC::CompactVariableMapKey key) { return key.isHashTableEmptyValue(); }
>+
>+    static void constructDeletedValue(JSC::CompactVariableMapKey& key) { JSC::CompactVariableMapKey::makeDeletedValue(key); }
>+    static bool isDeletedValue(JSC::CompactVariableMapKey key) { return key.isHashTableDeletedValue(); }
>+};
>+
>+} // namespace WTF
>+
>+namespace JSC {
>+
>+class CompactVariableMap : public RefCounted<CompactVariableMap> {
>+public:
>+    class Handle {
>+        WTF_MAKE_NONCOPYABLE(Handle); // If we wanted to make this copyable, we'd need to do a hashtable lookup and bump the refcount.
>+    public:
>+        Handle(CompactVariableEnvironment& environment, CompactVariableMap& map)
>+            : m_environment(&environment)
>+            , m_map(&map)
>+        { }
>+        Handle(Handle&& other)
>+            : m_environment(other.m_environment)
>+            , m_map(WTFMove(other.m_map))
>+        {
>+            RELEASE_ASSERT(!!m_environment == !!m_map);
>+            ASSERT(!other.m_map);
>+            other.m_environment = nullptr;
>+        }
>+        ~Handle();
>+
>+        const CompactVariableEnvironment& environment() const
>+        {
>+            return *m_environment;
>+        }
>+
>+    private:
>+        CompactVariableEnvironment* m_environment;
>+        RefPtr<CompactVariableMap> m_map;
>+    };
>+
>+    Handle get(const VariableEnvironment&);
>+
>+private:
>+    friend class Handle;
>+    HashMap<CompactVariableMapKey, unsigned> m_map;
>+};
>+
> } // namespace JSC
>Index: Source/JavaScriptCore/runtime/VM.cpp
>===================================================================
>--- Source/JavaScriptCore/runtime/VM.cpp	(revision 231394)
>+++ Source/JavaScriptCore/runtime/VM.cpp	(working copy)
>@@ -142,6 +142,7 @@
> #include "TypeProfiler.h"
> #include "TypeProfilerLog.h"
> #include "UnlinkedCodeBlock.h"
>+#include "VariableEnvironment.h"
> #include "VMEntryScope.h"
> #include "VMInspector.h"
> #include "WasmWorklist.h"
>@@ -333,6 +334,7 @@ VM::VM(VMType vmType, HeapType heapType)
>     , interpreter(0)
>     , entryScope(0)
>     , m_regExpCache(new RegExpCache(this))
>+    , m_compactVariableMap(adoptRef(*(new CompactVariableMap)))
> #if ENABLE(REGEXP_TRACING)
>     , m_rtTraceList(new RTTraceList())
> #endif
>Index: Source/JavaScriptCore/runtime/VM.h
>===================================================================
>--- Source/JavaScriptCore/runtime/VM.h	(revision 231394)
>+++ Source/JavaScriptCore/runtime/VM.h	(working copy)
>@@ -102,6 +102,7 @@ class BytecodeIntrinsicRegistry;
> class CodeBlock;
> class CodeCache;
> class CommonIdentifiers;
>+class CompactVariableMap;
> class CustomGetterSetter;
> class DOMAttributeGetterSetter;
> class ExecState;
>@@ -709,6 +710,7 @@ public:
>     void releaseRegExpPatternContexBuffer();
> #endif
> 
>+    Ref<CompactVariableMap> m_compactVariableMap;
> 
>     std::unique_ptr<HasOwnPropertyCache> m_hasOwnPropertyCache;
>     ALWAYS_INLINE HasOwnPropertyCache* hasOwnPropertyCache() { return m_hasOwnPropertyCache.get(); }

Flags:

msaboff: review+

Actions: View | Formatted Diff | Diff

Attachments on bug 185329: 339653 | 339765 | 339788