Implement a faster findBitInWord() using the hardware ctz instruction.
authormark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 May 2020 20:17:34 +0000 (20:17 +0000)
committermark.lam@apple.com <mark.lam@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 May 2020 20:17:34 +0000 (20:17 +0000)
https://bugs.webkit.org/show_bug.cgi?id=212032
<rdar://problem/63348086>

Reviewed by Saam Barati.

Source/bmalloc:

Apply same changes to bmalloc's copy of findBitInWord().

* bmalloc/Algorithm.h:
(bmalloc::ctz):
(bmalloc::findBitInWord):

Source/WTF:

Based on local microbenchmarking, both ARM64 and X86_64 shows a speed up of
28% - 95% faster than the loop.

The largest perf regressions for ctz vs the loop, are when finding 1 in a mostly
set word or finding 0 in a mostly cleared word. For example, on X86_64:
    Find 1 in 0xffffffffffffffff: using loop 8.67 ms, using ctz 6.07 ms, delta 30.0%
    Find 0 in 0x8000000000000000: using loop 9.01 ms, using ctz 6.54 ms, delta 28.1%

The largest perf progressions for ctz vs the loop, are the opposite: finding 1 in
a mostly cleared word, or finding a 0 in a mostly set word. For example, on X86_64:
    Find 1 in 0x8000000000000000: using loop 91.4 ms, using ctz 6.48 ms, delta 92.9%
    Find 0 in 0xffffffffffffffff: using loop 91.7 ms, using ctz 6.95 ms, delta 92.4%

TL;DR: the microbenchmark methodology used:

findBitInWord() takes:
    a. word to scan
    b. startIndex
    c. endIndex
    d. bool value to scan for, either 1 or 0.

1. Randomly select 1000 startIndex and endIndex pairs.
   The endIndex is guaranteed to be >= startIndex.

2. Using a base word of 0xffffffffffffffff (or uint64_t) and 0xffffffff (for uint32_t),
   shift left by 0 - N (where N is the number of bits in the word) to generate
   N + 1 words for the test.  This produces words with contiguous lengths of 1s
   and 0s.  We're choosing these words to deliberately measure the effects o
   run lengths of 0s or 1s on the algorithm in use.

3. For each test word, call findBitInWord() with the start and end indexes chosen
   in 1 for a 100 iterations.

4. Run (3) once to search for a true value, and once to search for a false value.

5. Print the results for each test word and value pair.

* wtf/BitVector.cpp:
* wtf/Bitmap.h:
* wtf/StdLibExtras.h:
(WTF::findBitInWord):

Tools:

Add tests to make sure that the ctz implementation matches the loop implementation
in behavior.

* TestWebKitAPI/CMakeLists.txt:
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/StdLibExtras.cpp: Added.
(TestWebKitAPI::testFindBitInWord):
(TestWebKitAPI::TEST):

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

Source/WTF/ChangeLog
Source/WTF/wtf/BitVector.cpp
Source/WTF/wtf/Bitmap.h
Source/WTF/wtf/StdLibExtras.h
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/Algorithm.h
Tools/ChangeLog
Tools/TestWebKitAPI/CMakeLists.txt
Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
Tools/TestWebKitAPI/Tests/WTF/StdLibExtras.cpp [new file with mode: 0644]

