included missing header

* re-enabled gc
* optimized mco calculation
* added heuristic to *reduce* mco at insertion time
* fixed signedness bug at update_size_ctrl

include/boost/unordered/detail/foa/concurrent_table.hpp

@@ -50,6 +50,13 @@
 #include <execution>
 #endif
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+#include <array>
+#include <algorithm>
+#include <vector>
+#include <iostream>
+#endif
+
 namespace boost{
 namespace unordered{
 namespace detail{
@@ -83,6 +90,8 @@ public:
   cache_aligned_array(const cache_aligned_array&)=delete;
   cache_aligned_array& operator=(const cache_aligned_array&)=delete;
 
+  constexpr std::size_t size()const noexcept{return N;}
+
   T& operator[](std::size_t pos)noexcept{return *data(pos);}
 
 private:
@@ -127,18 +136,16 @@ template<typename Mutex>
 class shared_lock
 {
 public:
-  shared_lock(Mutex& m_)noexcept:m(m_){m.lock_shared();}
-  ~shared_lock()noexcept{if(owns)m.unlock_shared();}
+  shared_lock(Mutex& m)noexcept:pm(&m){pm->lock_shared();}
+  shared_lock(shared_lock&& x)noexcept:pm(x.pm){x.pm=nullptr;x.owns=false;}
+  ~shared_lock()noexcept{if(owns&&pm)pm->unlock_shared();}
 
-  /* not used but VS in pre-C++17 mode needs to see it for RVO */
-  shared_lock(const shared_lock&);
-
-  void lock(){BOOST_ASSERT(!owns);m.lock_shared();owns=true;}
-  void unlock(){BOOST_ASSERT(owns);m.unlock_shared();owns=false;}
+  void lock(){BOOST_ASSERT(!owns&&pm);pm->lock_shared();owns=true;}
+  void unlock(){BOOST_ASSERT(owns&&pm);pm->unlock_shared();owns=false;}
 
 private:
-  Mutex &m;
-  bool owns=true;
+  Mutex* pm;
+  bool   owns=true;
 };
 
 /* VS in pre-C++17 mode can't implement RVO for std::lock_guard due to
@@ -149,14 +156,12 @@ template<typename Mutex>
 class lock_guard
 {
 public:
-  lock_guard(Mutex& m_)noexcept:m(m_){m.lock();}
-  ~lock_guard()noexcept{m.unlock();}
-
-  /* not used but VS in pre-C++17 mode needs to see it for RVO */
-  lock_guard(const lock_guard&);
+  lock_guard(Mutex& m)noexcept:pm(&m){pm->lock();}
+  lock_guard(lock_guard&& x)noexcept:pm(x.pm){x.pm=nullptr;}
+  ~lock_guard()noexcept{if(pm)pm->unlock();}
 
 private:
-  Mutex &m;
+  Mutex* pm;
 };
 
 /* inspired by boost/multi_index/detail/scoped_bilock.hpp */
@@ -198,15 +203,27 @@ private:
 template<typename Integral>
 struct atomic_integral
 {
+#if 0&&defined(BOOST_UNORDERED_LATCH_FREE)
   operator Integral()const{return n.load(std::memory_order_acquire);}
   void operator=(Integral m){n.store(m,std::memory_order_release);}
   void operator|=(Integral m){n.fetch_or(m);}
   void operator&=(Integral m){n.fetch_and(m);}
 
   atomic_integral& operator=(atomic_integral const& rhs) {
-    n.store(rhs.n.load());
+    n.store(rhs.n.load(std::memory_order_acquire),std::memory_order_release);
     return *this;
   }
+#else
+  operator Integral()const{return n.load(std::memory_order_relaxed);}
+  void operator=(Integral m){n.store(m,std::memory_order_relaxed);}
+  void operator|=(Integral m){n.fetch_or(m,std::memory_order_relaxed);}
+  void operator&=(Integral m){n.fetch_and(m,std::memory_order_relaxed);}
+
+  atomic_integral& operator=(atomic_integral const& rhs) {
+    n.store(rhs.n.load(std::memory_order_relaxed),std::memory_order_relaxed);
+    return *this;
+  }
+#endif
 
   std::atomic<Integral> n;
 };
@@ -216,6 +233,17 @@ struct atomic_integral
  * unprotected_norehash_emplace_or_visit).
  */
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+struct group_access
+{
+  using insert_counter_type=std::atomic<boost::uint32_t>;
+
+  insert_counter_type& insert_counter(){return icnt;}
+
+private:
+  insert_counter_type icnt{0};
+};
+#else
 struct group_access
 {    
   using mutex_type=rw_spinlock;
@@ -231,6 +259,7 @@ private:
   mutex_type          m;
   insert_counter_type cnt{0};
 };
+#endif
 
 template<std::size_t Size>
 group_access* dummy_group_accesses()
@@ -297,6 +326,16 @@ struct concurrent_table_arrays:table_arrays<Value,Group,SizePolicy,Allocator>
       for(std::size_t i=0;i<arrays.groups_size_mask+1;++i){
         ::new (arrays.group_accesses()+i) group_access();
       }
+
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    // initialize element access counters
+
+    static constexpr auto N=super::N;
+
+    for(std::size_t i=0;i<(arrays.groups_size_mask+1)*N-1;++i){
+      arrays.elements()[i].access=0;
+    }
+#endif
   }
 
   static void set_group_access(
@@ -480,8 +519,12 @@ public:
   concurrent_table(
     std::size_t n=default_bucket_count,const Hash& h_=Hash(),
     const Pred& pred_=Pred(),const Allocator& al_=Allocator()):
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    super{(std::max)(n,std::size_t(1)),h_,pred_,al_} // TODO: won't work with n==0
+#else
     super{n,h_,pred_,al_}
-    {}
+#endif
+  {}
 
   concurrent_table(const concurrent_table& x):
     concurrent_table(x,x.exclusive_access()){}
@@ -515,7 +558,19 @@ public:
     concurrent_table(std::move(x),x.make_empty_arrays())
   {}
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  ~concurrent_table(){
+    std::cout
+      <<"version: 2024/10/21 12:15; "
+      <<"lf: "<<(double)size()/capacity()<<"; "
+      <<"size: "<<size()<<", "
+      <<"capacity: "<<capacity()<<"; "
+      <<"rehashes: "<<rehashes<<"; "
+      <<"max probe:"<<max_probe<<"\n";
+  }
+#else
   ~concurrent_table()=default;
+#endif
 
   concurrent_table& operator=(const concurrent_table& x)
   {
@@ -668,10 +723,21 @@ public:
 
   bool empty()const noexcept{return size()==0;}
   
-  std::size_t size()const noexcept
+  auto size()const noexcept
   {
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    using ssize_t=std::make_signed<std::size_t>::type;
+
+    auto lck=exclusive_access();
+    ssize_t res=static_cast<ssize_t>(this->size_ctrl.size);
+    for(const auto& sc:local_size_ctrls){
+      res+=sc.size;
+    }
+    return res;
+#else
     auto lck=shared_access();
     return unprotected_size();
+#endif
   }
 
   using super::max_size; 
@@ -799,6 +865,30 @@ public:
     return erase_if(x,[](const value_type&){return true;});
   }
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  template<typename Key,typename F>
+  BOOST_FORCEINLINE auto erase_if(const Key& x,F&& f)->typename std::enable_if<
+    !is_execution_policy<Key>::value,std::size_t>::type
+  {
+    auto        lck=shared_access();
+    auto        hash=this->hash_for(x);
+    std::size_t res=0;
+    unprotected_internal_visit(
+      group_exclusive{},x,this->position_for(hash),hash,
+      [&,this](group_type* pg,unsigned int n,element_type* p)
+      {
+        if(f(cast_for(group_shared{},type_policy::value_from(*p)))){
+          pg->reset(n);
+          auto& sc=local_size_ctrl();
+          sc.size.fetch_sub(1,std::memory_order_relaxed);
+          sc.mcos.fetch_add(
+            !pg->is_not_overflowed(hash),std::memory_order_relaxed);
+          res=1;
+        }
+      });
+    return res;
+  }
+#else
   template<typename Key,typename F>
   BOOST_FORCEINLINE auto erase_if(const Key& x,F&& f)->typename std::enable_if<
     !is_execution_policy<Key>::value,std::size_t>::type
@@ -817,6 +907,7 @@ public:
       });
     return res;
   }
