Large array shouldn't be slow
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 5 May 2015 02:40:28 +0000 (02:40 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 5 May 2015 02:40:28 +0000 (02:40 +0000)
https://bugs.webkit.org/show_bug.cgi?id=144617

Reviewed by Geoffrey Garen.

PerformanceTests:

Add the hash-map benchmark to LongSpider. LongSpider was already not a perfect match of
SunSpider. It's not an official benchmark. It contains benchmarks that are relatively
long-running. So, hash-map sort of belongs here.

* LongSpider/hash-map.js: Added.
(HashMap):
(HashMap.):
(.get var):

Source/JavaScriptCore:

Decouple MIN_SPARSE_ARRAY_INDEX, which is the threshold for storing to the sparse map when
you're already using ArrayStorage mode, from the minimul array length required to use
ArrayStorage in a new Array(length) allocation.

Lift the array allocation length threshold to something very high. If this works, we'll
probably remove that threshold entirely.

This is a 27% speed-up on JetStream/hash-map. Because run-jsc-benchmarks still can't run
JetStream as a discrete suite, this adds hash-map to LongSpider so that we run it somewhere
for now.

* dfg/DFGCallArrayAllocatorSlowPathGenerator.h:
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::compileNewArrayWithSize):
* runtime/ArrayConventions.h:
* runtime/JSArray.h:
(JSC::JSArray::create):
* runtime/JSGlobalObject.h:
(JSC::constructEmptyArray):
* tests/stress/new-array-storage-array-with-size.js: Skip this test until we fix https://bugs.webkit.org/show_bug.cgi?id=144609.

Tools:

Add the hash-map benchmark to LongSpider. LongSpider was already not a perfect match of
SunSpider. It's not an official benchmark. It contains benchmarks that are relatively
long-running. So, hash-map sort of belongs here.

* Scripts/run-jsc-benchmarks:

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

13 files changed:
PerformanceTests/ChangeLog
PerformanceTests/LongSpider/hash-map.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGCallArrayAllocatorSlowPathGenerator.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/runtime/ArrayConventions.h
Source/JavaScriptCore/runtime/JSArray.h
Source/JavaScriptCore/runtime/JSGlobalObject.h
Source/JavaScriptCore/tests/stress/new-array-storage-array-with-size.js
Tools/ChangeLog
Tools/Scripts/run-jsc-benchmarks

index e6858c5..85c2b33 100644 (file)
@@ -1,3 +1,19 @@
+2015-05-04  Filip Pizlo  <fpizlo@apple.com>
+
+        Large array shouldn't be slow
+        https://bugs.webkit.org/show_bug.cgi?id=144617
+
+        Reviewed by Geoffrey Garen.
+        
+        Add the hash-map benchmark to LongSpider. LongSpider was already not a perfect match of
+        SunSpider. It's not an official benchmark. It contains benchmarks that are relatively
+        long-running. So, hash-map sort of belongs here.
+
+        * LongSpider/hash-map.js: Added.
+        (HashMap):
+        (HashMap.):
+        (.get var):
+
 2015-05-01  Dewei Zhu  <dewei_zhu@apple.com>
 
         Fix typo bug in Speedometer/resources/main.js
