Changeset 255889 in webkit


Ignore:
Timestamp:
Feb 5, 2020 6:37:32 PM (4 years ago)
Author:
ysuzuki@apple.com
Message:

[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:
Location:
trunk
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r255887 r255889  
     12020-02-05  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [WTF] Try using 75% load factor for HashTable
     4        https://bugs.webkit.org/show_bug.cgi?id=207183
     5
     6        Reviewed by Mark Lam.
     7
     8        It seems that this test is relying on hash-table's order.
     9
     10        * http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt:
     11
    1122020-02-05  Devin Rousso  <drousso@apple.com>
    213

  • trunk/LayoutTests/http/tests/resourceLoadStatistics/aggregate-sorted-data-no-storage-access-expected.txt

    r253863 r255889  
    55Resource load statistics:
    66
    7 Registrable domain: topframe2
     7Registrable domain: subframe3
    88    hadUserInteraction: No
    99    mostRecentUserInteraction: -1
    1010    grandfathered: No
    1111    gotLinkDecorationFromPrevalentResource: No
    12     isPrevalentResource: No
     12    subframeUnderTopFrameDomains:
     13        topframe1
     14        topframe4
     15    subresourceUnderTopFrameDomains:
     16        topframe3
     17    subresourceUniqueRedirectsTo:
     18        topframe2
     19    isPrevalentResource: Yes
    1320    isVeryPrevalentResource: No
    1421    dataRecordsRemoved: 0
    15 Registrable domain: topframe3
     22Registrable domain: topframe2
    1623    hadUserInteraction: No
    1724    mostRecentUserInteraction: -1
    … …  
    5966    isVeryPrevalentResource: No
    6067    dataRecordsRemoved: 0
    61 Registrable domain: subframe3
     68Registrable domain: topframe3
    6269    hadUserInteraction: No
    6370    mostRecentUserInteraction: -1
    6471    grandfathered: No
    6572    gotLinkDecorationFromPrevalentResource: No
    66     subframeUnderTopFrameDomains:
    67         topframe1
    68         topframe4
    69     subresourceUnderTopFrameDomains:
    70         topframe3
    71     subresourceUniqueRedirectsTo:
    72         topframe2
    73     isPrevalentResource: Yes
     73    isPrevalentResource: No
    7474    isVeryPrevalentResource: No
    7575    dataRecordsRemoved: 0

  • trunk/Source/WTF/ChangeLog

    r255874 r255889  
     12020-02-05  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [WTF] Try using 75% load factor for HashTable
     4        https://bugs.webkit.org/show_bug.cgi?id=207183
     5
     6        Reviewed by Mark Lam.
     7
     8        We know that hash-table is one of the most memory consuming part in WebKit.
     9        By analyzing many production hash-table implementations[1], I found that many
     10        of them are using 75% load-factor while our one is 50%.
     11
     12        A/B test shows that 75% load-factor is performance-neutral in Speedometer2 and
     13        JetStream2, while it offers 2~% improvement in Membuster. This means that we are
     14        wasting too much memory for no-performance-improvement.
     15
     16        This patch changes the load-factor from 50% to 75%.
     17
     18        [1]: LLVM DenseMap, Abseil's, rust's, and so on.
     19
     20        * wtf/HashTable.h:
     21        (WTF::HashTable::shouldExpand):
     22        (WTF::HashTable::shouldExpand const):
     23        (WTF::HashTableCapacityForSize::capacityForSize):
     24        (WTF::KeyTraits>::computeBestTableSize):
     25
    1262020-02-05  Per Arne Vollan  <pvollan@apple.com>
    227

  • trunk/Source/WTF/wtf/HashTable.h

    r255611 r255889  
    488488
    489489        static constexpr unsigned computeBestTableSize(unsigned keyCount);
    490         bool shouldExpand() const { return (keyCount() + deletedCount()) * maxLoad >= tableSize(); }
     490        static constexpr bool shouldExpand(uint64_t keyAndDeleteCount, uint64_t tableSize)
     491        {
     492            return keyAndDeleteCount * maxLoadDenominator >= tableSize * maxLoadNumerator;
     493        }
     494        bool shouldExpand() const { return shouldExpand(keyCount() + deletedCount(), tableSize()); }
    491495        bool mustRehashInPlace() const { return keyCount() * minLoad < tableSize() * 2; }
    492496        bool shouldShrink() const { return keyCount() * minLoad < tableSize() && tableSize() > KeyTraits::minimumTableSize; }
    … …  
    523527#endif
    524528
    525         static constexpr unsigned maxLoad = 2;
     529        // Load-factor is 75%.
     530        static constexpr unsigned maxLoadNumerator = 3;
     531        static constexpr unsigned maxLoadDenominator = 4;
    526532        static constexpr unsigned minLoad = 6;
    527533
    … …  
    557563    };
    558564
    559     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
    560     template<unsigned size> struct OneifyLowBits;
    561     template<>
    562     struct OneifyLowBits<0> {
    563         static constexpr unsigned value = 0;
    564     };
    565     template<unsigned number>
    566     struct OneifyLowBits {
    567         static constexpr unsigned value = number | OneifyLowBits<(number >> 1)>::value;
    568     };
    569     // Compute the first power of two integer that is an upper bound of the parameter 'number'.
    570     template<unsigned number>
    571     struct UpperPowerOfTwoBound {
    572         static constexpr unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
    573     };
    574 
    575     // Because power of two numbers are the limit of maxLoad, their capacity is twice the
    576     // UpperPowerOfTwoBound, or 4 times their values.
    577     template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
    578     template<unsigned size>
    579     struct HashTableCapacityForSizeSplitter<size, true> {
    580         static constexpr unsigned value = size * 4;
    581     };
    582     template<unsigned size>
    583     struct HashTableCapacityForSizeSplitter<size, false> {
    584         static constexpr unsigned value = UpperPowerOfTwoBound<size>::value;
    585     };
    586 
    587565    // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
    588566    // This is done at compile time to initialize the HashTraits.
    589567    template<unsigned size>
    590568    struct HashTableCapacityForSize {
    591         static constexpr unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
     569        static constexpr unsigned capacityForSize(uint64_t sizeArg)
     570        {
     571            constexpr uint64_t maxLoadNumerator = 3;
     572            constexpr uint64_t maxLoadDenominator = 4;
     573            if (!sizeArg)
     574                return 0;
     575            uint64_t capacity = roundUpToPowerOfTwo(sizeArg);
     576            if (sizeArg * maxLoadDenominator >= capacity * maxLoadNumerator)
     577                return capacity * 2;
     578            return capacity;
     579        }
     580
     581        static constexpr unsigned value = capacityForSize(size);
    592582        COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
    593583        COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
    594         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
    595584    };
    596585
    … …  
    12391228        unsigned bestTableSize = WTF::roundUpToPowerOfTwo(keyCount) * 2;
    12401229
    1241         // With maxLoad at 1/2 and minLoad at 1/6, our average load is 2/6.
    1242         // If we are getting halfway between 2/6 and 1/2 (past 5/12), we double the size to avoid being too close to
    1243         // loadMax and bring the ratio close to 2/6. This give us a load in the bounds [3/12, 5/12).
    1244         bool aboveThreeQuarterLoad = keyCount * 12 >= bestTableSize * 5;
    1245         if (aboveThreeQuarterLoad)
     1230        // With maxLoad at 3/4 and minLoad at 1/6, our average load is 11/24.
     1231        // If we are getting halfway between 11/24 and 3/4 (i.e. past 14.5/24,
     1232        // which we'll round up to 15/24 i.e. 5/8), we double the size to avoid
     1233        // being too close to loadMax and bring the ratio close to 11/24. This
     1234        // give us a load in the bounds [9/24, 15/24).
     1235        bool aboveThresholdForEagerExpansion = keyCount * 8 >= bestTableSize * 5;
     1236        if (aboveThresholdForEagerExpansion)
    12461237            bestTableSize *= 2;
    12471238

  • trunk/Tools/ChangeLog

    r255883 r255889  
     12020-02-05  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [WTF] Try using 75% load factor for HashTable
     4        https://bugs.webkit.org/show_bug.cgi?id=207183
     5
     6        Reviewed by Mark Lam.
     7
     8        Fix load-factor assumption in existing tests.
     9
     10        * TestWebKitAPI/Tests/WTF/HashSet.cpp:
     11        (TestWebKitAPI::testInitialCapacity):
     12
    1132020-02-05  Jonathan Bedard  <jbedard@apple.com>
    214

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

    r255611 r255889  
    5656    }
    5757
    58     // Adding items up to less than half the capacity should not change the capacity.
    59     unsigned capacityLimit = initialCapacity / 2 - 1;
     58    // Adding items up to less than 3/4 of the capacity should not change the capacity.
     59    unsigned capacityLimit = initialCapacity * 3 / 4 - 1;
    6060    for (size_t i = size; i < capacityLimit; ++i) {
    6161        testSet.add(i);
Note: See TracChangeset for help on using the changeset viewer.