+#endif
 
   template<typename F>
   std::size_t erase_if(F&& f)
@@ -970,9 +1061,16 @@ private:
   using exclusive_lock_guard=reentrancy_checked<lock_guard<multimutex_type>>;
   using exclusive_bilock_guard=
     reentrancy_bichecked<scoped_bilock<multimutex_type>>;
+
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  struct group_shared_lock_guard{};
+  struct group_exclusive_lock_guard{};
+  using group_insert_counter_type=typename group_access::insert_counter_type;
+#else
   using group_shared_lock_guard=typename group_access::shared_lock_guard;
   using group_exclusive_lock_guard=typename group_access::exclusive_lock_guard;
   using group_insert_counter_type=typename group_access::insert_counter_type;
+#endif
 
   concurrent_table(const concurrent_table& x,exclusive_lock_guard):
     super{x}{}
@@ -985,9 +1083,15 @@ private:
     concurrent_table&& x,const Allocator& al_,exclusive_lock_guard):
     super{std::move(x),al_}{}
 
+  static inline std::size_t thread_id()
+  {
+    thread_local auto id=(++thread_counter);
+    return id;
+  }
+
   inline shared_lock_guard shared_access()const
   {
-    thread_local auto id=(++thread_counter)%mutexes.size();
+    thread_local auto id=thread_id()%mutexes.size();
 
     return shared_lock_guard{this,mutexes[id]};
   }
