<!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>[204355] trunk/Source/JavaScriptCore</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/204355">204355</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2016-08-10 14:25:28 -0700 (Wed, 10 Aug 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] Speed up SparseCollection & related maps
https://bugs.webkit.org/show_bug.cgi?id=160733
Patch by Benjamin Poulain <bpoulain@apple.com> on 2016-08-10
Reviewed by Saam Barati.
On MBA, Graph::addNode() shows up in profiles due to SparseCollection::add().
This is unfortunate.
The first improvement is to build the new unique_ptr in the empty slot
instead of moving a new value into it.
Previously, the code would load the previous value, test if it is null
then invoke the destructor and finally fastFree(). The initial test
obviously fails so that's a whole bunch of code that is never executed.
With the new code, we just have a store.
I also removed the bounds checking on our maps based on node index.
Those bounds checks are never eliminated by clang because the index
is always loaded from memory instead of being computed.
There are unfortunately too many nodes processed and the bounds checks
get costly.
* b3/B3SparseCollection.h:
(JSC::B3::SparseCollection::add):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::abstractValuesCache):
* dfg/DFGInPlaceAbstractState.h:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3SparseCollectionh">trunk/Source/JavaScriptCore/b3/B3SparseCollection.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh">trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (204354 => 204355)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-08-10 21:23:20 UTC (rev 204354)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-08-10 21:25:28 UTC (rev 204355)
</span><span class="lines">@@ -1,5 +1,36 @@
</span><span class="cx"> 2016-08-10 Benjamin Poulain <bpoulain@apple.com>
</span><span class="cx">
</span><ins>+ [JSC] Speed up SparseCollection & related maps
+ https://bugs.webkit.org/show_bug.cgi?id=160733
+
+ Reviewed by Saam Barati.
+
+ On MBA, Graph::addNode() shows up in profiles due to SparseCollection::add().
+ This is unfortunate.
+
+ The first improvement is to build the new unique_ptr in the empty slot
+ instead of moving a new value into it.
+
+ Previously, the code would load the previous value, test if it is null
+ then invoke the destructor and finally fastFree(). The initial test
+ obviously fails so that's a whole bunch of code that is never executed.
+
+ With the new code, we just have a store.
+
+ I also removed the bounds checking on our maps based on node index.
+ Those bounds checks are never eliminated by clang because the index
+ is always loaded from memory instead of being computed.
+ There are unfortunately too many nodes processed and the bounds checks
+ get costly.
+
+ * b3/B3SparseCollection.h:
+ (JSC::B3::SparseCollection::add):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::abstractValuesCache):
+ * dfg/DFGInPlaceAbstractState.h:
+
+2016-08-10 Benjamin Poulain <bpoulain@apple.com>
+
</ins><span class="cx"> [JSC] Remove some useless code I left when rewriting CSE's large maps
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=160720
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3SparseCollectionh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3SparseCollection.h (204354 => 204355)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3SparseCollection.h 2016-08-10 21:23:20 UTC (rev 204354)
+++ trunk/Source/JavaScriptCore/b3/B3SparseCollection.h 2016-08-10 21:25:28 UTC (rev 204355)
</span><span class="lines">@@ -55,9 +55,9 @@
</span><span class="cx"> index = m_indexFreeList.takeLast();
</span><span class="cx">
</span><span class="cx"> value->m_index = index;
</span><ins>+ ASSERT(!m_vector[index]);
+ new (NotNull, &m_vector[index]) std::unique_ptr<T>(WTFMove(value));
</ins><span class="cx">
</span><del>- m_vector[index] = WTFMove(value);
-
</del><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -168,8 +168,8 @@
</span><span class="cx"> iterator end() const { return iterator(*this, size()); }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- Vector<std::unique_ptr<T>> m_vector;
- Vector<size_t> m_indexFreeList;
</del><ins>+ Vector<std::unique_ptr<T>, 0, UnsafeVectorOverflow> m_vector;
+ Vector<size_t, 0, UnsafeVectorOverflow> m_indexFreeList;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::B3
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (204354 => 204355)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-08-10 21:23:20 UTC (rev 204354)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-08-10 21:25:28 UTC (rev 204355)
</span><span class="lines">@@ -199,7 +199,7 @@
</span><span class="cx"> Node* nodeAt(unsigned index) const { return m_nodes[index]; }
</span><span class="cx"> void packNodeIndices();
</span><span class="cx">
</span><del>- Vector<AbstractValue>& abstractValuesCache() { return m_abstractValuesCache; }
</del><ins>+ Vector<AbstractValue, 0, UnsafeVectorOverflow>& abstractValuesCache() { return m_abstractValuesCache; }
</ins><span class="cx">
</span><span class="cx"> void dethread();
</span><span class="cx">
</span><span class="lines">@@ -957,7 +957,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> B3::SparseCollection<Node> m_nodes;
</span><del>- Vector<AbstractValue> m_abstractValuesCache;
</del><ins>+ Vector<AbstractValue, 0, UnsafeVectorOverflow> m_abstractValuesCache;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h (204354 => 204355)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-08-10 21:23:20 UTC (rev 204354)
+++ trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-08-10 21:25:28 UTC (rev 204355)
</span><span class="lines">@@ -133,7 +133,7 @@
</span><span class="cx">
</span><span class="cx"> Graph& m_graph;
</span><span class="cx">
</span><del>- Vector<AbstractValue>& m_abstractValues;
</del><ins>+ Vector<AbstractValue, 0, UnsafeVectorOverflow>& m_abstractValues;
</ins><span class="cx"> Operands<AbstractValue> m_variables;
</span><span class="cx"> BasicBlock* m_block;
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>