index ef76874..b5d18b3 100644 (file)
@@ -1,3 +1,53 @@
+2020-05-18  Mark Lam  <mark.lam@apple.com>
+
+        Implement a faster findBitInWord() using the hardware ctz instruction.
+        https://bugs.webkit.org/show_bug.cgi?id=212032
+        <rdar://problem/63348086>
+
+        Reviewed by Saam Barati.
+
+        Based on local microbenchmarking, both ARM64 and X86_64 shows a speed up of
+        28% - 95% faster than the loop.
+
+        The largest perf regressions for ctz vs the loop, are when finding 1 in a mostly
+        set word or finding 0 in a mostly cleared word. For example, on X86_64:
+            Find 1 in 0xffffffffffffffff: using loop 8.67 ms, using ctz 6.07 ms, delta 30.0%
+            Find 0 in 0x8000000000000000: using loop 9.01 ms, using ctz 6.54 ms, delta 28.1%
+
+        The largest perf progressions for ctz vs the loop, are the opposite: finding 1 in
+        a mostly cleared word, or finding a 0 in a mostly set word. For example, on X86_64:
+            Find 1 in 0x8000000000000000: using loop 91.4 ms, using ctz 6.48 ms, delta 92.9%
+            Find 0 in 0xffffffffffffffff: using loop 91.7 ms, using ctz 6.95 ms, delta 92.4%
+
+        TL;DR: the microbenchmark methodology used:
+
+        findBitInWord() takes:
+            a. word to scan
+            b. startIndex
+            c. endIndex
+            d. bool value to scan for, either 1 or 0.
+
+        1. Randomly select 1000 startIndex and endIndex pairs.
+           The endIndex is guaranteed to be >= startIndex.
+
+        2. Using a base word of 0xffffffffffffffff (or uint64_t) and 0xffffffff (for uint32_t),
+           shift left by 0 - N (where N is the number of bits in the word) to generate
+           N + 1 words for the test.  This produces words with contiguous lengths of 1s
+           and 0s.  We're choosing these words to deliberately measure the effects o
+           run lengths of 0s or 1s on the algorithm in use.
+
+        3. For each test word, call findBitInWord() with the start and end indexes chosen
+           in 1 for a 100 iterations.
+
+        4. Run (3) once to search for a true value, and once to search for a false value.
+
+        5. Print the results for each test word and value pair.
+
+        * wtf/BitVector.cpp:
+        * wtf/Bitmap.h:
+        * wtf/StdLibExtras.h:
+        (WTF::findBitInWord):
+
 2020-05-18  Darin Adler  <darin@apple.com>
 
         Add iterator checking to ListHashSet
index 8a30877..5fe8d95 100644 (file)
@@ -29,7 +29,7 @@
 #include <algorithm>
 #include <string.h>
 #include <wtf/Assertions.h>
-#include <wtf/StdLibExtras.h>
+#include <wtf/MathExtras.h>
 
 namespace WTF {
 
index ce9b3d5..bd4f0b0 100644 (file)
@@ -22,8 +22,8 @@
 #include <array>
 #include <wtf/Atomics.h>
 #include <wtf/HashFunctions.h>
+#include <wtf/MathExtras.h>
 #include <wtf/StdIntExtras.h>
-#include <wtf/StdLibExtras.h>
 #include <string.h>
 #include <type_traits>
 
index ee77ba7..8079339 100644 (file)
@@ -317,20 +317,42 @@ bool checkAndSet(T& left, U right)
 }
 
 template<typename T>
-bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
+inline unsigned ctz(T value); // Clients will also need to #include MathExtras.h
+
+template<typename T>
+bool findBitInWord(T word, size_t& startOrResultIndex, size_t endIndex, bool value)
 {
     static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
-    
+
+    constexpr size_t bitsInWord = sizeof(word) * 8;
+    ASSERT_UNUSED(bitsInWord, startOrResultIndex <= bitsInWord && endIndex <= bitsInWord);
+
+    size_t index = startOrResultIndex;
     word >>= index;
-    
+
+#if COMPILER(GCC_COMPATIBLE) && (CPU(X86_64) || CPU(ARM64))
+    // We should only use ctz() when we know that ctz() is implementated using
+    // a fast hardware instruction. Otherwise, this will actually result in
+    // worse performance.
+
+    word ^= (static_cast<T>(value) - 1);
+    index += ctz(word);
+    if (index < endIndex) {
+        startOrResultIndex = index;
+        return true;
+    }
+#else
     while (index < endIndex) {
-        if ((word & 1) == static_cast<T>(value))
+        if ((word & 1) == static_cast<T>(value)) {
+            startOrResultIndex = index;
             return true;
+        }
         index++;
         word >>= 1;
     }
-    
-    index = endIndex;
+#endif
+
+    startOrResultIndex = endIndex;
     return false;
 }
 
