Title: [295771] trunk
Revision
295771
Author
[email protected]
Date
2022-06-23 01:23:58 -0700 (Thu, 23 Jun 2022)

Log Message

[WTF] Use CompactPtr in AtomStringTable if it is more efficient
https://bugs.webkit.org/show_bug.cgi?id=241883

Reviewed by Darin Adler.

1. We add HashTable support for CompactPtr. Correctly setting up HashTraits and Hashers so that we can have HashSet<CompactPtr<T>>.
2. Use CompactPtr in AtomStringTable if it is more efficient than PackedPtr<StringImpl>. Typically, this means we are in iOS.

* Source/WTF/wtf/CompactPtr.h:
(WTF::CompactPtr::CompactPtr):
(WTF::CompactPtr::encode):
(WTF::CompactPtr::decode):
(WTF::CompactPtr::isHashTableDeletedValue const):
(WTF::CompactPtrTraits::hashTableDeletedValue):
(WTF::CompactPtrTraits::isHashTableDeletedValue):
* Source/WTF/wtf/Forward.h:
* Source/WTF/wtf/HashTraits.h:
(WTF::HashTraits<CompactPtr<P>>::emptyValue):
(WTF::HashTraits<CompactPtr<P>>::isEmptyValue):
(WTF::HashTraits<CompactPtr<P>>::peek):
* Source/WTF/wtf/text/AtomStringImpl.cpp:
(WTF::UCharBufferTranslator::equal):
(WTF::UCharBufferTranslator::translate):
(WTF::HashAndUTF8CharactersTranslator::equal):
(WTF::HashAndUTF8CharactersTranslator::translate):
(WTF::SubstringTranslator::translate):
(WTF::SubstringTranslator8::equal):
(WTF::SubstringTranslator16::equal):
(WTF::LCharBufferTranslator::equal):
(WTF::LCharBufferTranslator::translate):
(WTF::BufferFromStaticDataTranslator::equal):
(WTF::BufferFromStaticDataTranslator::translate):
* Source/WTF/wtf/text/AtomStringTable.h:
* Tools/TestWebKitAPI/Tests/WTF/CompactPtr.cpp:
(TestWebKitAPI::TEST):

Canonical link: https://commits.webkit.org/251776@main

Modified Paths

Diff

Modified: trunk/Source/WTF/wtf/CompactPtr.h (295770 => 295771)


--- trunk/Source/WTF/wtf/CompactPtr.h	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Source/WTF/wtf/CompactPtr.h	2022-06-23 08:23:58 UTC (rev 295771)
@@ -27,6 +27,9 @@
 
 #include <cstdint>
 #include <utility>
+#include <wtf/Forward.h>
+#include <wtf/GetPtr.h>
+#include <wtf/HashFunctions.h>
 #include <wtf/RawPtrTraits.h>
 #include <wtf/StdLibExtras.h>
 
@@ -47,7 +50,6 @@
 template <typename T>
 class CompactPtr {
     WTF_MAKE_FAST_ALLOCATED;
-
 public:
 #if HAVE(36BIT_ADDRESS)
     // The CompactPtr algorithm relies on being able to shift
@@ -56,8 +58,10 @@
     // loss is if the if the address is always 16 bytes aligned i.e.
     // the lower 4 bits is always 0.
     using StorageType = uint32_t;
+    static constexpr bool is32Bit = true;
 #else
     using StorageType = uintptr_t;
+    static constexpr bool is32Bit = false;
 #endif
     static constexpr bool isCompactedType = true;
 
@@ -82,6 +86,8 @@
         std::exchange(o.m_ptr, 0);
     }
 
+    ALWAYS_INLINE constexpr CompactPtr(HashTableDeletedValueType) : m_ptr(hashDeletedStorageValue) { }
+
     ALWAYS_INLINE ~CompactPtr() = default;
 
     T& operator*() const { return *get(); }
@@ -173,6 +179,7 @@
     {
         uintptr_t intPtr = bitwise_cast<uintptr_t>(ptr);
 #if HAVE(36BIT_ADDRESS)
+        static_assert(alignof(T) >= (1ULL << bitsShift));
         ASSERT(!(intPtr & alignmentMask));
         StorageType encoded = static_cast<StorageType>(intPtr >> bitsShift);
         ASSERT(decode(encoded) == ptr);
@@ -185,6 +192,7 @@
     static ALWAYS_INLINE T* decode(StorageType ptr)
     {
 #if HAVE(36BIT_ADDRESS)
+        static_assert(alignof(T) >= (1ULL << bitsShift));
         return bitwise_cast<T*>(static_cast<uintptr_t>(ptr) << bitsShift);
 #else
         return bitwise_cast<T*>(ptr);
@@ -191,6 +199,8 @@
 #endif
     }
 
+    bool isHashTableDeletedValue() const { return m_ptr == hashDeletedStorageValue; }
+
 private:
     template <typename X>
     friend class CompactPtr;
@@ -197,6 +207,7 @@
 
     static constexpr uint32_t bitsShift = 4;
     static constexpr uintptr_t alignmentMask = (1ull << bitsShift) - 1;
+    static constexpr StorageType hashDeletedStorageValue = 1; // 0x16 (encoded as 1) is within the first unmapped page for nullptr. Thus, it never appears.
 
     StorageType m_ptr { 0 };
 };
