fourth attempt

.github/workflows/ci.yml

@@ -217,13 +217,11 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '64',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '/RTCc'              }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '32',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '"/RTCc /arch:IA32"' }
-          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019, variant: 'debug,release' }
+          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022 }
+          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022 }
+          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019 }
 
     runs-on: ${{matrix.os}}
 
@@ -252,9 +250,6 @@ jobs:
           B2_TOOLSET: ${{matrix.toolset}}
           B2_CXXSTD: ${{matrix.cxxstd}}
           B2_ADDRESS_MODEL: ${{matrix.addrmd}}
-          B2_DEFINES: ${{matrix.defines}}
-          B2_VARIANT: ${{matrix.variant}}
-          B2_CXXFLAGS: ${{matrix.cxxflags}}
 
       - name: Collect coverage
         shell: powershell

benchmark/.gitignore

@@ -1,3 +0,0 @@
-enwik8
-enwik9
-*.exe

benchmark/string.cpp

@@ -3,18 +3,23 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -262,6 +267,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -285,10 +308,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -348,6 +384,14 @@ template<class K, class V> using boost_unordered_map_fnv1a =
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
     boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -358,10 +402,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -371,45 +428,67 @@ int main()
 {
     init_indices();
 
+#if 1
+
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
 #endif
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
     test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
-
-#endif
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/string_view.cpp

@@ -3,18 +3,23 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <string_view>
@@ -263,6 +268,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -286,10 +309,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -349,6 +385,14 @@ template<class K, class V> using boost_unordered_map_fnv1a =
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
     boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -359,10 +403,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -372,45 +429,67 @@ int main()
 {
     init_indices();
 
+#if 1
+
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
 #endif
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
     test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
-
-#endif
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint32.cpp

@@ -3,10 +3,12 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -14,8 +16,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -279,6 +284,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -302,10 +325,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -316,25 +352,34 @@ int main()
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint64.cpp

@@ -3,10 +3,12 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -14,8 +16,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -279,6 +284,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -302,10 +325,23 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH
 
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -313,38 +349,37 @@ int main()
 {
     init_indices();
 
-#if defined(BOOST_LIBSTDCXX_VERSION) && __SIZE_WIDTH__ == 32
-
-    // Pathological behavior:
-    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104945
-
-#else
-
     test<std_unordered_map>( "std::unordered_map" );
-
-#endif
-
     test<boost_unordered_map>( "boost::unordered_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uuid.cpp

@@ -3,10 +3,12 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/container_hash/hash.hpp>
@@ -15,9 +17,6 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -330,6 +329,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     times.push_back( rec );
 }
 
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator
 
 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -353,13 +370,6 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
 int main()
 {
     init_indices();
@@ -367,12 +377,7 @@ int main()
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
 
@@ -385,7 +390,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/word_count.cpp

@@ -1,376 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-#include <string_view>
-#include <string>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        ++map[ word ];
-        ++s;
-    }
-
-    print_time( t1, "Word count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_contains( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.contains( w2 );
-    }
-
-    print_time( t1, "Contains", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.count( w2 );
-    }
-
-    print_time( t1, "Count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t max = 0;
-    std::string_view word;
-
-    for( auto const& x: map )
-    {
-        if( x.second > max )
-        {
-            word = x.first;
-            max = x.second;
-        }
-    }
-
-    print_time( t1, "Iterate and find max element",  max, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::string_view, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_count( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_contains( map, t1 );
-    test_count( map, t1 );
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-// fnv1a_hash
-
-template<int Bits> struct fnv1a_hash_impl;
-
-template<> struct fnv1a_hash_impl<32>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0x811C9DC5u;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x01000193ul;
-        }
-
-        return h;
-    }
-};
-
-template<> struct fnv1a_hash_impl<64>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0xCBF29CE484222325ull;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x00000100000001B3ull;
-        }
-
-        return h;
-    }
-};
-
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = void;
-};
-
-template<class K, class V> using std_unordered_map_fnv1a =
-std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map_fnv1a =
-    boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map_fnv1a =
-    absl::node_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map_fnv1a =
-    absl::flat_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-//
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
-    test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
-
-#endif
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif

benchmark/word_size.cpp

