Use relaxed constexpr for StringHasher
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 9 Dec 2017 20:11:56 +0000 (20:11 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 9 Dec 2017 20:11:56 +0000 (20:11 +0000)
https://bugs.webkit.org/show_bug.cgi?id=180622

Reviewed by JF Bastien.

Now VC++ is updated and all the WebKit compilers support C++14 relaxed constexpr.
This patch uses relaxed constexpr for StringHasher constexpr implementation

* wtf/text/StringHasher.h:
(WTF::StringHasher::addCharactersAssumingAligned):
(WTF::StringHasher::Converter):
(WTF::StringHasher::computeHashAndMaskTop8Bits):
(WTF::StringHasher::computeHash):
(WTF::StringHasher::computeLiteralHash):
(WTF::StringHasher::computeLiteralHashAndMaskTop8Bits):
(WTF::StringHasher::defaultConverter):
(WTF::StringHasher::avalancheBits):
(WTF::StringHasher::finalize):
(WTF::StringHasher::finalizeAndMaskTop8Bits):
(WTF::StringHasher::avoidZero):
(WTF::StringHasher::calculateWithRemainingLastCharacter):
(WTF::StringHasher::calculateWithTwoCharacters):
(WTF::StringHasher::processPendingCharacter const):
(WTF::StringHasher::StringHasher): Deleted.
(WTF::StringHasher::avalancheBits3): Deleted.
(WTF::StringHasher::avalancheBits2): Deleted.
(WTF::StringHasher::avalancheBits1): Deleted.
(WTF::StringHasher::avalancheBits0): Deleted.
(WTF::StringHasher::calculateWithRemainingLastCharacter1): Deleted.
(WTF::StringHasher::calculateWithRemainingLastCharacter0): Deleted.
(WTF::StringHasher::calculate1): Deleted.
(WTF::StringHasher::calculate0): Deleted.
(WTF::StringHasher::calculate): Deleted.
(WTF::StringHasher::computeLiteralHashImpl): Deleted.

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

Source/WTF/ChangeLog
Source/WTF/wtf/text/StringHasher.h

index 46c2a9d..34ea748 100644 (file)
@@ -1,3 +1,40 @@
+2017-12-09  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        Use relaxed constexpr for StringHasher
+        https://bugs.webkit.org/show_bug.cgi?id=180622
+
+        Reviewed by JF Bastien.
+
+        Now VC++ is updated and all the WebKit compilers support C++14 relaxed constexpr.
+        This patch uses relaxed constexpr for StringHasher constexpr implementation
+
+        * wtf/text/StringHasher.h:
+        (WTF::StringHasher::addCharactersAssumingAligned):
+        (WTF::StringHasher::Converter):
+        (WTF::StringHasher::computeHashAndMaskTop8Bits):
+        (WTF::StringHasher::computeHash):
+        (WTF::StringHasher::computeLiteralHash):
+        (WTF::StringHasher::computeLiteralHashAndMaskTop8Bits):
+        (WTF::StringHasher::defaultConverter):
+        (WTF::StringHasher::avalancheBits):
+        (WTF::StringHasher::finalize):
+        (WTF::StringHasher::finalizeAndMaskTop8Bits):
+        (WTF::StringHasher::avoidZero):
+        (WTF::StringHasher::calculateWithRemainingLastCharacter):
+        (WTF::StringHasher::calculateWithTwoCharacters):
+        (WTF::StringHasher::processPendingCharacter const):
+        (WTF::StringHasher::StringHasher): Deleted.
+        (WTF::StringHasher::avalancheBits3): Deleted.
+        (WTF::StringHasher::avalancheBits2): Deleted.
+        (WTF::StringHasher::avalancheBits1): Deleted.
+        (WTF::StringHasher::avalancheBits0): Deleted.
+        (WTF::StringHasher::calculateWithRemainingLastCharacter1): Deleted.
+        (WTF::StringHasher::calculateWithRemainingLastCharacter0): Deleted.
+        (WTF::StringHasher::calculate1): Deleted.
+        (WTF::StringHasher::calculate0): Deleted.
+        (WTF::StringHasher::calculate): Deleted.
+        (WTF::StringHasher::computeLiteralHashImpl): Deleted.
+
 2017-12-08  Eric Carlson  <eric.carlson@apple.com>
 
         Move Logger from PAL to WTF so it can be used outside of WebCore
index a81607a..ae2e12a 100644 (file)
@@ -42,12 +42,7 @@ public:
     static constexpr const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
     static constexpr const unsigned maskHash = (1U << (sizeof(unsigned) * 8 - flagCount)) - 1;
 
-    StringHasher()
-        : m_hash(stringHashingStartValue)
-        , m_hasPendingCharacter(false)
-        , m_pendingCharacter(0)
-    {
-    }
+    StringHasher() = default;
 
     // The hasher hashes two characters at a time, and thus an "aligned" hasher is one
     // where an even number of characters have been added. Callers that always add
@@ -55,9 +50,7 @@ public:
     void addCharactersAssumingAligned(UChar a, UChar b)
     {
         ASSERT(!m_hasPendingCharacter);
-        m_hash += a;
-        m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash);
-        m_hash += m_hash >> 11;
+        m_hash = calculateWithTwoCharacters(m_hash, a, b);
     }
 
     void addCharacter(UChar character)
