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

diff --git a/folly/experimental/hazptr/bench/HazptrBench.h b/folly/experimental/hazptr/bench/HazptrBench.h
index b21a8e8057aa461673841edb9430c25ecb29ce85..097cd7f1e75c4f24874f9fb18f4c6c6f3f5fb842 100644 (file)
--- 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);
   }
 
     max = std::max(max, dur);
   }
 

+  const std::string unit = " ns";

   uint64_t avg = sum / reps;
   uint64_t res = min;
   std::cout << name;
   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 << "%";
   }
   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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 49bdf23f7c33b8b1ae368cc76b1919288cb3001d..341668730a6caedb4238b19c3c64788f5413ab95 100644 (file)
--- 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();
 
 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 {
 /** hazptr_mb */
 
 class hazptr_mb {


@@ -80,17 +86,16 @@ class hazptr_mb {
 
 class hazptr_tc_entry {
   friend class hazptr_tc;
 
 class hazptr_tc_entry {
   friend class hazptr_tc;

-  std::atomic<hazptr_rec*> hprec_{nullptr};
-  std::atomic<hazptr_domain*> domain_{nullptr};
+  hazptr_rec* hprec_{nullptr};

 
  public:
 
  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 {
   void evict();
 };
 
 class hazptr_tc {

+  hazptr_domain* domain_{&default_hazptr_domain()};

   hazptr_tc_entry tc_[HAZPTR_TC_SIZE];
 
  public:
   hazptr_tc_entry tc_[HAZPTR_TC_SIZE];
 
  public:


@@ -102,10 +107,6 @@ class hazptr_tc {
 
 hazptr_tc& hazptr_tc();
 
 
 hazptr_tc& hazptr_tc();
 

-std::mutex& hazptr_tc_lock();
-
-using hazptr_tc_guard = std::lock_guard<std::mutex>;
-

 /**
  * public functions
  */
 /**
  * public functions
  */


@@ -133,12 +134,11 @@ inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
 
 class hazptr_rec {
   friend class hazptr_domain;
 
 class hazptr_rec {
   friend class hazptr_domain;

-  friend class hazptr_tc_entry;

   friend class hazptr_holder;
   friend class hazptr_holder;

+  friend class hazptr_tc_entry;

 
   std::atomic<const void*> hazptr_{nullptr};
   hazptr_rec* next_{nullptr};
 
   std::atomic<const void*> hazptr_{nullptr};
   hazptr_rec* next_{nullptr};

-  std::atomic<hazptr_tc_entry*> tc_{nullptr};

   std::atomic<bool> active_{false};
 
   void set(const void* p) noexcept;
   std::atomic<bool> 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; }
 }
 
   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);
 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 <typename T>
 }
 
 template <typename T>


@@ -191,11 +215,13 @@ template <typename T>
 inline void hazptr_holder::reset(const T* ptr) noexcept {
   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 inline void hazptr_holder::reset(const T* ptr) noexcept {
   auto p = static_cast<hazptr_obj*>(const_cast<T*>(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);
   hazptr_->set(p);
 }
 
 inline void hazptr_holder::reset(std::nullptr_t) noexcept {
   DEBUG_PRINT(this);

+  DCHECK(hazptr_); // UB if *this is empty

   hazptr_->clear();
 }
 
   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_;
     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<void*>(p), sizeof(hazptr_rec));
     }
   }
       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
     }
   }


@@ -463,64 +478,48 @@ inline void hazptr_mb::light() {
   DEBUG_PRINT("");
   if (HAZPTR_AMB) {
     folly::asymmetricLightBarrier();
   DEBUG_PRINT("");
   if (HAZPTR_AMB) {
     folly::asymmetricLightBarrier();

-    hazptr_stats().light();
+    INC_HAZPTR_STATS(light);

   } else {
     atomic_thread_fence(std::memory_order_seq_cst);
   } 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) {
   }
 }
 
 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);
   } else {
     atomic_thread_fence(std::memory_order_seq_cst);

-    hazptr_stats().seq_cst();
+    INC_HAZPTR_STATS(seq_cst);

   }
 }
 
 /** hazptr_tc - functions */
 
   }
 }
 
 /** 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;
 }
 
   }
   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() {
 inline void hazptr_tc_entry::evict() {

-  auto hprec = hprec_.load(std::memory_order_relaxed);
+  auto hprec = hprec_;

   if (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() {
 }
 
 inline hazptr_tc::hazptr_tc() {


@@ -535,34 +534,30 @@ inline hazptr_tc::~hazptr_tc() {
 }
 
 inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) {
 }
 
 inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) {

+  if (domain != domain_) {
+    return nullptr;
+  }

   for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
   for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {

-    auto hprec = tc_[i].get(domain);
+    auto hprec = tc_[i].get();

     if (hprec) {
     if (hprec) {

-      DEBUG_PRINT(this << " " << domain << " " << hprec);
+      DEBUG_PRINT(this << " " << hprec);

       return 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) {
   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) {
   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;
     }
       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;
 }
   }
   return false;
 }

diff --git a/folly/experimental/hazptr/hazptr.h b/folly/experimental/hazptr/hazptr.h
index 3bd2fc034fd973fbbccebd255519e2158ec0b8e4..35d40113a1b35853b0767c92beddeb536f2b8a8c 100644 (file)
--- 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());
  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();
 
   /* 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(const hazptr_holder&) = delete;

-  hazptr_holder(hazptr_holder&&) = delete;

   hazptr_holder& operator=(const 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 */
 
   /** 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 5c135db47ea2e161c92afc6fe227056604cf481c..d40e9275fe75363419aa23abb2eb716c49831202 100644 (file)
--- a/folly/experimental/hazptr/test/HazptrTest.cpp
+++ b/folly/experimental/hazptr/test/HazptrTest.cpp
@@ -280,3 +280,32 @@ TEST_F(HazptrTest, DestructionTest) {
   }
   last->retire();
 }
   }
   last->retire();
 }

+
+TEST_F(HazptrTest, Move) {
+  struct Foo : hazptr_obj_base<Foo> {
+    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();
+  }
+}