@@ -1,238 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_size( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( auto const& word: words )
-    {
-        ++map[ word.size() ];
-    }
-
-    print_time( t1, "Word size count",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& x: map )
-    {
-        s += x.second;
-    }
-
-    print_time( t1, "Iterate and sum counts",  s, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::size_t, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_size( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif

doc/unordered/buckets.adoc

@@ -244,69 +244,4 @@ image::fca.png[align=center]
 
 Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to `O(size())`. In total, a bucket group is only 4 words in size and it views `sizeof(std::size_t) * CHAR_BIT` buckets meaning that for all common implementations, there's only 4 bits of space overhead per bucket introduced by the bucket groups.
 
-A more detailed description of Boost.Unordered's closed-addressing implementation is
-given in an
-https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article].
-For more information on implementation rationale, read the
-xref:#rationale_boostunordered_multiset_and_boostunordered_multimap[corresponding section].
-
-== Open Addressing Implementation
-
-The diagram shows the basic internal layout of `boost::unordered_flat_map` and
-`boost:unordered_flat_set`.
-
-
-[#img-foa-layout]
-.Open-addressing layout used by Boost.Unordered.
-image::foa.png[align=center]
-
-As with all open-addressing containers, elements are stored directly in the bucket array.
-This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
-In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
-16-byte words.
-
-[#img-foa-metadata]
-.Breakdown of a metadata word.
-image::foa-metadata.png[align=center]
-
-A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated
-bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
-
-  - 0 if the corresponding bucket is empty.
-  - 1 to encode a special empty bucket called a _sentinel_, which is used internally to
-  stop iteration when the container has been fully traversed.
-  - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of
-  the element.
-
-When looking for an element with hash value _h_, SIMD technologies such as
-https://en.wikipedia.org/wiki/SSE2[SSE2] and
-https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us
-to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the
-15 buckets with just a handful of CPU instructions: non-matching buckets can be
-readily discarded, and those whose reduced hash value matches need be inspected via full
-comparison with the corresponding element. If the looked-for element is not present,
-the overflow byte is inspected:
-
-- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the
-element is not present).
-- If the bit is set to 1 (the group has been _overflowed_), further groups are
-checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and
-the process is repeated.
-
-Insertion is algorithmically similar: empty buckets are located using SIMD,
-and when going past a full group its corresponding overflow bit is set to 1.
-
-In architectures without SIMD support, the logical layout stays the same, but the metadata
-word is codified using a technique we call _bit interleaving_: this layout allows us
-to emulate SIMD with reasonably good performance using only standard arithmetic and
-logical operations.
-
-[#img-foa-metadata-interleaving]
-.Bit-interleaved metadata word.
-image::foa-metadata-interleaving.png[align=center]
-
-A more detailed description of Boost.Unordered's open-addressing implementation is
-given in an
-https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article].
-For more information on implementation rationale, read the
-xref:#rationale_boostunordered_flat_set_and_boostunordered_flat_map[corresponding section].
+For more information on implementation rationale, read the <<Implementation Rationale, corresponding section>>.

doc/unordered/changes.adoc

@@ -10,8 +10,6 @@
 
 * Added fast containers `boost::unordered_flat_map` and `boost::unordered_flat_set`
   based on open addressing.
-* Added CTAD deduction guides for all containers.
-* Added missing constructors as specified in https://cplusplus.github.io/LWG/issue2713[LWG issue 2713].
 
 == Release 1.80.0 - Major update
 

include/boost/unordered/detail/foa.hpp

@@ -135,7 +135,6 @@ static const std::size_t default_bucket_count = 0;
 
 #if defined(BOOST_UNORDERED_SSE2)
 
-#if 0
 struct group15
 {
   static constexpr int N=15;
@@ -262,20 +261,12 @@ private:
       0xF8F8F8F8u,0xF9F9F9F9u,0xFAFAFAFAu,0xFBFBFBFBu,0xFCFCFCFCu,0xFDFDFDFDu,0xFEFEFEFEu,0xFFFFFFFFu,
     };
 
-#if defined(__MSVC_RUNTIME_CHECKS)
-    return (int)word[hash&0xffu];
-#else
     return (int)word[(unsigned char)hash];
-#endif
   }
 
   inline static unsigned char reduced_hash(std::size_t hash)
   {
-#if defined(__MSVC_RUNTIME_CHECKS)
-    return match_word(hash)&0xffu;
-#else
     return (unsigned char)match_word(hash);
-#endif
   }
 
   inline unsigned char& at(std::size_t pos)
@@ -300,157 +291,6 @@ private:
 
   alignas(16) __m128i m;
 };
-#else
-struct group15
-{
-  static constexpr int N=15;
-
-  struct dummy_group_type
-  {
-    alignas(16) unsigned char storage[N+1]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0};
-  };
-
-  inline void initialize(){m=_mm_setzero_si128();}
-
-  inline void set(std::size_t pos,std::size_t hash)
-  {
-    BOOST_ASSERT(pos<N);
-    at(pos)=reduced_hash(hash+pos);
-  }
-
-  inline void set_sentinel()
-  {
-    at(N-1)=sentinel_;
-  }
-
-  inline bool is_sentinel(std::size_t pos)const
-  {
-    BOOST_ASSERT(pos<N);
-    return at(pos)==sentinel_;
-  }
-
-  inline void reset(std::size_t pos)
-  {
-    BOOST_ASSERT(pos<N);
-    at(pos)=available_;
-  }
-
-  static inline void reset(unsigned char* pc)
-  {
-    *pc=available_;
-  }
-
-  inline int match(std::size_t hash)const
-  {
-    return _mm_movemask_epi8(_mm_cmpeq_epi8(m,match_word(hash)))&0x7FFF;
-  }
-
-  inline bool is_not_overflowed(std::size_t hash)const
-  {
-    static constexpr unsigned char shift[]={1,2,4,8,16,32,64,128};
-
-    return !(overflow()&shift[hash%8]);
-  }
-
-  inline void mark_overflow(std::size_t hash)
-  {
-#if BOOST_WORKAROUND(BOOST_GCC, >= 50000 && BOOST_GCC < 60000)
-    overflow() = static_cast<unsigned char>( overflow() | static_cast<unsigned char>(1<<(hash%8)) );
-#else
-    overflow()|=static_cast<unsigned char>(1<<(hash%8));
-#endif
-  }
-
-  static inline bool maybe_caused_overflow(unsigned char* pc)
-  {
-    std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
-    group15    *pg=reinterpret_cast<group15*>(pc-pos);
-    return !pg->is_not_overflowed(*pc-pos);
-  };
-
-  inline int match_available()const
-  {
-    return _mm_movemask_epi8(
-      _mm_cmpeq_epi8(m,_mm_setzero_si128()))&0x7FFF;
-  }
-
-  inline int match_occupied()const
-  {
-    return (~match_available())&0x7FFF;
-  }
-
-  inline int match_really_occupied()const /* excluding sentinel */
-  {
-    return at(N-1)==sentinel_?match_occupied()&0x3FFF:match_occupied();
-  }
-
-private:
-  static constexpr unsigned char available_=0,
-                                 sentinel_=1;
-
-  static constexpr unsigned char reduced_hash_table[]={
-    8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
-    16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
-    32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
-    48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
-    64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
-    80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
-    96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
-    112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
-    128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
-    144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
-    160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
-    176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
-    192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
-    208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
-    224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
-    240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
-    8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,
-  };
-
-  inline static __m128i match_word(std::size_t hash)
-  {
-#if defined(__MSVC_RUNTIME_CHECKS)
-    return _mm_loadu_si128(reinterpret_cast<const __m128i*>(
-      reduced_hash_table+(hash&0xffu)));
-#else
-    return _mm_loadu_si128(reinterpret_cast<const __m128i*>(
-      reduced_hash_table+(unsigned char)(hash)));
-#endif
-  }
-
-  inline static unsigned char reduced_hash(std::size_t hash)
-  {
-#if defined(__MSVC_RUNTIME_CHECKS)
-    return reduced_hash_table[hash&0xffu];
-#else
-    return reduced_hash_table[(unsigned char)hash];
-#endif
-  }
-
-  inline unsigned char& at(std::size_t pos)
-  {
-    return reinterpret_cast<unsigned char*>(&m)[pos];
-  }
-
-  inline unsigned char at(std::size_t pos)const
-  {
-    return reinterpret_cast<const unsigned char*>(&m)[pos];
-  }
-
-  inline unsigned char& overflow()
-  {
-    return at(N);
-  }
-
-  inline unsigned char overflow()const
-  {
-    return at(N);
-  }
-
-  alignas(16) __m128i m;
-};
-#endif
 
 #elif defined(BOOST_UNORDERED_LITTLE_ENDIAN_NEON)
 
