Title: [200438] trunk/Source/WTF
Revision
200438
Author
[email protected]
Date
2016-05-04 16:01:25 -0700 (Wed, 04 May 2016)

Log Message

Add a few more WTF locking benchmarks
https://bugs.webkit.org/show_bug.cgi?id=157365

Rubber stamped by Benjamin Poulain.
        
Factors out our toy locks into ToyLocks.h and adds a new test (LockFairnessTest) that measures
the fairness of locks.
        
The result: WTF::Lock is pretty fair enough.

* benchmarks/LockFairnessTest.cpp: Added.
(main):
* benchmarks/LockSpeedTest.cpp:
(main):
* benchmarks/ToyLocks.h: Added.

Modified Paths

Added Paths

Diff

Modified: trunk/Source/WTF/ChangeLog (200437 => 200438)


--- trunk/Source/WTF/ChangeLog	2016-05-04 22:29:18 UTC (rev 200437)
+++ trunk/Source/WTF/ChangeLog	2016-05-04 23:01:25 UTC (rev 200438)
@@ -1,5 +1,23 @@
 2016-05-04  Filip Pizlo  <[email protected]>
 
+        Add a few more WTF locking benchmarks
+        https://bugs.webkit.org/show_bug.cgi?id=157365
+
+        Rubber stamped by Benjamin Poulain.
+        
+        Factors out our toy locks into ToyLocks.h and adds a new test (LockFairnessTest) that measures
+        the fairness of locks.
+        
+        The result: WTF::Lock is pretty fair enough.
+
+        * benchmarks/LockFairnessTest.cpp: Added.
+        (main):
+        * benchmarks/LockSpeedTest.cpp:
+        (main):
+        * benchmarks/ToyLocks.h: Added.
+
+2016-05-04  Filip Pizlo  <[email protected]>
+
         Speed up JSGlobalObject initialization by making some properties lazy
         https://bugs.webkit.org/show_bug.cgi?id=157045
 

Added: trunk/Source/WTF/benchmarks/LockFairnessTest.cpp (0 => 200438)


--- trunk/Source/WTF/benchmarks/LockFairnessTest.cpp	                        (rev 0)
+++ trunk/Source/WTF/benchmarks/LockFairnessTest.cpp	2016-05-04 23:01:25 UTC (rev 200438)
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2016 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. ``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
+ * 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. 
+ */
+
+// On Mac, you can build this like so:
+// xcrun clang++ -o LockFairnessTest Source/WTF/benchmarks/LockFairnessTest.cpp -O3 -W -ISource/WTF -ISource/WTF/benchmarks -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11 -fvisibility=hidden
+
+#include "config.h"
+
+#include "ToyLocks.h"
+#include <thread>
+#include <unistd.h>
+#include <wtf/CommaPrinter.h>
+#include <wtf/CurrentTime.h>
+#include <wtf/DataLog.h>
+#include <wtf/HashMap.h>
+#include <wtf/Lock.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+#include <wtf/Vector.h>
+#include <wtf/WordLock.h>
+#include <wtf/text/CString.h>
+
+namespace {
+
+NO_RETURN void usage()
+{
+    printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test>\n");
+    exit(1);
+}
+
+unsigned numThreads;
+double secondsPerTest;
+
+struct Benchmark {
+    template<typename LockType>
+    static void run(const char* name)
+    {
+        LockType lock;
+        std::unique_ptr<unsigned[]> counts = std::make_unique<unsigned[]>(numThreads);
+        std::unique_ptr<ThreadIdentifier[]> threads = std::make_unique<ThreadIdentifier[]>(numThreads);
+    
+        volatile bool keepGoing = true;
+    
+        lock.lock();
+    
+        for (unsigned threadIndex = numThreads; threadIndex--;) {
+            counts[threadIndex] = 0;
+            threads[threadIndex] = createThread(
+                "Benchmark Thread",
+                [&, threadIndex] () {
+                    while (keepGoing) {
+                        lock.lock();
+                        counts[threadIndex]++;
+                        lock.unlock();
+                    }
+                });
+        }
+    
+        sleepMS(100);
+        lock.unlock();
+    
+        sleep(secondsPerTest);
+    
+        lock.lock();
+        keepGoing = false;
+    
+        dataLog(name, ": ");
+        CommaPrinter comma;
+        for (unsigned threadIndex = numThreads; threadIndex--;)
+            dataLog(comma, counts[threadIndex]);
+        dataLog("\n");
+    
+        lock.unlock();
+        for (unsigned threadIndex = numThreads; threadIndex--;)
+            waitForThreadCompletion(threads[threadIndex]);
+    }
+};
+
+} // anonymous namespace
+
+int main(int argc, char** argv)
+{
+    WTF::initializeThreading();
+    
+    if (argc != 4
+        || sscanf(argv[2], "%u", &numThreads) != 1
+        || sscanf(argv[3], "%lf", &secondsPerTest) != 1)
+        usage();
+    
+    runEverything<Benchmark>(argv[1]);
+    
+    return 0;
+}

Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (200437 => 200438)