diff --git a/PerformanceTests/LongSpider/hash-map.js b/PerformanceTests/LongSpider/hash-map.js
new file mode 100644 (file)
index 0000000..c9dff25
--- /dev/null
@@ -0,0 +1,602 @@
+//@ runDefault
+
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE below for additional
+ *  information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+/******* NOTICE *********
+
+Apache Harmony
+Copyright 2006, 2010 The Apache Software Foundation.
+
+This product includes software developed at
+The Apache Software Foundation (http://www.apache.org/).
+
+Portions of Apache Harmony were originally developed by
+Intel Corporation and are licensed to the Apache Software
+Foundation under the "Software Grant and Corporate Contribution
+License Agreement" and for which the following copyright notices
+apply
+         (C) Copyright 2005 Intel Corporation
+         (C) Copyright 2005-2006 Intel Corporation
+         (C) Copyright 2006 Intel Corporation
+
+
+The following copyright notice(s) were affixed to portions of the code
+with which this file is now or was at one time distributed
+and are placed here unaltered.
+
+(C) Copyright 1997,2004 International Business Machines Corporation.
+All rights reserved.
+
+(C) Copyright IBM Corp. 2003. 
+
+
+This software contains code derived from UNIX V7, Copyright(C)
+Caldera International Inc.
+
+************************/
+
+// This code is a manual translation of Apache Harmony's HashMap class to
+// JavaScript.
+
+var HashMap = (function() {
+    var DEFAULT_SIZE = 16;
+    
+    function calculateCapacity(x)
+    {
+        if (x >= 1 << 30)
+            return 1 << 30;
+        if (x == 0)
+            return 16;
+        x = x - 1;
+        x |= x >> 1;
+        x |= x >> 2;
+        x |= x >> 4;
+        x |= x >> 8;
+        x |= x >> 16;
+        return x + 1;
+    }
+    
+    function computeHashCode(key)
+    {
+        switch (typeof key) {
+        case "undefined":
+            return 0;
+        case "object":
+            if (!key)
+                return 0;
+        case "function":
+            return key.hashCode();
+        case "boolean":
+            return key | 0;
+        case "number":
+            if ((key | 0) == key)
+                return key;
+            key = "" + key; // Compute string hash of the double. It's the best we can do.
+        case "string":
+            // source: http://en.wikipedia.org/wiki/Java_hashCode()#Sample_implementations_of_the_java.lang.String_algorithm
+            var h = 0;
+            var len = key.length;
+            for (var index = 0; index < len; index++) {
+                h = (((31 * h) | 0) + key.charCodeAt(index)) | 0;
+            }
+            return h;
+        default:
+            throw new Error("Internal error: Bad JavaScript value type");
+        }
+    }
+    
+    function equals(a, b)
+    {
+        if (typeof a != typeof b)
+            return false;
+        switch (typeof a) {
+        case "object":
+            if (!a)
+                return !b;
+        case "function":
+            switch (typeof b) {
+            case "object":
+            case "function":
+                return a.equals(b);
+            default:
+                return false;
+            }
+        default:
+            return a == b;
+        }
+    }
+    
+    function Entry(key, hash, value)
+    {
+        this._key = key;
+        this._value = value;
+        this._origKeyHash = hash;
+        this._next = null;
+    }
+
+    Entry.prototype = {
+        clone: function()
+        {
+            var result = new Entry(this._key, this._hash, this._value);
+            if (this._next)
+                result._next = this._next.clone();
+            return result;
+        },
+        
+        toString: function()
+        {
+            return this._key + "=" + this._value;
+        },
+        
+        get key()
+        {
+            return this._key;
+        },
+        
+        get value()
+        {
+            return this._value;
+        }
+    };
+    
+    function AbstractMapIterator(map)
+    {
+        this._associatedMap = map;
+        this._expectedModCount = map._modCount;
+        this._futureEntry = null;
+        this._currentEntry = null;
+        this._prevEntry = null;
+        this._position = 0;
+    }
+    
+    AbstractMapIterator.prototype = {
+        hasNext: function()
+        {
+            if (this._futureEntry)
+                return true;
+            while (this._position < this._associatedMap._elementData.length) {
+                if (!this._associatedMap._elementData[this._position])
+                    this._position++;
+                else
+                    return true;
+            }
+            return false;
+        },
+        
+        _checkConcurrentMod: function()
+        {
+            if (this._expectedModCount != this._associatedMap._modCount)
+                throw new Error("Concurrent HashMap modification detected");
+        },
+        
+        _makeNext: function()
+        {
+            this._checkConcurrentMod();
+            if (!this.hasNext())
+                throw new Error("No such element");
+            if (!this._futureEntry) {
+                this._currentEntry = this._associatedMap._elementData[this._position++];
+                this._futureEntry = this._currentEntry._next;
+                this._prevEntry = null;
+                return;
+            }
+            if (this._currentEntry)
+                this._prevEntry = this._currentEntry;
+            this._currentEntry = this._futureEntry;
+            this._futureEntry = this._futureEntry._next;
+        },
+        
+        remove: function()
+        {
+            this._checkConcurrentMod();
+            if (!this._currentEntry)
+                throw new Error("Illegal state");
+            if (!this._prevEntry) {
+                var index = this._currentEntry._origKeyHash & (this._associatedMap._elementData.length - 1);
+                this._associatedMap._elementData[index] = this._associatedMap._elementData[index]._next;
+            } else
+                this._prevEntry._next = this._currentEntry._next;
+            this._currentEntry = null;
+            this._expectedModCount++;
+            this._associatedMap._modCount++;
+            this._associatedMap._elementCount--;
+        }
+    };
+    
+    function EntryIterator(map)
+    {
+        AbstractMapIterator.call(this, map);
+    }
+    
+    EntryIterator.prototype = {
+        next: function()
+        {
+            this._makeNext();
+            return this._currentEntry;
+        }
+    };
+    EntryIterator.prototype.__proto__ = AbstractMapIterator.prototype;
+    
+    function KeyIterator(map)
+    {
+        AbstractMapIterator.call(this, map);
+    }
+    
+    KeyIterator.prototype = {
+        next: function()
+        {
+            this.makeNext();
+            return this._currentEntry._key;
+        }
+    };
+    KeyIterator.prototype.__proto__ = AbstractMapIterator.prototype;
+    
+    function ValueIterator(map)
+    {
+        AbstractMapIterator.call(this, map);
+    }
+    
+    ValueIterator.prototype = {
+        next: function()
+        {
+            this.makeNext();
+            return this._currentEntry._value;
+        }
+    };
+    ValueIterator.prototype.__proto__ = AbstractMapIterator.prototype;
+    
+    function EntrySet(map)
+    {
+        this._associatedMap = map;
+    }
+    
+    EntrySet.prototype = {
+        size: function()
+        {
+            return this._associatedMap._elementCount;
+        },
+        
+        clear: function()
+        {
+            this._associatedMap.clear();
+        },
+        
+        remove: function(object)
+        {
+            var entry = this._associatedMap._getEntry(object.key);
+            if (!entry)
+                return false;
+            if (!equals(entry._value, object.value))
+                return false;
+            this._associatedMap._removeEntry(entry);
+            return true;
+        },
+        
+        contains: function(object)
+        {
+            var entry = this._associatedMap._getEntry(object.key);
+            if (!entry)
+                return false;
+            return equals(entry._value, object.value);
+        },
+        
+        iterator: function()
+        {
+            return new EntryIterator(this._associatedMap);
+        }
+    };
+    
+    function KeySet(map)
+    {
+        this._associatedMap = map;
+    }
+    
+    KeySet.prototype = {
+        contains: function(object)
+        {
+            return this._associatedMap.contains(object);
+        },
+        
+        size: function()
+        {
+            return this._associatedMap._elementCount;
+        },
+        
+        clear: function()
+        {
+            this._associatedMap.clear();
+        },
+        
+        remove: function(key)
+        {
+            return !!this._associatedMap.remove(key);
+        },
+        
+        iterator: function()
+        {
+            return new KeyIterator(this._associatedMap);
+        }
+    };
+    
+    function ValueCollection(map)
+    {
+        this._associatedMap = map;
+    }
+    
+    ValueCollection.prototype = {
+        contains: function(object)
+        {
+            return this._associatedMap.containsValue(object);
+        },
+        
+        size: function()
+        {
+            return this._associatedMap._elementCount;
+        },
+        
+        clear: function()
+        {
+            this._associatedMap.clear();
+        },
+        
+        iterator: function()
+        {
+            return new ValueIterator(this._associatedMap);
+        }
+    };
+    
+    function HashMap(capacity, loadFactor)
+    {
+        if (capacity == null)
+            capacity = DEFAULT_SIZE;
+        if (loadFactor == null)
+            loadFactor = 0.75;
+        
+        if (capacity < 0)
+            throw new Error("Invalid argument to HashMap constructor: capacity is negative");
+        if (loadFactor <= 0)
+            throw new Error("Invalid argument to HashMap constructor: loadFactor is not positive");
+        
+        this._capacity = calculateCapacity(capacity);
+        this._elementCount = 0;
+        this._elementData = new Array(this.capacity);
+        this._loadFactor = loadFactor;
+        this._modCount = 0;
+        this._computeThreshold();
+    }
+    
+    HashMap.prototype = {
+        _computeThreshold: function()
+        {
+            this._threshold = (this._elementData.length * this._loadFactor) | 0;
+        },
+        
+        clear: function()
+        {
+            if (!this._elementCount)
+                return;
+            
+            this._elementCount = 0;
+            for (var i = this._elementData.length; i--;)
+                this._elementData[i] = null;
+            this._modCount++;
+        },
+        
+        clone: function()
+        {
+            var result = new HashMap(this._elementData.length, this._loadFactor);
+            result.putAll(this);
+            return result;
+        },
+        
+        containsKey: function(key)
+        {
+            return !!this._getEntry(key);
+        },
+        
+        containsValue: function(value)
+        {
+            for (var i = this._elementData.length; i--;) {
+                for (var entry = this._elementData[i]; entry; entry = entry._next) {
+                    if (equals(value, entry._value))
+                        return true;
+                }
+            }
+            return false;
+        },
+        
+        entrySet: function()
+        {
+            return new EntrySet(this);
+        },
+        
+        get: function(key)
+        {
+            var entry = this._getEntry(key);
+            if (entry)
+                return entry._value;
+            return null;
+        },
+        
+        _getEntry: function(key)
+        {
+            var hash = computeHashCode(key);
+            var index = hash & (this._elementData.length - 1);
+            return this._findKeyEntry(key, index, hash);
+        },
+        
+        _findKeyEntry: function(key, index, keyHash)
+        {
+            var entry = this._elementData[index];
+            while (entry && (entry._origKeyHash != keyHash || !equals(key, entry._key)))
+                entry = entry._next;
+            return entry;
+        },
+        
+        isEmpty: function()
+        {
+            return !this._elementCount;
+        },
+        
+        keySet: function()
+        {
+            return new KeySet(this);
+        },
+        
+        put: function(key, value)
+        {
+            var hash = computeHashCode(key);
+            var index = hash & (this._elementData.length - 1);
+            var entry = this._findKeyEntry(key, index, hash);
+            if (!entry) {
+                this._modCount++;
+                entry = this._createHashedEntry(key, index, hash);
+                if (++this._elementCount > this._threshold)
+                    this._rehash();
+            }
+            
+            var result = entry._value;
+            entry._value = value;
+            return result;
+        },
+        
+        _createHashedEntry: function(key, index, hash)
+        {
+            var entry = new Entry(key, hash, null);
+            entry._next = this._elementData[index];
+            this._elementData[index] = entry;
+            return entry;
+        },
+        
+        putAll: function(map)
+        {
+            if (map.isEmpty())
+                return;
+            for (var iter = map.entrySet().iterator(); iter.hasNext();) {
+                var entry = iter.next();
+                put(entry.key, entry.value);
+            }
+        },
+        
+        _rehash: function(capacity)
+        {
+            if (capacity == null)
+                capacity = this._elementData.length;
+            
+            var length = calculateCapacity(!capacity ? 1 : capacity << 1);
+            var newData = new Array(length);
+            for (var i = 0; i < this._elementData.length; ++i) {
+                var entry = this._elementData[i];
+                this._elementData[i] = null;
+                while (entry) {
+                    var index = entry._origKeyHash & (length - 1);
+                    var next = entry._next;
+                    entry._next = newData[index];
+                    newData[index] = entry;
+                    entry = next;
+                }
+            }
+            this._elementData = newData;
+            this._computeThreshold();
+        },
+        
+        remove: function(key)
+        {
+            var entry = this._removeEntryForKey(key);
+            if (!entry)
+                return null;
+            return entry._value;
+        },
+        
+        _removeEntry: function(entry)
+        {
+            var index = entry._origKeyHash & (this._elementData.length - 1);
+            var current = this._elementData[index];
+            if (current == entry)
+                this._elementData[index] = entry._next;
+            else {
+                while (current._next != entry)
+                    current = current._next;
+                current._next = entry._next;
+            }
+            this._modCount++;
+            this._elementCount--;
+        },
+        
+        _removeEntryForKey: function(key)
+        {
+            var hash = computeHashCode(key);
+            var index = hash & (this._elementData.length - 1);
+            var entry = this._elementData[index];
+            var last = null;
+            while (entry != null && !(entry._origKeyHash == hash && equals(key, entry._key))) {
+                last = entry;
+                entry = entry._next;
+            }
+            if (!entry)
+                return null;
+            if (!last)
+                this._elementData[index] = entry._next;
+            else
+                last._next = entry._next;
+            this._modCount++;
+            this._elementCount--;
+            return entry;
+        },
+        
+        size: function()
+        {
+            return this._elementCount;
+        },
+        
+        values: function()
+        {
+            return new ValueCollection(this);
+        }
+    };
+    
+    return HashMap;
+})();
+
+var map = new HashMap();
+var COUNT = 500000;
+
+for (var i = 0; i < COUNT; ++i)
+    map.put(i, 42);
+
+var result = 0;
+for (var j = 0; j < 5; ++j) {
+    for (var i = 0; i < COUNT; ++i)
+        result += map.get(i);
+}
+
+var keySum = 0;
+var valueSum = 0;
+for (var iterator = map.entrySet().iterator(); iterator.hasNext();) {
+    var entry = iterator.next();
+    keySum += entry.key;
+    valueSum += entry.value;
+}
+
+if (result != 105000000)
+    throw "Error: result = " + result;
+if (keySum != 124999750000)
+    throw "Error: keySum = " + keySum;
+if (valueSum != 21000000)
+    throw "Error: valueSum = " + valueSum;
+
index 544a15c..bc340c6 100644 (file)
@@ -1,3 +1,35 @@
+2015-05-04  Filip Pizlo  <fpizlo@apple.com>
+
+        Large array shouldn't be slow
+        https://bugs.webkit.org/show_bug.cgi?id=144617
+
+        Reviewed by Geoffrey Garen.
+        
+        Decouple MIN_SPARSE_ARRAY_INDEX, which is the threshold for storing to the sparse map when
+        you're already using ArrayStorage mode, from the minimul array length required to use
+        ArrayStorage in a new Array(length) allocation.
+        
+        Lift the array allocation length threshold to something very high. If this works, we'll
+        probably remove that threshold entirely.
+        
+        This is a 27% speed-up on JetStream/hash-map. Because run-jsc-benchmarks still can't run
+        JetStream as a discrete suite, this adds hash-map to LongSpider so that we run it somewhere
+        for now.
+
+        * dfg/DFGCallArrayAllocatorSlowPathGenerator.h:
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * ftl/FTLLowerDFGToLLVM.cpp:
+        (JSC::FTL::LowerDFGToLLVM::compileNewArrayWithSize):
+        * runtime/ArrayConventions.h:
+        * runtime/JSArray.h:
+        (JSC::JSArray::create):
+        * runtime/JSGlobalObject.h:
+        (JSC::constructEmptyArray):
+        * tests/stress/new-array-storage-array-with-size.js: Skip this test until we fix https://bugs.webkit.org/show_bug.cgi?id=144609.
+
 2015-05-03  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Add backed intrinsics to private functions exposed with private symbols in global object
