updated concurrent map benchmark plots

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

@@ -17,10 +17,13 @@
 #include <boost/core/ignore_unused.hpp>
 #include <boost/core/no_exceptions_support.hpp>
 #include <boost/cstdint.hpp>
+#include <boost/mp11/algorithm.hpp>
+#include <boost/mp11/list.hpp>
 #include <boost/mp11/tuple.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/unordered/detail/foa/core.hpp>
 #include <boost/unordered/detail/foa/rw_spinlock.hpp>
+#include <boost/unordered/detail/foa/takes_arg_as_const_reference.hpp>
 #include <boost/unordered/detail/foa/tuple_rotate_right.hpp>
 #include <cstddef>
 #include <functional>
@@ -485,7 +488,7 @@ public:
   template<typename Key,typename F>
   BOOST_FORCEINLINE std::size_t visit(const Key& x,F&& f)
   {
-    return visit_impl(group_exclusive{},x,std::forward<F>(f));
+    return visit_impl(group_access_for<F>{},x,std::forward<F>(f));
   }
 
   template<typename Key,typename F>
@@ -502,7 +505,7 @@ public:
 
   template<typename F> std::size_t visit_all(F&& f)
   {
-    return visit_all_impl(group_exclusive{},std::forward<F>(f));
+    return visit_all_impl(group_access_for<F>{},std::forward<F>(f));
   }
 
   template<typename F> std::size_t visit_all(F&& f)const
@@ -520,7 +523,7 @@ public:
   void visit_all(ExecutionPolicy&& policy,F&& f)
   {
     visit_all_impl(
-      group_exclusive{},
+      group_access_for<F>{},
       std::forward<ExecutionPolicy>(policy),std::forward<F>(f));
   }
 
@@ -582,7 +585,7 @@ public:
   BOOST_FORCEINLINE bool try_emplace_or_visit(Key&& x,Args&&... args)
   {
     return emplace_or_visit_flast(
-      group_exclusive{},
+      group_access_for_last_of<Args...>{},
       try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
   }
 
@@ -598,7 +601,7 @@ public:
   BOOST_FORCEINLINE bool emplace_or_visit(Args&&... args)
   {
     return construct_and_emplace_or_visit_flast(
-      group_exclusive{},std::forward<Args>(args)...);
+      group_access_for_last_of<Args...>{},std::forward<Args>(args)...);
   }
 
   template<typename... Args>
@@ -611,7 +614,7 @@ public:
   template<typename F>
   BOOST_FORCEINLINE bool insert_or_visit(const init_type& x,F&& f)
   {
-    return emplace_or_visit_impl(group_exclusive{},std::forward<F>(f),x);
+    return emplace_or_visit_impl(group_access_for<F>{},std::forward<F>(f),x);
   }
 
   template<typename F>
@@ -624,7 +627,7 @@ public:
   BOOST_FORCEINLINE bool insert_or_visit(init_type&& x,F&& f)
   {
     return emplace_or_visit_impl(
-      group_exclusive{},std::forward<F>(f),std::move(x));
+      group_access_for<F>{},std::forward<F>(f),std::move(x));
   }
 
   template<typename F>
@@ -640,7 +643,7 @@ public:
   BOOST_FORCEINLINE auto insert_or_visit(const Value& x,F&& f)
     ->enable_if_is_value_type<Value,bool>
   {
-    return emplace_or_visit_impl(group_exclusive{},std::forward<F>(f),x);
+    return emplace_or_visit_impl(group_access_for<F>{},std::forward<F>(f),x);
   }
 
   template<typename Value,typename F>
@@ -655,7 +658,7 @@ public:
     ->enable_if_is_value_type<Value,bool>
   {
     return emplace_or_visit_impl(
-      group_exclusive{},std::forward<F>(f),std::move(x));
+      group_access_for<F>{},std::forward<F>(f),std::move(x));
   }
 
   template<typename Value,typename F>
