Cache toString results for CoW arrays
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 1 Jun 2018 03:07:28 +0000 (03:07 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 1 Jun 2018 03:07:28 +0000 (03:07 +0000)
https://bugs.webkit.org/show_bug.cgi?id=186160

Reviewed by Keith Miller.

JSTests:

* microbenchmarks/to-string-on-cow-array.js: Added.
(foo):

Source/JavaScriptCore:

This patch makes it so that we cache the result of toString on
arrays with a CoW butterfly. This cache lives on Heap and is
cleared after every GC. We only cache the toString result when
the CoW butterfly doesn't have a hole (currently, all CoW arrays
have a hole, but this isn't an invariant we want to rely on). The
reason for this is that if there is a hole, the value may be loaded
from the prototype, and the cache may produce a stale result.

This is a ~4% speedup on the ML subtest in ARES. And is a ~1% overall
progression on ARES.

* heap/Heap.cpp:
(JSC::Heap::finalize):
(JSC::Heap::addCoreConstraints):
* heap/Heap.h:
* runtime/ArrayPrototype.cpp:
(JSC::canUseFastJoin):
(JSC::holesMustForwardToPrototype):
(JSC::isHole):
(JSC::containsHole):
(JSC::fastJoin):
(JSC::arrayProtoFuncToString):

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

JSTests/ChangeLog
JSTests/microbenchmarks/to-string-on-cow-array.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/runtime/ArrayPrototype.cpp

index 0f4b6ef..4e8d8eb 100644 (file)
@@ -1,3 +1,13 @@
+2018-05-31  Saam Barati  <sbarati@apple.com>
+
+        Cache toString results for CoW arrays
+        https://bugs.webkit.org/show_bug.cgi?id=186160
+
+        Reviewed by Keith Miller.
+
+        * microbenchmarks/to-string-on-cow-array.js: Added.
+        (foo):
+
 2018-05-31  Keith Miller  <keith_miller@apple.com>
 
         Rebaseline test for change in Error.stack behavior.
diff --git a/JSTests/microbenchmarks/to-string-on-cow-array.js b/JSTests/microbenchmarks/to-string-on-cow-array.js
new file mode 100644 (file)
index 0000000..97e4b89
--- /dev/null
@@ -0,0 +1,16 @@
+let arrays = [
+    [0,0],
+    [0,1],
+    [1,0],
+    [1,1],
+];
+
+function foo(arr) {
+    return arr.toString();
+}
+noInline(foo);
+
+for (let i = 0; i < 30000; ++i) {
+    for (let arr of arrays)
+        foo(arr);
+}
index bbc4abf..7c092b5 100644 (file)
@@ -1,5 +1,35 @@
 2018-05-31  Saam Barati  <sbarati@apple.com>
 
+        Cache toString results for CoW arrays
+        https://bugs.webkit.org/show_bug.cgi?id=186160
+
+        Reviewed by Keith Miller.
+
+        This patch makes it so that we cache the result of toString on
+        arrays with a CoW butterfly. This cache lives on Heap and is
+        cleared after every GC. We only cache the toString result when
+        the CoW butterfly doesn't have a hole (currently, all CoW arrays
+        have a hole, but this isn't an invariant we want to rely on). The
+        reason for this is that if there is a hole, the value may be loaded
+        from the prototype, and the cache may produce a stale result.
+        
+        This is a ~4% speedup on the ML subtest in ARES. And is a ~1% overall
+        progression on ARES.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::finalize):
+        (JSC::Heap::addCoreConstraints):
+        * heap/Heap.h:
+        * runtime/ArrayPrototype.cpp:
+        (JSC::canUseFastJoin):
+        (JSC::holesMustForwardToPrototype):
+        (JSC::isHole):
+        (JSC::containsHole):
+        (JSC::fastJoin):
+        (JSC::arrayProtoFuncToString):
+
+2018-05-31  Saam Barati  <sbarati@apple.com>
+
         PutStructure AI rule needs to call didFoldClobberStructures when the incoming value's structure set is clear
         https://bugs.webkit.org/show_bug.cgi?id=186169
 