index 181c5d1..595125b 100644 (file)
@@ -1,3 +1,17 @@
+2020-05-18  Mark Lam  <mark.lam@apple.com>
+
+        Implement a faster findBitInWord() using the hardware ctz instruction.
+        https://bugs.webkit.org/show_bug.cgi?id=212032
+        <rdar://problem/63348086>
+
+        Reviewed by Saam Barati.
+
+        Apply same changes to bmalloc's copy of findBitInWord().
+
+        * bmalloc/Algorithm.h:
+        (bmalloc::ctz):
+        (bmalloc::findBitInWord):
+
 2020-05-13  Yusuke Suzuki  <ysuzuki@apple.com>
 
         [bmalloc] Introduce lock-less ObjectType query
index 5128ae8..a5f4562 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2020 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -176,24 +176,6 @@ constexpr unsigned long log2(unsigned long value)
 
 #define BOFFSETOF(class, field) (reinterpret_cast<ptrdiff_t>(&(reinterpret_cast<class*>(0x4000)->field)) - 0x4000)
 
-template<typename T>
-bool findBitInWord(T word, size_t& index, size_t endIndex, bool value)
-{
-    static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
-    
-    word >>= index;
-    
-    while (index < endIndex) {
-        if ((word & 1) == static_cast<T>(value))
-            return true;
-        index++;
-        word >>= 1;
-    }
-    
-    index = endIndex;
-    return false;
-}
-
 template <typename T>
 constexpr unsigned ctzConstexpr(T value)
 {
@@ -214,6 +196,67 @@ constexpr unsigned ctzConstexpr(T value)
 }
 
 template<typename T>
+inline unsigned ctz(T value)
+{
+    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
+
+    using UT = typename std::make_unsigned<T>::type;
+    UT uValue = value;
+
+#if BCOMPILER(GCC_COMPATIBLE)
+    if (uValue)
+        return __builtin_ctzll(uValue);
+    return bitSize;
+#elif BCOMPILER(MSVC) && !BCPU(X86)
+    unsigned long ret = 0;
+    if (_BitScanForward64(&ret, uValue))
+        return ret;
+    return bitSize;
+#else
+    UNUSED_PARAM(bitSize);
+    UNUSED_PARAM(uValue);
+    return ctzConstexpr(value);
+#endif
+}
+
+template<typename T>
+bool findBitInWord(T word, size_t& startOrResultIndex, size_t endIndex, bool value)
+{
+    static_assert(std::is_unsigned<T>::value, "Type used in findBitInWord must be unsigned");
+    constexpr size_t bitsInWord = sizeof(word) * 8;
+    BASSERT(startOrResultIndex <= bitsInWord && endIndex <= bitsInWord);
+    BUNUSED(bitsInWord);
+    
+    size_t index = startOrResultIndex;
+    word >>= index;
+
+#if BCOMPILER(GCC_COMPATIBLE) && (BCPU(X86_64) || BCPU(ARM64))
+    // We should only use ctz() when we know that ctz() is implementated using
+    // a fast hardware instruction. Otherwise, this will actually result in
+    // worse performance.
+
+    word ^= (static_cast<T>(value) - 1);
+    index += ctz(word);
+    if (index < endIndex) {
+        startOrResultIndex = index;
+        return true;
+    }
+#else
+    while (index < endIndex) {
+        if ((word & 1) == static_cast<T>(value)) {
+            startOrResultIndex = index;
+            return true;
+        }
+        index++;
+        word >>= 1;
+    }
+#endif
+
+    startOrResultIndex = endIndex;
+    return false;
+}
+
+template<typename T>
 constexpr unsigned getLSBSetNonZeroConstexpr(T t)
 {
     return ctzConstexpr(t);
index 530cffa..fe750f7 100644 (file)
@@ -1,3 +1,20 @@
+2020-05-18  Mark Lam  <mark.lam@apple.com>
+
+        Implement a faster findBitInWord() using the hardware ctz instruction.
+        https://bugs.webkit.org/show_bug.cgi?id=212032
+        <rdar://problem/63348086>
+
+        Reviewed by Saam Barati.
+
+        Add tests to make sure that the ctz implementation matches the loop implementation
+        in behavior.
+
+        * TestWebKitAPI/CMakeLists.txt:
+        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+        * TestWebKitAPI/Tests/WTF/StdLibExtras.cpp: Added.
+        (TestWebKitAPI::testFindBitInWord):
+        (TestWebKitAPI::TEST):
+
 2020-05-18  Wenson Hsieh  <wenson_hsieh@apple.com>
 
         Allow clipboard API access when pasting from a menu item or key binding
index c122664..a8a52a0 100644 (file)
@@ -83,6 +83,7 @@ set(TestWTF_SOURCES
     Tests/WTF/Scope.cpp
     Tests/WTF/ScopedLambda.cpp
     Tests/WTF/SetForScope.cpp
+    Tests/WTF/StdLibExtras.cpp
     Tests/WTF/StringBuilder.cpp
     Tests/WTF/StringConcatenate.cpp
     Tests/WTF/StringHasher.cpp
index d54b7d9..b7d0a13 100644 (file)
                F6B7BE9717469B96008A3445 /* associate-form-controls.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = F6B7BE9617469B7E008A3445 /* associate-form-controls.html */; };
                F6F49C6B15545CA70007F39D /* DOMWindowExtensionNoCache_Bundle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F6F49C6615545C8D0007F39D /* DOMWindowExtensionNoCache_Bundle.cpp */; };
                F6FDDDD614241C6F004F1729 /* push-state.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = F6FDDDD514241C48004F1729 /* push-state.html */; };