@@ -1018,13 +1122,21 @@ private:
 
   inline group_shared_lock_guard access(group_shared,std::size_t pos)const
   {
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    return {};
+#else
     return this->arrays.group_accesses()[pos].shared_access();
+#endif
   }
 
   inline group_exclusive_lock_guard access(
     group_exclusive,std::size_t pos)const
   {
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    return {};
+#else
     return this->arrays.group_accesses()[pos].exclusive_access();
+#endif
   }
 
   inline group_insert_counter_type& insert_counter(std::size_t pos)const
@@ -1154,12 +1266,118 @@ private:
         {f(cast_for(access_mode,type_policy::value_from(*p)));});
   }
 
+  /* check occupation with previous unsynced match */
+
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  static bool is_occupied(group_type* pg,std::size_t pos)
+  {
+    return pg->is_occupied(pos);
+    //return true;
+  }
+#else
+  static bool is_occupied(group_type* pg,std::size_t pos)
+  {
+    return pg->is_occupied(pos);
+  }
+#endif
+
 #if defined(BOOST_MSVC)
 /* warning: forcing value to bool 'true' or 'false' in bool(pred()...) */
 #pragma warning(push)
 #pragma warning(disable:4800)
 #endif
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  template<typename F>
+  BOOST_FORCEINLINE auto load_access(element_type* p,F f)const
+    ->std::pair<decltype(f()),boost::uint32_t>
+  {
+    auto& acnt=p->access;
+    for(;;){
+      auto n=
+        acnt.load(std::memory_order_acquire)&
+        ~boost::uint32_t(1);
+
+      auto res=f();
+
+      std::atomic_thread_fence(std::memory_order_acquire);
+      if(BOOST_LIKELY(acnt.load(std::memory_order_relaxed)==n))return {res,n};
+    }
+  }
+
+  template<typename F>
+  BOOST_FORCEINLINE bool save_access(element_type* p,boost::uint32_t n,F f)const
+  {
+    auto& acnt=p->access;
+    if(!acnt.compare_exchange_strong(n,n+1,std::memory_order_acq_rel)){
+      return false;
+    }
+    std::atomic_thread_fence(std::memory_order_release);
+
+    f();
+
+    acnt.store(n+2,std::memory_order_release);
+    return true;
+  }
+
+  template<typename F>
+  BOOST_FORCEINLINE void save_access(element_type* p,F f)const /* no previous load cnt */
+  {
+    auto &acnt=p->access;
+    for(;;){
+      auto n=
+        acnt.load(std::memory_order_acquire)&
+        ~boost::uint32_t(1);
+      //if(n%2==1)continue;
+
+      if(save_access(p,n,f))return;
+    }
+  }
+
+  template<typename GroupAccessMode,typename Key,typename F>
+  BOOST_FORCEINLINE std::size_t unprotected_internal_visit(
+    GroupAccessMode access_mode,
+    const Key& x,std::size_t pos0,std::size_t hash,F&& f)const
+  {    
+  startover:
+    prober pb(pos0);
+    do{
+      auto pos=pb.get();
+      auto pg=this->arrays.groups()+pos;
+      auto mask=pg->match(hash);
+      if(mask){
+        auto p=this->arrays.elements()+pos*N;
+        BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N);
+        do{
+          auto n=unchecked_countr_zero(mask);
+          auto [pr,acnt]=load_access(p+n,[&]{
+            return std::make_pair(is_occupied(pg,n),p[n].value);
+          });
+          auto [occupied,v]=pr;
+
+          if(BOOST_LIKELY(occupied&&this->pred()(x,this->key_from(v)))){
+            if constexpr(std::is_same<GroupAccessMode,group_exclusive>::value){
+              if(BOOST_UNLIKELY(!save_access(p+n,acnt,[&]{f(pg,n,p+n);}))){
+                goto startover;
+              }
+              return 1;
+            }else{
+              element_type e{v};
+              f(pg,n,&e);
+              return 1;
+            }
+          }
+          mask&=mask-1;
+        }while(mask);
+      }
+      if(BOOST_LIKELY(pg->is_not_overflowed(hash))){
+        return 0;
+      }
+    }
+    while(BOOST_LIKELY(pb.next(this->arrays.groups_size_mask)));
+    return 0;
+  }
+#else
   template<typename GroupAccessMode,typename Key,typename F>
   BOOST_FORCEINLINE std::size_t unprotected_internal_visit(
     GroupAccessMode access_mode,
@@ -1177,7 +1395,7 @@ private:
         do{
           auto n=unchecked_countr_zero(mask);
           if(BOOST_LIKELY(
-            is_occupied(pg,n)&&bool(this->pred()(x,this->key_from(p[n]))))){
+            pg->is_occupied(n)&&bool(this->pred()(x,this->key_from(p[n]))))){
             f(pg,n,p+n);
             return 1;
           }
@@ -1191,6 +1409,7 @@ private:
     while(BOOST_LIKELY(pb.next(this->arrays.groups_size_mask)));
     return 0;
   }
