- Revision
- 256682
- Author
- repst...@apple.com
- Date
- 2020-02-14 19:02:08 -0800 (Fri, 14 Feb 2020)
Log Message
Cherry-pick r255889. rdar://problem/59446995
[WTF] Try using 75% load factor for HashTable
https://bugs.webkit.org/show_bug.cgi?id=207183
Reviewed by Mark Lam.
Source/WTF:
We know that hash-table is one of the most memory consuming part in WebKit.
By analyzing many production hash-table implementations[1], I found that many
of them are using 75% load-factor while our one is 50%.
A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
JetStream2, while it offers 2~% improvement in Membuster. This means that we are
wasting too much memory for no-performance-improvement.
This patch changes the load-factor from 50% to 75%.
[1]: LLVM DenseMap, Abseil's, rust's, and so on.
* wtf/HashTable.h:
(WTF::HashTable::shouldExpand):
(WTF::HashTable::shouldExpand const):
(WTF::HashTableCapacityForSize::capacityForSize):
(WTF::KeyTraits>::computeBestTableSize):
Tools:
Fix load-factor assumption in existing tests.
* TestWebKitAPI/Tests/WTF/HashSet.cpp:
(TestWebKitAPI::testInitialCapacity):
LayoutTests:
It seems that this test is relying on hash-table's order.
* http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@255889 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Modified Paths
Diff
Modified: branches/safari-609-branch/LayoutTests/ChangeLog (256681 => 256682)
--- branches/safari-609-branch/LayoutTests/ChangeLog 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/LayoutTests/ChangeLog 2020-02-15 03:02:08 UTC (rev 256682)
@@ -1,5 +1,60 @@
2020-02-14 Russell Epstein <repst...@apple.com>
+ Cherry-pick r255889. rdar://problem/59446995
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ Source/WTF:
+
+ We know that hash-table is one of the most memory consuming part in WebKit.
+ By analyzing many production hash-table implementations[1], I found that many
+ of them are using 75% load-factor while our one is 50%.
+
+ A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
+ JetStream2, while it offers 2~% improvement in Membuster. This means that we are
+ wasting too much memory for no-performance-improvement.
+
+ This patch changes the load-factor from 50% to 75%.
+
+ [1]: LLVM DenseMap, Abseil's, rust's, and so on.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::shouldExpand):
+ (WTF::HashTable::shouldExpand const):
+ (WTF::HashTableCapacityForSize::capacityForSize):
+ (WTF::KeyTraits>::computeBestTableSize):
+
+ Tools:
+
+ Fix load-factor assumption in existing tests.
+
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ (TestWebKitAPI::testInitialCapacity):
+
+ LayoutTests:
+
+ It seems that this test is relying on hash-table's order.
+
+ * http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@255889 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2020-02-05 Yusuke Suzuki <ysuz...@apple.com>
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ It seems that this test is relying on hash-table's order.
+
+ * http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
+
+2020-02-14 Russell Epstein <repst...@apple.com>
+
Cherry-pick r256427. rdar://problem/59447029
Fix crash due to uninitialized currentStyle in CSSTransition
Modified: branches/safari-609-branch/LayoutTests/http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt (256681 => 256682)
--- branches/safari-609-branch/LayoutTests/http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/LayoutTests/http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt 2020-02-15 03:02:08 UTC (rev 256682)
@@ -4,15 +4,22 @@
Resource load statistics:
-Registrable domain: topframe2
+Registrable domain: subframe3
hadUserInteraction: No
mostRecentUserInteraction: -1
grandfathered: No
gotLinkDecorationFromPrevalentResource: No
- isPrevalentResource: No
+ subframeUnderTopFrameDomains:
+ topframe1
+ topframe4
+ subresourceUnderTopFrameDomains:
+ topframe3
+ subresourceUniqueRedirectsTo:
+ topframe2
+ isPrevalentResource: Yes
isVeryPrevalentResource: No
dataRecordsRemoved: 0
-Registrable domain: topframe3
+Registrable domain: topframe2
hadUserInteraction: No
mostRecentUserInteraction: -1
grandfathered: No
@@ -58,19 +65,12 @@
isPrevalentResource: Yes
isVeryPrevalentResource: No
dataRecordsRemoved: 0
-Registrable domain: subframe3
+Registrable domain: topframe3
hadUserInteraction: No
mostRecentUserInteraction: -1
grandfathered: No
gotLinkDecorationFromPrevalentResource: No
- subframeUnderTopFrameDomains:
- topframe1
- topframe4
- subresourceUnderTopFrameDomains:
- topframe3
- subresourceUniqueRedirectsTo:
- topframe2
- isPrevalentResource: Yes
+ isPrevalentResource: No
isVeryPrevalentResource: No
dataRecordsRemoved: 0
Modified: branches/safari-609-branch/Source/WTF/ChangeLog (256681 => 256682)
--- branches/safari-609-branch/Source/WTF/ChangeLog 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/Source/WTF/ChangeLog 2020-02-15 03:02:08 UTC (rev 256682)
@@ -1,5 +1,74 @@
2020-02-14 Russell Epstein <repst...@apple.com>
+ Cherry-pick r255889. rdar://problem/59446995
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ Source/WTF:
+
+ We know that hash-table is one of the most memory consuming part in WebKit.
+ By analyzing many production hash-table implementations[1], I found that many
+ of them are using 75% load-factor while our one is 50%.
+
+ A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
+ JetStream2, while it offers 2~% improvement in Membuster. This means that we are
+ wasting too much memory for no-performance-improvement.
+
+ This patch changes the load-factor from 50% to 75%.
+
+ [1]: LLVM DenseMap, Abseil's, rust's, and so on.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::shouldExpand):
+ (WTF::HashTable::shouldExpand const):
+ (WTF::HashTableCapacityForSize::capacityForSize):
+ (WTF::KeyTraits>::computeBestTableSize):
+
+ Tools:
+
+ Fix load-factor assumption in existing tests.
+
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ (TestWebKitAPI::testInitialCapacity):
+
+ LayoutTests:
+
+ It seems that this test is relying on hash-table's order.
+
+ * http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@255889 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2020-02-05 Yusuke Suzuki <ysuz...@apple.com>
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ We know that hash-table is one of the most memory consuming part in WebKit.
+ By analyzing many production hash-table implementations[1], I found that many
+ of them are using 75% load-factor while our one is 50%.
+
+ A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
+ JetStream2, while it offers 2~% improvement in Membuster. This means that we are
+ wasting too much memory for no-performance-improvement.
+
+ This patch changes the load-factor from 50% to 75%.
+
+ [1]: LLVM DenseMap, Abseil's, rust's, and so on.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::shouldExpand):
+ (WTF::HashTable::shouldExpand const):
+ (WTF::HashTableCapacityForSize::capacityForSize):
+ (WTF::KeyTraits>::computeBestTableSize):
+
+2020-02-14 Russell Epstein <repst...@apple.com>
+
Cherry-pick r255611. rdar://problem/59446995
Reduce size of HashMap and HashSet
Modified: branches/safari-609-branch/Source/WTF/wtf/HashTable.h (256681 => 256682)
--- branches/safari-609-branch/Source/WTF/wtf/HashTable.h 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/Source/WTF/wtf/HashTable.h 2020-02-15 03:02:08 UTC (rev 256682)
@@ -487,7 +487,11 @@
void remove(ValueType*);
static constexpr unsigned computeBestTableSize(unsigned keyCount);
- bool shouldExpand() const { return (keyCount() + deletedCount()) * maxLoad >= tableSize(); }
+ static constexpr bool shouldExpand(uint64_t keyAndDeleteCount, uint64_t tableSize)
+ {
+ return keyAndDeleteCount * maxLoadDenominator >= tableSize * maxLoadNumerator;
+ }
+ bool shouldExpand() const { return shouldExpand(keyCount() + deletedCount(), tableSize()); }
bool mustRehashInPlace() const { return keyCount() * minLoad < tableSize() * 2; }
bool shouldShrink() const { return keyCount() * minLoad < tableSize() && tableSize() > KeyTraits::minimumTableSize; }
ValueType* expand(ValueType* entry = nullptr);
@@ -522,7 +526,9 @@
static void invalidateIterators() { }
#endif
- static constexpr unsigned maxLoad = 2;
+ // Load-factor is 75%.
+ static constexpr unsigned maxLoadNumerator = 3;
+ static constexpr unsigned maxLoadDenominator = 4;
static constexpr unsigned minLoad = 6;
static constexpr int tableSizeOffset = -1;
@@ -556,42 +562,25 @@
#endif
};
- // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
- template<unsigned size> struct OneifyLowBits;
- template<>
- struct OneifyLowBits<0> {
- static constexpr unsigned value = 0;
- };
- template<unsigned number>
- struct OneifyLowBits {
- static constexpr unsigned value = number | OneifyLowBits<(number >> 1)>::value;
- };
- // Compute the first power of two integer that is an upper bound of the parameter 'number'.
- template<unsigned number>
- struct UpperPowerOfTwoBound {
- static constexpr unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
- };
-
- // Because power of two numbers are the limit of maxLoad, their capacity is twice the
- // UpperPowerOfTwoBound, or 4 times their values.
- template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
- template<unsigned size>
- struct HashTableCapacityForSizeSplitter<size, true> {
- static constexpr unsigned value = size * 4;
- };
- template<unsigned size>
- struct HashTableCapacityForSizeSplitter<size, false> {
- static constexpr unsigned value = UpperPowerOfTwoBound<size>::value;
- };
-
// HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
// This is done at compile time to initialize the HashTraits.
template<unsigned size>
struct HashTableCapacityForSize {
- static constexpr unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
+ static constexpr unsigned capacityForSize(uint64_t sizeArg)
+ {
+ constexpr uint64_t maxLoadNumerator = 3;
+ constexpr uint64_t maxLoadDenominator = 4;
+ if (!sizeArg)
+ return 0;
+ uint64_t capacity = roundUpToPowerOfTwo(sizeArg);
+ if (sizeArg * maxLoadDenominator >= capacity * maxLoadNumerator)
+ return capacity * 2;
+ return capacity;
+ }
+
+ static constexpr unsigned value = capacityForSize(size);
COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
- COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
};
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
@@ -1238,11 +1227,13 @@
{
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)
+ // With maxLoad at 3/4 and minLoad at 1/6, our average load is 11/24.
+ // If we are getting halfway between 11/24 and 3/4 (i.e. past 14.5/24,
+ // which we'll round up to 15/24 i.e. 5/8), we double the size to avoid
+ // being too close to loadMax and bring the ratio close to 11/24. This
+ // give us a load in the bounds [9/24, 15/24).
+ bool aboveThresholdForEagerExpansion = keyCount * 8 >= bestTableSize * 5;
+ if (aboveThresholdForEagerExpansion)
bestTableSize *= 2;
unsigned minimumTableSize = KeyTraits::minimumTableSize;
Modified: branches/safari-609-branch/Tools/ChangeLog (256681 => 256682)
--- branches/safari-609-branch/Tools/ChangeLog 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/Tools/ChangeLog 2020-02-15 03:02:08 UTC (rev 256682)
@@ -1,5 +1,61 @@
2020-02-14 Russell Epstein <repst...@apple.com>
+ Cherry-pick r255889. rdar://problem/59446995
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ Source/WTF:
+
+ We know that hash-table is one of the most memory consuming part in WebKit.
+ By analyzing many production hash-table implementations[1], I found that many
+ of them are using 75% load-factor while our one is 50%.
+
+ A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
+ JetStream2, while it offers 2~% improvement in Membuster. This means that we are
+ wasting too much memory for no-performance-improvement.
+
+ This patch changes the load-factor from 50% to 75%.
+
+ [1]: LLVM DenseMap, Abseil's, rust's, and so on.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::shouldExpand):
+ (WTF::HashTable::shouldExpand const):
+ (WTF::HashTableCapacityForSize::capacityForSize):
+ (WTF::KeyTraits>::computeBestTableSize):
+
+ Tools:
+
+ Fix load-factor assumption in existing tests.
+
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ (TestWebKitAPI::testInitialCapacity):
+
+ LayoutTests:
+
+ It seems that this test is relying on hash-table's order.
+
+ * http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
+
+ git-svn-id: https://svn.webkit.org/repository/webkit/trunk@255889 268f45cc-cd09-0410-ab3c-d52691b4dbfc
+
+ 2020-02-05 Yusuke Suzuki <ysuz...@apple.com>
+
+ [WTF] Try using 75% load factor for HashTable
+ https://bugs.webkit.org/show_bug.cgi?id=207183
+
+ Reviewed by Mark Lam.
+
+ Fix load-factor assumption in existing tests.
+
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+ (TestWebKitAPI::testInitialCapacity):
+
+2020-02-14 Russell Epstein <repst...@apple.com>
+
Cherry-pick r255611. rdar://problem/59446995
Reduce size of HashMap and HashSet
Modified: branches/safari-609-branch/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (256681 => 256682)
--- branches/safari-609-branch/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2020-02-15 03:02:05 UTC (rev 256681)
+++ branches/safari-609-branch/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2020-02-15 03:02:08 UTC (rev 256682)
@@ -55,8 +55,8 @@
ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
}
- // Adding items up to less than half the capacity should not change the capacity.
- unsigned capacityLimit = initialCapacity / 2 - 1;
+ // Adding items up to less than 3/4 of the capacity should not change the capacity.
+ unsigned capacityLimit = initialCapacity * 3 / 4 - 1;
for (size_t i = size; i < capacityLimit; ++i) {
testSet.add(i);
ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
