Changeset 244289 in webkit

Timestamp:

Apr 15, 2019, 2:30:38 PM (7 years ago)

Author:

rniwa@webkit.org

Message:

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.

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):

Location:

trunk

Files:

• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/HashTable.h (modified) (5 diffs)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (modified) (1 diff)

trunk/Source/WTF/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/WTF/wtf/HashTable.h

@@ -465 +465 @@
         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; }
@@ -470 +471 @@
         ValueType* expand(ValueType* entry = nullptr);
         void shrink() { rehash(m_tableSize / 2, nullptr); }
-
+        void shrinkToBestSize();
+    
         void deleteReleasedWeakBuckets();
 
@@ -1150 +1152 @@
 
         if (shouldShrink())
-            shrink();
+            shrinkToBestSize();
         
         internalCheckTableConsistency();
@@ -1194 +1196 @@
 
         return rehash(newSize, entry);
+    }
+
+    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);
     }
 
@@ -1302 +1327 @@
             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;

trunk/Tools/ChangeLog

@@ +1 @@
+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>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp

@@ -467 +467 @@
 }
 
+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