Speed up HashTable decoding by reserving capacity and avoiding rehashing
authorcdumez@apple.com <cdumez@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 21 Jul 2019 03:53:31 +0000 (03:53 +0000)
committercdumez@apple.com <cdumez@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 21 Jul 2019 03:53:31 +0000 (03:53 +0000)
https://bugs.webkit.org/show_bug.cgi?id=199982

Reviewed by Saam Barati.

Source/WebKit:

Use HashMap::reserveInitialCapacity() in the HashMap IPC decoder for
performance. I measured a ~35% improvement when decoding a very large
HashMap of Strings (~160k entries) in the context of the
StorageManager::GetValues IPC.

* Platform/IPC/ArgumentCoders.h:
* Shared/API/c/WKDictionary.cpp:
(WKDictionaryCreate):

Source/WTF:

Introduce reserveInitialCapacity() on HashMap to reserve capacity on a
HashMap and cut down on rehashing cost when possible.

* wtf/HashMap.h:
* wtf/HashTable.h:
(WTF::HashTable::reserveInitialCapacity):

* wtf/persistence/PersistentCoders.h:
Use HashMap::reserveInitialCapacity() in the HashMap persistent decoder for
performance.

Tools:

Add API test coverage.

* TestWebKitAPI/Tests/WTF/HashMap.cpp:
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@247673 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/HashMap.h
Source/WTF/wtf/HashTable.h
Source/WTF/wtf/persistence/PersistentCoders.h
Source/WebKit/ChangeLog
Source/WebKit/Platform/IPC/ArgumentCoders.h
Source/WebKit/Shared/API/c/WKDictionary.cpp
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

index 8e08fdc..9110814 100644 (file)
@@ -1,3 +1,21 @@
+2019-07-20  Chris Dumez  <cdumez@apple.com>
+
+        Speed up HashTable decoding by reserving capacity and avoiding rehashing
+        https://bugs.webkit.org/show_bug.cgi?id=199982
+
+        Reviewed by Saam Barati.
+
+        Introduce reserveInitialCapacity() on HashMap to reserve capacity on a
+        HashMap and cut down on rehashing cost when possible.
+
+        * wtf/HashMap.h:
+        * wtf/HashTable.h:
+        (WTF::HashTable::reserveInitialCapacity):
+
+        * wtf/persistence/PersistentCoders.h:
+        Use HashMap::reserveInitialCapacity() in the HashMap persistent decoder for
+        performance.
+
 2019-07-20  Alexander Mikhaylenko  <exalm7659@gmail.com>
 
         REGRESSION(r246033/r246496): [GTK] Kinetic scrolling doesn't work
 2019-07-20  Alexander Mikhaylenko  <exalm7659@gmail.com>
 
         REGRESSION(r246033/r246496): [GTK] Kinetic scrolling doesn't work
index 3406f54..2c872a6 100644 (file)
@@ -92,6 +92,8 @@ public:
     unsigned capacity() const;
     bool isEmpty() const;
 
     unsigned capacity() const;
     bool isEmpty() const;
 
+    void reserveInitialCapacity(unsigned keyCount) { m_impl.reserveInitialCapacity(keyCount); }
+
     // iterators iterate over pairs of keys and values
     iterator begin();
     iterator end();
     // iterators iterate over pairs of keys and values
     iterator begin();
     iterator end();
