Array.concat should be fast for integer or double arrays
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 6 Jul 2015 17:45:29 +0000 (17:45 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 6 Jul 2015 17:45:29 +0000 (17:45 +0000)
https://bugs.webkit.org/show_bug.cgi?id=146260

Reviewed by Darin Adler.

Added a fast path to Array.prototype.concat. When concatenating two Int32, Double, or Contiguous
arrays, simply memcopy the arrays into a new uninitialized buffer.

This improves huffman encoding in CompressionBench by 3.7x on a Mid 2014 MacBookPro.

* runtime/ArrayPrototype.cpp:
(JSC::arrayProtoFuncConcat):
* runtime/JSArray.cpp:
(JSC::JSArray::fastConcatWith): Added.
* runtime/JSArray.h:
(JSC::JSArray::fastConcatType): Added. Returns the resultant array's indexing type if we can use
the fact path. Returns NonArray otherwise.

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/ArrayPrototype.cpp
Source/JavaScriptCore/runtime/JSArray.cpp
Source/JavaScriptCore/runtime/JSArray.h

index 112aef740d3feaaf318da88dee945f8e027f6f20..e57434ccf1fe254554777398d53365d25096cd62 100644 (file)
@@ -1,3 +1,23 @@
+2015-07-06  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Array.concat should be fast for integer or double arrays
+        https://bugs.webkit.org/show_bug.cgi?id=146260
+
+        Reviewed by Darin Adler.
+
+        Added a fast path to Array.prototype.concat. When concatenating two Int32, Double, or Contiguous
+        arrays, simply memcopy the arrays into a new uninitialized buffer.
+
+        This improves huffman encoding in CompressionBench by 3.7x on a Mid 2014 MacBookPro.
+
+        * runtime/ArrayPrototype.cpp:
+        (JSC::arrayProtoFuncConcat):
+        * runtime/JSArray.cpp:
+        (JSC::JSArray::fastConcatWith): Added.
+        * runtime/JSArray.h:
+        (JSC::JSArray::fastConcatType): Added. Returns the resultant array's indexing type if we can use
+        the fact path. Returns NonArray otherwise.
+
 2015-07-06  Youenn Fablet  <youenn.fablet@crf.canon.fr>
 
         [Streams API] Remove ReadableStream custom constructor
index e682429792077a05c22aec384dbcd8449fe24856..87ceae1cbef55cf76be8581e17c2b39c75803ade 100644 (file)
@@ -506,8 +506,12 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec)
     JSValue curArg = thisValue.toObject(exec);
     Checked<unsigned, RecordOverflow> finalArraySize = 0;
 
+    JSArray* currentArray = nullptr;
+    JSArray* previousArray = nullptr;
     for (unsigned i = 0; ; ++i) {
-        if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
+        previousArray = currentArray;
+        currentArray = jsDynamicCast<JSArray*>(curArg);
+        if (currentArray) {
             // Can't use JSArray::length here because this might be a RuntimeArray!
             finalArraySize += getLength(exec, currentArray);
             if (exec->hadException())
@@ -522,6 +526,12 @@ EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec)
     if (finalArraySize.hasOverflowed())
         return JSValue::encode(throwOutOfMemoryError(exec));
 
+    if (argCount == 1 && previousArray && currentArray && finalArraySize.unsafeGet() < MIN_SPARSE_ARRAY_INDEX) {
+        IndexingType type = JSArray::fastConcatType(exec->vm(), *previousArray, *currentArray);
+        if (type != NonArray)
+            return previousArray->fastConcatWith(*exec, *currentArray);
+    }
+
     JSArray* arr = constructEmptyArray(exec, nullptr, finalArraySize.unsafeGet());
     if (exec->hadException())
         return JSValue::encode(jsUndefined());
index 51914da67e8fb517ae1edf680b1399387d156eee..db4fb29672f47f346f05d329be1f8a74ac97b9a7 100644 (file)
@@ -707,6 +707,37 @@ JSArray* JSArray::fastSlice(ExecState& exec, unsigned startIndex, unsigned count
     }
 }
 
+EncodedJSValue JSArray::fastConcatWith(ExecState& exec, JSArray& otherArray)
+{
+    auto newArrayType = indexingType();
+    ASSERT(newArrayType == fastConcatType(*this, otherArray));
+
+    VM& vm = exec.vm();
+    unsigned thisArraySize = m_butterfly->publicLength();
+    unsigned otherArraySize = otherArray.m_butterfly->publicLength();
+    ASSERT(thisArraySize + otherArraySize < MIN_SPARSE_ARRAY_INDEX);
+
+    Structure* resultStructure = exec.lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(newArrayType);
+    JSArray* resultArray = JSArray::tryCreateUninitialized(vm, resultStructure, thisArraySize + otherArraySize);
+    if (!resultArray)
+        return JSValue::encode(throwOutOfMemoryError(&exec));
+
+    auto& resultButterfly = *resultArray->butterfly();
+    auto& otherButterfly = *otherArray.butterfly();
+    if (newArrayType == ArrayWithDouble) {
+        auto buffer = resultButterfly.contiguousDouble().data();
+        memcpy(buffer, m_butterfly->contiguousDouble().data(), sizeof(JSValue) * thisArraySize);
+        memcpy(buffer + thisArraySize, otherButterfly.contiguousDouble().data(), sizeof(JSValue) * otherArraySize);
+    } else {
+        auto buffer = resultButterfly.contiguous().data();
+        memcpy(buffer, m_butterfly->contiguous().data(), sizeof(JSValue) * thisArraySize);
+        memcpy(buffer + thisArraySize, otherButterfly.contiguous().data(), sizeof(JSValue) * otherArraySize);
+    }
+
+    resultButterfly.setPublicLength(thisArraySize + otherArraySize);
+    return JSValue::encode(resultArray);
+}
+
 bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
 {
     unsigned oldLength = storage->length();
index 72c40305576df17e9b43b57036ac039d34608359..45b558b20098118f9e3e16208947fce676b99eb5 100644 (file)
@@ -78,6 +78,20 @@ public:
 
     JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
 
+    static IndexingType fastConcatType(VM& vm, JSArray& firstArray, JSArray& secondArray)
+    {
+        IndexingType type = firstArray.indexingType();
+        if (type != secondArray.indexingType())
+            return NonArray;
+        if (type != ArrayWithDouble && type != ArrayWithInt32 && type != ArrayWithContiguous)
+            return NonArray;
+        if (firstArray.structure(vm)->holesMustForwardToPrototype(vm)
+            || secondArray.structure(vm)->holesMustForwardToPrototype(vm))
+            return NonArray;
+        return type;
+    }
+    EncodedJSValue fastConcatWith(ExecState&, JSArray&);
+
     enum ShiftCountMode {
         // This form of shift hints that we're doing queueing. With this assumption in hand,
         // we convert to ArrayStorage, which has queue optimizations.