@@ -677,11 +517,7 @@ struct group15
     std::size_t     pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
     group15        *pg=reinterpret_cast<group15*>(pc-pos);
     boost::uint64_t x=((pg->m[0])>>pos)&0x000100010001ull;
-#if defined(__MSVC_RUNTIME_CHECKS)
-    boost::uint32_t y=(x|(x>>15)|(x>>30))&0xffffffffu;
-#else
     boost::uint32_t y=static_cast<boost::uint32_t>(x|(x>>15)|(x>>30));
-#endif
     return !pg->is_not_overflowed(y);
   };
 
@@ -696,11 +532,7 @@ struct group15
   inline int match_occupied()const
   {
     boost::uint64_t x=m[0]|m[1];
-#if defined(__MSVC_RUNTIME_CHECKS)
-    boost::uint32_t y=(x|(x>>32))&0xffffffffu;
-#else
     boost::uint32_t y=static_cast<boost::uint32_t>(x|(x>>32));
-#endif
     y|=y>>16;
     return y&0x7FFF;
   }
@@ -735,11 +567,7 @@ private:
       240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
     };
     
-#if defined(__MSVC_RUNTIME_CHECKS)
-  return table[hash&0xffu];
-#else
     return table[(unsigned char)hash];
-#endif
   }
 
   inline void set_impl(std::size_t pos,std::size_t n)
