Changeset 256011 in webkit

Timestamp:

Feb 7, 2020 12:55:58 AM (4 years ago)

Author:

ysuzuki@apple.com

Message:

Unreviewed, revert 75% load-factor because of JetStream2/string-unpack-code-SP regression
​https://bugs.webkit.org/show_bug.cgi?id=207183

Source/WTF:

• wtf/HashTable.h:

(WTF::HashTable::shouldExpand const):
(WTF::KeyTraits>::computeBestTableSize):
(WTF::HashTable::shouldExpand): Deleted.
(WTF::HashTableCapacityForSize::capacityForSize): Deleted.

Tools:

• TestWebKitAPI/Tests/WTF/HashSet.cpp:

(TestWebKitAPI::testInitialCapacity):

Location:

trunk

Files:

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

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2020-02-07  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        Unreviewed, revert 75% load-factor because of JetStream2/string-unpack-code-SP regression
+        https://bugs.webkit.org/show_bug.cgi?id=207183
+
+        * wtf/HashTable.h:
+        (WTF::HashTable::shouldExpand const):
+        (WTF::KeyTraits>::computeBestTableSize):
+        (WTF::HashTable::shouldExpand): Deleted.
+        (WTF::HashTableCapacityForSize::capacityForSize): Deleted.
+
 2020-02-07  youenn fablet  <youenn@apple.com>
 

trunk/Source/WTF/wtf/HashTable.h

@@ -488 +488 @@
 
         static constexpr unsigned computeBestTableSize(unsigned keyCount);
-        static constexpr bool shouldExpand(uint64_t keyAndDeleteCount, uint64_t tableSize)
-        {
-            return keyAndDeleteCount * maxLoadDenominator >= tableSize * maxLoadNumerator;
-        }
-        bool shouldExpand() const { return shouldExpand(keyCount() + deletedCount(), tableSize()); }
+        bool shouldExpand() const { return (keyCount() + deletedCount()) * maxLoad >= tableSize(); }
         bool mustRehashInPlace() const { return keyCount() * minLoad < tableSize() * 2; }
         bool shouldShrink() const { return keyCount() * minLoad < tableSize() && tableSize() > KeyTraits::minimumTableSize; }
@@ -527 +523 @@
 #endif
 
-        // Load-factor is 75%.
-        static constexpr unsigned maxLoadNumerator = 3;
-        static constexpr unsigned maxLoadDenominator = 4;
+        static constexpr unsigned maxLoad = 2;
         static constexpr unsigned minLoad = 6;
 
@@ -563 +557 @@
     };
 
+    // 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 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);
+        static constexpr unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
         COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
         COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
+        COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
     };
 
@@ -1228 +1239 @@
         unsigned bestTableSize = WTF::roundUpToPowerOfTwo(keyCount) * 2;
 
-        // 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)
+        // 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;
 

trunk/Tools/ChangeLog

@@ +1 @@
+2020-02-07  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        Unreviewed, revert 75% load-factor because of JetStream2/string-unpack-code-SP regression
+        https://bugs.webkit.org/show_bug.cgi?id=207183
+
+        * TestWebKitAPI/Tests/WTF/HashSet.cpp:
+        (TestWebKitAPI::testInitialCapacity):
+
 2020-02-06  Wenson Hsieh  <wenson_hsieh@apple.com>
 

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

@@ -56 +56 @@
     }
 
-    // Adding items up to less than 3/4 of the capacity should not change the capacity.
-    unsigned capacityLimit = initialCapacity * 3 / 4 - 1;
+    // Adding items up to less than half the capacity should not change the capacity.
+    unsigned capacityLimit = initialCapacity / 2 - 1;
     for (size_t i = size; i < capacityLimit; ++i) {
         testSet.add(i);