HashTable::removeIf always shrinks the hash table by half even if there is nothing...
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Apr 2019 21:30:38 +0000 (21:30 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 15 Apr 2019 21:30:38 +0000 (21:30 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196681

Reviewed by Darin Adler.

Source/WTF:

Made HashTable::removeIf shrink to the "best size", which is the least power of two bigger
than twice the key count as already used in the copy constructor.

* wtf/HashTable.h:
(WTF::HashTable::computeBestTableSize): Extracted from the copy constructor.
(WTF::HashTable::shrinkToBestSize): Added.
(WTF::HashTable::removeIf): Use shrinkToBestSize instead of shrink.
(WTF::HashTable::HashTable):

Tools:

Added tests.

* TestWebKitAPI/Tests/WTF/HashSet.cpp:
(WTF_HashSet.RemoveIf):
(WTF_HashSet.RemoveIfShrinkToBestSize):

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

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

index 6e26505..7a98b5a 100644 (file)
@@ -1,3 +1,19 @@
+2019-04-12  Ryosuke Niwa  <rniwa@webkit.org>
+
+        HashTable::removeIf always shrinks the hash table by half even if there is nothing left
+        https://bugs.webkit.org/show_bug.cgi?id=196681
+
+        Reviewed by Darin Adler.
+
+        Made HashTable::removeIf shrink to the "best size", which is the least power of two bigger
+        than twice the key count as already used in the copy constructor.
+
+        * wtf/HashTable.h:
+        (WTF::HashTable::computeBestTableSize): Extracted from the copy constructor.
+        (WTF::HashTable::shrinkToBestSize): Added.
+        (WTF::HashTable::removeIf): Use shrinkToBestSize instead of shrink.
+        (WTF::HashTable::HashTable):
+
 2019-04-12  Eric Carlson  <eric.carlson@apple.com>
 
         Update AudioSession route sharing policy
index 05a9211..daa84e6 100644 (file)
@@ -464,12 +464,14 @@ namespace WTF {
         void removeAndInvalidate(ValueType*);
         void remove(ValueType*);
 
+        static constexpr unsigned computeBestTableSize(unsigned keyCount);
         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
         ValueType* expand(ValueType* entry = nullptr);
         void shrink() { rehash(m_tableSize / 2, nullptr); }
-
+        void shrinkToBestSize();
+    
         void deleteReleasedWeakBuckets();
 
         ValueType* rehash(unsigned newTableSize, ValueType* entry);
@@ -1149,7 +1151,7 @@ namespace WTF {
         m_keyCount -= removedBucketCount;
 
         if (shouldShrink())
-            shrink();
+            shrinkToBestSize();
         
         internalCheckTableConsistency();
         return removedBucketCount;
@@ -1196,6 +1198,29 @@ namespace WTF {
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    constexpr unsigned HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::computeBestTableSize(unsigned keyCount)
+    {
+        unsigned bestTableSize = WTF::roundUpToPowerOfTwo(keyCount) * 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 = keyCount * 12 >= bestTableSize * 5;
+        if (aboveThreeQuarterLoad)
+            bestTableSize *= 2;
+
+        unsigned minimumTableSize = KeyTraits::minimumTableSize;
+        return std::max<unsigned>(bestTableSize, minimumTableSize);
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::shrinkToBestSize()
+    {
+        unsigned minimumTableSize = KeyTraits::minimumTableSize;
+        rehash(std::max<unsigned>(minimumTableSize, computeBestTableSize(m_keyCount)), nullptr);
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
     {
         for (unsigned i = 0; i < m_tableSize; ++i) {
@@ -1301,17 +1326,7 @@ namespace WTF {
         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_tableSize = computeBestTableSize(otherKeyCount);
         m_tableSizeMask = m_tableSize - 1;
         m_keyCount = otherKeyCount;
         m_table = allocateTable(m_tableSize);
index 9bddb95..ae4481a 100644 (file)
@@ -1,3 +1,16 @@
+2019-04-12  Ryosuke Niwa  <rniwa@webkit.org>
+
+        HashTable::removeIf always shrinks the hash table by half even if there is nothing left
+        https://bugs.webkit.org/show_bug.cgi?id=196681
+
+        Reviewed by Darin Adler.
+
+        Added tests.
+
+        * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+        (WTF_HashSet.RemoveIf):
+        (WTF_HashSet.RemoveIfShrinkToBestSize):
+
 2019-04-15  John Wilander  <wilander@apple.com>
 
         Send delayed Ad Click Attribution conversion requests to the click source
index 5d6e8dd..71ecfdd 100644 (file)
@@ -466,4 +466,40 @@ TEST(WTF_HashSet, RemoveRandom)
     ASSERT_TRUE(set1.isEmpty());
 }
 
+TEST(WTF_HashSet, RemoveIf)
+{
+    HashSet<unsigned> set1 { 1, 2, 3, 4, 5 };
+    ASSERT_EQ(set1.size(), 5u);
+    set1.removeIf([] (unsigned item) { return item % 2;  });
+    set1.checkConsistency();
+    ASSERT_TRUE(!set1.contains(1));
+    ASSERT_TRUE(set1.contains(2));
+    ASSERT_TRUE(!set1.contains(3));
+    ASSERT_TRUE(set1.contains(4));
+    ASSERT_TRUE(!set1.contains(5));
+    ASSERT_EQ(set1.size(), 2u);
+}
+
+TEST(WTF_HashSet, RemoveIfShrinkToBestSize)
+{
+    HashSet<unsigned> set1;
+    set1.add(1);
+    unsigned originalCapacity = set1.capacity();
+    while (set1.capacity() < originalCapacity * 4)
+        set1.add(set1.size() + 1);
+    set1.removeIf([] (unsigned item) { return item != 1; });
+    set1.checkConsistency();
+    ASSERT_EQ(set1.size(), 1u);
+    ASSERT_EQ(set1.capacity(), originalCapacity);
+
+    set1.clear();
+    set1.checkConsistency();
+    while (set1.capacity() < originalCapacity * 8)
+        set1.add(set1.size() + 1);
+    set1.removeIf([originalCapacity] (unsigned item) { return item >= originalCapacity / 2; });
+    set1.checkConsistency();
+    ASSERT_EQ(set1.size(), originalCapacity / 2 - 1);
+    ASSERT_EQ(set1.capacity(), originalCapacity);
+}
+
 } // namespace TestWebKitAPI