+#endif
 
  template<typename GroupAccessMode,typename FwdIterator,typename F>
   BOOST_FORCEINLINE std::size_t unprotected_bulk_visit(
@@ -1436,33 +1655,37 @@ private:
     bool        commit_=false;
   };
 
+#if defined(BOOST_UNORDERED_LATCH_FREE)
   struct latch_free_reserve_slot
   {
-    latch_free_reserve_slot(group_type* pg_,std::size_t pos_):pg{pg_},pos{pos_}
+    latch_free_reserve_slot(group_type* pg,std::size_t pos):
+      pc{reinterpret_cast<std::atomic<unsigned char>*>(pg)+pos}
     {
       unsigned char expected=0;
-      succeeded_=reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos].
-        compare_exchange_weak(expected,1);
+      succeeded_=pc->compare_exchange_weak(
+          expected,1,std::memory_order_relaxed,std::memory_order_relaxed);
     }
 
     ~latch_free_reserve_slot()
     {
-      if(succeeded_&&!commit_)pg->reset(pos);
+      if(succeeded_&&!commit_)pc->store(0,std::memory_order_relaxed);
     }
 
     bool succeeded()const{return succeeded_;}
 
     void commit(){commit_=true;}
 
-    group_type  *pg;
-    std::size_t pos;
-    bool        succeeded_;
-    bool        commit_=false;
+    std::atomic<unsigned char>* pc;
+    bool                        succeeded_;
+    bool                        commit_=false;
   };
 
   struct assign_insert_counter_on_exit
   {
-    ~assign_insert_counter_on_exit(){counter=x;}
+    ~assign_insert_counter_on_exit()
+    {
+      counter.store(x,std::memory_order_release);
+    }
 
     group_insert_counter_type &counter;
     boost::uint32_t            x;
@@ -1472,66 +1695,57 @@ private:
   BOOST_FORCEINLINE int
   unprotected_norehash_emplace_or_visit(
     GroupAccessMode access_mode,F&& f,Args&&... args)
-  {
-    return unprotected_norehash_emplace_or_visit_with_layout(
-      std::integral_constant<bool,group_type::regular_layout>{},
-      access_mode,std::forward<F>(f),std::forward<Args>(args)...);
-  }
-
-  template<typename GroupAccessMode,typename F,typename... Args>
-  BOOST_FORCEINLINE int
-  unprotected_norehash_emplace_or_visit_with_layout(
-    std::true_type, /* regular layout, almost-latch-free */
-    GroupAccessMode access_mode,F&& f,Args&&... args)
   {
     const auto &k=this->key_from(std::forward<Args>(args)...);
     auto        hash=this->hash_for(k);
     auto        pos0=this->position_for(hash);
 
-    for(;;){
-    startover:
-      boost::uint32_t counter=0;
-      while(BOOST_UNLIKELY((counter=insert_counter(pos0))%2==1)){}
-      if(unprotected_visit(
-        access_mode,k,pos0,hash,std::forward<F>(f)))return 0;
+  startover:
+    boost::uint32_t counter=0;
+    do{
+      counter=insert_counter(pos0).load(std::memory_order_acquire);
+    }
+    while(BOOST_UNLIKELY(counter%2==1));
 
-      reserve_size rsize(*this);
-      if(BOOST_LIKELY(rsize.succeeded())){
-        for(prober pb(pos0);;pb.next(this->arrays.groups_size_mask)){
-          auto pos=pb.get();
-          auto pg=this->arrays.groups()+pos;
-          auto mask=pg->match_available();
-          if(BOOST_LIKELY(mask!=0)){
-            auto n=unchecked_countr_zero(mask);
-            latch_free_reserve_slot rslot{pg,n};
-            if(BOOST_UNLIKELY(!rslot.succeeded())){
-              /* slot wasn't empty */
-              goto startover;
-            }
-            if(BOOST_UNLIKELY(
-              !insert_counter(pos0).compare_exchange_weak(counter,counter+1))){
-              /* other thread inserted from pos0, need to start over */
-              goto startover;
-            }
+    if(unprotected_visit(
+      access_mode,k,pos0,hash,std::forward<F>(f)))return 0;
+
+    std::size_t pbn=max_probe;
+    for(prober pb(pos0);;pb.next(this->arrays.groups_size_mask)){
+      auto pos=pb.get();
+      auto p=this->arrays.elements()+pos*N;
+      BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N);
+      auto pg=this->arrays.groups()+pos;
+      auto mask=pg->match_available();
+      if(BOOST_LIKELY(mask!=0)){
+        auto n=unchecked_countr_zero(mask);
+        auto [ocuppied,acnt]=load_access(p+n,[&]{return is_occupied(pg,n);});
+        if(ocuppied)goto startover;
+
+        auto res=false;
+        if(!save_access(p+n,acnt,[&]{
+          if(insert_counter(pos0).compare_exchange_strong(
+                counter,counter+1,std::memory_order_relaxed)){
             assign_insert_counter_on_exit a{insert_counter(pos0),counter+2};
-            auto p=this->arrays.elements()+pos*N+n;
-            this->construct_element(p,std::forward<Args>(args)...);
+            this->construct_element(p+n,std::forward<Args>(args)...);
             pg->set(n,hash);
-            rslot.commit();
-            rsize.commit();
-            return 1;
+            res=true;
           }
-          pg->mark_overflow(hash);
-        }
+        })||!res)goto startover;
+
+        auto& sc=local_size_ctrl();            
+        sc.size.fetch_add(1,std::memory_order_relaxed);
+        sc.mcos.fetch_sub(!pg->is_not_overflowed(hash),std::memory_order_relaxed);
+        return 1;
       }
-      else return -1;
+      if(!pbn--)return -1;
+      pg->mark_overflow(hash);
     }
   }
-
+#else
   template<typename GroupAccessMode,typename F,typename... Args>
   BOOST_FORCEINLINE int
-  unprotected_norehash_emplace_or_visit_with_layout(
-    std::false_type, /* non-regular layout, latched */
+  unprotected_norehash_emplace_or_visit(
     GroupAccessMode access_mode,F&& f,Args&&... args)
   {
     const auto &k=this->key_from(std::forward<Args>(args)...);
@@ -1570,53 +1784,30 @@ private:
       else return -1;
     }
   }
+#endif
 
   void rehash_if_full()
   {
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+    auto lck=shared_access();
+    auto p=calculate_size_ctrl();
+    lck.unlock();
+    if(p.first>=p.second){ // NB >=
+      auto lck=exclusive_access();
+      update_size_ctrl();
+      ++rehashes;
+      this->unchecked_rehash_for_growth();
+      max_probe=default_max_probe;
+    }
+    else{
+      ++max_probe;
+    }
+#else
     auto lck=exclusive_access();
     if(this->size_ctrl.size==this->size_ctrl.ml){
       this->unchecked_rehash_for_growth();
     }
-  }
-
-  /* check occupation with previous unsynced match */
-
-  static bool is_occupied(group_type* pg,std::size_t pos)
-  {
-    return is_occupied(
-      std::integral_constant<bool,group_type::regular_layout>{},pg,pos);
-  }
-
-  static bool is_occupied(std::true_type,group_type* pg,std::size_t pos)
-  {
-    /* regular layout, almost-latch-free insertion -> possible reserved slot */
-    return reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos]>1;
-  }
-
-  static bool is_occupied(std::false_type,group_type* pg,std::size_t pos)
-  {
-    /* non-regular layout, latched insertion -> no reserved slots */
-    return pg->is_occupied(pos);
-  }
-
-  /* check occupation with previous synced match */
-
-  static bool is_really_occupied(group_type* pg,std::size_t pos)
-  {
-    return is_really_occupied(
-      std::integral_constant<bool,group_type::regular_layout>{},pg,pos);
-  }
-
-  static bool is_really_occupied(std::true_type,group_type* pg,std::size_t pos)
-  {
-    /* regular layout, almost-latch-free insertion -> possible reserved slot */
-    return reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos]>1;
-  }
-
-  static bool is_really_occupied(std::false_type,group_type*,std::size_t)
-  {
-    /* non-regular layout, latched insertion -> no false positives */
-    return true;
+#endif
   }
 
   template<typename GroupAccessMode,typename F>
@@ -1656,7 +1847,7 @@ private:
         auto mask=this->match_really_occupied(pg,last);
         while(mask){
           auto n=unchecked_countr_zero(mask);
-          if(BOOST_LIKELY(is_really_occupied(pg,n))&&!f(pg,n,p+n))return false;
+          if(!f(pg,n,p+n))return false;
           mask&=mask-1;
         }
       }