--- trunk/Source/WTF/benchmarks/LockSpeedTest.cpp	2016-05-04 22:29:18 UTC (rev 200437)
+++ trunk/Source/WTF/benchmarks/LockSpeedTest.cpp	2016-05-04 23:01:25 UTC (rev 200438)
@@ -24,10 +24,11 @@
  */
 
 // On Mac, you can build this like so:
-// clang++ -o LockSpeedTest Source/WTF/benchmarks/LockSpeedTest.cpp -O3 -W -ISource/WTF -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11
+// xcrun clang++ -o LockSpeedTest Source/WTF/benchmarks/LockSpeedTest.cpp -O3 -W -ISource/WTF -ISource/WTF/benchmarks -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11 -fvisibility=hidden
 
 #include "config.h"
 
+#include "ToyLocks.h"
 #include <thread>
 #include <unistd.h>
 #include <wtf/CurrentTime.h>
@@ -48,358 +49,8 @@
 unsigned numThreadsPerGroup;
 unsigned workPerCriticalSection;
 unsigned workBetweenCriticalSections;
-unsigned spinLimit;
 double secondsPerTest;
     
-// This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
-// spinlock baseline.
-class YieldSpinLock {
-public:
-    YieldSpinLock()
-    {
-        m_lock.store(0, std::memory_order_relaxed);
-    }
-
-    void lock()
-    {
-        while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
-            std::this_thread::yield();
-    }
-
-    void unlock()
-    {
-        m_lock.store(0, std::memory_order_release);
-    }
-
-    bool isLocked() const
-    {
-        return m_lock.load(std::memory_order_acquire);
-    }
-
-private:
-    Atomic<unsigned> m_lock;
-};
-
-class PauseSpinLock {
-public:
-    PauseSpinLock()
-    {
-        m_lock.store(0, std::memory_order_relaxed);
-    }
-
-    void lock()
-    {
-        while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
-            asm volatile ("pause");
-    }
-
-    void unlock()
-    {
-        m_lock.store(0, std::memory_order_release);
-    }
-
-    bool isLocked() const
-    {
-        return m_lock.load(std::memory_order_acquire);
-    }
-
-private:
-    Atomic<unsigned> m_lock;
-};
-
-template<typename StateType>
-class BargingLock {
-public:
-    BargingLock()
-    {
-        m_state.store(0);
-    }
-    
-    void lock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
-            return;
-        
-        lockSlow();
-    }
-    
-    void unlock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
-            return;
-        
-        unlockSlow();
-    }
-    
-    bool isLocked() const
-    {
-        return m_state.load(std::memory_order_acquire) & isLockedBit;
-    }
-    
-private:
-    NEVER_INLINE void lockSlow()
-    {
-        for (unsigned i = spinLimit; i--;) {
-            StateType currentState = m_state.load();
-            
-            if (!(currentState & isLockedBit)
-                && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
-                return;
-            
-            if (currentState & hasParkedBit)
-                break;
-            
-            std::this_thread::yield();
-        }
-        
-        for (;;) {
-            StateType currentState = m_state.load();
-            
-            if (!(currentState & isLockedBit)
-                && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
-                return;
-            
-            m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
-            
-            ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
-        }
-    }
-    
-    NEVER_INLINE void unlockSlow()
-    {
-        ParkingLot::unparkOne(
-            &m_state,
-            [this] (ParkingLot::UnparkResult result) {
-                if (result.mayHaveMoreThreads)
-                    m_state.store(hasParkedBit);
-                else
-                    m_state.store(0);
-            });
-    }
-    
-    static const StateType isLockedBit = 1;
-    static const StateType hasParkedBit = 2;
-    
-    Atomic<StateType> m_state;
-};
-
-template<typename StateType>
-class ThunderLock {
-public:
-    ThunderLock()
-    {
-        m_state.store(Unlocked);
-    }
-    
-    void lock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
-            return;
-        
-        lockSlow();
-    }
-    
-    void unlock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
-            return;
-        
-        unlockSlow();
-    }
-    
-    bool isLocked() const
-    {
-        return m_state.load(std::memory_order_acquire) != Unlocked;
-    }
-    
-private:
-    NEVER_INLINE void lockSlow()
-    {
-        for (unsigned i = spinLimit; i--;) {
-            State currentState = m_state.load();
-            
-            if (currentState == Unlocked
-                && m_state.compareExchangeWeak(Unlocked, Locked))
-                return;
-            
-            if (currentState == LockedAndParked)
-                break;
-            
-            std::this_thread::yield();
-        }
-        
-        for (;;) {
-            if (m_state.compareExchangeWeak(Unlocked, Locked))
-                return;
-            
-            m_state.compareExchangeWeak(Locked, LockedAndParked);
-            ParkingLot::compareAndPark(&m_state, LockedAndParked);
-        }
-    }
-    
-    NEVER_INLINE void unlockSlow()
-    {
-        if (m_state.exchange(Unlocked) == LockedAndParked)
-            ParkingLot::unparkAll(&m_state);
-    }
-    
-    enum State : StateType {
-        Unlocked,
-        Locked,
-        LockedAndParked
-    };
-    
-    Atomic<State> m_state;
-};
-
-template<typename StateType>
-class CascadeLock {
-public:
-    CascadeLock()
-    {
-        m_state.store(Unlocked);
-    }
-    
-    void lock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
-            return;
-        
-        lockSlow();
-    }
-    
-    void unlock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
-            return;
-        
-        unlockSlow();
-    }
-    
-    bool isLocked() const
-    {
-        return m_state.load(std::memory_order_acquire) != Unlocked;
-    }
-    
-private:
-    NEVER_INLINE void lockSlow()
-    {
-        for (unsigned i = spinLimit; i--;) {
-            State currentState = m_state.load();
-            
-            if (currentState == Unlocked
-                && m_state.compareExchangeWeak(Unlocked, Locked))
-                return;
-            
-            if (currentState == LockedAndParked)
-                break;
-            
-            std::this_thread::yield();
-        }
-        
-        State desiredState = Locked;
-        for (;;) {
-            if (m_state.compareExchangeWeak(Unlocked, desiredState))
-                return;
-            
-            desiredState = LockedAndParked;
-            m_state.compareExchangeWeak(Locked, LockedAndParked);
-            ParkingLot::compareAndPark(&m_state, LockedAndParked);
-        }
-    }
-    
-    NEVER_INLINE void unlockSlow()
-    {
-        if (m_state.exchange(Unlocked) == LockedAndParked)
-            ParkingLot::unparkOne(&m_state);
-    }
-    
-    enum State : StateType {
-        Unlocked,
-        Locked,
-        LockedAndParked
-    };
-    
-    Atomic<State> m_state;
-};
-
-class HandoffLock {
-public:
-    HandoffLock()
-    {
-        m_state.store(0);
-    }
-    
-    void lock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
-            return;
-
-        lockSlow();
-    }
-
-    void unlock()
-    {
-        if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
-            return;
-
-        unlockSlow();
-    }
-
-    bool isLocked() const
-    {
-        return m_state.load(std::memory_order_acquire) & isLockedBit;
-    }
-    
-private:
-    NEVER_INLINE void lockSlow()
-    {
-        for (;;) {
-            unsigned state = m_state.load();
-            
-            if (!(state & isLockedBit)) {
-                if (m_state.compareExchangeWeak(state, state | isLockedBit))
-                    return;
-                continue;
-            }
-            
-            if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
-                bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit);
-                m_state.exchangeAndAdd(-parkedCountUnit);
-                if (result)
-                    return;
-            }
-        }
-    }
-    
-    NEVER_INLINE void unlockSlow()
-    {
-        for (;;) {
-            unsigned state = m_state.load();
-            
-            if (!(state >> parkedCountShift)) {
-                RELEASE_ASSERT(state == isLockedBit);
-                if (m_state.compareExchangeWeak(isLockedBit, 0))
-                    return;
-                continue;
-            }
-            
-            if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
-                // We unparked someone. There are now running and they hold the lock.
-                return;
-            }
-            
-            // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
-        }
-    }
-    
-    static const unsigned isLockedBit = 1;
-    static const unsigned parkedCountShift = 1;
-    static const unsigned parkedCountUnit = 1 << parkedCountShift;
-    
-    Atomic<unsigned> m_state;
-};
-
 NO_RETURN void usage()
 {
     printf("Usage: LockSpeedTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num thread groups> <num threads per group> <work per critical section> <work between critical sections> <spin limit> <seconds per test>\n");
@@ -420,64 +71,63 @@
     results.add(name, Vector<double>()).iterator->value.append(value);
 }
 