+               FE2BCDC72470FDA300DEC33B /* StdLibExtras.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE2BCDC62470FC7000DEC33B /* StdLibExtras.cpp */; };
                FE2D9474245EB2F400E48135 /* Bitmap.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE2D9473245EB2DF00E48135 /* Bitmap.cpp */; };
 /* End PBXBuildFile section */
 
                F6F49C6715545C8D0007F39D /* DOMWindowExtensionNoCache.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DOMWindowExtensionNoCache.cpp; sourceTree = "<group>"; };
                F6FDDDD214241AD4004F1729 /* PrivateBrowsingPushStateNoHistoryCallback.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PrivateBrowsingPushStateNoHistoryCallback.cpp; sourceTree = "<group>"; };
                F6FDDDD514241C48004F1729 /* push-state.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "push-state.html"; sourceTree = "<group>"; };
+               FE2BCDC62470FC7000DEC33B /* StdLibExtras.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StdLibExtras.cpp; sourceTree = "<group>"; };
                FE2D9473245EB2DF00E48135 /* Bitmap.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Bitmap.cpp; sourceTree = "<group>"; };
                FEB6F74E1B2BA44E009E4922 /* NakedPtr.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NakedPtr.cpp; sourceTree = "<group>"; };
 /* End PBXFileReference section */
                                0BCD85691485C98B00EA2003 /* SetForScope.cpp */,
                                CD5393C91757BAC400C07123 /* SHA1.cpp */,
                                E3953F951F2CF32100A76A2E /* Signals.cpp */,
+                               FE2BCDC62470FC7000DEC33B /* StdLibExtras.cpp */,
                                81B50192140F232300D9EB58 /* StringBuilder.cpp */,
                                7CD4C26C1E2C0E6E00929470 /* StringConcatenate.cpp */,
                                93ABA80816DDAB91002DB2FA /* StringHasher.cpp */,
                                7C83DED41D0A590C00FEBCF3 /* HashSet.cpp in Sources */,
                                7C8BFF7123C0107A00C009B3 /* HexNumber.cpp in Sources */,
                                7C83DEE01D0A590C00FEBCF3 /* IntegerToStringConversion.cpp in Sources */,