@@ -1691,7 +1882,7 @@ private:
         auto mask=this->match_really_occupied(&g,last);
         while(mask){
           auto n=unchecked_countr_zero(mask);
-          if(BOOST_LIKELY(is_really_occupied(&g,n)))f(&g,n,p+n);
+          f(&g,n,p+n);
           mask&=mask-1;
         }
       }
@@ -1713,7 +1904,7 @@ private:
         auto mask=this->match_really_occupied(&g,last);
         while(mask){
           auto n=unchecked_countr_zero(mask);
-          if(BOOST_LIKELY(is_really_occupied(&g,n))&&!f(p+n))return false;
+          if(!f(p+n))return false;
           mask&=mask-1;
         }
         return true;
@@ -1857,6 +2048,62 @@ private:
 
   static std::atomic<std::size_t> thread_counter;
   mutable multimutex_type         mutexes;
+
+#if defined(BOOST_UNORDERED_LATCH_FREE)
+  struct alignas(64) local_size_ctrl_type
+  {
+    using ssize_t=std::make_signed<std::size_t>::type;
+
+    std::atomic<ssize_t>     size=0;
+    std::atomic<ssize_t>     mcos=0;
+  };
+  static constexpr std::size_t default_max_probe=3;
+
+  mutable std::array<local_size_ctrl_type,128> local_size_ctrls;
+  std::atomic<std::size_t>                     max_probe=default_max_probe;
+  std::size_t                                  rehashes=0;
+  //unsigned char paddd[64];
+
+  local_size_ctrl_type& local_size_ctrl()const
+  {
+    return local_size_ctrls[thread_id()%local_size_ctrls.size()];
+  }
+
+  std::pair<std::size_t,std::size_t> calculate_size_ctrl()
+  {
+    using ssize_t=std::make_signed<std::size_t>::type;
+
+    ssize_t ssize=0,smcos=0;
+    for(const auto& sc:local_size_ctrls){
+      ssize+=sc.size.load(std::memory_order_relaxed);
+      smcos+=sc.mcos.load(std::memory_order_relaxed);
+    }
+    std::size_t size_=this->size_ctrl.size.load(std::memory_order_relaxed),
+                ml_=this->size_ctrl.ml.load(std::memory_order_relaxed);
+    size_+=ssize;
+    if(ssize_t(ml_)>=smcos)ml_-=smcos;
+    else                   ml_=0;
+    auto max_ml=super::initial_max_load();
+    if(ml_>max_ml)ml_=max_ml;
+    return {size_,ml_};
+  }
+
+  void update_size_ctrl()
+  {
+    using ssize_t=std::make_signed<std::size_t>::type;
+
+    ssize_t ssize=0,smcos=0;
+    for(auto& sc:local_size_ctrls){
+      ssize+=sc.size.exchange(0);
+      smcos+=sc.mcos.exchange(0);
+    }
+    this->size_ctrl.size+=ssize;
+    if(ssize_t(this->size_ctrl.ml)>=smcos)this->size_ctrl.ml-=smcos;
+    else                                 this->size_ctrl.ml=0;
+    auto max_ml=super::initial_max_load();
+    if(this->size_ctrl.ml>max_ml)this->size_ctrl.ml=max_ml;
+  }
+#endif
 };
 
 template<typename T,typename H,typename P,typename A>