index 77a779e..3b1aacf 100644 (file)
@@ -2043,6 +2043,8 @@ void Heap::finalize()
     
     if (HasOwnPropertyCache* cache = vm()->hasOwnPropertyCache())
         cache->clear();
+
+    immutableButterflyToStringCache.clear();
     
     for (const HeapFinalizerCallback& callback : m_heapFinalizerCallbacks)
         callback.run(*vm());
index c8a6f0d..e7d99fb 100644 (file)
@@ -68,6 +68,7 @@ class IncrementalSweeper;
 class JITStubRoutine;
 class JITStubRoutineSet;
 class JSCell;
+class JSImmutableButterfly;
 class JSValue;
 class LLIntOffsetsExtractor;
 class MachineThreads;
@@ -381,6 +382,8 @@ public:
     
     Seconds totalGCTime() const { return m_totalGCTime; }
 
+    HashMap<JSImmutableButterfly*, JSString*> immutableButterflyToStringCache;
+
 private:
     friend class AllocatingScope;
     friend class CodeBlock;
index 3a82334..306e8ec 100644 (file)
@@ -385,8 +385,142 @@ void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned curre
     }
 }
 
-static bool canUseFastJoin(const JSObject*);
-static JSValue fastJoin(ExecState&, JSObject*, StringView, unsigned);
+inline bool canUseFastJoin(const JSObject* thisObject)
+{
+    switch (thisObject->indexingType()) {
+    case ALL_CONTIGUOUS_INDEXING_TYPES:
+    case ALL_INT32_INDEXING_TYPES:
+    case ALL_DOUBLE_INDEXING_TYPES:
+        return true;
+    default:
+        break;
+    }
+    return false;
+}
+
+inline bool holesMustForwardToPrototype(VM& vm, JSObject* object)
+{
+    return object->structure(vm)->holesMustForwardToPrototype(vm, object);
+}
+
+inline bool isHole(double value)
+{
+    return std::isnan(value);
+}
+
+inline bool isHole(const WriteBarrier<Unknown>& value)
+{
+    return !value;
+}
+
+template<typename T>
+inline bool containsHole(T* data, unsigned length)
+{
+    for (unsigned i = 0; i < length; ++i) {
+        if (isHole(data[i]))
+            return true;
+    }
+    return false;
+}
+
+inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length, bool* sawHoles = nullptr)
+{
+    VM& vm = state.vm();
+    auto scope = DECLARE_THROW_SCOPE(vm);
+
+    switch (thisObject->indexingType()) {
+    case ALL_INT32_INDEXING_TYPES: {
+        auto& butterfly = *thisObject->butterfly();
+        if (UNLIKELY(length > butterfly.publicLength()))
+            break;
+        JSStringJoiner joiner(state, separator, length);
+        RETURN_IF_EXCEPTION(scope, { });
+        auto data = butterfly.contiguous().data();
+        bool holesKnownToBeOK = false;
+        for (unsigned i = 0; i < length; ++i) {
+            JSValue value = data[i].get();
+            if (LIKELY(value))
+                joiner.appendNumber(vm, value.asInt32());
+            else {
+                if (sawHoles)
+                    *sawHoles = true;
+                if (!holesKnownToBeOK) {
+                    if (holesMustForwardToPrototype(vm, thisObject))
+                        goto generalCase;
+                    holesKnownToBeOK = true;
+                }
+                joiner.appendEmptyString();
+            }
+        }
+        scope.release();
+        return joiner.join(state);
+    }
+    case ALL_CONTIGUOUS_INDEXING_TYPES: {
+        auto& butterfly = *thisObject->butterfly();
+        if (UNLIKELY(length > butterfly.publicLength()))
+            break;
+        JSStringJoiner joiner(state, separator, length);
+        RETURN_IF_EXCEPTION(scope, { });
+        auto data = butterfly.contiguous().data();
+        bool holesKnownToBeOK = false;
+        for (unsigned i = 0; i < length; ++i) {
+            if (JSValue value = data[i].get()) {
+                if (!joiner.appendWithoutSideEffects(state, value))
+                    goto generalCase;
+            } else {
+                if (sawHoles)
+                    *sawHoles = true;
+                if (!holesKnownToBeOK) {
+                    if (holesMustForwardToPrototype(vm, thisObject))
+                        goto generalCase;
+                    holesKnownToBeOK = true;
+                }
+                joiner.appendEmptyString();
+            }
+        }
+        scope.release();
+        return joiner.join(state);
+    }
+    case ALL_DOUBLE_INDEXING_TYPES: {
+        auto& butterfly = *thisObject->butterfly();
+        if (UNLIKELY(length > butterfly.publicLength()))
+            break;
+        JSStringJoiner joiner(state, separator, length);
+        RETURN_IF_EXCEPTION(scope, { });
+        auto data = butterfly.contiguousDouble().data();
+        bool holesKnownToBeOK = false;
+        for (unsigned i = 0; i < length; ++i) {
+            double value = data[i];
+            if (LIKELY(!isHole(value)))
+                joiner.appendNumber(vm, value);
+            else {
+                if (sawHoles)
+                    *sawHoles = true;
+                if (!holesKnownToBeOK) {
+                    if (holesMustForwardToPrototype(vm, thisObject))
+                        goto generalCase;
+                    holesKnownToBeOK = true;
+                }
+                joiner.appendEmptyString();
+            }
+        }
+        scope.release();
+        return joiner.join(state);
+    }
+    }
+
+generalCase:
+    JSStringJoiner joiner(state, separator, length);
+    RETURN_IF_EXCEPTION(scope, { });
+    for (unsigned i = 0; i < length; ++i) {
+        JSValue element = thisObject->getIndex(&state, i);
+        RETURN_IF_EXCEPTION(scope, { });
+        joiner.append(state, element);
+        RETURN_IF_EXCEPTION(scope, { });
+    }
+    scope.release();
+    return joiner.join(state);
+}
 
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
 {
@@ -435,7 +569,25 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
     if (LIKELY(canUseFastJoin(thisArray))) {
         const LChar comma = ',';
         scope.release();
-        return JSValue::encode(fastJoin(*exec, thisArray, { &comma, 1 }, length));
+
+        bool isCoW = isCopyOnWrite(thisArray->indexingMode());
+        JSImmutableButterfly* immutableButterfly = nullptr;
+        if (isCoW) {
+            immutableButterfly = JSImmutableButterfly::fromButterfly(thisArray->butterfly());
+            auto iter = vm.heap.immutableButterflyToStringCache.find(immutableButterfly);
+            if (iter != vm.heap.immutableButterflyToStringCache.end())
+                return JSValue::encode(iter->value);
+        }
+
+        bool sawHoles = false;
+        JSValue result = fastJoin(*exec, thisArray, { &comma, 1 }, length, &sawHoles);
+
+        if (!sawHoles && result && isJSString(result) && isCoW) {
+            ASSERT(JSImmutableButterfly::fromButterfly(thisArray->butterfly()) == immutableButterfly);
+            vm.heap.immutableButterflyToStringCache.add(immutableButterfly, jsCast<JSString*>(result));
+        }
+
+        return JSValue::encode(result);
     }
 
     JSStringJoiner joiner(*exec, ',', length);
@@ -504,30 +656,6 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
     return JSValue::encode(stringJoiner.join(*exec));
 }
 