@@ -219,6 +230,8 @@
 
     using StorageType = CompactPtr<T>;
 
+    static constexpr bool is32Bit = StorageType::is32Bit;
+
     template <typename U>
     static ALWAYS_INLINE T* exchange(StorageType& ptr, U&& newValue) { return ptr.exchange(newValue); }
 
@@ -227,10 +240,12 @@
 
     static ALWAYS_INLINE T* unwrap(const StorageType& ptr) { return ptr.get(); }
 
-    static StorageType hashTableDeletedValue() { return bitwise_cast<StorageType>(static_cast<StorageType>(-1)); }
-    static ALWAYS_INLINE bool isHashTableDeletedValue(const StorageType& ptr) { return ptr == hashTableDeletedValue(); }
+    static StorageType hashTableDeletedValue() { return StorageType { HashTableDeletedValue }; }
+    static ALWAYS_INLINE bool isHashTableDeletedValue(const StorageType& ptr) { return ptr.isHashTableDeletedValue(); }
 };
 
+template<typename P> struct DefaultHash<CompactPtr<P>> : PtrHash<CompactPtr<P>> { };
+
 } // namespace WTF
 
 using WTF::CompactPtr;

Modified: trunk/Source/WTF/wtf/Forward.h (295770 => 295771)


--- trunk/Source/WTF/wtf/Forward.h	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Source/WTF/wtf/Forward.h	2022-06-23 08:23:58 UTC (rev 295771)
@@ -65,6 +65,7 @@
 
 template<typename> struct DefaultRefDerefTraits;
 
+template<typename> class CompactPtr;
 template<typename> class CompletionHandler;
 template<typename> class FixedVector;
 template<typename> class Function;

Modified: trunk/Source/WTF/wtf/HashTraits.h (295770 => 295771)


--- trunk/Source/WTF/wtf/HashTraits.h	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Source/WTF/wtf/HashTraits.h	2022-06-23 08:23:58 UTC (rev 295771)
@@ -253,6 +253,18 @@
     static PeekType peek(P* value) { return value; }
 };
 
+template<typename P> struct HashTraits<CompactPtr<P>> : SimpleClassHashTraits<CompactPtr<P>> {
+    static constexpr bool hasIsEmptyValueFunction = true;
+    using TargetType = CompactPtr<P>;
+
+    static CompactPtr<P> emptyValue() { return nullptr; }
+    static bool isEmptyValue(const TargetType& value) { return !value; }
+
+    using PeekType = P*;
+    static PeekType peek(const TargetType& value) { return value.get(); }
+    static PeekType peek(P* value) { return value; }
+};
+
 template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
     static constexpr bool hasIsEmptyValueFunction = true;
     static bool isEmptyValue(const String&);

Modified: trunk/Source/WTF/wtf/text/AtomStringImpl.cpp (295770 => 295771)


--- trunk/Source/WTF/wtf/text/AtomStringImpl.cpp	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Source/WTF/wtf/text/AtomStringImpl.cpp	2022-06-23 08:23:58 UTC (rev 295771)
@@ -95,12 +95,12 @@
         return buf.hash;
     }
 
-    static bool equal(PackedPtr<StringImpl> const& str, const UCharBuffer& buf)
+    static bool equal(AtomStringTable::StringEntry const& str, const UCharBuffer& buf)
     {
         return WTF::equal(str.get(), buf.characters, buf.length);
     }
 
-    static void translate(PackedPtr<StringImpl>& location, const UCharBuffer& buf, unsigned hash)
+    static void translate(AtomStringTable::StringEntry& location, const UCharBuffer& buf, unsigned hash)
     {
         auto* pointer = &StringImpl::create8BitIfPossible(buf.characters, buf.length).leakRef();
         pointer->setHash(hash);
@@ -122,7 +122,7 @@
         return buffer.hash;
     }
 
-    static bool equal(PackedPtr<StringImpl> const& passedString, const HashAndUTF8Characters& buffer)
+    static bool equal(AtomStringTable::StringEntry const& passedString, const HashAndUTF8Characters& buffer)
     {
         auto* string = passedString.get();
         if (buffer.utf16Length != string->length())
@@ -159,7 +159,7 @@
         return true;
     }
 
-    static void translate(PackedPtr<StringImpl>& location, const HashAndUTF8Characters& buffer, unsigned hash)
+    static void translate(AtomStringTable::StringEntry& location, const HashAndUTF8Characters& buffer, unsigned hash)
     {
         UChar* target;
         auto newString = StringImpl::createUninitialized(buffer.utf16Length, target);
@@ -198,7 +198,7 @@
 };
 
 struct SubstringTranslator {
-    static void translate(PackedPtr<StringImpl>& location, const SubstringLocation& buffer, unsigned hash)
+    static void translate(AtomStringTable::StringEntry& location, const SubstringLocation& buffer, unsigned hash)
     {
         auto* pointer = &StringImpl::createSubstringSharingImpl(*buffer.baseString, buffer.start, buffer.length).leakRef();
         pointer->setHash(hash);
@@ -213,7 +213,7 @@
         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters8() + buffer.start, buffer.length);
     }
 
