From a09deddad8c64f9663fdfccbab67a43cf214543f Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Fri, 26 Jan 2018 10:50:44 -0800 Subject: [PATCH] Reorgs added benchmarks (put them in misc folder) --- cds/misc/RigtorpMPMCQueue.h | 221 ++++++++++++++++++ cds/{sync => misc}/backoff.h | 0 cds/{sync => misc}/barrier.h | 0 cds/{container => misc}/chase-lev-deque.h | 2 +- cds/{sync => misc}/mcs-lock.h | 0 cds/{sync => misc}/rwlock.h | 0 cds/{sync => misc}/seqlock.h | 0 cds/{sync => misc}/ticket_lock.h | 0 test/stress/misc/barrier_driver.cpp | 2 +- test/stress/misc/deque_driver.cpp | 2 +- test/stress/misc/mcslock_driver.cpp | 2 +- test/stress/misc/rwlock_driver.cpp | 2 +- test/stress/misc/seqlock_driver.cpp | 2 +- test/stress/misc/spinlock_driver.cpp | 2 +- .../sequential/sequential-misc/CMakeLists.txt | 3 +- .../sequential-misc/deque_driver.cpp | 2 +- .../sequential-misc/mcslock_driver.cpp | 2 +- .../sequential-misc/rigtorp_mpmc_driver.cpp | 61 +++++ .../sequential-misc/rwlock_driver.cpp | 2 +- .../sequential-misc/seqlock_driver.cpp | 2 +- .../sequential-misc/spinlock_driver.cpp | 2 +- 21 files changed, 296 insertions(+), 13 deletions(-) create mode 100644 cds/misc/RigtorpMPMCQueue.h rename cds/{sync => misc}/backoff.h (100%) rename cds/{sync => misc}/barrier.h (100%) rename cds/{container => misc}/chase-lev-deque.h (99%) rename cds/{sync => misc}/mcs-lock.h (100%) rename cds/{sync => misc}/rwlock.h (100%) rename cds/{sync => misc}/seqlock.h (100%) rename cds/{sync => misc}/ticket_lock.h (100%) create mode 100644 test/stress/sequential/sequential-misc/rigtorp_mpmc_driver.cpp diff --git a/cds/misc/RigtorpMPMCQueue.h b/cds/misc/RigtorpMPMCQueue.h new file mode 100644 index 00000000..5f56c4b7 --- /dev/null +++ b/cds/misc/RigtorpMPMCQueue.h @@ -0,0 +1,221 @@ +/* +Copyright (c) 2017 Erik Rigtorp + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. + */ + +#pragma once + +#include +#include +#include +#include +#include + +namespace rigtorp { + +template class MPMCQueue { +private: + static_assert(std::is_nothrow_copy_assignable::value || + std::is_nothrow_move_assignable::value, + "T must be nothrow copy or move assignable"); + + static_assert(std::is_nothrow_destructible::value, + "T must be nothrow destructible"); + +public: + explicit MPMCQueue(const size_t capacity) + : capacity_(capacity), head_(0), tail_(0) { + if (capacity_ < 1) { + throw std::invalid_argument("capacity < 1"); + } + size_t space = capacity * sizeof(Slot) + kCacheLineSize - 1; + buf_ = malloc(space); + if (buf_ == nullptr) { + throw std::bad_alloc(); + } + void *buf = buf_; + slots_ = reinterpret_cast( + std::align(kCacheLineSize, capacity * sizeof(Slot), buf, space)); + if (slots_ == nullptr) { + free(buf_); + throw std::bad_alloc(); + } + for (size_t i = 0; i < capacity_; ++i) { + new (&slots_[i]) Slot(); + } + static_assert(sizeof(MPMCQueue) % kCacheLineSize == 0, + "MPMCQueue size must be a multiple of cache line size to " + "prevent false sharing between adjacent queues"); + static_assert(sizeof(Slot) % kCacheLineSize == 0, + "Slot size must be a multiple of cache line size to prevent " + "false sharing between adjacent slots"); + assert(reinterpret_cast(slots_) % kCacheLineSize == 0 && + "slots_ array must be aligned to cache line size to prevent false " + "sharing between adjacent slots"); + assert(reinterpret_cast(&tail_) - + reinterpret_cast(&head_) >= + kCacheLineSize && + "head and tail must be a cache line apart to prevent false sharing"); + } + + ~MPMCQueue() noexcept { + for (size_t i = 0; i < capacity_; ++i) { + slots_[i].~Slot(); + } + free(buf_); + } + + // non-copyable and non-movable + MPMCQueue(const MPMCQueue &) = delete; + MPMCQueue &operator=(const MPMCQueue &) = delete; + + template void emplace(Args &&... args) noexcept { + static_assert(std::is_nothrow_constructible::value, + "T must be nothrow constructible with Args&&..."); + auto const head = head_.fetch_add(1); + auto &slot = slots_[idx(head)]; + while (turn(head) * 2 != slot.turn.load(std::memory_order_acquire)) + ; + slot.construct(std::forward(args)...); + slot.turn.store(turn(head) * 2 + 1, std::memory_order_release); + } + + template bool try_emplace(Args &&... args) noexcept { + static_assert(std::is_nothrow_constructible::value, + "T must be nothrow constructible with Args&&..."); + auto head = head_.load(std::memory_order_acquire); + for (;;) { + auto &slot = slots_[idx(head)]; + if (turn(head) * 2 == slot.turn.load(std::memory_order_acquire)) { + if (head_.compare_exchange_strong(head, head + 1)) { + slot.construct(std::forward(args)...); + slot.turn.store(turn(head) * 2 + 1, std::memory_order_release); + return true; + } + } else { + auto const prevHead = head; + head = head_.load(std::memory_order_acquire); + if (head == prevHead) { + return false; + } + } + } + } + + void push(const T &v) noexcept { + static_assert(std::is_nothrow_copy_constructible::value, + "T must be nothrow copy constructible"); + emplace(v); + } + + template ::value>::type> + void push(P &&v) noexcept { + emplace(std::forward

