Make a compact version of VariableEnvironment that UnlinkedFunctionExecutable stores...

https://bugs.webkit.org/show_bug.cgi?id=185329
<rdar://problem/39961536>

Reviewed by Michael Saboff.

I was made aware of a memory goof inside of JSC where we would inefficiently
use space to represent an 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>::emptyValue):
(WTF::HashTraits<JSC::CompactVariableMapKey>::isEmptyValue):
(WTF::HashTraits<JSC::CompactVariableMapKey>::constructDeletedValue):
(WTF::HashTraits<JSC::CompactVariableMapKey>::isDeletedValue):
(JSC::CompactVariableMap::Handle::Handle):
(JSC::CompactVariableMap::Handle::environment const):
(JSC::VariableEnvironment::VariableEnvironment): Deleted.
* runtime/VM.cpp:
(JSC::VM::VM):
* runtime/VM.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@231477 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
index 9661600..12cb95a 100644 (file)
--- a/Source/JavaScriptCore/ChangeLog
+++ b/Source/JavaScriptCore/ChangeLog
@@ -1,3 +1,77 @@
+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
+        <rdar://problem/39961536>
+
+        Reviewed by Michael Saboff.
+
+        I was made aware of a memory goof inside of JSC where we would inefficiently
+        use space to represent an 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>::emptyValue):
+        (WTF::HashTraits<JSC::CompactVariableMapKey>::isEmptyValue):
+        (WTF::HashTraits<JSC::CompactVariableMapKey>::constructDeletedValue):
+        (WTF::HashTraits<JSC::CompactVariableMapKey>::isDeletedValue):
+        (JSC::CompactVariableMap::Handle::Handle):
+        (JSC::CompactVariableMap::Handle::environment const):
+        (JSC::VariableEnvironment::VariableEnvironment): Deleted.
+        * runtime/VM.cpp:
+        (JSC::VM::VM):
+        * runtime/VM.h:
+
 2018-05-06  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [DFG][MIPS] Simplify DFG code by increasing MIPS temporary registers

diff --git a/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp b/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp
index cff726a..49fcea2 100644 (file)
--- a/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp
+++ b/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.cpp
@@ -68,7 +68,8 @@ static UnlinkedFunctionCodeBlock* generateUnlinkedFunctionCodeBlock(
 
     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::UnlinkedFunctionExecutable(VM* vm, Structure* struct
     , 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::UnlinkedFunctionExecutable(VM* vm, Structure* struct
     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)

diff --git a/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h b/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h
index de0bfec..367e144 100644 (file)
--- a/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h
+++ b/Source/JavaScriptCore/bytecode/UnlinkedFunctionExecutable.h
@@ -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&);

diff --git a/Source/JavaScriptCore/parser/VariableEnvironment.cpp b/Source/JavaScriptCore/parser/VariableEnvironment.cpp
index 692592c..24fd233 100644 (file)
--- a/Source/JavaScriptCore/parser/VariableEnvironment.cpp
+++ b/Source/JavaScriptCore/parser/VariableEnvironment.cpp
@@ -96,4 +96,91 @@ void VariableEnvironment::markVariableAsExported(const RefPtr<UniquedStringImpl>
     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

diff --git a/Source/JavaScriptCore/parser/VariableEnvironment.h b/Source/JavaScriptCore/parser/VariableEnvironment.h
index eb05605..129b5ea 100644 (file)
--- a/Source/JavaScriptCore/parser/VariableEnvironment.h
+++ b/Source/JavaScriptCore/parser/VariableEnvironment.h
@@ -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 reference count of the map entry.
+    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

diff --git a/Source/JavaScriptCore/runtime/VM.cpp b/Source/JavaScriptCore/runtime/VM.cpp
index 7d366d6..fcd8e04 100644 (file)
--- a/Source/JavaScriptCore/runtime/VM.cpp
+++ b/Source/JavaScriptCore/runtime/VM.cpp
@@ -144,6 +144,7 @@
 #include "UnlinkedCodeBlock.h"
 #include "VMEntryScope.h"
 #include "VMInspector.h"
+#include "VariableEnvironment.h"
 #include "WasmWorklist.h"
 #include "Watchdog.h"
 #include "WeakGCMapInlines.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

diff --git a/Source/JavaScriptCore/runtime/VM.h b/Source/JavaScriptCore/runtime/VM.h
index 8afa7e2..1797be9 100644 (file)
--- a/Source/JavaScriptCore/runtime/VM.h
+++ b/Source/JavaScriptCore/runtime/VM.h
@@ -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(); }