@@ -170,54 +163,59 @@ public:
         return finalize(processPendingCharacter());
     }
 
-    template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
+    template<typename T, UChar Converter(T)> static constexpr unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
     {
-        StringHasher hasher;
-        hasher.addCharactersAssumingAligned<T, Converter>(data, length);
-        return hasher.hashWithTop8BitsMasked();
+        return finalizeAndMaskTop8Bits(computeHashImpl<T, Converter>(data, length));
     }
 
-    template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data)
+    template<typename T, UChar Converter(T)> static constexpr unsigned computeHashAndMaskTop8Bits(const T* data)
     {
-        StringHasher hasher;
-        hasher.addCharactersAssumingAligned<T, Converter>(data);
-        return hasher.hashWithTop8BitsMasked();
+        return finalizeAndMaskTop8Bits(computeHashImpl<T, Converter>(data));
     }
 
-    template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
+    template<typename T> static constexpr unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
     {
         return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length);
     }
 
-    template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data)
+    template<typename T> static constexpr unsigned computeHashAndMaskTop8Bits(const T* data)
     {
         return computeHashAndMaskTop8Bits<T, defaultConverter>(data);
     }
 
-    template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length)
+    template<typename T, UChar Converter(T)> static constexpr unsigned computeHash(const T* data, unsigned length)
     {
-        StringHasher hasher;
-        hasher.addCharactersAssumingAligned<T, Converter>(data, length);
-        return hasher.hash();
+        return finalize(computeHashImpl<T, Converter>(data, length));
     }
 
-    template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data)
+    template<typename T, UChar Converter(T)> static constexpr unsigned computeHash(const T* data)
     {
-        StringHasher hasher;
-        hasher.addCharactersAssumingAligned<T, Converter>(data);
-        return hasher.hash();
+        return finalize(computeHashImpl<T, Converter>(data));
     }
 
-    template<typename T> static unsigned computeHash(const T* data, unsigned length)
+    template<typename T> static constexpr unsigned computeHash(const T* data, unsigned length)
     {
         return computeHash<T, defaultConverter>(data, length);
     }
 
-    template<typename T> static unsigned computeHash(const T* data)
+    template<typename T> static constexpr unsigned computeHash(const T* data)
     {
         return computeHash<T, defaultConverter>(data);
     }
 
+
+    template<typename T, unsigned charactersCount>
+    static constexpr unsigned computeLiteralHash(const T (&characters)[charactersCount])
+    {
+        return computeHash<T, defaultConverter>(characters, charactersCount - 1);
+    }
+
+    template<typename T, unsigned charactersCount>
+    static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[charactersCount])
+    {
+        return computeHashAndMaskTop8Bits<T, defaultConverter>(characters, charactersCount - 1);
+    }
+
     static unsigned hashMemory(const void* data, unsigned length)
     {
         size_t lengthInUChar = length / sizeof(UChar);
@@ -235,64 +233,50 @@ public:
         return hashMemory(data, length);
     }
 
-    static constexpr unsigned finalize(unsigned hash)
-    {
-        return avoidZero(avalancheBits(hash));
-    }
-
-    static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash)
-    {
-        // Reserving space from the high bits for flags preserves most of the hash's
-        // value, since hash lookup typically masks out the high bits anyway.
-        return avoidZero(avalancheBits(hash) & StringHasher::maskHash);
-    }
-
-    template<typename T, unsigned characterCount>
-    static constexpr unsigned computeLiteralHash(const T (&characters)[characterCount])
+private:
+    static constexpr UChar defaultConverter(UChar character)
     {
-        return StringHasher::finalize(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
+        return character;
     }
 
-    template<typename T, unsigned characterCount>
-    static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[characterCount])
+    static constexpr UChar defaultConverter(LChar character)
     {
-        return StringHasher::finalizeAndMaskTop8Bits(computeLiteralHashImpl(stringHashingStartValue, 0, characters, characterCount - 1));
+        return character;
     }
 
-private:
-    static UChar defaultConverter(UChar character)
+    static constexpr UChar defaultConverter(char character)
     {
         return character;
     }
 
-    static UChar defaultConverter(LChar character)
+    static constexpr UChar defaultConverter(char16_t character)
     {
         return character;
     }
 
-    ALWAYS_INLINE static constexpr unsigned avalancheBits3(unsigned hash)
+    ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash)
     {
-        return hash ^ (hash << 10);
-    }
+        unsigned result = hash;
 
-    ALWAYS_INLINE static constexpr unsigned avalancheBits2(unsigned hash)
-    {
-        return avalancheBits3(hash + (hash >> 15));
-    }
+        result ^= result << 3;
+        result += result >> 5;
+        result ^= result << 2;
+        result += result >> 15;
+        result ^= result << 10;
 