@@ -683,7 +686,7 @@ public:
       group_exclusive{},x,this->position_for(hash),hash,
       [&,this](group_type* pg,unsigned int n,element_type* p)
       {
-        if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
+        if(f(cast_for(group_access_for<F>{},type_policy::value_from(*p)))){
           super::erase(pg,n,p);
           res=1;
         }
@@ -699,7 +702,7 @@ public:
     for_all_elements(
       group_exclusive{},
       [&,this](group_type* pg,unsigned int n,element_type* p){
-        if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
+        if(f(cast_for(group_access_for<F>{},type_policy::value_from(*p)))){
           super::erase(pg,n,p);
           ++res;
         }
@@ -716,7 +719,7 @@ public:
     for_all_elements(
       group_exclusive{},std::forward<ExecutionPolicy>(policy),
       [&,this](group_type* pg,unsigned int n,element_type* p){
-        if(f(cast_for(group_exclusive{},type_policy::value_from(*p)))){
+        if(f(cast_for(group_access_for<F>{},type_policy::value_from(*p)))){
           super::erase(pg,n,p);
         }
       });
@@ -886,6 +889,17 @@ private:
   using group_shared=std::false_type;
   using group_exclusive=std::true_type;
 
+  template<typename F>
+  using group_access_for=typename std::conditional<
+    takes_arg_as_const_reference<F,value_type>::value,
+    group_shared,
+    group_exclusive
+  >::type;
+
+  template<typename... Args>
+  using group_access_for_last_of=
+    group_access_for<mp11::mp_back<mp11::mp_list<Args...>>>;
+
   inline group_shared_lock_guard access(group_shared,std::size_t pos)const
   {
     return this->arrays.group_accesses[pos].shared_access();

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

@@ -0,0 +1,98 @@
+/* Copyright 2023 Joaquin M Lopez Munoz.
+ * 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)
+ *
+ * See https://www.boost.org/libs/unordered for library home page.
+ */
+
+#ifndef BOOST_UNORDERED_DETAIL_FOA_TAKES_ARG_AS_CONST_REFERENCE_HPP
+#define BOOST_UNORDERED_DETAIL_FOA_TAKES_ARG_AS_CONST_REFERENCE_HPP
+
+#include <boost/type_traits/make_void.hpp>
+#include <type_traits>
+#include <utility>
+
+namespace boost{
+namespace unordered{
+namespace detail{
+namespace foa{
+
+template<typename Arg,typename R,typename... Args>
+void check_function_1st_arg(R(*)(Arg,Args...));
+
+template<typename Arg,typename R,typename... Args>
+void check_function_1st_arg(R(*)(Arg,Args...,...));
+
+#define BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(qualifier)       \
+template<typename Arg,typename R,typename C,typename... Args> \
+void check_memfun_1st_arg(R(C::*)(Arg,Args...)qualifier);     \
+                                                              \
+template<typename Arg,typename R,typename C,typename... Args> \
+void check_memfun_1st_arg(R(C::*)(Arg,Args...,...)qualifier);
+
+/* VS warns when a pp function is directly called with an empty arg */
+#define BOOST_UNORDERED_EMPTY_PP_ARG()
+
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(BOOST_UNORDERED_EMPTY_PP_ARG())
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(volatile)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const volatile)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(volatile&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const volatile&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(&&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const&&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(volatile&&)
+BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG(const volatile&&)
+
+#undef BOOST_UNORDERED_EMPTY_PP_ARG
+#undef BOOST_UNORDERED_CHECK_MEMFUN_1ST_ARG
+
+/* Detects if f(x) takes x as a const reference. From an implementation
+ * technique by Kenneth Gorking.
+ * Requires: F is invocable with an Arg&.
+ */
+
+template<typename F,typename Arg,typename=void>
+struct takes_arg_as_const_reference0:std::false_type{};
+
+template<typename F,typename Arg>
+struct takes_arg_as_const_reference0<
+  F,Arg,
+  decltype(check_function_1st_arg<const Arg&>(std::declval<F>()))
+>:std::true_type{};
+
+template<typename F,typename Arg>
+struct takes_arg_as_const_reference0<
+  F,Arg,
+  boost::void_t<
+    decltype(std::declval<F>().operator()(std::declval<Arg&>()))
+  >
+>:std::true_type{};
+
+template<typename F,typename Arg,typename=void>
+struct takes_arg_as_const_reference:takes_arg_as_const_reference0<F,Arg>{};
+
+template<
+  typename F,typename Arg,
+  typename R=decltype(std::declval<F>()(std::declval<Arg&>())),
+  typename RawF=
+    typename std::remove_cv<typename std::remove_reference<F>::type>::type
+>
+decltype(check_memfun_1st_arg<Arg&,R,RawF>(&RawF::operator()))
+check_operator_call_takes_arg_as_reference();
+
+template<typename F,typename Arg>
+struct takes_arg_as_const_reference<
+  F,Arg,
+  decltype(check_operator_call_takes_arg_as_reference<F,Arg>())
+>:std::false_type{};
+
+} /* namespace foa */
+} /* namespace detail */
+} /* namespace unordered */
+} /* namespace boost */
+
+#endif

test/Jamfile.v2

@@ -202,6 +202,7 @@ local CFOA_TESTS =
   rw_spinlock_test6
   rw_spinlock_test7
   rw_spinlock_test8
+  takes_arg_as_cref_tests
 ;
 
 for local test in $(CFOA_TESTS)

test/cfoa/takes_arg_as_cref_tests.cpp

@@ -0,0 +1,178 @@
+// Copyright 2023 Joaquin M Lopez Munoz
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/config.hpp>
+#include <boost/unordered/detail/foa/takes_arg_as_const_reference.hpp>
+#include <boost/core/lightweight_test.hpp>
+
+using boost::unordered::detail::foa::takes_arg_as_const_reference;
+
+using  f1  = void ( const int& );
+void   function2( const int& ) noexcept;
+using  f2  = decltype(function2);
+using  f3  = void ( const int&, char* );
+using  f4  = void ( const int&, ... );
+using  f5  = void ( int& );
+void   function6( int& ) noexcept;
+using  f6  = decltype(function6);
+using  f7  = void ( int&, char* );
+using  f8  = void ( int&, ... );
+struct f9  { void operator()( const int& ); };
+struct f10 { void operator()( const int& ) const; };
+struct f11 { void operator()( const int& ) volatile; };
+struct f12 { void operator()( const int& ) const volatile; };
+struct f13 { void operator()( const int& )&; };
+struct f14 { void operator()( const int& ) const&; };
+struct f15 { void operator()( const int& ) volatile&; };
+struct f16 { void operator()( const int& ) const volatile&; };
+struct f17 { void operator()( const int& )&&; };
+struct f18 { void operator()( const int& ) const&&; };
+struct f19 { void operator()( const int& ) volatile&&; };
+struct f20 { void operator()( const int& ) const volatile&&; };
+struct f21 { void operator()( const int& ) noexcept; };
+struct f22 { void operator()( const int& ) const noexcept; };
+struct f23 { void operator()( const int&, int=0 ); };
+struct f24 { void operator()( const int&, ... ) noexcept; };
+struct f25 { void operator()( int& ); };
+struct f26 { void operator()( int& ) const; };
+struct f27 { void operator()( int& ) volatile; };
+struct f28 { void operator()( int& ) const volatile; };
+struct f29 { void operator()( int& )&; };
+struct f30 { void operator()( int& ) const&; };
+struct f31 { void operator()( int& ) volatile&; };
+struct f32 { void operator()(  int& ) const volatile&; };
+struct f33 { void operator()( int& )&&; };
+struct f34 { void operator()( int& ) const&&; };
+struct f35 { void operator()( int& ) volatile&&; };
+struct f36 { void operator()( int& ) const volatile&&; };
+struct f37 { void operator()( int& ) noexcept; };
+struct f38 { void operator()( int& ) const noexcept; };
+struct f39 { void operator()( int&, int=0 ); };
+struct f40 { void operator()( int&, ... ) noexcept; };
+struct f41 { template<typename Arg> void operator()( const Arg& ); };
+struct f42 { template<typename Arg> void operator()( const Arg& ) const; };
+struct f43 { template<typename Arg> void operator()( const Arg& ) const noexcept; };
+struct f44 { template<typename Arg> void operator()( Arg& ); };
+struct f45 { template<typename Arg> void operator()( Arg& ) const; };
+struct f46 { template<typename Arg> void operator()( Arg& ) const noexcept; };
+struct f47 { template<typename Arg> void operator()( Arg ); };
+struct f48 { template<typename Arg> void operator()( Arg ) const; };
+struct f49 { template<typename Arg> void operator()( Arg ) const noexcept; };
+struct f50
+{
+    void operator()( const int& );
+    void operator()( char* );
+};
+struct f51 // expected false negative
+{
+    void operator()( const int& );
+    template<typename Arg> void operator()( Arg& );
+};
+using f52=int; // detection doesn't crash even if requirements violated
+
+int main()
+{
+    auto  lambda53 = []( const int& ){};
+    using f53=decltype(lambda53);
+    int   retrieved=0;
+    auto  lambda54 = [&]( const int& x ) mutable { retrieved = x; };
+    using f54=decltype(lambda54);
+    auto  lambda55 = []( int& x ){ x = 0; };
+    using f55=decltype(lambda55);
+    auto  lambda56 = [&]( int& x ) mutable { retrieved = x; x = 0; };
+    using f56=decltype(lambda56);
+
+#if !defined(BOOST_NO_CXX14_GENERIC_LAMBDAS)
+    auto  lambda57 = []( const auto& ){};
+    using f57=decltype(lambda57);
+    auto  lambda58 = [&]( const auto& x ) mutable { retrieved = x; };
+    using f58=decltype(lambda58);
+    auto  lambda59 = []( auto& x ){ x = 0; };
+    using f59=decltype(lambda59);
+    auto  lambda60 = [&]( auto& x ) mutable { retrieved = x; x = 0; };
+    using f60=decltype(lambda60);
+#endif
+
+    BOOST_TEST((  takes_arg_as_const_reference<f1,    int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f2,    int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f3,    int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f4,    int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f5,    int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f6,    int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f7,    int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f8,    int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f1*,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f2*,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f3*,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f4*,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f5*,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f6*,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f7*,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f8*,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f1&,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f2&,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f3&,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f4&,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f5&,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f6&,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f7&,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f8&,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f9,    int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f10,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f11,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f12,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f13&,  int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f14&,  int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f15&,  int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f16&,  int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f17&&, int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f18&&, int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f19&&, int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f20&&, int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f21,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f22,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f23,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f24,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f25,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f26,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f27,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f28,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f29&,  int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f30&,  int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f31&,  int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f32&,  int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f33&&, int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f34&&, int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f35&&, int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f36&&, int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f37,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f38,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f39,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f40,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f41,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f42,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f43,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f44,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f45,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f46,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f47,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f48,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f49,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f50,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f51,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f52,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f53,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f54,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f55,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f56,   int>::value ));
+
+#if !defined(BOOST_NO_CXX14_GENERIC_LAMBDAS)
+    BOOST_TEST((  takes_arg_as_const_reference<f57,   int>::value ));
+    BOOST_TEST((  takes_arg_as_const_reference<f58,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f59,   int>::value ));
+    BOOST_TEST(( !takes_arg_as_const_reference<f60,   int>::value ));
+#endif
+
+    return boost::report_errors();
+}