-bool didRun;
+struct Benchmark {
+    template<typename LockType>
+    static void run(const char* name)
+    {
+        std::unique_ptr<WithPadding<LockType>[]> locks = std::make_unique<WithPadding<LockType>[]>(numThreadGroups);
+        std::unique_ptr<WithPadding<double>[]> words = std::make_unique<WithPadding<double>[]>(numThreadGroups);
+        std::unique_ptr<ThreadIdentifier[]> threads = std::make_unique<ThreadIdentifier[]>(numThreadGroups * numThreadsPerGroup);
 
-template<typename LockType>
-void runBenchmark(const char* name)
-{
-    std::unique_ptr<WithPadding<LockType>[]> locks = std::make_unique<WithPadding<LockType>[]>(numThreadGroups);
-    std::unique_ptr<WithPadding<double>[]> words = std::make_unique<WithPadding<double>[]>(numThreadGroups);
-    std::unique_ptr<ThreadIdentifier[]> threads = std::make_unique<ThreadIdentifier[]>(numThreadGroups * numThreadsPerGroup);
+        volatile bool keepGoing = true;
 
-    volatile bool keepGoing = true;
-
-    double before = monotonicallyIncreasingTime();
+        double before = monotonicallyIncreasingTime();
     
-    Lock numIterationsLock;
-    uint64_t numIterations = 0;
+        Lock numIterationsLock;
+        uint64_t numIterations = 0;
     
-    for (unsigned threadGroupIndex = numThreadGroups; threadGroupIndex--;) {
-        words[threadGroupIndex].value = 0;
+        for (unsigned threadGroupIndex = numThreadGroups; threadGroupIndex--;) {
+            words[threadGroupIndex].value = 0;
 
-        for (unsigned threadIndex = numThreadsPerGroup; threadIndex--;) {
-            threads[threadGroupIndex * numThreadsPerGroup + threadIndex] = createThread(
-                "Benchmark thread",
-                [threadGroupIndex, &locks, &words, &keepGoing, &numIterationsLock, &numIterations] () {
-                    double localWord = 0;
-                    double value = 1;
-                    unsigned myNumIterations = 0;
-                    while (keepGoing) {
-                        locks[threadGroupIndex].value.lock();
-                        for (unsigned j = workPerCriticalSection; j--;) {
-                            words[threadGroupIndex].value += value;
-                            words[threadGroupIndex].value *= 1.01;
-                            value = words[threadGroupIndex].value;
+            for (unsigned threadIndex = numThreadsPerGroup; threadIndex--;) {
+                threads[threadGroupIndex * numThreadsPerGroup + threadIndex] = createThread(
+                    "Benchmark thread",
+                    [threadGroupIndex, &locks, &words, &keepGoing, &numIterationsLock, &numIterations] () {
+                        double localWord = 0;
+                        double value = 1;
+                        unsigned myNumIterations = 0;
+                        while (keepGoing) {
+                            locks[threadGroupIndex].value.lock();
+                            for (unsigned j = workPerCriticalSection; j--;) {
+                                words[threadGroupIndex].value += value;
+                                words[threadGroupIndex].value *= 1.01;
+                                value = words[threadGroupIndex].value;
+                            }
+                            locks[threadGroupIndex].value.unlock();
+                            for (unsigned j = workBetweenCriticalSections; j--;) {
+                                localWord += value;
+                                localWord *= 1.01;
+                                value = localWord;
+                            }
+                            myNumIterations++;
                         }
-                        locks[threadGroupIndex].value.unlock();
-                        for (unsigned j = workBetweenCriticalSections; j--;) {
-                            localWord += value;
-                            localWord *= 1.01;
-                            value = localWord;
-                        }
-                        myNumIterations++;
-                    }
-                    LockHolder locker(numIterationsLock);
-                    numIterations += myNumIterations;
-                });
+                        LockHolder locker(numIterationsLock);
+                        numIterations += myNumIterations;
+                    });
+            }
         }
-    }
 
-    sleep(secondsPerTest);
-    keepGoing = false;
+        sleep(secondsPerTest);
+        keepGoing = false;
     
-    for (unsigned threadIndex = numThreadGroups * numThreadsPerGroup; threadIndex--;)
-        waitForThreadCompletion(threads[threadIndex]);
+        for (unsigned threadIndex = numThreadGroups * numThreadsPerGroup; threadIndex--;)
+            waitForThreadCompletion(threads[threadIndex]);
 
-    double after = monotonicallyIncreasingTime();
+        double after = monotonicallyIncreasingTime();
     
-    reportResult(name, numIterations / (after - before) / 1000);
-    didRun = true;
-}
+        reportResult(name, numIterations / (after - before) / 1000);
+    }
+};
 
 unsigned rangeMin;
 unsigned rangeMax;
@@ -508,37 +158,6 @@
     return false;
 }
 
-void runEverything(const char* what)
-{
-    if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
-        runBenchmark<YieldSpinLock>("YieldSpinLock");
-    if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
-        runBenchmark<PauseSpinLock>("PauseSpinLock");
-    if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
-        runBenchmark<WordLock>("WTFWordLock");
-    if (!strcmp(what, "lock") || !strcmp(what, "all"))
-        runBenchmark<Lock>("WTFLock");
-    if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
-        runBenchmark<BargingLock<uint8_t>>("ByteBargingLock");
-    if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
-        runBenchmark<BargingLock<uint32_t>>("WordBargingLock");
-    if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
-        runBenchmark<ThunderLock<uint8_t>>("ByteThunderLock");
-    if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
-        runBenchmark<ThunderLock<uint32_t>>("WordThunderLock");
-    if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
-        runBenchmark<CascadeLock<uint8_t>>("ByteCascadeLock");
-    if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
-        runBenchmark<CascadeLock<uint32_t>>("WordCascadeLock");
-    if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
-        runBenchmark<HandoffLock>("HandoffLock");
-    if (!strcmp(what, "mutex") || !strcmp(what, "all"))
-        runBenchmark<Mutex>("PlatformMutex");
-
-    if (!didRun)
-        usage();
-}
-
 } // anonymous namespace
 
 int main(int argc, char** argv)