-    ALWAYS_INLINE static constexpr unsigned avalancheBits1(unsigned hash)
-    {
-        return avalancheBits2(hash ^ (hash << 2));
+        return result;
     }
 
-    ALWAYS_INLINE static constexpr unsigned avalancheBits0(unsigned hash)
+    static constexpr unsigned finalize(unsigned hash)
     {
-        return avalancheBits1(hash + (hash >> 5));
+        return avoidZero(avalancheBits(hash));
     }
 
-    ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash)
+    static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash)
     {
-        return avalancheBits0(hash ^ (hash << 3));
+        // Reserving space from the high bits for flags preserves most of the hash's
+        // value, since hash lookup typically masks out the high bits anyway.
+        return avoidZero(avalancheBits(hash) & StringHasher::maskHash);
     }
 
     // This avoids ever returning a hash code of 0, since that is used to
@@ -301,66 +285,76 @@ private:
     // exactly 0 when hash lookup masks out the high bits.
     ALWAYS_INLINE static constexpr unsigned avoidZero(unsigned hash)
     {
-        return hash ? hash : (0x80000000 >> StringHasher::flagCount);
+        if (hash)
+            return hash;
+        return 0x80000000 >> flagCount;
     }
 
-    unsigned processPendingCharacter() const
+    static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character)
     {
-        unsigned result = m_hash;
+        unsigned result = hash;
+
+        result += character;
+        result ^= result << 11;
+        result += result >> 17;
 
-        // Handle end case.
-        if (m_hasPendingCharacter) {
-            result += m_pendingCharacter;
-            result ^= result << 11;
-            result += result >> 17;
-        }
         return result;
     }
 
-    // FIXME: This code limits itself to the older, more limited C++11 constexpr capabilities, using
-    // recursion instead of looping, for example. Would be nice to rewrite this in a simpler way
-    // once we no longer need to support compilers like GCC 4.9 that do not yet support it.
-    static constexpr unsigned calculateWithRemainingLastCharacter1(unsigned hash)
+    ALWAYS_INLINE static constexpr unsigned calculateWithTwoCharacters(unsigned hash, unsigned firstCharacter, unsigned secondCharacter)
     {
-        return hash + (hash >> 17);
-    }
+        unsigned result = hash;
 
-    static constexpr unsigned calculateWithRemainingLastCharacter0(unsigned hash)
-    {
-        return calculateWithRemainingLastCharacter1((hash << 11) ^ hash);
-    }
+        result += firstCharacter;
+        result = (result << 16) ^ ((secondCharacter << 11) ^ result);
+        result += result >> 11;
 
-    static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character)
-    {
-        return calculateWithRemainingLastCharacter0(hash + character);
+        return result;
     }
 
-    static constexpr unsigned calculate1(unsigned hash)
+    template<typename T, UChar Converter(T)>
+    static constexpr unsigned computeHashImpl(const T* characters, unsigned length)
     {
-        return hash + (hash >> 11);
-    }
+        unsigned result = stringHashingStartValue;
+        bool remainder = length & 1;
+        length >>= 1;
 
-    static constexpr unsigned calculate0(unsigned hash, unsigned secondCharacter)
-    {
-        return calculate1((hash << 16) ^ ((secondCharacter << 11) ^ hash));
+        while (length--) {
+            result = calculateWithTwoCharacters(result, Converter(characters[0]), Converter(characters[1]));
+            characters += 2;
+        }
+
+        if (remainder)
+            return calculateWithRemainingLastCharacter(result, Converter(characters[0]));
+        return result;
     }
 
-    static constexpr unsigned calculate(unsigned hash, unsigned firstCharacter, unsigned secondCharacter)
+    template<typename T, UChar Converter(T)>
+    static constexpr unsigned computeHashImpl(const T* characters)
     {
-        return calculate0(hash + firstCharacter, secondCharacter);
+        unsigned result = stringHashingStartValue;
+        while (T a = *characters++) {
+            T b = *characters++;
+            if (!b)
+                return calculateWithRemainingLastCharacter(result, Converter(a));
+            result = calculateWithTwoCharacters(result, Converter(a), Converter(b));
+        }
+        return result;
     }
 
-    static constexpr unsigned computeLiteralHashImpl(unsigned hash, unsigned index, const char* characters, unsigned length)
+    unsigned processPendingCharacter() const
     {
-        return (index == length)
-            ? hash : ((index + 1) == length)
-            ? calculateWithRemainingLastCharacter(hash, characters[index])
-            : computeLiteralHashImpl(calculate(hash, characters[index], characters[index + 1]), index + 2, characters, length);
+        unsigned result = m_hash;
+
+        // Handle end case.
+        if (m_hasPendingCharacter)
+            return calculateWithRemainingLastCharacter(result, m_pendingCharacter);
+        return result;
     }
 
-    unsigned m_hash;
-    bool m_hasPendingCharacter;
-    UChar m_pendingCharacter;
+    unsigned m_hash { stringHashingStartValue };
+    UChar m_pendingCharacter { 0 };
+    bool m_hasPendingCharacter { false };
 };
 
 } // namespace WTF