<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[183787] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/183787">183787</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-05-04 19:40:28 -0700 (Mon, 04 May 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Large array shouldn't be slow
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:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkPerformanceTestsChangeLog">trunk/PerformanceTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCallArrayAllocatorSlowPathGeneratorh">trunk/Source/JavaScriptCore/dfg/DFGCallArrayAllocatorSlowPathGenerator.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSpeculativeJIT32_64cpp">trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSpeculativeJIT64cpp">trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeArrayConventionsh">trunk/Source/JavaScriptCore/runtime/ArrayConventions.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSArrayh">trunk/Source/JavaScriptCore/runtime/JSArray.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeJSGlobalObjecth">trunk/Source/JavaScriptCore/runtime/JSGlobalObject.h</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstressnewarraystoragearraywithsizejs">trunk/Source/JavaScriptCore/tests/stress/new-array-storage-array-with-size.js</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsScriptsrunjscbenchmarks">trunk/Tools/Scripts/run-jsc-benchmarks</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkPerformanceTestsLongSpiderhashmapjs">trunk/PerformanceTests/LongSpider/hash-map.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkPerformanceTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/ChangeLog (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/ChangeLog 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/PerformanceTests/ChangeLog 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -1,3 +1,19 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-05-01 Dewei Zhu <dewei_zhu@apple.com>
</span><span class="cx">
</span><span class="cx"> Fix typo bug in Speedometer/resources/main.js
</span></span></pre></div>
<a id="trunkPerformanceTestsLongSpiderhashmapjs"></a>
<div class="addfile"><h4>Added: trunk/PerformanceTests/LongSpider/hash-map.js (0 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/LongSpider/hash-map.js (rev 0)
+++ trunk/PerformanceTests/LongSpider/hash-map.js 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -0,0 +1,602 @@
</span><ins>+//@ 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;
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-05-03 Yusuke Suzuki <utatane.tea@gmail.com>
</span><span class="cx">
</span><span class="cx"> Add backed intrinsics to private functions exposed with private symbols in global object
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCallArrayAllocatorSlowPathGeneratorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCallArrayAllocatorSlowPathGenerator.h (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCallArrayAllocatorSlowPathGenerator.h 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/dfg/DFGCallArrayAllocatorSlowPathGenerator.h 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -96,7 +96,7 @@
</span><span class="cx"> for (unsigned i = 0; i < m_plans.size(); ++i)
</span><span class="cx"> jit->silentSpill(m_plans[i]);
</span><span class="cx"> GPRReg scratchGPR = AssemblyHelpers::selectScratchGPR(m_sizeGPR);
</span><del>- MacroAssembler::Jump bigLength = jit->m_jit.branch32(MacroAssembler::AboveOrEqual, m_sizeGPR, MacroAssembler::TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
</del><ins>+ MacroAssembler::Jump bigLength = jit->m_jit.branch32(MacroAssembler::AboveOrEqual, m_sizeGPR, MacroAssembler::TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
</ins><span class="cx"> jit->m_jit.move(MacroAssembler::TrustedImmPtr(m_contiguousStructure), scratchGPR);
</span><span class="cx"> MacroAssembler::Jump done = jit->m_jit.jump();
</span><span class="cx"> bigLength.link(&jit->m_jit);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSpeculativeJIT32_64cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -3317,7 +3317,7 @@
</span><span class="cx"> GPRReg scratch2GPR = scratch2.gpr();
</span><span class="cx">
</span><span class="cx"> MacroAssembler::JumpList slowCases;
</span><del>- slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX)));
</del><ins>+ slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
</ins><span class="cx">
</span><span class="cx"> ASSERT((1 << 3) == sizeof(JSValue));
</span><span class="cx"> m_jit.move(sizeGPR, scratchGPR);
</span><span class="lines">@@ -3361,7 +3361,7 @@
</span><span class="cx"> GPRFlushedCallResult result(this);
</span><span class="cx"> GPRReg resultGPR = result.gpr();
</span><span class="cx"> GPRReg structureGPR = selectScratchGPR(sizeGPR);
</span><del>- MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
</del><ins>+ MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
</ins><span class="cx"> m_jit.move(TrustedImmPtr(globalObject->arrayStructureForIndexingTypeDuringAllocation(node->indexingType())), structureGPR);
</span><span class="cx"> MacroAssembler::Jump done = m_jit.jump();
</span><span class="cx"> bigLength.link(&m_jit);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSpeculativeJIT64cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -3408,7 +3408,7 @@
</span><span class="cx"> GPRReg scratch2GPR = scratch2.gpr();
</span><span class="cx">
</span><span class="cx"> MacroAssembler::JumpList slowCases;
</span><del>- slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX)));
</del><ins>+ slowCases.append(m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)));
</ins><span class="cx">
</span><span class="cx"> ASSERT((1 << 3) == sizeof(JSValue));
</span><span class="cx"> m_jit.move(sizeGPR, scratchGPR);
</span><span class="lines">@@ -3450,7 +3450,7 @@
</span><span class="cx"> GPRFlushedCallResult result(this);
</span><span class="cx"> GPRReg resultGPR = result.gpr();
</span><span class="cx"> GPRReg structureGPR = selectScratchGPR(sizeGPR);
</span><del>- MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_SPARSE_ARRAY_INDEX));
</del><ins>+ MacroAssembler::Jump bigLength = m_jit.branch32(MacroAssembler::AboveOrEqual, sizeGPR, TrustedImm32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH));
</ins><span class="cx"> m_jit.move(TrustedImmPtr(globalObject->arrayStructureForIndexingTypeDuringAllocation(node->indexingType())), structureGPR);
</span><span class="cx"> MacroAssembler::Jump done = m_jit.jump();
</span><span class="cx"> bigLength.link(&m_jit);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -3249,7 +3249,7 @@
</span><span class="cx"> LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("NewArrayWithSize continuation"));
</span><span class="cx">
</span><span class="cx"> m_out.branch(
</span><del>- m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_SPARSE_ARRAY_INDEX)),
</del><ins>+ m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)),
</ins><span class="cx"> rarely(largeCase), usually(fastCase));
</span><span class="cx">
</span><span class="cx"> LBasicBlock lastNext = m_out.appendTo(fastCase, largeCase);
</span><span class="lines">@@ -3325,7 +3325,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> LValue structureValue = m_out.select(
</span><del>- m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_SPARSE_ARRAY_INDEX)),
</del><ins>+ m_out.aboveOrEqual(publicLength, m_out.constInt32(MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH)),
</ins><span class="cx"> m_out.constIntPtr(
</span><span class="cx"> globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage)),
</span><span class="cx"> m_out.constIntPtr(structure));
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeArrayConventionsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ArrayConventions.h (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ArrayConventions.h 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/runtime/ArrayConventions.h 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -58,7 +58,14 @@
</span><span class="cx">
</span><span class="cx"> // These values have to be macros to be used in max() and min() without introducing
</span><span class="cx"> // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
</span><ins>+
+// 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).
</ins><span class="cx"> #define MIN_SPARSE_ARRAY_INDEX 100000U
</span><ins>+// 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
</ins><span class="cx"> #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
</span><span class="cx"> // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
</span><span class="cx"> #define MAX_ARRAY_INDEX 0xFFFFFFFEU
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSArrayh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSArray.h (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/runtime/JSArray.h 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -200,7 +200,7 @@
</span><span class="cx"> || hasContiguous(structure->indexingType()));
</span><span class="cx"> unsigned vectorLength;
</span><span class="cx"> butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
</span><del>- ASSERT(initialLength < MIN_SPARSE_ARRAY_INDEX);
</del><ins>+ ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH);
</ins><span class="cx"> if (hasDouble(structure->indexingType())) {
</span><span class="cx"> for (unsigned i = 0; i < vectorLength; ++i)
</span><span class="cx"> butterfly->contiguousDouble()[i] = PNaN;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeJSGlobalObjecth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/JSGlobalObject.h (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/JSGlobalObject.h 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/runtime/JSGlobalObject.h 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -672,7 +672,7 @@
</span><span class="cx">
</span><span class="cx"> inline JSArray* constructEmptyArray(ExecState* exec, ArrayAllocationProfile* profile, JSGlobalObject* globalObject, unsigned initialLength = 0)
</span><span class="cx"> {
</span><del>- return ArrayAllocationProfile::updateLastAllocationFor(profile, JSArray::create(exec->vm(), initialLength >= MIN_SPARSE_ARRAY_INDEX ? globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage) : globalObject->arrayStructureForProfileDuringAllocation(profile), initialLength));
</del><ins>+ return ArrayAllocationProfile::updateLastAllocationFor(profile, JSArray::create(exec->vm(), initialLength >= MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH ? globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithArrayStorage) : globalObject->arrayStructureForProfileDuringAllocation(profile), initialLength));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline JSArray* constructEmptyArray(ExecState* exec, ArrayAllocationProfile* profile, unsigned initialLength = 0)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressnewarraystoragearraywithsizejs"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/tests/stress/new-array-storage-array-with-size.js (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/new-array-storage-array-with-size.js 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Source/JavaScriptCore/tests/stress/new-array-storage-array-with-size.js 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -1,3 +1,6 @@
</span><ins>+// https://bugs.webkit.org/show_bug.cgi?id=144609
+//@ skip
+
</ins><span class="cx"> function foo(x) {
</span><span class="cx"> return new Array(x);
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Tools/ChangeLog 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+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:
+
</ins><span class="cx"> 2015-05-04 Doug Russell <d_russell@apple.com>
</span><span class="cx">
</span><span class="cx"> AX: setting focus via accessibility object needs to set isSynchronizing in resulting selection intent
</span></span></pre></div>
<a id="trunkToolsScriptsrunjscbenchmarks"></a>
<div class="modfile"><h4>Modified: trunk/Tools/Scripts/run-jsc-benchmarks (183786 => 183787)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/Scripts/run-jsc-benchmarks 2015-05-05 01:00:49 UTC (rev 183786)
+++ trunk/Tools/Scripts/run-jsc-benchmarks 2015-05-05 02:40:28 UTC (rev 183787)
</span><span class="lines">@@ -2897,7 +2897,7 @@
</span><span class="cx"> "access-fannkuch", "access-nbody", "access-nsieve",
</span><span class="cx"> "bitops-3bit-bits-in-byte", "bitops-bits-in-byte", "bitops-nsieve-bits",
</span><span class="cx"> "controlflow-recursive", "crypto-aes", "crypto-md5", "crypto-sha1",
</span><del>- "date-format-tofte", "date-format-xparb", "math-cordic",
</del><ins>+ "date-format-tofte", "date-format-xparb", "hash-map", "math-cordic",
</ins><span class="cx"> "math-partial-sums", "math-spectral-norm", "string-base64",
</span><span class="cx"> "string-fasta", "string-tagcloud"].each {
</span><span class="cx"> | name |
</span></span></pre>
</div>
</div>
</body>
</html>