index 2281d1f..940b052 100644 (file)
@@ -398,6 +398,20 @@ namespace WTF {
         unsigned capacity() const { return m_tableSize; }
         bool isEmpty() const { return !m_keyCount; }
 
         unsigned capacity() const { return m_tableSize; }
         bool isEmpty() const { return !m_keyCount; }
 
+        void reserveInitialCapacity(unsigned keyCount)
+        {
+            ASSERT(!m_table);
+            ASSERT(!m_tableSize);
+            ASSERT(!m_deletedCount);
+
+            unsigned minimumTableSize = KeyTraits::minimumTableSize;
+            unsigned newTableSize = std::max(minimumTableSize, computeBestTableSize(keyCount));
+
+            m_tableSize = newTableSize;
+            m_tableSizeMask = newTableSize - 1;
+            m_table = allocateTable(newTableSize);
+        }
+
         AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
         AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
 
         AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
         AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
 
index 7ee3c93..b416ad8 100644 (file)
@@ -196,6 +196,7 @@ template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTrai
             return false;
 
         HashMapType tempHashMap;
             return false;
 
         HashMapType tempHashMap;
+        tempHashMap.reserveInitialCapacity(hashMapSize);
         for (uint64_t i = 0; i < hashMapSize; ++i) {
             KeyArg key;
             MappedArg value;
         for (uint64_t i = 0; i < hashMapSize; ++i) {
             KeyArg key;
             MappedArg value;
index d171091..3f3b04a 100644 (file)
@@ -1,5 +1,21 @@
 2019-07-20  Chris Dumez  <cdumez@apple.com>
 
 2019-07-20  Chris Dumez  <cdumez@apple.com>
 
+        Speed up HashTable decoding by reserving capacity and avoiding rehashing
+        https://bugs.webkit.org/show_bug.cgi?id=199982
+
+        Reviewed by Saam Barati.
+
+        Use HashMap::reserveInitialCapacity() in the HashMap IPC decoder for
+        performance. I measured a ~35% improvement when decoding a very large
+        HashMap of Strings (~160k entries) in the context of the
+        StorageManager::GetValues IPC.
+
+        * Platform/IPC/ArgumentCoders.h:
+        * Shared/API/c/WKDictionary.cpp:
+        (WKDictionaryCreate):
+
+2019-07-20  Chris Dumez  <cdumez@apple.com>
+
         Micro-optimize HashMap & String IPC decoding
         https://bugs.webkit.org/show_bug.cgi?id=199967
 
         Micro-optimize HashMap & String IPC decoding
         https://bugs.webkit.org/show_bug.cgi?id=199967
 
index a9302b4..2cd6096 100644 (file)
@@ -378,6 +378,7 @@ template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTrai
             return WTF::nullopt;
 
         HashMapType hashMap;
             return WTF::nullopt;
 
         HashMapType hashMap;
+        hashMap.reserveInitialCapacity(hashMapSize);
         for (uint32_t i = 0; i < hashMapSize; ++i) {
             Optional<KeyArg> key;
             decoder >> key;
         for (uint32_t i = 0; i < hashMapSize; ++i) {
             Optional<KeyArg> key;
             decoder >> key;
index 2f5a00e..2e490fa 100644 (file)
@@ -38,6 +38,7 @@ WKTypeID WKDictionaryGetTypeID()
 WK_EXPORT WKDictionaryRef WKDictionaryCreate(const WKStringRef* keys, const WKTypeRef* values, size_t numberOfValues)
 {
     API::Dictionary::MapType map;
 WK_EXPORT WKDictionaryRef WKDictionaryCreate(const WKStringRef* keys, const WKTypeRef* values, size_t numberOfValues)
 {
     API::Dictionary::MapType map;
+    map.reserveInitialCapacity(numberOfValues);
     for (size_t i = 0; i < numberOfValues; ++i)
         map.add(WebKit::toImpl(keys[i])->string(), WebKit::toImpl(values[i]));
 
     for (size_t i = 0; i < numberOfValues; ++i)
         map.add(WebKit::toImpl(keys[i])->string(), WebKit::toImpl(values[i]));
 
index 7826119..dd4b9e1 100644 (file)
@@ -1,3 +1,15 @@
+2019-07-20  Chris Dumez  <cdumez@apple.com>
+
+        Speed up HashTable decoding by reserving capacity and avoiding rehashing
+        https://bugs.webkit.org/show_bug.cgi?id=199982
+
+        Reviewed by Saam Barati.
+
+        Add API test coverage.
+
+        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+        (TestWebKitAPI::TEST):
+
 2019-07-20  Andres Gonzalez  <andresg_22@apple.com>
 
         Add accessibilityInsertText for text insertion in edit fields.
 2019-07-20  Andres Gonzalez  <andresg_22@apple.com>
 
         Add accessibilityInsertText for text insertion in edit fields.
index d4ba35a..1e163d3 100644 (file)
@@ -34,6 +34,7 @@
 #include <string>
 #include <wtf/HashMap.h>
 #include <wtf/Ref.h>
 #include <string>
 #include <wtf/HashMap.h>
 #include <wtf/Ref.h>
+#include <wtf/text/StringConcatenateNumbers.h>
 #include <wtf/text/StringHash.h>
 
 namespace TestWebKitAPI {
 #include <wtf/text/StringHash.h>
 
 namespace TestWebKitAPI {
@@ -1037,6 +1038,39 @@ TEST(WTF_HashMap, Random_IsEvenlyDistributed)
     ASSERT_LE(ones, 600u);
 }
 
     ASSERT_LE(ones, 600u);
 }
 
+TEST(WTF_HashMap, ReserveInitialCapacity)
+{
+    HashMap<String, String> map;
+    EXPECT_EQ(0u, map.size());
+    map.reserveInitialCapacity(9999);
+    EXPECT_EQ(0u, map.size());
+    for (int i = 0; i < 9999; ++i)
+        map.add(makeString("foo", i), makeString("bar", i));
+    EXPECT_EQ(9999u, map.size());
+    EXPECT_TRUE(map.contains("foo3"_str));
+    EXPECT_STREQ("bar3", map.get("foo3"_str).utf8().data());
+    for (int i = 0; i < 9999; ++i)
+        map.add(makeString("excess", i), makeString("baz", i));
+    EXPECT_EQ(9999u + 9999u, map.size());
+    for (int i = 0; i < 9999; ++i)
+        EXPECT_TRUE(map.remove(makeString("foo", i)));
+    EXPECT_EQ(9999u, map.size());
+    EXPECT_STREQ("baz3", map.get("excess3"_str).utf8().data());
+    for (int i = 0; i < 9999; ++i)
+        EXPECT_TRUE(map.remove(makeString("excess", i)));
+    EXPECT_EQ(0u, map.size());
+    
+    HashMap<String, String> map2;
+    map2.reserveInitialCapacity(9999);
+    EXPECT_FALSE(map2.remove("foo1"_s));
+    for (int i = 0; i < 2000; ++i)
+        map2.add(makeString("foo", i), makeString("bar", i));
+    EXPECT_EQ(2000u, map2.size());
+    for (int i = 0; i < 2000; ++i)
+        EXPECT_TRUE(map2.remove(makeString("foo", i)));
+    EXPECT_EQ(0u, map2.size());
+}
+
 TEST(WTF_HashMap, Random_IsEvenlyDistributedAfterRemove)
 {
     for (size_t tableSize = 2; tableSize <= 2 * 6; ++tableSize) { // Our hash tables shrink at a load factor of 1 / 6.
 TEST(WTF_HashMap, Random_IsEvenlyDistributedAfterRemove)
 {
     for (size_t tableSize = 2; tableSize <= 2 * 6; ++tableSize) { // Our hash tables shrink at a load factor of 1 / 6.