Mercurial > hg > icedtea9-forest > nashorn

changeset 632:a2065f67857c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8026701: Array.prototype.splice is slow on dense arrays Reviewed-by: lagergren, sundar, jlaskey
author hannesw
date Thu, 17 Oct 2013 17:33:16 +0200
parents b01a10c7c7c2
children 66d27c77b455
files src/jdk/nashorn/internal/objects/NativeArray.java src/jdk/nashorn/internal/runtime/ScriptObject.java src/jdk/nashorn/internal/runtime/arrays/ArrayData.java src/jdk/nashorn/internal/runtime/arrays/IntArrayData.java src/jdk/nashorn/internal/runtime/arrays/LongArrayData.java src/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java src/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java test/examples/array-micro.js test/script/basic/JDK-8026701.js test/script/basic/JDK-8026701.js.EXPECTED
diffstat 10 files changed, 403 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/src/jdk/nashorn/internal/objects/NativeArray.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/objects/NativeArray.java	Thu Oct 17 17:33:16 2013 +0200
@@ -1007,19 +1007,42 @@
         final long actualStart = relativeStart < 0 ? Math.max(len + relativeStart, 0) : Math.min(relativeStart, len);
         final long actualDeleteCount = Math.min(Math.max(JSType.toLong(deleteCount), 0), len - actualStart);
 
