Investigate HashTable::HashTable(const HashTable&) and HashTable::operator=(const...
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Aug 2015 04:33:15 +0000 (04:33 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Aug 2015 04:33:15 +0000 (04:33 +0000)
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):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/HashTable.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp

index b573916..33cd6a7 100644 (file)
@@ -1,3 +1,25 @@
+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.
+
 2015-08-01  Saam barati  <saambarati1@gmail.com>
 
         Unreviewed. Remove unintentional "print" statement in test case.
index b2dc4d2..7496616 100644 (file)
@@ -84,9 +84,7 @@ private:
         BasicBlock* block = m_graph.block(blockIndex);
         if (!block)
             return;
-        
-        // FIXME: It's likely that this can be improved, for static analyses that use
-        // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
+
         m_live = block->ssa->liveAtTail;
         
         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
@@ -134,9 +132,9 @@ private:
             return;
         
         m_changed = true;
-        block->ssa->liveAtHead = m_live;
         for (unsigned i = block->predecessors.size(); i--;)
             block->predecessors[i]->ssa->liveAtTail.add(m_live.begin(), m_live.end());
+        block->ssa->liveAtHead = WTF::move(m_live);
     }
     
     void addChildUse(Node*, Edge& edge)
index a963f1a..68fe76e 100644 (file)
@@ -1,3 +1,30 @@
+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):
+
 2015-08-01  Myles C. Maxfield  <mmaxfield@apple.com>
 
         HashTraits<AtomicString> can use SimpleClassHashTraits
index 1454512..34480c7 100644 (file)
@@ -30,6 +30,7 @@
 #include <wtf/Assertions.h>
 #include <wtf/FastMalloc.h>
 #include <wtf/HashTraits.h>
+#include <wtf/MathExtras.h>
 #include <wtf/StdLibExtras.h>
 #include <wtf/ValueCheck.h>
 
@@ -431,6 +432,8 @@ namespace WTF {
         template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
         template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
 
+        template<typename HashTranslator, typename T, typename Extra> void addUniqueForInitialization(T&& key, Extra&&);
+
         template<typename HashTranslator, typename T> void checkKey(const T&);
 
         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
@@ -761,6 +764,59 @@ namespace WTF {
         }
     }
 
+    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();
+    }
+
     template<bool emptyValueIsZero> struct HashTableBucketInitializer;
 
     template<> struct HashTableBucketInitializer<false> {
@@ -1155,26 +1211,40 @@ namespace WTF {
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
-        : m_table(0)
+        : m_table(nullptr)
         , m_tableSize(0)
         , m_tableSizeMask(0)
         , m_keyCount(0)
         , m_deletedCount(0)
 #if CHECK_HASHTABLE_ITERATORS
-        , m_iterators(0)
+        , m_iterators(nullptr)
         , m_mutex(std::make_unique<std::mutex>())
 #endif
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         , m_stats(std::make_unique<Stats>(*other.m_stats))
 #endif
     {
-        // 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);
+        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);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
@@ -1197,8 +1267,6 @@ namespace WTF {
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
     {
-        // FIXME: It's likely that this can be improved, for static analyses that use
-        // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
         HashTable tmp(other);
         swap(tmp);
         return *this;
index 887341f..4c6dd0d 100644 (file)
@@ -1,3 +1,13 @@
+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):
+
 2015-07-31  Alex Christensen  <achristensen@webkit.org>
 
         Prepare for VS2015
index ddb178c..79cb5e7 100644 (file)
@@ -206,4 +206,75 @@ TEST(WTF_HashSet, UniquePtrKey_TakeUsingRawPointer)
     EXPECT_EQ(1u, ConstructorDestructorCounter::destructionCount);
 }
 
+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));
+    }
+}
+
+
 } // namespace TestWebKitAPI