index 02abdfd..9780e50 100644 (file)
@@ -96,7 +96,7 @@ protected:
         for (unsigned i = 0; i < m_plans.size(); ++i)
             jit->silentSpill(m_plans[i]);
         GPRReg scratchGPR = AssemblyHelpers::selectScratchGPR(m_sizeGPR);
-        MacroAssembler::Jump bigLength = jit->m_jit.branch32(MacroAssembler::AboveOrEqual, m_sizeGPR, MacroAssembler::TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
+        MacroAssembler::Jump bigLength = jit->m_jit.branch32(MacroAssembler::AboveOrEqual, m_sizeGPR, MacroAssembler::TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
         jit->m_jit.move(MacroAssembler::TrustedImmPtr(m_contiguousStructure), scratchGPR);
         MacroAssembler::Jump done = jit->m_jit.jump();
         bigLength.link(&jit->m_jit);
index f9ca771..745c9a8 100644 (file)
@@ -3317,7 +3317,7 @@ void SpeculativeJIT::compile(Node* node)
             GPRReg scratch2GPR = scratch2.gpr();
             
             MacroAssembler::JumpList slowCases;
-            slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX)));
+            slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
             
             ASSERT((1 << 3) == sizeof(JSValue));
             m_jit.move(sizeGPR, scratchGPR);
