Modified: trunk/Source/WTF/ChangeLog (244288 => 244289)
--- trunk/Source/WTF/ChangeLog 2019-04-15 21:10:03 UTC (rev 244288)
+++ trunk/Source/WTF/ChangeLog 2019-04-15 21:30:38 UTC (rev 244289)
@@ -1,3 +1,19 @@
+2019-04-12 Ryosuke Niwa <[email protected]>
+
+ 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 <[email protected]>
Update AudioSession route sharing policy
Modified: trunk/Source/WTF/wtf/HashTable.h (244288 => 244289)
--- trunk/Source/WTF/wtf/HashTable.h 2019-04-15 21:10:03 UTC (rev 244288)
+++ trunk/Source/WTF/wtf/HashTable.h 2019-04-15 21:30:38 UTC (rev 244289)
@@ -464,12 +464,14 @@
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 @@
m_keyCount -= removedBucketCount;
if (shouldShrink())
- shrink();
+ shrinkToBestSize();
internalCheckTableConsistency();
return removedBucketCount;
@@ -1196,6 +1198,29 @@
}
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 @@
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);
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (244288 => 244289)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2019-04-15 21:10:03 UTC (rev 244288)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2019-04-15 21:30:38 UTC (rev 244289)
@@ -466,4 +466,40 @@
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
