<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[200438] trunk/Source/WTF</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/200438">200438</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-05-04 16:01:25 -0700 (Wed, 04 May 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>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.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFbenchmarksLockSpeedTestcpp">trunk/Source/WTF/benchmarks/LockSpeedTest.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFbenchmarksLockFairnessTestcpp">trunk/Source/WTF/benchmarks/LockFairnessTest.cpp</a></li>
<li><a href="#trunkSourceWTFbenchmarksToyLocksh">trunk/Source/WTF/benchmarks/ToyLocks.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (200437 => 200438)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,23 @@
</span><span class="cx"> 2016-05-04 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ 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 <fpizlo@apple.com>
+
</ins><span class="cx"> Speed up JSGlobalObject initialization by making some properties lazy
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=157045
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksLockFairnessTestcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/benchmarks/LockFairnessTest.cpp (0 => 200438)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/benchmarks/LockFairnessTest.cpp (rev 0)
+++ trunk/Source/WTF/benchmarks/LockFairnessTest.cpp 2016-05-04 23:01:25 UTC (rev 200438)
</span><span class="lines">@@ -0,0 +1,117 @@
</span><ins>+/*
+ * 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;
+}
</ins></span></pre></div>
<a id="trunkSourceWTFbenchmarksLockSpeedTestcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (200437 => 200438)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -24,10 +24,11 @@
</span><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> // On Mac, you can build this like so:
</span><del>-// clang++ -o LockSpeedTest Source/WTF/benchmarks/LockSpeedTest.cpp -O3 -W -ISource/WTF -LWebKitBuild/Release -lWTF -framework Foundation -licucore -std=c++11
</del><ins>+// 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
</ins><span class="cx">
</span><span class="cx"> #include "config.h"
</span><span class="cx">
</span><ins>+#include "ToyLocks.h"
</ins><span class="cx"> #include <thread>
</span><span class="cx"> #include <unistd.h>
</span><span class="cx"> #include <wtf/CurrentTime.h>
</span><span class="lines">@@ -48,358 +49,8 @@
</span><span class="cx"> unsigned numThreadsPerGroup;
</span><span class="cx"> unsigned workPerCriticalSection;
</span><span class="cx"> unsigned workBetweenCriticalSections;
</span><del>-unsigned spinLimit;
</del><span class="cx"> double secondsPerTest;
</span><span class="cx">
</span><del>-// 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;
-};
-
</del><span class="cx"> NO_RETURN void usage()
</span><span class="cx"> {
</span><span class="cx"> 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");
</span><span class="lines">@@ -420,64 +71,63 @@
</span><span class="cx"> results.add(name, Vector<double>()).iterator->value.append(value);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-bool didRun;
</del><ins>+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);
</ins><span class="cx">
</span><del>-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);
</del><ins>+ volatile bool keepGoing = true;
</ins><span class="cx">
</span><del>- volatile bool keepGoing = true;
-
- double before = monotonicallyIncreasingTime();
</del><ins>+ double before = monotonicallyIncreasingTime();
</ins><span class="cx">
</span><del>- Lock numIterationsLock;
- uint64_t numIterations = 0;
</del><ins>+ Lock numIterationsLock;
+ uint64_t numIterations = 0;
</ins><span class="cx">
</span><del>- for (unsigned threadGroupIndex = numThreadGroups; threadGroupIndex--;) {
- words[threadGroupIndex].value = 0;
</del><ins>+ for (unsigned threadGroupIndex = numThreadGroups; threadGroupIndex--;) {
+ words[threadGroupIndex].value = 0;
</ins><span class="cx">
</span><del>- 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;
</del><ins>+ 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++;
</ins><span class="cx"> }
</span><del>- locks[threadGroupIndex].value.unlock();
- for (unsigned j = workBetweenCriticalSections; j--;) {
- localWord += value;
- localWord *= 1.01;
- value = localWord;
- }
- myNumIterations++;
- }
- LockHolder locker(numIterationsLock);
- numIterations += myNumIterations;
- });
</del><ins>+ LockHolder locker(numIterationsLock);
+ numIterations += myNumIterations;
+ });
+ }
</ins><span class="cx"> }
</span><del>- }
</del><span class="cx">
</span><del>- sleep(secondsPerTest);
- keepGoing = false;
</del><ins>+ sleep(secondsPerTest);
+ keepGoing = false;
</ins><span class="cx">
</span><del>- for (unsigned threadIndex = numThreadGroups * numThreadsPerGroup; threadIndex--;)
- waitForThreadCompletion(threads[threadIndex]);
</del><ins>+ for (unsigned threadIndex = numThreadGroups * numThreadsPerGroup; threadIndex--;)
+ waitForThreadCompletion(threads[threadIndex]);
</ins><span class="cx">
</span><del>- double after = monotonicallyIncreasingTime();
</del><ins>+ double after = monotonicallyIncreasingTime();
</ins><span class="cx">
</span><del>- reportResult(name, numIterations / (after - before) / 1000);
- didRun = true;
-}
</del><ins>+ reportResult(name, numIterations / (after - before) / 1000);
+ }
+};
</ins><span class="cx">
</span><span class="cx"> unsigned rangeMin;
</span><span class="cx"> unsigned rangeMax;
</span><span class="lines">@@ -508,37 +158,6 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-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();
-}
-
</del><span class="cx"> } // anonymous namespace
</span><span class="cx">
</span><span class="cx"> int main(int argc, char** argv)
</span><span class="lines">@@ -550,7 +169,7 @@
</span><span class="cx"> || !parseValue(argv[3], &numThreadsPerGroup)
</span><span class="cx"> || !parseValue(argv[4], &workPerCriticalSection)
</span><span class="cx"> || !parseValue(argv[5], &workBetweenCriticalSections)
</span><del>- || !parseValue(argv[6], &spinLimit)
</del><ins>+ || !parseValue(argv[6], &toyLockSpinLimit)
</ins><span class="cx"> || sscanf(argv[7], "%lf", &secondsPerTest) != 1)
</span><span class="cx"> usage();
</span><span class="cx">
</span><span class="lines">@@ -559,10 +178,10 @@
</span><span class="cx"> for (unsigned value = rangeMin; value <= rangeMax; value += rangeStep) {
</span><span class="cx"> dataLog("Running with value = ", value, "\n");
</span><span class="cx"> *rangeVariable = value;
</span><del>- runEverything(argv[1]);
</del><ins>+ runEverything<Benchmark>(argv[1]);
</ins><span class="cx"> }
</span><span class="cx"> } else
</span><del>- runEverything(argv[1]);
</del><ins>+ runEverything<Benchmark>(argv[1]);
</ins><span class="cx">
</span><span class="cx"> for (auto& entry : results) {
</span><span class="cx"> printf("%s = {", entry.key.data());
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksToyLocksh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/benchmarks/ToyLocks.h (0 => 200438)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/benchmarks/ToyLocks.h (rev 0)
+++ trunk/Source/WTF/benchmarks/ToyLocks.h 2016-05-04 23:01:25 UTC (rev 200438)
</span><span class="lines">@@ -0,0 +1,420 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre>
</div>
</div>
</body>
</html>