@@ -3361,7 +3361,7 @@ void SpeculativeJIT::compile(Node* node)
         GPRFlushedCallResult result(this);
         GPRReg resultGPR = result.gpr();
         GPRReg structureGPR = selectScratchGPR(sizeGPR);
-        MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
+        MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
         m_jit.move(TrustedImmPtr(globalObject->arrayStructureForIndexingTypeDuringAllocation(node->indexingType())), structureGPR);
         MacroAssembler::Jump done = m_jit.jump();
         bigLength.link(&m_jit);
index 35c41e4..9e9b1c9 100644 (file)
@@ -3408,7 +3408,7 @@ void SpeculativeJIT::compile(Node* node)
             GPRReg scratch2GPR = scratch2.gpr();
             
             MacroAssembler::JumpList slowCases;
-            slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX)));
+            slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
             
             ASSERT((1 << 3) == sizeof(JSValue));
             m_jit.move(sizeGPR, scratchGPR);
@@ -3450,7 +3450,7 @@ void SpeculativeJIT::compile(Node* node)
         GPRFlushedCallResult result(this);
         GPRReg resultGPR = result.gpr();
         GPRReg structureGPR = selectScratchGPR(sizeGPR);
-        MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
+        MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
         m_jit.move(TrustedImmPtr(globalObject->arrayStructureForIndexingTypeDuringAllocation(node->indexingType())), structureGPR);
         MacroAssembler::Jump done = m_jit.jump();
         bigLength.link(&m_jit);