-        final NativeArray array = new NativeArray(actualDeleteCount);
+        NativeArray returnValue;
+
+        if (actualStart <= Integer.MAX_VALUE && actualDeleteCount <= Integer.MAX_VALUE && bulkable(sobj)) {
+            try {
+                returnValue =  new NativeArray(sobj.getArray().fastSplice((int)actualStart, (int)actualDeleteCount, items.length));
 
-        for (long k = 0; k < actualDeleteCount; k++) {
-            final long from = actualStart + k;
+                // Since this is a dense bulkable array we can use faster defineOwnProperty to copy new elements
+                int k = (int) actualStart;
+                for (int i = 0; i < items.length; i++, k++) {
+                    sobj.defineOwnProperty(k, items[i]);
+                }
+            } catch (UnsupportedOperationException uoe) {
+                returnValue = slowSplice(sobj, actualStart, actualDeleteCount, items, len);
+            }
+        } else {
+            returnValue = slowSplice(sobj, actualStart, actualDeleteCount, items, len);
+        }
+
+        return returnValue;
+    }
+
+    private static NativeArray slowSplice(final ScriptObject sobj, final long start, final long deleteCount, final Object[] items, final long len) {
+
+        final NativeArray array = new NativeArray(deleteCount);
+
+        for (long k = 0; k < deleteCount; k++) {
+            final long from = start + k;
 
             if (sobj.has(from)) {
                 array.defineOwnProperty(ArrayIndex.getArrayIndex(k), sobj.get(from));
             }
         }
 
-        if (items.length < actualDeleteCount) {
-            for (long k = actualStart; k < (len - actualDeleteCount); k++) {
-                final long from = k + actualDeleteCount;
+        if (items.length < deleteCount) {
+            for (long k = start; k < (len - deleteCount); k++) {
+                final long from = k + deleteCount;
                 final long to   = k + items.length;
 
                 if (sobj.has(from)) {
@@ -1029,12 +1052,12 @@
                 }
             }
 
-            for (long k = len; k > (len - actualDeleteCount + items.length); k--) {
+            for (long k = len; k > (len - deleteCount + items.length); k--) {
                 sobj.delete(k - 1, true);
             }
-        } else if (items.length > actualDeleteCount) {
-            for (long k = len - actualDeleteCount; k > actualStart; k--) {
-                final long from = k + actualDeleteCount - 1;
+        } else if (items.length > deleteCount) {
+            for (long k = len - deleteCount; k > start; k--) {
+                final long from = k + deleteCount - 1;
                 final long to   = k + items.length - 1;
 
                 if (sobj.has(from)) {
@@ -1046,12 +1069,12 @@
             }
         }
 
-        long k = actualStart;
+        long k = start;
         for (int i = 0; i < items.length; i++, k++) {
             sobj.set(k, items[i], true);
         }
 
-        final long newLength = len - actualDeleteCount + items.length;
+        final long newLength = len - deleteCount + items.length;
         sobj.set("length", newLength, true);
 
         return array;
--- a/src/jdk/nashorn/internal/runtime/ScriptObject.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/ScriptObject.java	Thu Oct 17 17:33:16 2013 +0200
@@ -594,7 +594,7 @@
      * @param index key for property
      * @param value value to define
      */
-    protected final void defineOwnProperty(final int index, final Object value) {
+    public final void defineOwnProperty(final int index, final Object value) {
         assert isValidArrayIndex(index) : "invalid array index";
         final long longIndex = ArrayIndex.toLongIndex(index);
         if (longIndex >= getArray().length()) {
--- a/src/jdk/nashorn/internal/runtime/arrays/ArrayData.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/arrays/ArrayData.java	Thu Oct 17 17:33:16 2013 +0200
@@ -461,7 +461,23 @@
      */
     public abstract ArrayData slice(long from, long to);
 
-    private static Class<?> widestType(final Object... items) {
+    /**
+     * Fast splice operation. This just modifies the array according to the number of
+     * elements added and deleted but does not insert the added elements. Throws
+     * {@code UnsupportedOperationException} if fast splice operation is not supported
+     * for this class or arguments.
+     *
+     * @param start start index of splice operation
+     * @param removed number of removed elements
+     * @param added number of added elements
+     * @throws UnsupportedOperationException if fast splice is not supported for the class or arguments.
+     */
+    public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
+        throw new UnsupportedOperationException();
+    }
+
+
+    static Class<?> widestType(final Object... items) {
         assert items.length > 0;
 
         Class<?> widest = Integer.class;
--- a/src/jdk/nashorn/internal/runtime/arrays/IntArrayData.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/arrays/IntArrayData.java	Thu Oct 17 17:33:16 2013 +0200
@@ -269,4 +269,32 @@
 
         return new IntArrayData(Arrays.copyOfRange(array, (int)from, (int)to), (int)newLength);
     }
+
+    @Override
+    public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
+        final long oldLength = length();
+        final long newLength = oldLength - removed + added;
+        if (newLength > SparseArrayData.MAX_DENSE_LENGTH && newLength > array.length) {
+            throw new UnsupportedOperationException();
+        }
+        final ArrayData returnValue = (removed == 0) ?
+                EMPTY_ARRAY : new IntArrayData(Arrays.copyOfRange(array, start, start + removed), removed);
+
+        if (newLength != oldLength) {
+            final int[] newArray;
+
+            if (newLength > array.length) {
+                newArray = new int[ArrayData.nextSize((int)newLength)];
+                System.arraycopy(array, 0, newArray, 0, start);
+            } else {
+                newArray = array;
+            }
+
+            System.arraycopy(array, start + removed, newArray, start + added, (int)(oldLength - start - removed));
+            array = newArray;
+            setLength(newLength);
+        }
+
+        return returnValue;
+    }
 }
--- a/src/jdk/nashorn/internal/runtime/arrays/LongArrayData.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/arrays/LongArrayData.java	Thu Oct 17 17:33:16 2013 +0200
@@ -92,7 +92,7 @@
 
     @Override
     public ArrayData convert(final Class<?> type) {
-        if (type == Long.class) {
+        if (type == Integer.class || type == Long.class) {
             return this;
         }
         final int length = (int) length();
@@ -238,4 +238,32 @@
         final long newLength = to - start;
         return new LongArrayData(Arrays.copyOfRange(array, (int)from, (int)to), (int)newLength);
     }
+
+    @Override
+    public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
+        final long oldLength = length();
+        final long newLength = oldLength - removed + added;
+        if (newLength > SparseArrayData.MAX_DENSE_LENGTH && newLength > array.length) {
+            throw new UnsupportedOperationException();
+        }
+        final ArrayData returnValue = (removed == 0) ?
+                EMPTY_ARRAY : new LongArrayData(Arrays.copyOfRange(array, start, start + removed), removed);
+
+        if (newLength != oldLength) {
+            final long[] newArray;
+
+            if (newLength > array.length) {
+                newArray = new long[ArrayData.nextSize((int)newLength)];
+                System.arraycopy(array, 0, newArray, 0, start);
+            } else {
+                newArray = array;
+            }
+
+            System.arraycopy(array, start + removed, newArray, start + added, (int)(oldLength - start - removed));
+            array = newArray;
+            setLength(newLength);
+        }
+
+        return returnValue;
+    }
 }
--- a/src/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java	Thu Oct 17 17:33:16 2013 +0200
@@ -218,4 +218,32 @@
         final long newLength = to - start;
         return new NumberArrayData(Arrays.copyOfRange(array, (int)from, (int)to), (int)newLength);
     }
+
+    @Override
+    public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
+        final long oldLength = length();
+        final long newLength = oldLength - removed + added;
+        if (newLength > SparseArrayData.MAX_DENSE_LENGTH && newLength > array.length) {
+            throw new UnsupportedOperationException();
+        }
+        final ArrayData returnValue = (removed == 0) ?
+                EMPTY_ARRAY : new NumberArrayData(Arrays.copyOfRange(array, start, start + removed), removed);
+
+        if (newLength != oldLength) {
+            final double[] newArray;
+
+            if (newLength > array.length) {
+                newArray = new double[ArrayData.nextSize((int)newLength)];
+                System.arraycopy(array, 0, newArray, 0, start);
+            } else {
+                newArray = array;
+            }
+
+            System.arraycopy(array, start + removed, newArray, start + added, (int)(oldLength - start - removed));
+            array = newArray;
+            setLength(newLength);
+        }
+
+        return returnValue;
+    }
 }
--- a/src/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java	Thu Oct 17 12:38:50 2013 +0200
+++ b/src/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java	Thu Oct 17 17:33:16 2013 +0200
@@ -206,4 +206,32 @@
         final long newLength = to - start;
         return new ObjectArrayData(Arrays.copyOfRange(array, (int)from, (int)to), (int)newLength);
     }
+
+    @Override
+    public ArrayData fastSplice(final int start, final int removed, final int added) throws UnsupportedOperationException {
+        final long oldLength = length();
+        final long newLength = oldLength - removed + added;
+        if (newLength > SparseArrayData.MAX_DENSE_LENGTH && newLength > array.length) {
+            throw new UnsupportedOperationException();
+        }
+        final ArrayData returnValue = (removed == 0) ?
+                EMPTY_ARRAY : new ObjectArrayData(Arrays.copyOfRange(array, start, start + removed), removed);
+
+        if (newLength != oldLength) {
+            final Object[] newArray;
+
+            if (newLength > array.length) {
+                newArray = new Object[ArrayData.nextSize((int)newLength)];
+                System.arraycopy(array, 0, newArray, 0, start);
+            } else {
+                newArray = array;
+            }
+
+            System.arraycopy(array, start + removed, newArray, start + added, (int)(oldLength - start - removed));
+            array = newArray;
+            setLength(newLength);
+        }
+
+        return returnValue;
+    }
 }
--- a/test/examples/array-micro.js	Thu Oct 17 12:38:50 2013 +0200
+++ b/test/examples/array-micro.js	Thu Oct 17 17:33:16 2013 +0200
@@ -90,6 +90,24 @@
     array[6] = 6;
 });
 