(v)); + } + + bool try_push(const T &v) noexcept { + static_assert(std::is_nothrow_copy_constructible::value, + "T must be nothrow copy constructible"); + return try_emplace(v); + } + + template ::value>::type> + bool try_push(P &&v) noexcept { + return try_emplace(std::forward

(v)); + } + + void pop(T &v) noexcept { + auto const tail = tail_.fetch_add(1); + auto &slot = slots_[idx(tail)]; + while (turn(tail) * 2 + 1 != slot.turn.load(std::memory_order_acquire)) + ; + v = slot.move(); + slot.destroy(); + slot.turn.store(turn(tail) * 2 + 2, std::memory_order_release); + } + + bool try_pop(T &v) noexcept { + auto tail = tail_.load(std::memory_order_acquire); + for (;;) { + auto &slot = slots_[idx(tail)]; + if (turn(tail) * 2 + 1 == slot.turn.load(std::memory_order_acquire)) { + if (tail_.compare_exchange_strong(tail, tail + 1)) { + v = slot.move(); + slot.destroy(); + slot.turn.store(turn(tail) * 2 + 2, std::memory_order_release); + return true; + } + } else { + auto const prevTail = tail; + tail = tail_.load(std::memory_order_acquire); + if (tail == prevTail) { + return false; + } + } + } + } + +private: + constexpr size_t idx(size_t i) const noexcept { return i % capacity_; } + + constexpr size_t turn(size_t i) const noexcept { return i / capacity_; } + + static constexpr size_t kCacheLineSize = 128; + + struct Slot { + ~Slot() noexcept { + if (turn & 1) { + destroy(); + } + } + + template void construct(Args &&... args) noexcept { + static_assert(std::is_nothrow_constructible::value, + "T must be nothrow constructible with Args&&..."); + new (&storage) T(std::forward(args)...); + } + + void destroy() noexcept { + static_assert(std::is_nothrow_destructible::value, + "T must be nothrow destructible"); + reinterpret_cast(&storage)->~T(); + } + + T &&move() noexcept { return reinterpret_cast(storage); } + + // Align to avoid false sharing between adjacent slots + alignas(kCacheLineSize) std::atomic turn = {0}; + typename std::aligned_storage::type storage; + }; + +private: + const size_t capacity_; + Slot *slots_; + void *buf_; + + // Align to avoid false sharing between head_ and tail_ + alignas(kCacheLineSize) std::atomic head_; + alignas(kCacheLineSize) std::atomic tail_; +}; +} diff --git a/cds/sync/backoff.h b/cds/misc/backoff.h similarity index 100% rename from cds/sync/backoff.h rename to cds/misc/backoff.h diff --git a/cds/sync/barrier.h b/cds/misc/barrier.h similarity index 100% rename from cds/sync/barrier.h rename to cds/misc/barrier.h diff --git a/cds/container/chase-lev-deque.h b/cds/misc/chase-lev-deque.h similarity index 99% rename from cds/container/chase-lev-deque.h rename to cds/misc/chase-lev-deque.h index 4f812584..a5c6cc2a 100644 --- a/cds/container/chase-lev-deque.h +++ b/cds/misc/chase-lev-deque.h @@ -2,7 +2,7 @@ #define _CHASE_LEV_DEQUE_H #include -#include +#include #include #include #include diff --git a/cds/sync/mcs-lock.h b/cds/misc/mcs-lock.h similarity index 100% rename from cds/sync/mcs-lock.h rename to cds/misc/mcs-lock.h diff --git a/cds/sync/rwlock.h b/cds/misc/rwlock.h similarity index 100% rename from cds/sync/rwlock.h rename to cds/misc/rwlock.h diff --git a/cds/sync/seqlock.h b/cds/misc/seqlock.h similarity index 100% rename from cds/sync/seqlock.h rename to cds/misc/seqlock.h diff --git a/cds/sync/ticket_lock.h b/cds/misc/ticket_lock.h similarity index 100% rename from cds/sync/ticket_lock.h rename to cds/misc/ticket_lock.h diff --git a/test/stress/misc/barrier_driver.cpp b/test/stress/misc/barrier_driver.cpp index 3ffe5aec..90ca2399 100644 --- a/test/stress/misc/barrier_driver.cpp +++ b/test/stress/misc/barrier_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/misc/deque_driver.cpp b/test/stress/misc/deque_driver.cpp index 60809472..8976c3cd 100644 --- a/test/stress/misc/deque_driver.cpp +++ b/test/stress/misc/deque_driver.cpp @@ -1,5 +1,5 @@ #include "common.h" -#include +#include #include #include #include diff --git a/test/stress/misc/mcslock_driver.cpp b/test/stress/misc/mcslock_driver.cpp index e37e4324..ea3370ae 100644 --- a/test/stress/misc/mcslock_driver.cpp +++ b/test/stress/misc/mcslock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/misc/rwlock_driver.cpp b/test/stress/misc/rwlock_driver.cpp index 548d16a9..fa425c9e 100644 --- a/test/stress/misc/rwlock_driver.cpp +++ b/test/stress/misc/rwlock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/misc/seqlock_driver.cpp b/test/stress/misc/seqlock_driver.cpp index ba47d4a9..c3ee487a 100644 --- a/test/stress/misc/seqlock_driver.cpp +++ b/test/stress/misc/seqlock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/misc/spinlock_driver.cpp b/test/stress/misc/spinlock_driver.cpp index 159c18af..94c6c7ce 100644 --- a/test/stress/misc/spinlock_driver.cpp +++ b/test/stress/misc/spinlock_driver.cpp @@ -3,7 +3,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/sequential/sequential-misc/CMakeLists.txt b/test/stress/sequential/sequential-misc/CMakeLists.txt index 6b48b52a..c5d1c335 100644 --- a/test/stress/sequential/sequential-misc/CMakeLists.txt +++ b/test/stress/sequential/sequential-misc/CMakeLists.txt @@ -2,8 +2,9 @@ set(PACKAGE_NAME stress-sequential-misc) set(CDSSTRESS_STACK_SOURCES ../../main.cpp - spinlock_driver.cpp + rigtorp_mpmc_driver.cpp deque_driver.cpp + spinlock_driver.cpp seqlock_driver.cpp rwlock_driver.cpp mcslock_driver.cpp diff --git a/test/stress/sequential/sequential-misc/deque_driver.cpp b/test/stress/sequential/sequential-misc/deque_driver.cpp index 9fe98137..4fc584d1 100644 --- a/test/stress/sequential/sequential-misc/deque_driver.cpp +++ b/test/stress/sequential/sequential-misc/deque_driver.cpp @@ -1,5 +1,5 @@ #include "common.h" -#include +#include #include #include #include diff --git a/test/stress/sequential/sequential-misc/mcslock_driver.cpp b/test/stress/sequential/sequential-misc/mcslock_driver.cpp index 5914f559..d0b83cb6 100644 --- a/test/stress/sequential/sequential-misc/mcslock_driver.cpp +++ b/test/stress/sequential/sequential-misc/mcslock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/sequential/sequential-misc/rigtorp_mpmc_driver.cpp b/test/stress/sequential/sequential-misc/rigtorp_mpmc_driver.cpp new file mode 100644 index 00000000..743a64aa --- /dev/null +++ b/test/stress/sequential/sequential-misc/rigtorp_mpmc_driver.cpp @@ -0,0 +1,61 @@ +#include "common.h" +#include +#include +#include +#include + +using namespace std; + +namespace { + +class rigtorpMPMCQueueTest : public cds_test::stress_fixture { +protected: + static size_t s_nRigtorpMPMCQueuePassCount; + static size_t s_nRigtorpMPMCQueueEnqueueStride; + static size_t s_nRigtorpMPMCQueueCapacity; + + static void SetUpTestCase() { + cds_test::config const &cfg = get_config("Misc"); + GetConfig(RigtorpMPMCQueuePassCount); + GetConfig(RigtorpMPMCQueueEnqueueStride); + GetConfig(RigtorpMPMCQueueCapacity); + } + + void test() { + rigtorp::MPMCQueue q(s_nRigtorpMPMCQueueCapacity); + size_t nNo = 0; + size_t pop_sum = 0; + + while (nNo < s_nRigtorpMPMCQueuePassCount) { + size_t curr_push_count = + std::min(s_nRigtorpMPMCQueuePassCount - nNo, s_nRigtorpMPMCQueueEnqueueStride); + for (size_t i = 0; i < curr_push_count; i++) { + q.push(nNo); + ++nNo; + } + + for (size_t i = 0; i < curr_push_count; i++) { + size_t res; + q.pop(res); + pop_sum += res; + } + } + + size_t supposed_sum = + s_nRigtorpMPMCQueuePassCount * (s_nRigtorpMPMCQueuePassCount - 1) / 2; + if (pop_sum != supposed_sum) { + std::cout << "Sequential rigtorpMPMC queue pop sum: " << pop_sum + << " != " << supposed_sum << "\n"; + } + } +}; + +size_t rigtorpMPMCQueueTest::s_nRigtorpMPMCQueuePassCount; +size_t rigtorpMPMCQueueTest::s_nRigtorpMPMCQueueEnqueueStride; +size_t rigtorpMPMCQueueTest::s_nRigtorpMPMCQueueCapacity; + +TEST_F(rigtorpMPMCQueueTest, PushPop) { + test(); +} + +} // namespace diff --git a/test/stress/sequential/sequential-misc/rwlock_driver.cpp b/test/stress/sequential/sequential-misc/rwlock_driver.cpp index 61dc9893..aee9463a 100644 --- a/test/stress/sequential/sequential-misc/rwlock_driver.cpp +++ b/test/stress/sequential/sequential-misc/rwlock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/sequential/sequential-misc/seqlock_driver.cpp b/test/stress/sequential/sequential-misc/seqlock_driver.cpp index f3680b64..21313b3f 100644 --- a/test/stress/sequential/sequential-misc/seqlock_driver.cpp +++ b/test/stress/sequential/sequential-misc/seqlock_driver.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/test/stress/sequential/sequential-misc/spinlock_driver.cpp b/test/stress/sequential/sequential-misc/spinlock_driver.cpp index bd2c42a3..99a48153 100644 --- a/test/stress/sequential/sequential-misc/spinlock_driver.cpp +++ b/test/stress/sequential/sequential-misc/spinlock_driver.cpp @@ -3,7 +3,7 @@ #include #include #include -#include +#include #include #include #include -- 2.34.1