+                               FE2BCDC72470FDA300DEC33B /* StdLibExtras.cpp in Sources */,
                                53FCDE6B229EFFB900598ECF /* IsoHeap.cpp in Sources */,
                                7CEB62AB223609DE0069CBB0 /* IteratorRange.cpp in Sources */,
                                7A0509411FB9F06400B33FB8 /* JSONValue.cpp in Sources */,
diff --git a/Tools/TestWebKitAPI/Tests/WTF/StdLibExtras.cpp b/Tools/TestWebKitAPI/Tests/WTF/StdLibExtras.cpp
new file mode 100644 (file)
index 0000000..d33f701
--- /dev/null
@@ -0,0 +1,114 @@
+/*
+ * Copyright (C) 2020 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include <wtf/StdLibExtras.h>
+
+#include <wtf/MathExtras.h>
+#include <wtf/RandomNumber.h>
+
+namespace TestWebKitAPI {
+
+template<typename WordType>
+void testFindBitInWord()
+{
+    constexpr size_t bitsInWord = sizeof(WordType) * 8;
+    constexpr size_t numberOfShiftValues = bitsInWord + 1;
+    constexpr size_t testPermutationsPerShift = 100;
+
+    constexpr size_t numberOfTestValues = numberOfShiftValues * testPermutationsPerShift;
+    uint8_t startIndex[numberOfTestValues];
+    uint8_t endIndex[numberOfTestValues];
+
+    auto initTestValues = [&] () {
+        // Set some internal and boundary cases.
+        uint8_t specialCases[] = {
+            0,
+            bitsInWord / 2,
+            bitsInWord - 1,
+            bitsInWord,
+        };
+
+        constexpr size_t numberOfSpecialCases = sizeof(specialCases) / sizeof(specialCases[0]);
+
+        size_t nextTestValue = 0;
+        for (size_t i = 0; i < numberOfSpecialCases; ++i) {
+            for (size_t j = 0; j < numberOfSpecialCases; ++j) {
+                startIndex[nextTestValue] = specialCases[i];
+                endIndex[nextTestValue++] = specialCases[j];
+            }
+        }
+
+        // Fill in some random cases.
+        for (size_t i = nextTestValue; i < numberOfTestValues; ++i) {
+            startIndex[i] = static_cast<uint8_t>(randomNumber() * bitsInWord);
+            uint8_t remainingBits = bitsInWord - startIndex[i];
+            endIndex[i] = static_cast<uint8_t>(randomNumber() * remainingBits) + startIndex[i];
+        }
+    };
+
+    auto expectedBitInWord = [] (WordType word, size_t& index, size_t endIndex, bool value) -> bool {
+        word >>= index;
+        while (index < endIndex) {
+            if ((word & 1) == static_cast<WordType>(value))
+                return true;
+            index++;
+            word >>= 1;
+        }
+        index = endIndex;
+        return false;
+    };
+
+    auto test = [&] (bool value, size_t shift) {
+        constexpr uint64_t baseWord = std::numeric_limits<uint64_t>::max();
+        uint64_t word = (shift < bitsInWord) ? baseWord << shift : 0;
+
+        for (size_t i = 0; i < numberOfTestValues; ++i) {
+            size_t index = startIndex[i];
+            bool result = findBitInWord(word, index, endIndex[i], value);
+
+            size_t expectedIndex = startIndex[i];
+            bool expectedResult = expectedBitInWord(word, expectedIndex, endIndex[i], value);
+
+            ASSERT_EQ(result, expectedResult);
+            ASSERT_EQ(index, expectedIndex);
+        }
+    };
+
+    initTestValues();
+
+    // Testing find a set bit.
+    for (size_t i = 0; i < numberOfShiftValues; ++i)
+        test(true, i);
+
+    // Testing find a cleared bit.
+    for (size_t i = 0; i < numberOfShiftValues; ++i)
+        test(false, i);
+}
+
+TEST(WTF_StdLibExtras, findBitInWord_uint32_t) { testFindBitInWord<uint32_t>(); }
+TEST(WTF_StdLibExtras, findBitInWord_uint64_t) { testFindBitInWord<uint64_t>(); }
+
+} // namespace TestWebKitAPI