@@ -828,6 +656,7 @@ private:
  *     these values and positioning to be as uncorrelated as possible.
  */
 
+#if 0
 struct pow2_size_policy
 {
   static inline std::size_t size_index(std::size_t n)
@@ -851,6 +680,47 @@ struct pow2_size_policy
     return hash>>size_index_;
   }
 };
+#else
+struct pow2_size_policy
+{
+  static inline std::size_t size_index(std::size_t n)
+  {
+    // TODO: min size is 2, see if we can bring it down to 1 without loss
+    // of performance
+
+    std::size_t used_bits_=n<=2?1:((std::size_t)(boost::core::bit_width(n-1)));
+    std::size_t shift_right_=total_bits-used_bits_;
+    std::size_t shift_left_=shift_right_%2?0:shift_right_-8;
+
+    return (shift_left_<<16)|shift_right_;
+  }
+
+  static inline std::size_t size(std::size_t size_index_)
+  {
+    return std::size_t(1)<<(total_bits-shift_right(size_index_));
+  }
+    
+  static constexpr std::size_t min_size(){return 2;}
+
+  static inline std::size_t position(std::size_t hash,std::size_t size_index_)
+  {
+    return (hash<<shift_left(size_index_))>>shift_right(size_index_);
+  }
+
+private:
+  static constexpr std::size_t total_bits=sizeof(std::size_t)*CHAR_BIT;
+
+  static inline std::size_t shift_left(std::size_t size_index_)
+  {
+    return size_index_>>16;
+  }
+
+  static inline std::size_t shift_right(std::size_t size_index_)
+  {
+    return size_index_&0xffffu;
+  }
+};
+#endif
 
 /* size index of a group array for a given *element* capacity */
 