-static inline bool isHole(double value)
-{
-    return std::isnan(value);
-}
-
-static inline bool isHole(const WriteBarrier<Unknown>& value)
-{
-    return !value;
-}
-
-template<typename T> static inline bool containsHole(T* data, unsigned length)
-{
-    for (unsigned i = 0; i < length; ++i) {
-        if (isHole(data[i]))
-            return true;
-    }
-    return false;
-}
-
-static inline bool holesMustForwardToPrototype(VM& vm, JSObject* object)
-{
-    return object->structure(vm)->holesMustForwardToPrototype(vm, object);
-}
-
 static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separator, uint64_t length)
 {
     VM& vm = exec.vm();
@@ -576,112 +704,6 @@ static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separat
     return r;
 }
 
-static inline bool canUseFastJoin(const JSObject* thisObject)
-{
-    switch (thisObject->indexingType()) {
-    case ALL_CONTIGUOUS_INDEXING_TYPES:
-    case ALL_INT32_INDEXING_TYPES:
-    case ALL_DOUBLE_INDEXING_TYPES:
-        return true;
-    default:
-        break;
-    }
-    return false;
-}
-
-static inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length)
-{
-    VM& vm = state.vm();
-    auto scope = DECLARE_THROW_SCOPE(vm);
-
-    switch (thisObject->indexingType()) {
-    case ALL_INT32_INDEXING_TYPES: {
-        auto& butterfly = *thisObject->butterfly();
-        if (UNLIKELY(length > butterfly.publicLength()))
-            break;
-        JSStringJoiner joiner(state, separator, length);
-        RETURN_IF_EXCEPTION(scope, { });
-        auto data = butterfly.contiguous().data();
-        bool holesKnownToBeOK = false;
-        for (unsigned i = 0; i < length; ++i) {
-            JSValue value = data[i].get();
-            if (LIKELY(value))
-                joiner.appendNumber(vm, value.asInt32());
-            else {
-                if (!holesKnownToBeOK) {
-                    if (holesMustForwardToPrototype(vm, thisObject))
-                        goto generalCase;
-                    holesKnownToBeOK = true;
-                }
-                joiner.appendEmptyString();
-            }
-        }
-        scope.release();
-        return joiner.join(state);
-    }
-    case ALL_CONTIGUOUS_INDEXING_TYPES: {
-        auto& butterfly = *thisObject->butterfly();
-        if (UNLIKELY(length > butterfly.publicLength()))
-            break;
-        JSStringJoiner joiner(state, separator, length);
-        RETURN_IF_EXCEPTION(scope, { });
-        auto data = butterfly.contiguous().data();
-        bool holesKnownToBeOK = false;
-        for (unsigned i = 0; i < length; ++i) {
-            if (JSValue value = data[i].get()) {
-                if (!joiner.appendWithoutSideEffects(state, value))
-                    goto generalCase;
-            } else {
-                if (!holesKnownToBeOK) {
-                    if (holesMustForwardToPrototype(vm, thisObject))
-                        goto generalCase;
-                    holesKnownToBeOK = true;
-                }
-                joiner.appendEmptyString();
-            }
-        }
-        scope.release();
-        return joiner.join(state);
-    }
-    case ALL_DOUBLE_INDEXING_TYPES: {
-        auto& butterfly = *thisObject->butterfly();
-        if (UNLIKELY(length > butterfly.publicLength()))
-            break;
-        JSStringJoiner joiner(state, separator, length);
-        RETURN_IF_EXCEPTION(scope, { });
-        auto data = butterfly.contiguousDouble().data();
-        bool holesKnownToBeOK = false;
-        for (unsigned i = 0; i < length; ++i) {
-            double value = data[i];
-            if (LIKELY(!isHole(value)))
-                joiner.appendNumber(vm, value);
-            else {
-                if (!holesKnownToBeOK) {
-                    if (holesMustForwardToPrototype(vm, thisObject))
-                        goto generalCase;
-                    holesKnownToBeOK = true;
-                }
-                joiner.appendEmptyString();
-            }
-        }
-        scope.release();
-        return joiner.join(state);
-    }
-    }
-
-generalCase:
-    JSStringJoiner joiner(state, separator, length);
-    RETURN_IF_EXCEPTION(scope, { });
-    for (unsigned i = 0; i < length; ++i) {
-        JSValue element = thisObject->getIndex(&state, i);
-        RETURN_IF_EXCEPTION(scope, { });
-        joiner.append(state, element);
-        RETURN_IF_EXCEPTION(scope, { });
-    }
-    scope.release();
-    return joiner.join(state);
-}
-
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
 {
     VM& vm = exec->vm();