include/boost/unordered/detail/foa/core.hpp

@@ -382,11 +382,13 @@ private:
     return (int)word[narrow_cast<unsigned char>(hash)];
   }
 
+public:
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     return narrow_cast<unsigned char>(match_word(hash));
   }
 
+private:
   inline slot_type& at(std::size_t pos)
   {
     return m[pos];
@@ -532,6 +534,7 @@ private:
 #endif
   }
 
+public:
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     static constexpr unsigned char table[]={
@@ -556,6 +559,7 @@ private:
     return table[(unsigned char)hash];
   }
 
+private:
   /* Copied from 
    * https://github.com/simd-everywhere/simde/blob/master/simde/x86/
    * sse2.h#L3763

include/boost/unordered/detail/throw_exception.hpp

@@ -1,30 +0,0 @@
-// Copyright (C) 2023 Braden Ganetsky
-// Distributed under the Boost Software License, Version 1.0. (See accompanying
-// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP
-#define BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP
-
-#include <boost/config.hpp>
-#if defined(BOOST_HAS_PRAGMA_ONCE)
-#pragma once
-#endif
-
-#include <boost/throw_exception.hpp>
-#include <stdexcept>
-
-namespace boost {
-  namespace unordered {
-    namespace detail {
-
-      BOOST_NOINLINE BOOST_NORETURN inline void throw_out_of_range(
-        char const* message)
-      {
-        boost::throw_exception(std::out_of_range(message));
-      }
-
-    } // namespace detail
-  } // namespace unordered
-} // namespace boost
-
-#endif // BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP

include/boost/unordered/unordered_flat_map.hpp

@@ -14,12 +14,12 @@
 #include <boost/unordered/detail/foa/flat_map_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/serialize_container.hpp>
-#include <boost/unordered/detail/throw_exception.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_flat_map_fwd.hpp>
 
 #include <boost/core/allocator_access.hpp>
 #include <boost/container_hash/hash.hpp>
+#include <boost/throw_exception.hpp>
 
 #include <initializer_list>
 #include <iterator>
@@ -459,8 +459,8 @@ namespace boost {
         // TODO: someday refactor this to conditionally serialize the key and
         // include it in the error message
         //
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_flat_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
       }
 
       mapped_type const& at(key_type const& key) const
@@ -469,8 +469,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_flat_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
       }
 
       template <class K>
@@ -483,8 +483,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_flat_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
       }
 
       template <class K>
@@ -497,8 +497,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_flat_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
       }
 
       BOOST_FORCEINLINE mapped_type& operator[](key_type const& key)

include/boost/unordered/unordered_map.hpp

@@ -16,7 +16,6 @@
 
 #include <boost/unordered/detail/map.hpp>
 #include <boost/unordered/detail/serialize_fca_container.hpp>
-#include <boost/unordered/detail/throw_exception.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 
 #include <boost/container_hash/hash.hpp>
@@ -1587,8 +1586,8 @@ namespace boost {
           return p->value().second;
       }
 
-      boost::unordered::detail::throw_out_of_range(
-        "Unable to find key in unordered_map.");
+      boost::throw_exception(
+        std::out_of_range("Unable to find key in unordered_map."));
     }
 
     template <class K, class T, class H, class P, class A>
@@ -1603,8 +1602,8 @@ namespace boost {
           return p->value().second;
       }
 
-      boost::unordered::detail::throw_out_of_range(
-        "Unable to find key in unordered_map.");
+      boost::throw_exception(
+        std::out_of_range("Unable to find key in unordered_map."));
     }
 
     template <class K, class T, class H, class P, class A>
@@ -1621,8 +1620,8 @@ namespace boost {
           return p->value().second;
       }
 
-      boost::unordered::detail::throw_out_of_range(
-        "Unable to find key in unordered_map.");
+      boost::throw_exception(
+        std::out_of_range("Unable to find key in unordered_map."));
     }
 
     template <class K, class T, class H, class P, class A>
@@ -1639,8 +1638,8 @@ namespace boost {
           return p->value().second;
       }
 
-      boost::unordered::detail::throw_out_of_range(
-        "Unable to find key in unordered_map.");
+      boost::throw_exception(
+        std::out_of_range("Unable to find key in unordered_map."));
     }
 
     template <class K, class T, class H, class P, class A>

include/boost/unordered/unordered_node_map.hpp

@@ -15,12 +15,12 @@
 #include <boost/unordered/detail/foa/node_map_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/serialize_container.hpp>
-#include <boost/unordered/detail/throw_exception.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_node_map_fwd.hpp>
 
 #include <boost/core/allocator_access.hpp>
 #include <boost/container_hash/hash.hpp>
+#include <boost/throw_exception.hpp>
 
 #include <initializer_list>
 #include <iterator>
@@ -554,8 +554,8 @@ namespace boost {
         // TODO: someday refactor this to conditionally serialize the key and
         // include it in the error message
         //
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_node_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_node_map"));
       }
 
       mapped_type const& at(key_type const& key) const
@@ -564,8 +564,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_node_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_node_map"));
       }
 
       template <class K>
@@ -578,8 +578,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_node_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_node_map"));
       }
 
       template <class K>
@@ -592,8 +592,8 @@ namespace boost {
         if (pos != table_.end()) {
           return pos->second;
         }
-        boost::unordered::detail::throw_out_of_range(
-          "key was not found in unordered_node_map");
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_node_map"));
       }
 
       BOOST_FORCEINLINE mapped_type& operator[](key_type const& key)