From 703049c3e12de7abe34c44e3862f44e593cf2b90 Mon Sep 17 00:00:00 2001 From: Maged Michael Date: Wed, 21 Jun 2017 15:56:45 -0700 Subject: [PATCH] Add support for move operations on hazptr-holder. Other optimizations. Summary: - Support empty hazptr_holder, move constructor and assignment operator - Limit thread caching to the default domain to improve performance of thread caching - Fix unnecessary calls to stats singleton - Use the mprotect version of AsymmetricMemoryBarrier for reducing the overhead of bulkReclaim(). - Update read-side benchmark results Reviewed By: djwatson Differential Revision: D5292885 fbshipit-source-id: bc5713ac95492a7114e1e467e71d2278e64b165d --- folly/experimental/hazptr/bench/HazptrBench.h | 71 ++++----- folly/experimental/hazptr/hazptr-impl.h | 141 +++++++++--------- folly/experimental/hazptr/hazptr.h | 14 +- folly/experimental/hazptr/test/HazptrTest.cpp | 29 ++++ 4 files changed, 141 insertions(+), 114 deletions(-) diff --git a/folly/experimental/hazptr/bench/HazptrBench.h b/folly/experimental/hazptr/bench/HazptrBench.h index b21a8e80..097cd7f1 100644 --- a/folly/experimental/hazptr/bench/HazptrBench.h +++ b/folly/experimental/hazptr/bench/HazptrBench.h @@ -86,12 +86,13 @@ inline uint64_t bench(std::string name, int nthreads, int size, uint64_t base) { max = std::max(max, dur); } + const std::string unit = " ns"; uint64_t avg = sum / reps; uint64_t res = min; std::cout << name; - std::cout << " " << std::setw(4) << max / ops << " ns"; - std::cout << " " << std::setw(4) << avg / ops << " ns"; - std::cout << " " << std::setw(4) << res / ops << " ns"; + std::cout << " " << std::setw(4) << max / ops << unit; + std::cout << " " << std::setw(4) << avg / ops << unit; + std::cout << " " << std::setw(4) << res / ops << unit; if (base) { std::cout << " " << std::setw(3) << 100 * base / res << "%"; } @@ -109,58 +110,58 @@ const std::string header = "Test_name, Max time, Avg time, Min time"; /* ------------------------------------------- No AMB - No Tc 1 threads -- 10-item list -no amb - no tc 756 ns 688 ns 674 ns -no amb - no tc - dup 725 ns 688 ns 676 ns +no amb - no tc 713 ns 672 ns 648 ns +no amb - no tc - dup 692 ns 660 ns 648 ns 1 threads -- 100-item list -no amb - no tc 2469 ns 2366 ns 2334 ns -no amb - no tc - dup 2404 ns 2353 ns 2328 ns +no amb - no tc 2167 ns 2146 ns 2133 ns +no amb - no tc - dup 2210 ns 2153 ns 2133 ns 10 threads -- 10-item list -no amb - no tc 802 ns 764 ns 750 ns -no amb - no tc - dup 798 ns 776 ns 733 ns +no amb - no tc 716 ns 614 ns 285 ns +no amb - no tc - dup 750 ns 546 ns 285 ns 10 threads -- 100-item list -no amb - no tc 2209 ns 2157 ns 2118 ns -no amb - no tc - dup 2266 ns 2152 ns 1993 ns +no amb - no tc 1923 ns 1482 ns 862 ns +no amb - no tc - dup 1978 ns 1614 ns 1112 ns ---------------------------------------------------------- ---------------------------------------------- AMB - No TC 1 threads -- 10-item list -amb - no tc 554 ns 538 ns 525 ns -amb - no tc - dup 540 ns 530 ns 524 ns +amb - no tc 519 ns 504 ns 501 ns +amb - no tc - dup 533 ns 511 ns 500 ns 1 threads -- 100-item list -amb - no tc 731 ns 721 ns 715 ns -amb - no tc - dup 745 ns 724 ns 714 ns +amb - no tc 721 ns 696 ns 689 ns +amb - no tc - dup 786 ns 718 ns 688 ns 10 threads -- 10-item list -amb - no tc 777 ns 717 ns 676 ns -amb - no tc - dup 726 ns 669 ns 638 ns +amb - no tc 695 ns 565 ns 380 ns +amb - no tc - dup 710 ns 450 ns 242 ns 10 threads -- 100-item list -amb - no tc 1015 ns 985 ns 955 ns -amb - no tc - dup 1000 ns 978 ns 952 ns +amb - no tc 921 ns 773 ns 573 ns +amb - no tc - dup 594 ns 441 ns 409 ns ---------------------------------------------------------- ---------------------------------------------- No AMB - TC 1 threads -- 10-item list -no amb - tc 209 ns 203 ns 199 ns -no amb - tc - dup 210 ns 202 ns 196 ns +no amb - tc 182 ns 180 ns 178 ns +no amb - tc - dup 205 ns 183 ns 178 ns 1 threads -- 100-item list -no amb - tc 1872 ns 1849 ns 1840 ns -no amb - tc - dup 1902 ns 1865 ns 1838 ns +no amb - tc 1756 ns 1697 ns 1670 ns +no amb - tc - dup 1718 ns 1681 ns 1666 ns 10 threads -- 10-item list -no amb - tc 136 ns 50 ns 23 ns -no amb - tc - dup 178 ns 85 ns 23 ns +no amb - tc 174 ns 120 ns 55 ns +no amb - tc - dup 174 ns 143 ns 114 ns 10 threads -- 100-item list -no amb - tc 1594 ns 651 ns 201 ns -no amb - tc - dup 1492 ns 615 ns 203 ns +no amb - tc 1480 ns 1058 ns 565 ns +no amb - tc - dup 1834 ns 1327 ns 1065 ns ---------------------------------------------------------- ------------------------------------------------- AMB - TC 1 threads -- 10-item list -amb - tc 45 ns 44 ns 44 ns -amb - tc - dup 46 ns 46 ns 45 ns +amb - tc 32 ns 32 ns 31 ns +amb - tc - dup 32 ns 32 ns 31 ns 1 threads -- 100-item list -amb - tc 256 ns 246 ns 240 ns -amb - tc - dup 242 ns 240 ns 238 ns +amb - tc 238 ns 229 ns 221 ns +amb - tc - dup 224 ns 222 ns 221 ns 10 threads -- 10-item list -amb - tc 120 ns 35 ns 13 ns -amb - tc - dup 104 ns 34 ns 9 ns +amb - tc 27 ns 20 ns 13 ns +amb - tc - dup 28 ns 22 ns 18 ns 10 threads -- 100-item list -amb - tc 267 ns 129 ns 49 ns -amb - tc - dup 766 ns 147 ns 42 ns +amb - tc 221 ns 165 ns 116 ns +amb - tc - dup 277 ns 169 ns 120 ns ---------------------------------------------------------- */ diff --git a/folly/experimental/hazptr/hazptr-impl.h b/folly/experimental/hazptr/hazptr-impl.h index 49bdf23f..34166873 100644 --- a/folly/experimental/hazptr/hazptr-impl.h +++ b/folly/experimental/hazptr/hazptr-impl.h @@ -68,6 +68,12 @@ namespace hazptr { class hazptr_stats; hazptr_stats& hazptr_stats(); +#if HAZPTR_STATS +#define INC_HAZPTR_STATS(x) hazptr_stats().x() +#else +#define INC_HAZPTR_STATS(x) +#endif + /** hazptr_mb */ class hazptr_mb { @@ -80,17 +86,16 @@ class hazptr_mb { class hazptr_tc_entry { friend class hazptr_tc; - std::atomic hprec_{nullptr}; - std::atomic domain_{nullptr}; + hazptr_rec* hprec_{nullptr}; public: - void fill(hazptr_rec* hprec, hazptr_domain* domain); - hazptr_rec* get(hazptr_domain* domain); - void invalidate(hazptr_rec* hprec); + void fill(hazptr_rec* hprec); + hazptr_rec* get(); void evict(); }; class hazptr_tc { + hazptr_domain* domain_{&default_hazptr_domain()}; hazptr_tc_entry tc_[HAZPTR_TC_SIZE]; public: @@ -102,10 +107,6 @@ class hazptr_tc { hazptr_tc& hazptr_tc(); -std::mutex& hazptr_tc_lock(); - -using hazptr_tc_guard = std::lock_guard; - /** * public functions */ @@ -133,12 +134,11 @@ inline void hazptr_obj_base::retire(hazptr_domain& domain, D deleter) { class hazptr_rec { friend class hazptr_domain; - friend class hazptr_tc_entry; friend class hazptr_holder; + friend class hazptr_tc_entry; std::atomic hazptr_{nullptr}; hazptr_rec* next_{nullptr}; - std::atomic tc_{nullptr}; std::atomic active_{false}; void set(const void* p) noexcept; @@ -158,9 +158,33 @@ inline hazptr_holder::hazptr_holder(hazptr_domain& domain) { if (hazptr_ == nullptr) { std::bad_alloc e; throw e; } } +inline hazptr_holder::hazptr_holder(std::nullptr_t) { + domain_ = nullptr; + hazptr_ = nullptr; + DEBUG_PRINT(this << " " << domain_ << " " << hazptr_); +} + hazptr_holder::~hazptr_holder() { DEBUG_PRINT(this); - domain_->hazptrRelease(hazptr_); + if (domain_) { + domain_->hazptrRelease(hazptr_); + } +} + +hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept { + domain_ = rhs.domain_; + hazptr_ = rhs.hazptr_; + rhs.domain_ = nullptr; + rhs.hazptr_ = nullptr; +} + +hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept { + /* Self-move is a no-op. */ + if (this != &rhs) { + this->~hazptr_holder(); + new (this) hazptr_holder(std::move(rhs)); + } + return *this; } template @@ -191,11 +215,13 @@ template inline void hazptr_holder::reset(const T* ptr) noexcept { auto p = static_cast(const_cast(ptr)); DEBUG_PRINT(this << " " << ptr << " p:" << p); + DCHECK(hazptr_); // UB if *this is empty hazptr_->set(p); } inline void hazptr_holder::reset(std::nullptr_t) noexcept { DEBUG_PRINT(this); + DCHECK(hazptr_); // UB if *this is empty hazptr_->clear(); } @@ -289,18 +315,7 @@ inline hazptr_domain::~hazptr_domain() { hazptr_rec* next; for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) { next = p->next_; - if (HAZPTR_TC) { - if (p->isActive()) { - hazptr_tc_guard g(hazptr_tc_lock()); - if (p->isActive()) { - auto tc = p->tc_.load(std::memory_order_acquire); - DCHECK(tc != nullptr); - tc->invalidate(p); - } - } - } else { - CHECK(!p->isActive()); - } + DCHECK(!p->isActive()); mr_->deallocate(static_cast(p), sizeof(hazptr_rec)); } } @@ -463,64 +478,48 @@ inline void hazptr_mb::light() { DEBUG_PRINT(""); if (HAZPTR_AMB) { folly::asymmetricLightBarrier(); - hazptr_stats().light(); + INC_HAZPTR_STATS(light); } else { atomic_thread_fence(std::memory_order_seq_cst); - hazptr_stats().seq_cst(); + INC_HAZPTR_STATS(seq_cst); } } inline void hazptr_mb::heavy() { DEBUG_PRINT(""); if (HAZPTR_AMB) { - folly::asymmetricHeavyBarrier(); - hazptr_stats().heavy(); + folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED); + INC_HAZPTR_STATS(heavy); } else { atomic_thread_fence(std::memory_order_seq_cst); - hazptr_stats().seq_cst(); + INC_HAZPTR_STATS(seq_cst); } } /** hazptr_tc - functions */ -inline void hazptr_tc_entry::fill(hazptr_rec* hprec, hazptr_domain* domain) { - hprec_.store(hprec, std::memory_order_release); - domain_.store(domain, std::memory_order_release); - hprec->tc_.store(this, std::memory_order_release); - DEBUG_PRINT(this << " " << domain << " " << hprec); +inline void hazptr_tc_entry::fill(hazptr_rec* hprec) { + hprec_ = hprec; + DEBUG_PRINT(this << " " << hprec); } -inline hazptr_rec* hazptr_tc_entry::get(hazptr_domain* domain) { - if (domain == domain_.load(std::memory_order_acquire)) { - auto hprec = hprec_.load(std::memory_order_acquire); - if (hprec) { - hprec_.store(nullptr, std::memory_order_release); - DEBUG_PRINT(this << " " << domain << " " << hprec); - return hprec; - } +inline hazptr_rec* hazptr_tc_entry::get() { + auto hprec = hprec_; + if (hprec) { + hprec_ = nullptr; + DEBUG_PRINT(this << " " << hprec); + return hprec; } return nullptr; } -inline void hazptr_tc_entry::invalidate(hazptr_rec* hprec) { - DCHECK_EQ(hprec, hprec_); - hprec_.store(nullptr, std::memory_order_release); - domain_.store(nullptr, std::memory_order_release); - hprec->tc_.store(nullptr, std::memory_order_relaxed); - hprec->release(); - DEBUG_PRINT(this << " " << hprec); -} - inline void hazptr_tc_entry::evict() { - auto hprec = hprec_.load(std::memory_order_relaxed); + auto hprec = hprec_; if (hprec) { - hazptr_tc_guard g(hazptr_tc_lock()); - hprec = hprec_.load(std::memory_order_relaxed); - if (hprec) { - invalidate(hprec); - } + hprec_ = nullptr; + hprec->release(); } - DEBUG_PRINT(hprec); + DEBUG_PRINT(this << " " << hprec); } inline hazptr_tc::hazptr_tc() { @@ -535,34 +534,30 @@ inline hazptr_tc::~hazptr_tc() { } inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) { + if (domain != domain_) { + return nullptr; + } for (int i = 0; i < HAZPTR_TC_SIZE; ++i) { - auto hprec = tc_[i].get(domain); + auto hprec = tc_[i].get(); if (hprec) { - DEBUG_PRINT(this << " " << domain << " " << hprec); + DEBUG_PRINT(this << " " << hprec); return hprec; } } - DEBUG_PRINT(this << " " << domain << " nullptr"); + DEBUG_PRINT(this << " nullptr"); return nullptr; } inline bool hazptr_tc::put(hazptr_rec* hprec, hazptr_domain* domain) { - int other = HAZPTR_TC_SIZE; + if (domain != domain_) { + return false; + } for (int i = 0; i < HAZPTR_TC_SIZE; ++i) { - if (tc_[i].hprec_.load(std::memory_order_acquire) == nullptr) { - tc_[i].fill(hprec, domain); + if (tc_[i].hprec_ == nullptr) { + tc_[i].fill(hprec); DEBUG_PRINT(this << " " << i); return true; } - if (tc_[i].domain_.load(std::memory_order_relaxed) != domain) { - other = i; - } - } - if (other < HAZPTR_TC_SIZE) { - tc_[other].evict(); - tc_[other].fill(hprec, domain); - DEBUG_PRINT(this << " " << other); - return true; } return false; } diff --git a/folly/experimental/hazptr/hazptr.h b/folly/experimental/hazptr/hazptr.h index 3bd2fc03..35d40113 100644 --- a/folly/experimental/hazptr/hazptr.h +++ b/folly/experimental/hazptr/hazptr.h @@ -103,17 +103,19 @@ class hazptr_holder { public: /* Constructor automatically acquires a hazard pointer. */ explicit hazptr_holder(hazptr_domain& domain = default_hazptr_domain()); + /* Construct an empty hazptr_holder. */ + // Note: This diverges from the proposal in P0233R4 + explicit hazptr_holder(std::nullptr_t); + /* Destructor automatically clears and releases the owned hazard pointer. */ ~hazptr_holder(); - /* Copy and move constructors and assignment operators are - * disallowed because: - * - Each hazptr_holder owns exactly one hazard pointer at any time. - * - Each hazard pointer may have up to one owner at any time. */ hazptr_holder(const hazptr_holder&) = delete; - hazptr_holder(hazptr_holder&&) = delete; hazptr_holder& operator=(const hazptr_holder&) = delete; - hazptr_holder& operator=(hazptr_holder&&) = delete; + // Note: This diverges from the proposal in P0233R4 which disallows + // move constructor and assignment operator. + hazptr_holder(hazptr_holder&&) noexcept; + hazptr_holder& operator=(hazptr_holder&&) noexcept; /** Hazard pointer operations */ /* Returns a protected pointer from the source */ diff --git a/folly/experimental/hazptr/test/HazptrTest.cpp b/folly/experimental/hazptr/test/HazptrTest.cpp index 5c135db4..d40e9275 100644 --- a/folly/experimental/hazptr/test/HazptrTest.cpp +++ b/folly/experimental/hazptr/test/HazptrTest.cpp @@ -280,3 +280,32 @@ TEST_F(HazptrTest, DestructionTest) { } last->retire(); } + +TEST_F(HazptrTest, Move) { + struct Foo : hazptr_obj_base { + int a; + }; + for (int i = 0; i < 100; ++i) { + Foo* x = new Foo; + x->a = i; + hazptr_holder hptr0; + // Protect object + hptr0.reset(x); + // Retire object + x->retire(); + // Move constructor - still protected + hazptr_holder hptr1(std::move(hptr0)); + // Self move is no-op - still protected + hazptr_holder* phptr1 = &hptr1; + CHECK_EQ(phptr1, &hptr1); + hptr1 = std::move(*phptr1); + // Empty constructor + hazptr_holder hptr2(nullptr); + // Move assignment - still protected + hptr2 = std::move(hptr1); + // Access object + CHECK_EQ(x->a, i); + // Unprotect object - hptr2 is nonempty + hptr2.reset(); + } +} -- 2.34.1