@@ -1166,7 +1036,6 @@ void swap_if(T&,T&){}
 
 inline void prefetch(const void* p)
 {
-  (void) p;
 #if defined(BOOST_GCC)||defined(BOOST_CLANG)
   __builtin_prefetch((const char*)p);
 #elif defined(BOOST_UNORDERED_SSE2)

include/boost/unordered/detail/prime_fmod.hpp

@@ -117,15 +117,9 @@ namespace boost {
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
           std::size_t sizes_under_32bit = inv_sizes32_len;
           if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
-#if defined(__MSVC_RUNTIME_CHECKS)
-            return fast_modulo(
-              boost::uint32_t(hash & 0xffffffffu) + boost::uint32_t(hash >> 32),
-              inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
-#else
             return fast_modulo(
               boost::uint32_t(hash) + boost::uint32_t(hash >> 32),
               inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
-#endif
           } else {
             return positions[size_index - sizes_under_32bit](hash);
           }

include/boost/unordered/unordered_flat_map.hpp

@@ -427,24 +427,24 @@ namespace boost {
           std::out_of_range("key was not found in unordered_flat_map"));
       }
 
-      BOOST_FORCEINLINE mapped_type& operator[](key_type const& key)
+      mapped_type& operator[](key_type const& key)
       {
         return table_.try_emplace(key).first->second;
       }
 
-      BOOST_FORCEINLINE mapped_type& operator[](key_type&& key)
+      mapped_type& operator[](key_type&& key)
       {
         return table_.try_emplace(std::move(key)).first->second;
       }
 
-      BOOST_FORCEINLINE size_type count(key_type const& key) const
+      size_type count(key_type const& key) const
       {
         auto pos = table_.find(key);
         return pos != table_.end() ? 1 : 0;
       }
 
       template <class K>
-      BOOST_FORCEINLINE typename std::enable_if<
+      typename std::enable_if<
         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
       count(K const& key) const
       {
@@ -480,13 +480,13 @@ namespace boost {
         return table_.find(key);
       }
 
-      BOOST_FORCEINLINE bool contains(key_type const& key) const
+      bool contains(key_type const& key) const
       {
         return this->find(key) != this->end();
       }
 
       template <class K>
-      BOOST_FORCEINLINE typename std::enable_if<
+      typename std::enable_if<
         boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
         bool>::type
       contains(K const& key) const

include/boost/unordered/unordered_flat_set.hpp

@@ -313,14 +313,14 @@ namespace boost {
       /// Lookup
       ///
 
-      BOOST_FORCEINLINE size_type count(key_type const& key) const
+      size_type count(key_type const& key) const
       {
         auto pos = table_.find(key);
         return pos != table_.end() ? 1 : 0;
       }
 
       template <class K>
-      BOOST_FORCEINLINE typename std::enable_if<
+      typename std::enable_if<
         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
       count(K const& key) const
       {
@@ -356,13 +356,13 @@ namespace boost {
         return table_.find(key);
       }
 
-      BOOST_FORCEINLINE bool contains(key_type const& key) const
+      bool contains(key_type const& key) const
       {
         return this->find(key) != this->end();
       }
 
       template <class K>
-      BOOST_FORCEINLINE typename std::enable_if<
+      typename std::enable_if<
         boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
         bool>::type
       contains(K const& key) const

test/unordered/prime_fmod_tests.cpp

@@ -21,7 +21,8 @@ void macros_test()
     BOOST_ERROR("std::numeric_limits<size_t>::digits >= 64, but "
                 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is not defined");
 #endif
-  } else {
+  }
+  else {
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
     BOOST_ERROR("std::numeric_limits<size_t>::digits < 64, but "
                 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is defined");
@@ -154,7 +155,7 @@ void get_remainder_test()
 
   for (std::size_t i = 0; i < 1000000u; ++i) {
     boost::uint64_t f = rng();
-    boost::uint32_t d = rng() & 0xffffffffu;
+    boost::uint32_t d = static_cast<uint32_t>(rng());
 
     boost::uint64_t r1 =
       boost::unordered::detail::prime_fmod_size<>::get_remainder(f, d);
@@ -179,14 +180,14 @@ void modulo_test()
   boost::detail::splitmix64 rng;
 
   for (std::size_t i = 0; i < 1000000u; ++i) {
-    std::size_t hash = static_cast<std::size_t>(-1) & rng();
+    std::size_t hash = static_cast<std::size_t>(rng());
 
     for (std::size_t j = 0; j < sizes_len; ++j) {
       std::size_t h = hash;
 
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
       if (sizes[j] <= UINT_MAX) {
-        h = boost::uint32_t(h & 0xffffffffu) + boost::uint32_t(h >> 32);
+        h = boost::uint32_t(h) + boost::uint32_t(h >> 32);
       }
 #endif
       std::size_t p1 =