<!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>[187733] 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/187733">187733</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-08-02 21:33:15 -0700 (Sun, 02 Aug 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses
https://bugs.webkit.org/show_bug.cgi?id=118455
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-08-02
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
LivenessAnalysisPhase lights up like a christmas tree in profiles.
This patch cuts its cost by 4.
About half of the gains come from removing many rehash() when copying
the HashSet.
The last quarter is achieved by having a special add() function for initializing
a HashSet.
This makes benchmarks progress by 1-2% here and there. Nothing massive.
* dfg/DFGLivenessAnalysisPhase.cpp:
(JSC::DFG::LivenessAnalysisPhase::process):
The m_live HashSet is only useful per block. When we are done with it,
we can transfer it to liveAtHead to avoid a copy.
Source/WTF:
Previously, when copying a HashTable, we would start from scratch
with an empty table and insert elements one by one, growing-rehashing
the table as needed.
With this patch, we have 2 improvements to remove most of the cost.
First, we compute a good size from the start. This removes all the
reallocations and rehashs.
This is where the biggest gain comes from.
The second part is a simpler version of add() when we know that
we cannot find a bucket with the same key and there cannot
be any deleted bucket.
This removes most branches from the hot loop, cutting another 25%
of the time.
* wtf/HashTable.h:
(WTF::KeyTraits>::addUniqueForInitialization):
(WTF::KeyTraits>::HashTable):
Tools:
* TestWebKitAPI/Tests/WTF/HashSet.cpp:
(TestWebKitAPI::TEST):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfHashTableh">trunk/Source/WTF/wtf/HashTable.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFHashSetcpp">trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -1,3 +1,25 @@
</span><ins>+2015-08-02 Benjamin Poulain <bpoulain@apple.com>
+
+ Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses
+ https://bugs.webkit.org/show_bug.cgi?id=118455
+
+ Reviewed by Filip Pizlo.
+
+ LivenessAnalysisPhase lights up like a christmas tree in profiles.
+
+ This patch cuts its cost by 4.
+ About half of the gains come from removing many rehash() when copying
+ the HashSet.
+ The last quarter is achieved by having a special add() function for initializing
+ a HashSet.
+
+ This makes benchmarks progress by 1-2% here and there. Nothing massive.
+
+ * dfg/DFGLivenessAnalysisPhase.cpp:
+ (JSC::DFG::LivenessAnalysisPhase::process):
+ The m_live HashSet is only useful per block. When we are done with it,
+ we can transfer it to liveAtHead to avoid a copy.
+
</ins><span class="cx"> 2015-08-01 Saam barati <saambarati1@gmail.com>
</span><span class="cx">
</span><span class="cx"> Unreviewed. Remove unintentional "print" statement in test case.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -84,9 +84,7 @@
</span><span class="cx"> BasicBlock* block = m_graph.block(blockIndex);
</span><span class="cx"> if (!block)
</span><span class="cx"> return;
</span><del>-
- // FIXME: It's likely that this can be improved, for static analyses that use
- // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
</del><ins>+
</ins><span class="cx"> m_live = block->ssa->liveAtTail;
</span><span class="cx">
</span><span class="cx"> for (unsigned nodeIndex = block->size(); nodeIndex--;) {
</span><span class="lines">@@ -134,9 +132,9 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> m_changed = true;
</span><del>- block->ssa->liveAtHead = m_live;
</del><span class="cx"> for (unsigned i = block->predecessors.size(); i--;)
</span><span class="cx"> block->predecessors[i]->ssa->liveAtTail.add(m_live.begin(), m_live.end());
</span><ins>+ block->ssa->liveAtHead = WTF::move(m_live);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void addChildUse(Node*, Edge& edge)
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Source/WTF/ChangeLog 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -1,3 +1,30 @@
</span><ins>+2015-08-02 Benjamin Poulain <bpoulain@apple.com>
+
+ Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses
+ https://bugs.webkit.org/show_bug.cgi?id=118455
+
+ Reviewed by Filip Pizlo.
+
+ Previously, when copying a HashTable, we would start from scratch
+ with an empty table and insert elements one by one, growing-rehashing
+ the table as needed.
+
+ With this patch, we have 2 improvements to remove most of the cost.
+
+ First, we compute a good size from the start. This removes all the
+ reallocations and rehashs.
+ This is where the biggest gain comes from.
+
+ The second part is a simpler version of add() when we know that
+ we cannot find a bucket with the same key and there cannot
+ be any deleted bucket.
+ This removes most branches from the hot loop, cutting another 25%
+ of the time.
+
+ * wtf/HashTable.h:
+ (WTF::KeyTraits>::addUniqueForInitialization):
+ (WTF::KeyTraits>::HashTable):
+
</ins><span class="cx"> 2015-08-01 Myles C. Maxfield <mmaxfield@apple.com>
</span><span class="cx">
</span><span class="cx"> HashTraits<AtomicString> can use SimpleClassHashTraits
</span></span></pre></div>
<a id="trunkSourceWTFwtfHashTableh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/HashTable.h (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/HashTable.h 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Source/WTF/wtf/HashTable.h 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx"> #include <wtf/Assertions.h>
</span><span class="cx"> #include <wtf/FastMalloc.h>
</span><span class="cx"> #include <wtf/HashTraits.h>
</span><ins>+#include <wtf/MathExtras.h>
</ins><span class="cx"> #include <wtf/StdLibExtras.h>
</span><span class="cx"> #include <wtf/ValueCheck.h>
</span><span class="cx">
</span><span class="lines">@@ -431,6 +432,8 @@
</span><span class="cx"> template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
</span><span class="cx"> template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
</span><span class="cx">
</span><ins>+ template<typename HashTranslator, typename T, typename Extra> void addUniqueForInitialization(T&& key, Extra&&);
+
</ins><span class="cx"> template<typename HashTranslator, typename T> void checkKey(const T&);
</span><span class="cx">
</span><span class="cx"> void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
</span><span class="lines">@@ -761,6 +764,59 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+ template<typename HashTranslator, typename T, typename Extra>
+ ALWAYS_INLINE void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addUniqueForInitialization(T&& key, Extra&& extra)
+ {
+ ASSERT(m_table);
+
+ checkKey<HashTranslator>(key);
+
+ invalidateIterators();
+
+ internalCheckTableConsistency();
+
+ unsigned k = 0;
+ ValueType* table = m_table;
+ unsigned sizeMask = m_tableSizeMask;
+ unsigned h = HashTranslator::hash(key);
+ unsigned i = h & sizeMask;
+
+#if DUMP_HASHTABLE_STATS
+ ++HashTableStats::numAccesses;
+ unsigned probeCount = 0;
+#endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+ ++m_stats->numAccesses;
+#endif
+
+ ValueType* entry;
+ while (1) {
+ entry = table + i;
+
+ if (isEmptyBucket(*entry))
+ break;
+
+#if DUMP_HASHTABLE_STATS
+ ++probeCount;
+ HashTableStats::recordCollisionAtCount(probeCount);
+#endif
+
+#if DUMP_HASHTABLE_STATS_PER_TABLE
+ m_stats->recordCollisionAtCount(probeCount);
+#endif
+
+ if (k == 0)
+ k = 1 | doubleHash(h);
+ i = (i + k) & sizeMask;
+ }
+
+ HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
+
+ internalCheckTableConsistency();
+ }
+
</ins><span class="cx"> template<bool emptyValueIsZero> struct HashTableBucketInitializer;
</span><span class="cx">
</span><span class="cx"> template<> struct HashTableBucketInitializer<false> {
</span><span class="lines">@@ -1155,26 +1211,40 @@
</span><span class="cx">
</span><span class="cx"> template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</span><span class="cx"> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
</span><del>- : m_table(0)
</del><ins>+ : m_table(nullptr)
</ins><span class="cx"> , m_tableSize(0)
</span><span class="cx"> , m_tableSizeMask(0)
</span><span class="cx"> , m_keyCount(0)
</span><span class="cx"> , m_deletedCount(0)
</span><span class="cx"> #if CHECK_HASHTABLE_ITERATORS
</span><del>- , m_iterators(0)
</del><ins>+ , m_iterators(nullptr)
</ins><span class="cx"> , m_mutex(std::make_unique<std::mutex>())
</span><span class="cx"> #endif
</span><span class="cx"> #if DUMP_HASHTABLE_STATS_PER_TABLE
</span><span class="cx"> , m_stats(std::make_unique<Stats>(*other.m_stats))
</span><span class="cx"> #endif
</span><span class="cx"> {
</span><del>- // Copy the hash table the dumb way, by adding each element to the new table.
- // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
- // FIXME: It's likely that this can be improved, for static analyses that use
- // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
- const_iterator end = other.end();
- for (const_iterator it = other.begin(); it != end; ++it)
- add(*it);
</del><ins>+ unsigned otherKeyCount = other.size();
+ if (!otherKeyCount)
+ return;
+
+ unsigned bestTableSize = WTF::roundUpToPowerOfTwo(otherKeyCount) * 2;
+
+ // With maxLoad at 1/2 and minLoad at 1/6, our average load is 2/6.
+ // If we are getting halfway between 2/6 and 1/2 (past 5/12), we double the size to avoid being too close to
+ // loadMax and bring the ratio close to 2/6. This give us a load in the bounds [3/12, 5/12).
+ bool aboveThreeQuarterLoad = otherKeyCount * 12 >= bestTableSize * 5;
+ if (aboveThreeQuarterLoad)
+ bestTableSize *= 2;
+
+ unsigned minimumTableSize = KeyTraits::minimumTableSize;
+ m_tableSize = std::max<unsigned>(bestTableSize, minimumTableSize);
+ m_tableSizeMask = m_tableSize - 1;
+ m_keyCount = otherKeyCount;
+ m_table = allocateTable(m_tableSize);
+
+ for (const auto& otherValue : other)
+ addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</span><span class="lines">@@ -1197,8 +1267,6 @@
</span><span class="cx"> template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
</span><span class="cx"> auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
</span><span class="cx"> {
</span><del>- // FIXME: It's likely that this can be improved, for static analyses that use
- // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
</del><span class="cx"> HashTable tmp(other);
</span><span class="cx"> swap(tmp);
</span><span class="cx"> return *this;
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Tools/ChangeLog 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -1,3 +1,13 @@
</span><ins>+2015-08-02 Benjamin Poulain <bpoulain@apple.com>
+
+ Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const HashTable&) performance for hash-based static analyses
+ https://bugs.webkit.org/show_bug.cgi?id=118455
+
+ Reviewed by Filip Pizlo.
+
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ (TestWebKitAPI::TEST):
+
</ins><span class="cx"> 2015-07-31 Alex Christensen <achristensen@webkit.org>
</span><span class="cx">
</span><span class="cx"> Prepare for VS2015
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFHashSetcpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (187732 => 187733)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2015-08-03 01:44:05 UTC (rev 187732)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2015-08-03 04:33:15 UTC (rev 187733)
</span><span class="lines">@@ -206,4 +206,75 @@
</span><span class="cx"> EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST(WTF_HashSet, CopyEmpty)
+{
+ {
+ HashSet<unsigned> foo;
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(0u, bar.capacity());
+ EXPECT_EQ(0u, bar.size());
+ }
+ {
+ HashSet<unsigned> foo({ 1, 5, 64, 42 });
+ EXPECT_EQ(4u, foo.size());
+ foo.remove(1);
+ foo.remove(5);
+ foo.remove(42);
+ foo.remove(64);
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(0u, bar.capacity());
+ EXPECT_EQ(0u, bar.size());
+ }
+}
+
+TEST(WTF_HashSet, CopyAllocateAtLeastMinimumCapacity)
+{
+ HashSet<unsigned> foo({ 42 });
+ EXPECT_EQ(1u, foo.size());
+ HashSet<unsigned> bar(foo);
+
+ EXPECT_EQ(8u, bar.capacity());
+ EXPECT_EQ(1u, bar.size());
+}
+
+TEST(WTF_HashSet, CopyCapacityIsNotOnBoundary)
+{
+ // Starting at 4 because the minimum size is 8.
+ // With a size of 8, a medium load can be up to 3.3333->3.
+ // Adding 1 to 3 would reach max load.
+ // While correct, that's not really what we care about here.
+ for (unsigned size = 4; size < 100; ++size) {
+ HashSet<unsigned> source;
+ for (unsigned i = 1; i < size + 1; ++i)
+ source.add(i);
+
+ HashSet<unsigned> copy1(source);
+ HashSet<unsigned> copy2(source);
+ HashSet<unsigned> copy3(source);
+
+ EXPECT_EQ(size, copy1.size());
+ EXPECT_EQ(size, copy2.size());
+ EXPECT_EQ(size, copy3.size());
+ for (unsigned i = 1; i < size + 1; ++i) {
+ EXPECT_TRUE(copy1.contains(i));
+ EXPECT_TRUE(copy2.contains(i));
+ EXPECT_TRUE(copy3.contains(i));
+ }
+ EXPECT_FALSE(copy1.contains(size + 2));
+ EXPECT_FALSE(copy2.contains(size + 2));
+ EXPECT_FALSE(copy3.contains(size + 2));
+
+ EXPECT_TRUE(copy2.remove(1));
+ EXPECT_EQ(copy1.capacity(), copy2.capacity());
+ EXPECT_FALSE(copy2.contains(1));
+
+ EXPECT_TRUE(copy3.add(size + 2).isNewEntry);
+ EXPECT_EQ(copy1.capacity(), copy3.capacity());
+ EXPECT_TRUE(copy3.contains(size + 2));
+ }
+}
+
+
</ins><span class="cx"> } // namespace TestWebKitAPI
</span></span></pre>
</div>
</div>
</body>
</html>