@@ -550,7 +169,7 @@
         || !parseValue(argv[3], &numThreadsPerGroup)
         || !parseValue(argv[4], &workPerCriticalSection)
         || !parseValue(argv[5], &workBetweenCriticalSections)
-        || !parseValue(argv[6], &spinLimit)
+        || !parseValue(argv[6], &toyLockSpinLimit)
         || sscanf(argv[7], "%lf", &secondsPerTest) != 1)
         usage();
     
@@ -559,10 +178,10 @@
         for (unsigned value = rangeMin; value <= rangeMax; value += rangeStep) {
             dataLog("Running with value = ", value, "\n");
             *rangeVariable = value;
-            runEverything(argv[1]);
+            runEverything<Benchmark>(argv[1]);
         }
     } else
-        runEverything(argv[1]);
+        runEverything<Benchmark>(argv[1]);
     
     for (auto& entry : results) {
         printf("%s = {", entry.key.data());

Added: trunk/Source/WTF/benchmarks/ToyLocks.h (0 => 200438)


--- trunk/Source/WTF/benchmarks/ToyLocks.h	                        (rev 0)
+++ trunk/Source/WTF/benchmarks/ToyLocks.h	2016-05-04 23:01:25 UTC (rev 200438)
@@ -0,0 +1,420 @@
+/*
+ * Copyright (C) 2015-2016 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. ``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
+ * 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. 
+ */
+
+#ifndef ToyLocks_h
+#define ToyLocks_h
+
+#include <thread>
+#include <wtf/Atomics.h>
+#include <wtf/Lock.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/WordLock.h>
+
+namespace {
+
+unsigned toyLockSpinLimit = 40;
+
+// This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
+// spinlock baseline.
+class YieldSpinLock {
+public:
+    YieldSpinLock()
+    {
+        m_lock.store(0, std::memory_order_relaxed);
+    }
+
+    void lock()
+    {
+        while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
+            std::this_thread::yield();
+    }
+
+    void unlock()
+    {
+        m_lock.store(0, std::memory_order_release);
+    }
+
+    bool isLocked() const
+    {
+        return m_lock.load(std::memory_order_acquire);
+    }
+
+private:
+    Atomic<unsigned> m_lock;
+};
+
+class PauseSpinLock {
+public:
+    PauseSpinLock()
+    {
+        m_lock.store(0, std::memory_order_relaxed);
+    }
+
+    void lock()
+    {
+        while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
+            asm volatile ("pause");
+    }
+
+    void unlock()
+    {
+        m_lock.store(0, std::memory_order_release);
+    }
+
+    bool isLocked() const
+    {
+        return m_lock.load(std::memory_order_acquire);
+    }
+
+private:
+    Atomic<unsigned> m_lock;
+};
+
+template<typename StateType>
+class BargingLock {
+public:
+    BargingLock()
+    {
+        m_state.store(0);
+    }
+    
+    void lock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
+            return;
+        
+        lockSlow();
+    }
+    
+    void unlock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
+            return;
+        
+        unlockSlow();
+    }
+    
+    bool isLocked() const
+    {
+        return m_state.load(std::memory_order_acquire) & isLockedBit;
+    }
+    
+private:
+    NEVER_INLINE void lockSlow()
+    {
+        for (unsigned i = toyLockSpinLimit; i--;) {
+            StateType currentState = m_state.load();
+            
+            if (!(currentState & isLockedBit)
+                && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
+                return;
+            
+            if (currentState & hasParkedBit)
+                break;
+            
+            std::this_thread::yield();
+        }
+        
+        for (;;) {
+            StateType currentState = m_state.load();
+            
+            if (!(currentState & isLockedBit)
+                && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
+                return;
+            
+            m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
+            
+            ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
+        }
+    }
+    
+    NEVER_INLINE void unlockSlow()
+    {
+        ParkingLot::unparkOne(
+            &m_state,
+            [this] (ParkingLot::UnparkResult result) {
+                if (result.mayHaveMoreThreads)
+                    m_state.store(hasParkedBit);
+                else
+                    m_state.store(0);
+            });
+    }
+    
+    static const StateType isLockedBit = 1;
+    static const StateType hasParkedBit = 2;
+    
+    Atomic<StateType> m_state;
+};
+
+template<typename StateType>
+class ThunderLock {
+public:
+    ThunderLock()
+    {
+        m_state.store(Unlocked);
+    }
+    
+    void lock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
+            return;
+        
+        lockSlow();
+    }
+    
+    void unlock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
+            return;
+        
+        unlockSlow();
+    }
+    
+    bool isLocked() const
+    {
+        return m_state.load(std::memory_order_acquire) != Unlocked;
+    }
+    
+private:
+    NEVER_INLINE void lockSlow()
+    {
+        for (unsigned i = toyLockSpinLimit; i--;) {
+            State currentState = m_state.load();
+            
+            if (currentState == Unlocked
+                && m_state.compareExchangeWeak(Unlocked, Locked))
+                return;
+            
+            if (currentState == LockedAndParked)
+                break;
+            
+            std::this_thread::yield();
+        }
+        
+        for (;;) {
+            if (m_state.compareExchangeWeak(Unlocked, Locked))
+                return;
+            
+            m_state.compareExchangeWeak(Locked, LockedAndParked);
+            ParkingLot::compareAndPark(&m_state, LockedAndParked);
+        }
+    }
+    
+    NEVER_INLINE void unlockSlow()
+    {
+        if (m_state.exchange(Unlocked) == LockedAndParked)
+            ParkingLot::unparkAll(&m_state);
+    }
+    
+    enum State : StateType {
+        Unlocked,
+        Locked,
+        LockedAndParked
+    };
+    
+    Atomic<State> m_state;
+};
+
+template<typename StateType>
+class CascadeLock {
+public:
+    CascadeLock()
+    {
+        m_state.store(Unlocked);
+    }
+    
+    void lock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
+            return;
+        
+        lockSlow();
+    }
+    
+    void unlock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
+            return;
+        
+        unlockSlow();
+    }
+    
+    bool isLocked() const
+    {
+        return m_state.load(std::memory_order_acquire) != Unlocked;
+    }
+    
+private:
+    NEVER_INLINE void lockSlow()
+    {
+        for (unsigned i = toyLockSpinLimit; i--;) {
+            State currentState = m_state.load();
+            
+            if (currentState == Unlocked
+                && m_state.compareExchangeWeak(Unlocked, Locked))
+                return;
+            
+            if (currentState == LockedAndParked)
+                break;
+            
+            std::this_thread::yield();
+        }
+        
+        State desiredState = Locked;
+        for (;;) {
+            if (m_state.compareExchangeWeak(Unlocked, desiredState))
+                return;
+            
+            desiredState = LockedAndParked;
+            m_state.compareExchangeWeak(Locked, LockedAndParked);
+            ParkingLot::compareAndPark(&m_state, LockedAndParked);
+        }
+    }
+    
+    NEVER_INLINE void unlockSlow()
+    {
+        if (m_state.exchange(Unlocked) == LockedAndParked)
+            ParkingLot::unparkOne(&m_state);
+    }
+    
+    enum State : StateType {
+        Unlocked,
+        Locked,
+        LockedAndParked
+    };
+    
+    Atomic<State> m_state;
+};
+
+class HandoffLock {
+public:
+    HandoffLock()
+    {
+        m_state.store(0);
+    }
+    
+    void lock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
+            return;
+
+        lockSlow();
+    }
+
+    void unlock()
+    {
+        if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
+            return;
+
+        unlockSlow();
+    }
+
+    bool isLocked() const
+    {
+        return m_state.load(std::memory_order_acquire) & isLockedBit;
+    }
+    
+private:
+    NEVER_INLINE void lockSlow()
+    {
+        for (;;) {
+            unsigned state = m_state.load();
+            
+            if (!(state & isLockedBit)) {
+                if (m_state.compareExchangeWeak(state, state | isLockedBit))
+                    return;
+                continue;
+            }
+            
+            if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
+                bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit);
+                m_state.exchangeAndAdd(-parkedCountUnit);
+                if (result)
+                    return;
+            }
+        }
+    }
+    
+    NEVER_INLINE void unlockSlow()
+    {
+        for (;;) {
+            unsigned state = m_state.load();
+            
+            if (!(state >> parkedCountShift)) {
+                RELEASE_ASSERT(state == isLockedBit);
+                if (m_state.compareExchangeWeak(isLockedBit, 0))
+                    return;
+                continue;
+            }
+            
+            if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
+                // We unparked someone. There are now running and they hold the lock.
+                return;
+            }
+            
+            // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
+        }
+    }
+    
+    static const unsigned isLockedBit = 1;
+    static const unsigned parkedCountShift = 1;
+    static const unsigned parkedCountUnit = 1 << parkedCountShift;
+    
+    Atomic<unsigned> m_state;
+};
+
+template<typename Benchmark>
+void runEverything(const char* what)
+{
+    if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
+        Benchmark::template run<YieldSpinLock>("YieldSpinLock");
+    if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
+        Benchmark::template run<PauseSpinLock>("PauseSpinLock");
+    if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
+        Benchmark::template run<WordLock>("WTFWordLock");
+    if (!strcmp(what, "lock") || !strcmp(what, "all"))
+        Benchmark::template run<Lock>("WTFLock");
+    if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
+        Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
+    if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
+        Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
+    if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
+        Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
+    if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
+        Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
+    if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
+        Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
+    if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
+        Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
+    if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
+        Benchmark::template run<HandoffLock>("HandoffLock");
+    if (!strcmp(what, "mutex") || !strcmp(what, "all"))
+        Benchmark::template run<Mutex>("PlatformMutex");
+}
+
+} // anonymous namespace
+
+#endif // ToyLocks_h
+
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to