index e3e0e30..901700b 100644 (file)
@@ -3249,7 +3249,7 @@ private:
             LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("NewArrayWithSize continuation"));
             
             m_out.branch(
-                m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_SPARSE_ARRAY_INDEX)),
+                m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)),
                 rarely(largeCase), usually(fastCase));
 
             LBasicBlock lastNext = m_out.appendTo(fastCase, largeCase);
@@ -3325,7 +3325,7 @@ private:
         }
         
         LValue structureValue = m_out.select(
-            m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_SPARSE_ARRAY_INDEX)),
+            m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)),
             m_out.constIntPtr(
                 globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage)),
             m_out.constIntPtr(structure));
index 988cbc4..9c62ea9 100644 (file)
@@ -58,7 +58,14 @@ namespace JSC {
 
 // These values have to be macros to be used in max() and min() without introducing
 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
+
+// If you grow an ArrayStorage array by more than this, then the array will go sparse. Note that we
+// could probably make this smaller (it's large because it used to be conflated with
+// MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH).
 #define MIN_SPARSE_ARRAY_INDEX 100000U
+// If you try to allocate a contiguous array larger than this, then we will allocate an ArrayStorage
+// array instead. We allow for an array that occupies 1GB of VM.
+#define MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH 1024 * 1024 * 1024 / 8
 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
index 6208ba8..ea3431a 100644 (file)
@@ -200,7 +200,7 @@ inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLe
             || hasContiguous(structure->indexingType()));
         unsigned vectorLength;
         butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