+bench("push", function() {
+    var arr = [1, 2, 3];
+    arr.push(4);
+    arr.push(5);
+    arr.push(6);
+});
+
+bench("pop", function() {
+    var arr = [1, 2, 3];
+    arr.pop();
+    arr.pop();
+    arr.pop();
+});
+
+bench("splice", function() {
+    [1, 2, 3].splice(0, 2, 5, 6, 7);
+});
+
 var all = function(e) { return true; };
 var none = function(e) { return false; };
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/script/basic/JDK-8026701.js	Thu Oct 17 17:33:16 2013 +0200
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ * 
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ * 
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ * 
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ * 
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * JDK-8026701: Array.prototype.splice is slow on dense arrays
+ *
+ * @test
+ * @run
+ */
+
+function testSplice(arr, e1, e2, e3) {
+    try {
+        print(arr);
+        print(arr.splice(3, 0, e1, e2, e3));
+        print(arr);
+        print(arr.splice(2, 3));
+        print(arr);
+        print(arr.splice(2, 3, arr[2], arr[3], arr[4]));
+        print(arr);
+        print(arr.splice(20, 10));
+        print(arr);
+        print(arr.splice(arr.length, 0, e1, e2, e3));
+        print(arr);
+        print(arr.splice(0, 2, arr[0], arr[1], arr[2], arr[3]));
+        print(arr);
+    } catch (error) {
+        print(error);
+    }
+}
+
+function convert(array, type) {
+    return (typeof Java === "undefined") ? array : Java.from(Java.to(array, type));
+}
+
+// run some splice tests on all dense array implementations
+testSplice([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], -1, -2, -3);
+testSplice(convert([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "long[]"), -1, -2, -3);
+testSplice(convert([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "double[]"), -1, -2, -3);
+testSplice(["1", "2", "3", "4", "5", "6", "7", "8", "9", "10"], -1, -2, -3);
+
+// test array conversion during splice
+testSplice([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], -1, "-2", "-3");
+testSplice([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], -1, -2.5, -3.5);
+testSplice(convert([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "long[]"), -1, "-2", "-3");
+testSplice(convert([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "long[]"), -1, -2.5, -3.5);
+testSplice(convert([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], "double[]"), -1, "-2", "-3");
+
+// test combination with defined elements
+testSplice(Object.defineProperty([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, {value: 13}), -1, -2, -3);
+testSplice(Object.defineProperty([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, {value: 13, writable: false}), -1, -2, -3);
+testSplice(Object.defineProperty([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, {value: 13, configurable: false}), -1, -2, -3);
+testSplice(Object.defineProperty([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, {value: 13, writable: false, configurable: false}), -1, -2, -3);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/script/basic/JDK-8026701.js.EXPECTED	Thu Oct 17 17:33:16 2013 +0200
@@ -0,0 +1,147 @@
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2.5,-3.5,4,5,6,7,8,9,10
+3,-1,-2.5
+1,2,-3.5,4,5,6,7,8,9,10
+-3.5,4,5
+1,2,-3.5,4,5,6,7,8,9,10
+
+1,2,-3.5,4,5,6,7,8,9,10
+
+1,2,-3.5,4,5,6,7,8,9,10,-1,-2.5,-3.5
+1,2
+1,2,-3.5,4,-3.5,4,5,6,7,8,9,10,-1,-2.5,-3.5
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2.5,-3.5,4,5,6,7,8,9,10
+3,-1,-2.5
+1,2,-3.5,4,5,6,7,8,9,10
+-3.5,4,5
+1,2,-3.5,4,5,6,7,8,9,10
+
+1,2,-3.5,4,5,6,7,8,9,10
+
+1,2,-3.5,4,5,6,7,8,9,10,-1,-2.5,-3.5
+1,2
+1,2,-3.5,4,-3.5,4,5,6,7,8,9,10,-1,-2.5,-3.5
+1,2,3,4,5,6,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,6,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,6,7,8,9,10
+-3,4,5
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10
+
+1,2,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,6,7,8,9,10,-1,-2,-3
+1,2,3,4,5,13,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,13,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,13,7,8,9,10
+-3,4,5
+1,2,-3,4,5,13,7,8,9,10
+
+1,2,-3,4,5,13,7,8,9,10
+
+1,2,-3,4,5,13,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,13,7,8,9,10,-1,-2,-3
+1,2,3,4,5,13,7,8,9,10
+TypeError: "5" is not a writable property of [object Array]
+1,2,3,4,5,13,7,8,9,10
+
+1,2,3,-1,-2,-3,4,5,13,7,8,9,10
+3,-1,-2
+1,2,-3,4,5,13,7,8,9,10
+-3,4,5
+1,2,-3,4,5,13,7,8,9,10
+
+1,2,-3,4,5,13,7,8,9,10
+
+1,2,-3,4,5,13,7,8,9,10,-1,-2,-3
+1,2
+1,2,-3,4,-3,4,5,13,7,8,9,10,-1,-2,-3
+1,2,3,4,5,13,7,8,9,10
+TypeError: "5" is not a writable property of [object Array]