-    static bool equal(PackedPtr<StringImpl> const& string, const SubstringLocation& buffer)
+    static bool equal(AtomStringTable::StringEntry const& string, const SubstringLocation& buffer)
     {
         return WTF::equal(string.get(), buffer.baseString->characters8() + buffer.start, buffer.length);
     }
@@ -225,7 +225,7 @@
         return StringHasher::computeHashAndMaskTop8Bits(buffer.baseString->characters16() + buffer.start, buffer.length);
     }
 
-    static bool equal(PackedPtr<StringImpl> const& string, const SubstringLocation& buffer)
+    static bool equal(AtomStringTable::StringEntry const& string, const SubstringLocation& buffer)
     {
         return WTF::equal(string.get(), buffer.baseString->characters16() + buffer.start, buffer.length);
     }
@@ -259,12 +259,12 @@
         return buf.hash;
     }
 
-    static bool equal(PackedPtr<StringImpl> const& str, const LCharBuffer& buf)
+    static bool equal(AtomStringTable::StringEntry const& str, const LCharBuffer& buf)
     {
         return WTF::equal(str.get(), buf.characters, buf.length);
     }
 
-    static void translate(PackedPtr<StringImpl>& location, const LCharBuffer& buf, unsigned hash)
+    static void translate(AtomStringTable::StringEntry& location, const LCharBuffer& buf, unsigned hash)
     {
         auto* pointer = &StringImpl::create(buf.characters, buf.length).leakRef();
         pointer->setHash(hash);
@@ -281,12 +281,12 @@
         return buf.hash;
     }
 
-    static bool equal(PackedPtr<StringImpl> const& str, const Buffer& buf)
+    static bool equal(AtomStringTable::StringEntry const& str, const Buffer& buf)
     {
         return WTF::equal(str.get(), buf.characters, buf.length);
     }
 
-    static void translate(PackedPtr<StringImpl>& location, const Buffer& buf, unsigned hash)
+    static void translate(AtomStringTable::StringEntry& location, const Buffer& buf, unsigned hash)
     {
         auto* pointer = &StringImpl::createWithoutCopying(buf.characters, buf.length).leakRef();
         pointer->setHash(hash);

Modified: trunk/Source/WTF/wtf/text/AtomStringTable.h (295770 => 295771)


--- trunk/Source/WTF/wtf/text/AtomStringTable.h	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Source/WTF/wtf/text/AtomStringTable.h	2022-06-23 08:23:58 UTC (rev 295771)
@@ -22,6 +22,7 @@
 
 #pragma once
 
+#include <wtf/CompactPtr.h>
 #include <wtf/HashSet.h>
 #include <wtf/Packed.h>
 #include <wtf/text/StringHash.h>
@@ -34,7 +35,9 @@
 class AtomStringTable {
     WTF_MAKE_FAST_ALLOCATED;
 public:
-    using StringEntry = PackedPtr<StringImpl>;
+    // If CompactPtr is 32bit, it is more efficient than PackedPtr (6 bytes).
+    // We select underlying implementation based on CompactPtr's efficacy.
+    using StringEntry = std::conditional_t<CompactPtrTraits<StringImpl>::is32Bit, CompactPtr<StringImpl>, PackedPtr<StringImpl>>;
     using StringTableImpl = HashSet<StringEntry>;
 
     WTF_EXPORT_PRIVATE ~AtomStringTable();

Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/CompactPtr.cpp (295770 => 295771)


--- trunk/Tools/TestWebKitAPI/Tests/WTF/CompactPtr.cpp	2022-06-23 07:45:56 UTC (rev 295770)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/CompactPtr.cpp	2022-06-23 08:23:58 UTC (rev 295771)
@@ -28,6 +28,7 @@
 
 #include "AlignedRefLogger.h"
 #include "Utilities.h"
+#include <wtf/HashMap.h>
 #include <wtf/MainThread.h>
 #include <wtf/NeverDestroyed.h>
 #include <wtf/RefCounted.h>
@@ -195,4 +196,24 @@
     }
 }
 
+struct alignas(16) AlignedPackingTarget {
+    unsigned m_value { 0 };
+};
+TEST(WTF_CompactPtr, HashMap)
+{
+    Vector<AlignedPackingTarget> vector;
+    HashMap<PackedPtr<AlignedPackingTarget>, unsigned> map;
+    vector.reserveCapacity(10000);
+    for (unsigned i = 0; i < 10000; ++i)
+        vector.uncheckedAppend(AlignedPackingTarget { i });
+
+    for (auto& target : vector)
+        map.add(&target, target.m_value);
+
+    for (auto& target : vector) {
+        EXPECT_TRUE(map.contains(&target));
+        EXPECT_EQ(map.get(&target), target.m_value);
+    }
+}
+
 } // namespace TestWebKitAPI
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to