-        ASSERT(initialLength < MIN_SPARSE_ARRAY_INDEX);
+        ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH);
         if (hasDouble(structure->indexingType())) {
             for (unsigned i = 0; i < vectorLength; ++i)
                 butterfly->contiguousDouble()[i] = PNaN;
index 589fa39..7acc1dd 100644 (file)
@@ -672,7 +672,7 @@ inline bool JSGlobalObject::symbolTableHasProperty(PropertyName propertyName)
 
 inline JSArray* constructEmptyArray(ExecState* exec, ArrayAllocationProfile* profile, JSGlobalObject* globalObject, unsigned initialLength = 0)
 {
-    return ArrayAllocationProfile::updateLastAllocationFor(profile, JSArray::create(exec->vm(), initialLength >= MIN_SPARSE_ARRAY_INDEX ? globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage) : globalObject->arrayStructureForProfileDuringAllocation(profile), initialLength));
+    return ArrayAllocationProfile::updateLastAllocationFor(profile, JSArray::create(exec->vm(), initialLength >= MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH ? globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage) : globalObject->arrayStructureForProfileDuringAllocation(profile), initialLength));
 }
 
 inline JSArray* constructEmptyArray(ExecState* exec, ArrayAllocationProfile* profile, unsigned initialLength = 0)
index 3bc98fd..82dd551 100644 (file)
@@ -1,3 +1,16 @@
+2015-05-04  Filip Pizlo  <fpizlo@apple.com>
+
+        Large array shouldn't be slow
+        https://bugs.webkit.org/show_bug.cgi?id=144617
+
+        Reviewed by Geoffrey Garen.
+        
+        Add the hash-map benchmark to LongSpider. LongSpider was already not a perfect match of
+        SunSpider. It's not an official benchmark. It contains benchmarks that are relatively
+        long-running. So, hash-map sort of belongs here.
+
+        * Scripts/run-jsc-benchmarks:
+
 2015-05-04  Doug Russell  <d_russell@apple.com>
 
         AX: setting focus via accessibility object needs to set isSynchronizing in resulting selection intent
index bfc680f..d70acf5 100755 (executable)
@@ -2897,7 +2897,7 @@ begin
    "access-fannkuch", "access-nbody", "access-nsieve",
    "bitops-3bit-bits-in-byte", "bitops-bits-in-byte", "bitops-nsieve-bits",
    "controlflow-recursive", "crypto-aes", "crypto-md5", "crypto-sha1",
-   "date-format-tofte", "date-format-xparb", "math-cordic",
+   "date-format-tofte", "date-format-xparb", "hash-map", "math-cordic",
    "math-partial-sums", "math-spectral-norm", "string-base64",
    "string-fasta", "string-tagcloud"].each {
     | name |